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(2): Clarification of infinite sequence by Spoiler)

I have to admit I was quite taken aback by your post, Spoiler.  I had no intention of trying to put down other people in any of my comments.  If you feel that my response to Farthing's request for clarification bore an air of superiority or ostentation, please let me know how you would have reworded it differently. 

If I seemed to be assuming some sort of unwarranted authority in my posts, it is simply because I am the author of this particular puzzle.  Consequently, I am in a position to answer questions as well as explain to others why certain approaches do or do not work.  In a problem like this, it is very easy for someone to post a solution with a subtle error that can easily be missed by others, so I am quick to point such errors out when I spot them. 

In general, I find that things like emails, online posts, and IM's are very easily misunderstood.  People oftentimes assume that the writer was using some kind of tone when he/she really wasn't.  Please be careful about interpreting tone.

Posted by David Shin on 2005-02-10 04:17:57