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)

Hugo,

I was amused when I saw your wager.  I actually play a lot of poker and decided at some point that I would donate all my earnings to charity.  It seems I am not the only one with a propensity to link charity and gambling.  =)

In any case, I believe that the comments for this problem prove without a doubt that God will win.  This, in my mind, is the proper criterion for displaying the official solution, so I am going ahead and posting it.  Please take a look at the official solution and let us know if you are still not convinced. 

If you are convinced, may I recommend WorldVision - it has one of the highest ratios of ($ needy receive)/($ you pay) of all charity organizations. 

Posted by David Shin on 2005-02-16 16:47:03