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)

So the question that's essentially being asked, reworded is: "Given an infinite number of moves, can you escape a maze in finite time?"

The answer is "yes."  Eventually God will exit the maze following his predefined, potentially arbirtary/random set of legal moves.  No matter how complex the maze becomes, the correct combination of moves will eventually be executed.

Take the following extremely simple one-square maze: |_| where God is in the center and the exit is "up".  It may take several "moves" but eventually God will move "up" and exit the maze.  It's just a matter of time.  As soon as he exits the maze, the amount of time it took became finite.

Likewise, withe the following two-square maze:
 ___
|___
Eventually God would move two squares to the right and exit the maze.  You can logically proceed through iterations of this until the maze becomes as complex as the actual maze that the Devil is designing.

Posted by John on 2005-02-08 22:07:47