God and the Devil decide to play a game. God will start by picking an infinite sequence of moves of the form "left", "right", "up", and "down". The Devil responds by creating a finite maze with an exit and by placing God somewhere inside. God then follows His pre-selected sequence to traverse the maze. Unmakable moves are ignored; for example, if the next move is "left" and there is a wall to the left of the current square, God goes on to the next move in the sequence without moving.

If God escapes the maze in finite time, He wins. Otherwise, the Devil wins.

Assuming both agents act optimally, who will win?

(assume that the maze is formed by deleting some edges from a rectangular grid, and that it has no isolated regions; i.e., it is always possible to get to the exit from any point inside the maze)

To Jack and Ken:
I agree that a defined, fixed list, can still be an infinite list, but it will be a fixed sequence of moves, it is not changeable. 
The devil just has to look through the list up to the point that contains the right escape sequence and block that.  And, God cannot change this list anymore (to change the sequence a bit, so it leads to the exit).

On the philosophical aspect, the different infinity forms I referred to are better reworded at http://pespmc1.vub.ac.be/INFINITY.html.
The devil just has to look through the list up to the point that contains the right escape sequence and block that.  And, God cannot change this list anymore (to change the sequence a bit, so it leads to the exit).

To ronen:
As Dustin (Thanks) already posted in his answer to Jrdn: God has to go first, the maze is calculated (Or whatever Devils do to create a maze) later.

Posted by Hugo on 2005-02-12 17:08:52