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: No Subject by Ken Haley)

Thanks for all the work Ken.

I did read your first posting, wrote down an answer to part one, but part two was much more difficult and it being a sunday, I gave up on it- Sorry. I thought the thing I posted was maybe a better point, so I posted that.

Now replying to your numbered list: In general, I am sold (for 90%) to the idea af God getting out in a finite time. There is however one problem to be solved, before I'll send in my $20. I tried to do it myself, but I am not absolutely sure that it works.

Here's my problem:
I agree up till point 6 and get stuck at 7 1/2, which is also repeated at 15.
Just to make sure that I correctly understand you: S1 is the sequence to the exit from P1 (the first starting point), S2 is the sequence to the exit from P2. P2 is found after S1 being executed from a certain point that was not solved by S1. You now create a new S(long), being S1:S2, this is: do S1, then do S2. (If you answer- which I would appreciate very much - please mention it if I didn't correctly understood you)
If the above is correct: Then what about this: The Devil picks a starting point for God, such that after doing S1, he ends up at P1. The rest of the sequences are now not guaranteed to find the exit.
I tried to solve this by extending your list to be all combinations of all S(n), but it would have to be proven that at a given moment, God is in a place where the right sequence starts. Although the probability that this happens is high, it isn't 1.

Once the above is solved, I agree that God wins.

Posted by Hugo on 2005-02-14 09:48:07