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)

No clarification from David Shin yet on "infinite sequence" but my thoughts are that the Devil, knowing all of God's moves (and if there is a finite number of moves that are repeated ad infinitem), could be able to design a maze that sends God around the maze and arriving back at the start point for each iteration of the sequence of moves.  If there are the same number of lefts and rights they would cancel each other out.  If there are more lefts than rights, the Devil could design the maze to negate the excess lefts by making a left turn impossible at those points. etc, etc, etc.

Posted by Farthing on 2005-02-09 04:42:22