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: Gambling and Charity by Hugo)

The problem you describe is a specific instance of what is known as the Angel Problem.  Usually, in the formulation, it is the Angel that does the moves and the Devil that deletes entires squares off the board.  The Devil essentially tries to create a moat to trap the Angel. 

In the more general version, the Angel has "power k", meaning that it is able to jump to any square that is k king-moves away from its current position.  Berlekamp proved that if the Angel has power 1, the Devil wins.  If the Angel has greater power, the answer is unknown. 

The version you offer seems very similiar to the Power-1 Angel Problem, so I suspect that the Devil (or in your case, God) would win.

Posted by David Shin on 2005-02-16 20:56:44