## Wednesday, July 23, 2008

### Colored maze discussion

See the original puzzle

Recap: The basic idea of the game is that player 1 chases player 2 on a circular board. If player 1 catches player 2 within twenty rounds, player 1 wins.

I have a policy of giving free link love to any bloggers that post good solutions. This time, Hugo of thinktoomuch.net wins! (Hugo's blog, by the way, has become a new favorite of mine.) Here's his solution:
Call the middle "ring 0", the next "ring 1", the outer is "ring 4".

If player 2 is in ring N, player 1 wants to be in ring N-1, always moving to a place that is adjacent to player 2's position. Player 2 can race around and around in ring N, with player 1 chasing in ring N-1, only until it gets to the point where player 1 is in the N-1 region that is adjacent to 3 N regions. That forces player 2 to go to ring N+1.

To start, player 1 goes to ring 0, from there heading out to get adjacent to player 2. To finish, player 1 traps player 2 in ring 4, at the bottom.
Allow me to illustrate this solution:
As long as player 1 stays one ring closer to the center, player 2 will eventually be forced outwards. When player 1 is in the cyan region and player 2 in the corresponding blue region, player 2 will have no choice to move outwards. When player 2 is stuck in the outermost blue region, the game is over.

Hugo also said:
New question: what's the maximum number of moves that player 2 can survive? I believe it would have player 1 on ring 4 to begin with, and player 2 playing in a way that player 1 has to chase player 2 all the way around every ring. I've not counted, but I place my bets on player 2 if player 1 only gets 20 moves.
Here, I admit to making a "mistake" in writing this puzzle. I meant to give player 1 plenty of time, but in a lapse of judgment I limited it to 20 moves. Player 1 might not be able to win that quickly! But regardless of my original intention, it is still an interesting question. I am not sure of the answer, but here are my rambling thoughts on the matter. I welcome any proofs you can come up with.

We can put some upper bounds on the number of moves required:
• 4 moves to get to ring 0.
• 3 moves to force player 2 to ring 2.
• 5 moves to force player 2 to ring 3.
• 6 moves to force player 2 to ring 4.
• 7 moves to trap player 2 at the bottom.
• 1 move to win.
That's 26 moves total. But we should be able to reduce some of those numbers.

One way to reduce them is by saying that the first player can choose which direction to go around the rings. This would reduce the number of required moves to maybe 18 or less. However, there is a way for player 2 to choose the direction, if player 2 jumps to the next ring before being forced to. I found a 21-move path in which player 2 constantly forces the direction to be clockwise. That's enough for player 2 to win! To win this way, allow 4 moves for player 1 to reach the cyan region below, and then run along the red path for 16 moves.
However, this path only works if player 1 strictly follows the strategy of remaining adjacent to player 2 at all times. I suspect that player 1 can slightly modify his strategy and win.

This game turns out to be more complicated than I thought.

Anonymous said...

Heh, brilliant! Hadn't thought of that: clearly premature is sometimes better.

Anonymous said...

Player 1 can reach any of the center three regions, from anywhere, with only 4 moves. I think that reduces the number of moves by one.

Player 1 can force player 2 to change direction by staying in the current ring an extra move when player 2 prematurely hops out. But this might actually take an extra move. The "ideal" number of moves (for best play by both sides) depends somewhat on the positioning of each ring.

Finding the "best" solution is getting a bit too fiddly for me to solve right now. The ideal direction for each ring might even depend on the ideal direction on the *next* ring, as player one cannot force player two to *not* change direction as he hops out another ring. Though, optionally changing direction seems something of a short-cut, so it also seems unlikely that that would be useful *in this instance* of the problem. But I'm also thinking of a generalized solution for an N-ring problem. ;)

miller said...

Better yet would be a generalization to any bunch of connected regions. That would be a pretty difficult graph theory/game theory combo problem.