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)

One type of infinite sequence which would always win would be a sequence in which all directions are traversed in every possible order. Let the term xL mean "move x units to the left" and xR xU xD can mean "move x units right, up, down" respectively. 

The key for God is not to miss any orders that the Devil could exploit. One way to do this would be a sequence of the type: 1L 1U 1R 1D; 2L 1U 1R 1D; 1L 2U 1R 1D; 1L 1U 2R 1D; 1L 1U 1R 2D; 3L 1U 1R 1D; etc.

Essentially God would be moving in a spiral. Starting from any point in the maze the spiral would eventually reach any finite edge.

Posted by Ben Gornall on 2005-02-09 09:00:26