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
No Subject by Hugo)
Hugo,
Did you read my last post? I tried to show clearly and carefully that no matter what maze the devil gives God, that God's escape sequence will escape from it in a FINITE number of moves.
Here's an algorithm for ALL possible 10x10 mazes. I'll number the steps, so you can challenge me at the step number you disagree with.
0. We'll start by picking any one of the myriad of possible 10x10 mazes, and focusing on it. The method described below will work, no matter which one we pick.
1. There exists an escape route from the maze no matter what the starting point is. (Otherwise the maze is illegal--no escape).
2. The optimal escape route, will never visit the same point more than once. (This should be obvious, with a little thought).
3. There are only 100 points in the maze, so the escape sequence FROM THE FIRST STARTING POINT THAT WE TRY cannot be longer than 100 moves. Let's call this escape sequence, S.
4. Obviously, S may not work for every point in the maze. But let's start by crossing out every point in the maze for which S works (including the point in step 3) .
5. Pick a point that we haven't crossed out. Make all the moves in S--we know we're not out yet. Now, make the minimal number of additional moves to get to the exit from here. We know we can do this, because we're able to escape from the maze no matter what the starting point is.
6. Append the moves made in step 5 to S. This can't be more than 100 more moves, because, as we showed in step 3, we can escape from any point in the maze with no more than 100 moves.
7. This longer S will still be a valid escape sequence for any of the points that we've already crossed out, because it still starts with the same moves that allowed us to escape starting at those points. (Don't gloss over this point, it's important.)
8. Repeat steps 4-7 for any point not yet crossed out, until all the points have been crossed out, appending more and more moves to S. In the worst case, you'd append 100 more moves each iteration to S. (I'm sure it could be shown that it wouldn't take anywhere near that many, but this will do--we're only trying to show finite-ness).
9. Because we cross out at least one point each iteration, the total number of iterations can't be more than 100.
10. So now S is no more than 100x100 = 10,000 moves long. and it will lead to an escape from the arbitrarily chosen maze. The sequence we derived won't get us out of ANY 10x10 maze--just this one.
11. But we know that every 10x10 maze has a sequence of moves no more that 10,000 moves long, that, when applied to it, will let us escape from it no matter where we start. We'll call it the "solution sequence" for the maze.
12. Now consider the sequence of ALL 10,000 move sequences in alphabetical order. It's quite long--it starts with 10,000 D's, then 9,999 D's followed by an L ... and ending with 10,000 U's. In fact, the number of moves in this sequence is 4 to the 10,000th power. This is a number with 6021 digits starting with 39802768... Let's call this the monster sequence. It's not God's sequence because it's finite.
13. Notice, also that every sequence of moves shorter than 10,000 is also in the monster sequence (many times, as a matter of fact). This should be obvious, but it is important because not all 10x10 mazes will require such long solution sequences.
14. This is key: Every 10x10 maze's solution sequence is contained in the monster sequence, because EVERY 10,000-move (or shorter) sequence is contained in the monster sequence.
15. Because each maze's solution sequence works no matter where you start, we don't have to worry about where the sequence of moves before the solution sequence leaves us in the maze (if we haven't escaped already). Once we execute the solution sequence, we're out.
There you have it. Any questions?
P.S. It's easy to get from here to God's sequence. It's just the monster sequence for the 1x1 mazes (only 4 moves long!), followed by the monster sequence for 2x2 mazes (16 moves long), etc. Once we know the size of the devil's maze we can truncate God's sequence off after the monster sequence that solves mazes of that size.
re: No Subject
