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(3): No Subject by Ken Haley)

Ken Haley wrote: Well, in that case you execute S1 again, and you're out

I agree with that, but the problem now is that God has to change his list after it was given and after the maze was created, which is not allowed by the problem setting. 
So I fear the idea doesn't really solve it. 

The only thing I can think of is to make a long list of 100 times repeating the sequence and then adding in one extra move each time the whole 100x sequence is done.  This way the 100x sequence jumps further one move until at a certain moment it gets lined up with the start places (I have some difficulties putting this idea in writing and hope you understand it.  I want to offset the start of each sequence 1 move extra after each sequence).  Problem here is that the extra move may not actually change anything: e.g. if its a L move and there is a wall to the left, then nothing happens.
And, it creates another problem as well, but before posting that, I have to give it some more thinking.
Ken, to me,  the master escape sequence for one maze doesn't need to be shorter then 10000 moves, as long as it is finite its OK.  And it doesn't have to be optimal either.
 

Posted by Hugo on 2005-02-15 16:33:57