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:

Here are several legal moves, marked in green:

And several illegal moves, marked in red:

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.

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

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

The left position is losing. The only available moves are , and thus since it’s missing , its value is . Remember how . The right position is winning; indeed, its value is as we expected, , since it has the additional available move of marking the two middle squares to leave .

…got confused? Try digesting it more slowly. The left position is losing, as it is .

But the right position is winning, as it is .

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 one), and among its choices, see the one that separates into . With nimbers, we can clearly see that they add up to . 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 . 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:

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:

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 as one can move in it to reach all of positions.

However, the d-part has value ! Yes, I made a mistake in the original analysis. (I think. Someone please verify? I got the d-part is .) Thus the value of the original board is , and by using Nim strategy, the player to move wins by playing on to reduce it to .

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:

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).

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.