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)

This is an expansion of Jack's idea.

First of all - the number of possible finite mazes is countable: proof - the number of rational numbers are countable, and thus all of the pairs (m,n) where m represents the width of the maze and n represents the height is also countable. for any couple (m,n) there is a finite number of possible mazes, so by creating a sequence of mazes ordered by (m,n) and inside by any internal order we have a way of "counting" all possible finite mazes. Now build a sequence in the following algorythm:

- take the next possible maze in the sequence. for each maze,

     - iterate over all possible starting positions (for instance from upper left corner go right then down). for each position:

            - calculate where in the maze you are located after executing all of the steps which have already been added to the sequence (it is a finite number of steps), calculate how to get to the exit from that position and add the route to the existing sequence.

 

the sequence created above is countable and solves every possible maze.

 

 

Posted by ronen on 2005-02-12 10:46:06