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 have a hypothesis which I can use to solve this, if the hypothesis is true. I am still working on a proof of the hypothesis.

Hypothesis: For any given maze, there exists a finite sequence of moves which will get to the exit, no matter what the starting point.

As an example, consider David Shin's example below.
 _
| |_ _
|  _ _
|_|

For this maze, the sequence UUDRRR will get to the exit from wherever it is executed.

If this hypothesis is true, God would simply construct a sequence of moves consisting of all sequences of length 1, followed by all sequences of length 2, etc. Whatever maze the Devil comes up with will fall to it's solver sequence (if not before).

Now to prove the hypothesis. Any thoughts?

Posted by SteveH on 2005-02-08 23:12:46