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)

(In reply to re: No Subject by Gamer)

The only problem with doing one solution and then retracing your steps if it doesn't work is: How does God know which steps were taken to get there?  Let me give you an example (I hope it turns out OK):

_____________________

|      ____       ________|

|     |  A  |  B  |         C  |

|     |      |      |      |      |

|     |_________D_ |___|

   |

   V

Suppose God does the solution for starting at A.  D, D, R, U, U, U, L, L, D, D, D, D.  But suppose God didn't start at A, God started at B.  Then the ending point would be D.  So, God would do the reverse of what path God took before.  U, U, U, U, R, R, D, D, D, L, U, U.  But that wouldn't lead God back to B, it would lead to C.

Is there a way to get back to the starting point?

Edited on February 9, 2005, 12:14 am

Posted by Dustin on 2005-02-09 00:13:52