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)

I haven't read all of the thoughts as of yet, but here's my original thoughts upon the problem. :)

Logically, it follows that a finite maze however large, however difficult, will eventually be escaped given enough patterns of escape by trial and error alone.  This is provided that there is an escapable exit in the first place. The thought of getting "lost" in the maze is irrelevant. The problem isn't for God to find the quickest way out, it's for him to find a way out before infinity. If it takes him 10^1,000,000^1,000,000 moves, then so what?

To me, (perhaps me alone), it follows that once this path has been found in an infinite sequence, the time, or moves in this case can only be finite, however long. Once the sequence stops, so has the stop watch.

I'm almost sure there is a better model to proove these thoughts, but perhaps no better ideas.

Edited on February 9, 2005, 4:35 am

Posted by Michael Cottle on 2005-02-09 04:15:20