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)

For any given finite maze, assuming the composition is known but the starting position is not, the following method can be used to create a sequence that will guarantee successful exit:

Assume it is possible to be in any position.  Choose one position and create an exit sequence from there.  Then find the final destination from each of the possible starting positions, assuming this created sequence was followed.  As at least one of the starting positions would have led to exit, so there will be at least one less possible position in the maze now than there were starting positions.  Choose one of these remaining possible positions and create an exit sequence.  Again, the number of possible positions will be reduced by at least one.  Continute this method until the number of possible positions in the maze is exhausted, put all the sequences together, and you have a finite sequence that will guarantee an exit.

Given the fact that there exists a finite sequence that will guarantee an exit for any maze given any starting position, an infinite sequence containing all the possible one-move sequences, then two-move sequences, and so on will guarantee exit from any maze in any position.

First post.. comments?

Posted by Jack on 2005-02-09 00:37:25