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 $10 on the Devil by Farthing)

Oooh!  Good Call!  If the devil were to devise a maze that puts god in an endless loop, the devil definitely wins.  Now what if God's sequence isn't repeating?  Is there any maze the devil could design that can send that infinite sequence around in circles, either negating god's moves or sending him away from the exit. I mean, the maze he could design could be friggin' huge, as long as it's finite, right?  So what if he made the maze in such a way that the exit is only approachable by one specific spot, and the rest of the maze is devoted to sending god away from that spot?

The more i think about that, i don't think the devil could win.  because in an infinite sequence, every possible combination is present, right? I mean, anyone can find their birthdate in ð (pi).  No matter how big or convoluted the devil made the maze, at any given point in that maze, there would have to be a specific path that would have to be followed by god in order to escape.  Eventually, god is going to have a sequence that matches up with the excape route from the space he happens to be on.  And because it is reached eventually, that makes it finite.

So, if the sequence repeats, the devil wins.  If the sequence never repeats, god wins.

Posted by Graham on 2005-02-09 05:17:07