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)

My first idea was to let God walk randomly in the Devils maze. 
Then it turned out that God had to give in his infinite list first and the Devil got the possibility to create a maze and choose a starting point.
This made me think that it would be easier to look at the Devils point of vue:  Would it be possible to develop a maze (After having received a list of escape moves), such that it would resist the escape attempt. (Farthings idea)
At first, developping such a maze seemed possible, but, while developping, I was forced to accept the idea that in an infinite list there would always be a sequence that brings God to the exit.
Now I believe that this problem is more a philosophical question: the question of what infinity is. 
God's list may be an infinite list when created, containing all possible unknown sequences, but once God gives it to the Devil, it is a fixed list, with a fixed number of (fixed) moves.
I strongly believe that it is then possible to make a finite maze, such that it is not possible to reach the exit.
 

Posted by Hugo on 2005-02-11 20:19:11