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
Reply to comment 53 & 54 by Hugo)
I'm embedding my remarks in your last one this time. My responses are enclosed in [square brackets.]
Ken,
I think we are having a problem:
[we sure are! hehe]
- In comment 48 I asked if I understood your idea correctly: that the list was S1:S2:S3...
["the list" in this case, isn't God's list. If you thought it was, I DID misunderstand you. S (= S1:S2:S3, or whatever it is) is just the list to escape from this maze. God's list is much much longer because it has to escape from ANY maze. I called that the "monster list".
There are a total of 3 lists that we're talking about:
(1) S1, which is the list that gets you out of some maze, starting at some point. It's a maximum of 100 moves long. It changes for every starting point, for every maze.
(2) S (= S1:S2:S3, or S1:S1:something else, is the list that doesn't change for any given maze, but does change from maze to maze. The point is, it's a maximum of 10,000 moves long.
(3) God's list which is the huge "monster list" that solves any 10x10 maze.]
- In comment 49 you said: "So now, S is just S1:S1."
[That's right, but S isn't God's list.]
- In comment 50 I said: God has to change his list
[Again, S is not God's list. It's a tiny part of the monster list. The monster list is the constant list of all lists and contains S PLUS all possible changes to it. Because it contains ALL POSSIBLE sequences of that length.]
- 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.
[It's a change to S, not God's list. Again God's list contains both versions of S, before and after the "change" (along with all other possible versions).]
With your posting to Angela, you said that God had to give anfinite list
[In most of yours and my interchange, we were only dealing with the 10x10 case. And a finite God's list works in that case.
In my quote to Angela, I was referring back to the original problem of ANY finite maze, no matter how big. In that case, the fixed list must be infinite in length, but it only takes a finite subset of it to solve a given maze. The reason it has to be infinite is that once you pick a finite subset, the devil can pick a maze that's much larger than that subset can solve.]
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.
[I've read that 3 times... I don't understand what you're saying.]
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).
[Now that I agree with! This is why God's fixed list must be infinite if it hopes to solve ANY maze. But once the devil has chosen his maze we can find where, in God's infinite list, God will escape from it. ("Here it is, he escapes at move # ___!") And you can ALWAYS fill in the blank with some finite number. The number will be bigger for bigger mazes, but it will always be finite.
Here's a similar, but much simpler problem: Suppose I showed you a jar of ping pong balls, numbered from 1 to however many balls there are in the jar, and challenged you to pick a number such that I can't find a ball in the jar with a higher number. You'd say, "Easy" and just add one to the largest numbered ball.
But if I told you to imagine an infinitely large jar with an infinite number of ping pong balls numbered with all the positive integers, and gave you the same challenge, you couldn't do it. No matter what number you pick, I simply pull the ball with the next higher number (or any higher number).
]
--------------------------------------------------------
I hope you see the proof now... If not, I think I'll have to give up. I don't know how else to say it. Although exasperating (for both of us, I imagine). the exchange has been fun. I don't know if anyone else thinks so, though... :-)
re: Reply to comment 53 & 54
