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(2): No Subject by Hugo)
Interesting question, and you had me thinking for a minute. But,
the original proof works, if you just follow it through. Here's
how:
In your example, we start at the devil's chosen point, apply
sequence S1 (which is the escape sequence for P1) but instead of
escaping we find ourselves at P1. Right?
Well, in that
case you execute S1 again, and you're out. So now, S is just
S1:S1. There's nothing in my proof that says the sequence we
append to S1 can't be another copy of S1. S1 is only 100 moves
long (or less); so S1:S1 <= 200 moves. As long as we
keep the whole thing under 10,000 moves (which we do), the proof works.
Agree?
Let me add this. The final solution sequence will likely NOT
contain the optimal sequence from any given point. In your
example, S2 is the optimal escape route from P2, but we may never see
S2 in the final S. Why? Because we started with P1, created
S1, then applied this sequence to the starting point P2. Then we
appended moves to get out from there (in this case, S1 again). So
we're using S1:S1 (instead of the optimal S2) to get us out from point
P2. I don't know if that helps, but I thought it might.
Edited on February 15, 2005, 5:23 am
re(3): No Subject
