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)

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 depth-first, breadth-first and iterative deepening. Depth-first 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. Breadth-first seach is non-sensical 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 one-move sequences, coming back to his starting point after each one, then tries all two-move 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 depth-first 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 sub-sections 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 side-note, 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 2005-02-09 09:02:51