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 SteveH)
Steve, I think your method is sound, and I think I have a proof of your hypothesis. I'll restate it, so readers don't have to go back and read your post (#9 in this thread). You said, "For any given maze, there exists a finite sequence of moves which will get to the exit, no matter what the starting point."
Here's my proof: Pick any point in the maze and construct the sequence of moves required to get to the exit. Now, apply this sequence to every other point in the maze, crossing out those points for which the sequence leads to the exit (including the point you picked to begin with). You're now left with fewer points than you started with. Now, pick another point, apply the sequence you've already got, then add additional moves to get to the exit. The sequence is now longer, but it still works for all the points already crossed out, and now at least one more point. Continue doing this until you've crossed out all the points in the maze, making the sequence longer and longer as you go. This algorithm is guaranteed to end, because each iteration crosses out at least one point. When you're done, the sequence you've constructed will get you out of the maze no matter where you start.
Knowing this, as Steve stated in his post, we can construct an exit strategy for any maze. Simply create the infinite sequence that consists of all one-move sequences, followed by all two-move sequences, followed by all three-move sequences, etc. This is a guaranteed exit sequence for any maze!
Think about it. Suppose we're in one of the devil's most diabolical mazes. As we showed above there's a sequence that will lead to the exit NO MATTER WHERE WE ARE in the maze. Call this the solution sequence for this maze. It may be trillions of moves long, but it's finite. But God's sequence contains the solution sequence, because it contains ALL finite-length sequences. In executing God's sequence, we'll eventually reach the solution sequence for this maze (unless we've already escaped). At that point, we'll execute the solution sequence and escape!
Edited on February 9, 2005, 5:31 am
re: No Subject (and solution!)
