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)

Forgetting the fact that I have some trouble to see if a given, immutable list (That is a sequence of L,U,R,D,...D) is still infinite, I keep having problems to accept God wins. 
When the list is finite, then its possible to build a finite maze to keep God in.
When the list has to be infinite in order for God to reach the exit, it will take God an infinite time to get out, and that's a loss. (I agree, I am not an expert on the speed of the average God, but it sounds OK).

Anyway, if I am convinced that God gets out, I'll send $20 to a tsunami relief fund.

BTW, can anybody provide an escape list/algorithm for say a 10 x 10 wall maze?

Posted by Hugo on 2005-02-13 15:21:49