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 preselected 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)
Hmmm.... Having read over the comments list, I'm not as sure of this
idea as I was at the beginning, but I'll give it a shot anyway.
We picture the maze as a search tree. From any position there are only
three branches heading out from that position, forward, right and left.
Therefore if we create an infinite search tree from the original
position, the exit must lie at a reachable node, as the exit in the
actual maze is reachable from any point. That is, there exists some
combination of {F, L, R} that hits the exit node.
Using this manner of thinking about the maze, God becomes a blind
search algorithm. Of blind search algorithms, the most straight forward
are depthfirst, breadthfirst and iterative deepening. Depthfirst
would mean that he picks an arbritrary sequence of moves, follows it
all the way down to the end, and, if he isn't out, comes back up and
tries again. This obviously won't work, as the search space is infinite
and there would be no accounting for loops. Breadthfirst seach is
nonsensical in this situaion, as he'd have to teleport himself to
different places in order to unfold differnent nodes.
The only logical way outwould be iterative deepening. In this, he tries
out all onemove sequences, coming back to his starting point after
each one, then tries all twomove sequences, coming back to his
starting point after each, and so on. His move list therefore would
look like this (parentheses used to show him going then coming back):
{(F, B), (L, R), (R, L), (F,F,B,B), (F,R,L,B), (F,L,R,B), (R,F,B,L) ....}
If it were possible to come back to the starting point each time there
is no question that this move list would get him out, as it is
guaranteed that each node will be visited (it's basically depthfirst
search to successive levels).
Therein lies the rub, though. As someone else mentioned, Gad can't be
sure of getting back to the starting point. In the very first move,
were he not allowed to go forward, he would end up one square back from
where he started, not back at his starting place as he would like.
I haven't yet worked out whether this is a problem. Intuitively I feel
that God could still get out this way, as subsections that are longer
than the actual exit path will actually contain the exit path, so his
move list contains the correct sequence of moves from point A to point
B an infinite number of times, and there always exists an exit path
from his current position. I haven't been able to prove it though.
On a sidenote, were God allowed to change the definition of "move"
such that {F,B} was one move, meaning that if he weren't allowed to
move forward, he wouldn't move backwards either, the problem would be
trivially solved through iterative deepening, as he could always
guarantee getting back to his original position.

Posted by Sam
on 20050209 09:02:51 