### DIMACS Theoretical Computer Science Seminar

Title: How Hard Are Computer Games?

Speaker: **Graham Cormode**, DIMACS, Rutgers University

Date: February 16, 2004 3:30-4:30pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

Computer Scientists often devote a great amount of time and effort in
playing computer games. With the intention of legitimizing this endeavour
in the name of academic research, I will focus on the algorithmic
complexity of computer games. I'll begin by surveying some of the known
results and outline the proof techniques, for such well known games as
Minesweeper, Sokoban and Tetris.

In the game of Lemmings, the player must guide a tribe of green-haired
lemming creatures to safety, and save them from an untimely demise. I
will describe and analyze the problem of deciding whether or not it is
possible to complete a level of this game (and hence to find a solution to
that level). Under certain limitations, this can be decided in polynomial
time, but I will show that in general the problem is NP-Hard. I will
outline my latest results, to show that this hardness holds even if there
is only a single lemming to save, thus showing that it is hard to
approximate the number of saved lemmings to any factor.

See Webpage: http://www.cs.rutgers.edu/~muthu/theory.html