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 No Subject by SteveH)

Does the Devil get to create the maze based on the sequence or do they both work independently?

I had an idea, trying to string together sequences of 1 move, 2 moves, and so on so they made sense. This didn't work because it depended on where you started.

One thing to realize about stringing together possiblities is you may change your "starting position" for other possibilities. This can be cured by putting the inverse moves (your path except going backwards) after it.

How about just stringing together all solutions to all mazes (each solution being followed by its inverse)? There's a finite number of starting positions in a finite dimension maze, and so there would have been a finite number of solutions prior to the one that works, and so there would have been a finite number of moves (since a finite dimension maze has finite move solution)

This solution would obviously have an infinite number of moves, but every solution would work (since it's included) and would have a finite number of solutions before it.

I assume there's an actual solution to this, but it brings up another question, does doing increasingly larger sets of directions work? (For example, U, UR, UUR, URR, U, UL, UUL, ULL, D, DL... UU, UUR, UUUR...)

Posted by Gamer on 2005-02-08 23:49:04