Introduction to Combinatorial Game Theory, Part 3

Follow-up of the first part and the second part.

Remember our discussion about impartial games and nimbers? Why do they matter? Well, a theorem called Sprague—Grundy theorem states that every impartial game is equivalent to a nimber; that is, its value is a nimber. Got any terribly complicated impartial game? It’s actually just Nim in disguise. This theorem is very powerful to analyze most impartial games, allowing all sorts of results from Nim to be borrowed in, which is exactly what we’re going to do here with Monorail (also known as Venice Connection). The rules of Monorail have been posted when I made my post a month or two ago; basically, you place tiles and attempt to produce a cycle using all tiles.

Before we start, let’s create a new game which we will call “Straight” for the lack of a better name. We have a board of an irregular shape, but the board is composed of squares and is gridded. (Basically you can cut off the board from a graph paper.) Some of the squares are initially marked. A move is to mark 1-3 squares that are contiguous and are in a straight line (horizontal/vertical), such that at least one of the new marked squares is orthogonally adjacent to a previously marked square. Here’s an example board with the marked squares in dark blue and other squares in dark blue:

straight0

Here are several legal moves, marked in green:

straight1

And several illegal moves, marked in red:

straight2

Note that this is an impartial game. Also note that as long as the board is connected and there is at least one marked square in the beginning, the whole board will eventually be filled. The player that cannot move (because the board is full) loses.

Let’s begin analyzing this game…

First, if the board is completely full, clearly the first player loses because it’s already full. The next simplest is when there is one empty square. Since we need a marked square and the board is connected, this empty square will be adjacent to some marked square, allowing the first player to mark it to win.

The next few simple games are two and three empty squares in a straight line. They are also trivially winning, as long as these squares are adjacent to some previously marked square. Note that we only need one marked square. In all cases, these positions are winning.

straight3

But what are their values? The full board is clearly *0. The single empty square board is *1, as the only move is to leave it to a full board with is *0. (Remember that *1 = \{*0\}.) The double empty squares board is *2; we can mark one square, leaving a *1, or two squares, leaving a *0. Similar with the triple empty squares giving *3.

What about four empty squares? Welcome to the first weirdness of the game!

straight4

The left position is losing. The only available moves are *3, *2, *1, and thus since it’s missing *0, its value is *0. Remember how \{*3, *2, *1\} = *0. The right position is winning; indeed, its value is as we expected, *4, since it has the additional available move of marking the two middle squares to leave *1 + *1 = *0.

…got confused? Try digesting it more slowly. The left position is losing, as it is \{*3, *2, *1\} = *0.

straight5

But the right position is winning, as it is \{*1+*2, *1+*1, *1, *2, *1\} = \{*3, *0, *1, *2, *1\} = *4.

straight6

That’s more or less everything required! Simply carefully break down every move, compute its value, and find the minimum excluded value to find the original board’s value.

Note the second position above (the *4 one), and among its choices, see the one that separates into *1+*1. With nimbers, we can clearly see that they add up to *0. But sometimes the original position makes it more obvious: they are two identical shapes! So certainly they equate to the same value, summing up to *0. In winning strategy terms, this is “play symmetrically; whatever your opponent plays in one part, copy it in the other part”. Thus you can see how the following position is winning, by simply finding a single move that breaks the rest into pairs of identical pieces:

straight7

Evaluating the value is harder, but sticking with the same principle, we can try searching for moves that break into pairs of identical pieces, except for some piece whose value we already know. Of course, we cannot always get such move, and sometimes we need to look for pretty much all moves to determine that some value can or cannot be obtained.

Also note that the value is never more than the number of squares. This is not a coincidence and can be proven by strong induction.

With that, we’ll do one more board:

straight8

You might be familiar with the shape; indeed, this is the exact Monorail board that I suggested in the original discussion linked above. As it turns out, the left L-part has value *6 as one can move in it to reach all of *0, *1, \ldots, *5 positions.

straight9

However, the d-part has value *2! Yes, I made a mistake in the original analysis. (I think. Someone please verify? I got the d-part is \{*0, *0, *0, *1, *4, *4, *5, *5, *5, *5, *6, *6\} = *2.) Thus the value of the original board is *6+*2 = *4, and by using Nim strategy, the player to move wins by playing on *6 to reduce it to *2.

Of course, in Monorail, the first player was the one that forced the above configuration and now it’s second player’s turn, so the first player made a fatal mistake of playing that move. But again, the reason I suggested this move was more psychological than logical. The fact that you know exactly how to respond on any opponent’s mistake also helps.

Then, another game for Jinho versus Hyunmin. The track is completely determined at this point, and so we convert to a Straight position:

straight10

I haven’t completely evaluated the above. Anyone interested on figuring it out? I know when Hyunmin claimed the win (1:25), it was actually a loss (a win for player to move, Jinho).

straight11

That’s pretty much all I have about Monorail and Straight at the moment. I might write more, but it would be about some other impartial game and interesting observations from it.

Advertisements

8 thoughts on “Introduction to Combinatorial Game Theory, Part 3

  1. How would you go about evaluating this board state:

    Where blue is the original station, red is P1s move that forces a particular path, and black is empty space (ie, putting a tile over black results in opponent calling impossible)

    My current hunch is that Monorail as a game is a win for P2 given perfect play, but I’m not sure how to go about proving that.

    Reply
    • I’m not sure it’s possible to force that particular path:

      However, in either case, the domino at top-right is a *2. The giant 11-square area below needs massive case checking, much more than the L-shape above; this is the problem with nimbers (you need to test everything to get a perfect count). Of course, you actually only need to find if it’s possible to make the lower one a *2 (so that the sum is *2 + *2 = *0, meaning the next player to move loses, which means by playing that move you’ll win), but still checking everything.

      Reply
      • Ah, I missed the different paths you could take in the bottom left! Thanks for that, it’s clear now that there’s a forced win for player 2:

        If player 2 plays in green:

        He leaves player one with two 1×2 units and a 2×4 unit. Any movement by player one in the 1×2 units can be mirrored by player 2, and the 2×4 unit is a forced win for the player to move second (invariably player 2), since after any move by the first player, the second can simply divide it to form *0.

        Reply
        • I’m interested on what reply there is for the move R4C3-4 (a domino along row 4, column 3-4 in the above picture). (Too lazy to make another picture.)

          Reply
          • That moves loses to R3C4-3+R4C4-3. This produces one 1×1 and one 2×2 (where one square in the 2×2 is inaccessible). No move P1 makes in the 2×2 can stop P2 from reducing the 2×2 into a 1×1, leaving a symmetric, *0 position. If P1 plays in the 1×1, P2 responds with R3C5-2!, which wins because P1 cannot respond in the bottom right corner.

            The other “feisty” move P1 has is R3C6-1, but this ends up losing to R3C4-2.

          • Remember that the 2×4 unit is not a rectangle (it’s 7 squares, missing one corner).

            On the other hand, that’s true, the reply would be R3C4-5 to make an L of 3 squares with the elbow inaccessible.

            What is R3C6-1? R3C6, playing one tile? R4C3-4 means Row 4, Column 3-4, not Row 4, Column 3, playing 4 tiles.

          • Ah, my apologies, I misunderstood your syntax. I intended “R3C6-1” to mean Row 3, Column 6 (from the left), Column 1 (from the right), playing one tile. Looking back, an alternate response to your move could be Row 3, far right + Row 3, middle right, (columns 5 and 6) which produces 2 2×1 units.

          • That response doesn’t quite work for the same reason: the 2×4 is not a rectangle.

            Playing there makes a domino and a single square.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s