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
$ 20 on the Devil by Hugo)
Sorry Hugo--you'd lose $20. The proof given in detail in my earlier post (thanks to SteveH's earlier post) goes like this: For every finite maze there's a way to get out--that's given. That is, there's a finite sequence that gets you out. Furthermore, there's a SINGLE finite sequence that will get you out no matter where you start. (that was a little harder to show--but not bad...)
So, God just creates an infinite sequence that contains every possible finite sequence as follows: First, 4 one-move sequences (L, U, R, D) followed by 16 two-move sequences (... L,L, L,U, L,R, L,D, U,L, U,U, U,R, U,D, R,L, R,U, R,R, R,D, D,L, D,U, D,R, D,D) followed by 64 three-move sequences, etc. If the solution to the devil's maze contains 3 billion moves (or whatever), you just scan forward in God's sequence until you find all the 3-billion-move sequences. (It will be just after all the 2,999,999,999-move sequences, and just before all the 3,000,000,001-move sequences.) The solution to the maze HAS TO be there! It's a long ways in, but, hey--we haven't even scratched the surface of infinity.
re: $ 20 on the Devil
