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: Solution attempt by SteveH)

It isn't really the number of possible "starting positions" that is reduced, it is the number of possible "current positions" in the maze.  To think about the problem differently, you could assume there are 4 positions in the maze.  We will create a sequence that, if followed, will result in an exit regardless of the starting position.  Assume there is a person currently in each possible starting position, named A, B, C, D.  Now devise a path that will result in A's exit.  This is the start of the solution sequence.  Now have A, B, C, and D each follow this sequence.  A exits the maze and B, C, and D could possibly remain.  Now, wherever B ended up, assuming he remains, find an exit path for him.  Again, have C and D follow this path as well.  Continute the process for C and D if they remain.

So whatever path D followed (or the last person to exit the maze in the case that D exited early) is a sequence that will result in exit regardless of starting position.

 

Posted by Jack on 2005-02-09 01:27:42