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(4): No Subject by Hugo)

Hugo,

What??  God did NOT have to change his list.  God's list was the monster list that contained all possible 10,000 move sequences.  What did he have to change?

In your example, I followed the steps in my original 15-step proof to construct the exit sequence.  It HAPPENED to contain a certain sequence (that we called S1) twice.  So what?  The final sequence would still be 10,000 moves (or less), which is all we needed to know.

Here's a two-step summary of the proof.  I don't know if it's any clearer than what I've already posted, but maybe...

1.  For any given 10x10 maze there's a solution sequence that lets you escape FROM THAT MAZE, no matter where you start, in 10,000 moves or less.

2.  By executing the monster sequence which is simply ALL POSSIBLE 10,000 move sequences, you're guaranteed to exit from ANY 10x10 maze, because sooner or later you're going to run into that maze's solution sequence.

If you're still not convinced, which of the 2 summary points do you think we haven't proved?

 

Posted by Ken Haley on 2005-02-16 05:35:09