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 re: boiling it down - Not so simple by David Shin)

I don't see how whether God's current position was his original position is relevant.  From any position in the maze, there exists a combination of moves which will extricate Him.  After every move, you could repeat my assertion using His current position as His starting position.

Regarding the possibility of God choosing only double moves... if that were possible, then sure, He would lose.  However, the problem is worded around the premise that both entities did their best to win.  I would assert that using an infinite sequence containing nothing but double-moves would not be His best way to win (as you have shown), and would therefore be illegal behavior for Him.

The problem specifies that God's move list is an infinite sequence, meaning it is not constrained by internal repetitions, patterns, or rules.  As such, it is unlikely that "double-moves" could constitute the move list in its entirety, and as the sequence approaches infinite members this becomes increasingly less likely.

Are there combinations of moves that will *not* get Him out of the maze, from any given point?  Sure.  However, from any given point in the maze, all He needs to win is to have the winning combination executed once, from one spot in the maze, to win.

Posted by John on 2005-02-08 22:38:29