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)

Ken,

I think we are having a problem:
- In comment 48 I asked if I understood your idea correctly: that   the list was S1:S2:S3...
- In comment 49 you said: "So now, S is just S1:S1."
- In comment 50 I said:  God has to change his list
- In comment 53 you said: "God did NOT have to change his list"
Well, the first list was S1:S2, the new list is S1:S1:S2, and I believe that's a change.

With your posting to Angela, you said that God had to give anfinite list
Quote: "(I take "finite time" to mean a finite number of moves)". Unquote.  And in posting 40 you said: Quote: "God just creates an infinite sequence" Unquote.  All the reactions after my $20 posting came because I said that an infinite list changed in a finite list (Because it had a start and an end move), after God had given it to the Devil.
Now I have a question to you.  What do you think of the following:
When the list is finite, then its possible to build a finite maze to keep God in.  The Devil just puts another big square around his exixting maze (with of course an exit somewhere).

 

 

Posted by Hugo on 2005-02-16 16:12:25