First steps on strategy (part 3/3)

This is the third post in a series; you can find the first one here. As with the first two posts in this series, it is arguably a spoiler for Aces’ Nim if you want to figure the whole thing out from first principles – so you may want to stop reading here if you want to remain unspoiled.

In the previous part of this devlog we introduced the Grundy value of a position, written 𝒢(X). We saw that two positions X and Y with the same Grundy value are equal, in the sense that X + Y is a 𝒫-position, and saw that 𝒢(X) can be calculated recursively by examining the Grundy values of the options of X. But, especially for a position that consists of a sum of multiple strips, enumerating all the options of the position can be tedious work. For example, one option of T₅ is the sum T₃ + T₁, which several options:

• Three options obtained from various moves in the T₃ piece:

  • T₂ + T₁,

  • T₁ + T₁,

  • T₁ + T₁ + T₁,

• T₃, obtained by moving in the T₁ piece.

For a larger sum like T₂ + T₃ + T₄ + T₅ it would quickly become bewildering to keep track of all the options obtained from considering moves in each possible piece. It would instead be ideal if we could consider each piece separately, compute its Grundy value, and then somehow combined those Grundy values in order to arrive at a final value for the entire sum. In this post we will see how to do that.

The key turns out to be writing the Grundy values in question as binary number and applying the bitwise XOR operator – an operation sometimes known in this context as the "nim-sum". Expressed in notation, we write x ⊕ y to stand for the bitwise XOR of the numbers x and y when expressed in binary, so that, for example, 7 ⊕ 3 = 4 and 5 ⊕ 3 = 6. Somewhat magically, this turns out to be the correct operation for combining Grundy values in a sum of positions: for any positions X and Y we have 𝒢(X + Y) = 𝒢(X) ⊕ 𝒢(Y).

This nim-sum formula generalizes some of our early observations. For example, the mirroring argument showed that X + X = 0 for every position X; using the nim-sum formula shows that 𝒢(X + X) = 𝒢(X) + 𝒢(X) = 0, the second equality following from the fact that k ⊕ k = 0 for every nonnegative integer k. And we have already seen that 𝒢(T₂ + T₁) = 3, which can now be properly explained by observing that 3 = 2 ⊕ 1 = 𝒢(T₂) + 𝒢(T₁). (While ⊕ usually does not usually coincide with ordinary addition, in this particular case the binary expansions of 2 and 1 do not have any 1-bits in the same location, so we get the same result as ordinary addition.)

Using this formula we can now compute 𝒢(T₅) using the grundy values we already know without having to recurse deeply down into each of the options. The options of T₅, and their respective Grundy values, are:

• T₄, with 𝒢(T₄) = 1 (as computed earlier),

• T₃ + T₁, with 𝒢(T₃ + T₁) = 𝒢(T₃) ⊕ 𝒢(T₁) = 3 ⊕ 1 = 2,

• T₂ + T₂, with 𝒢(T₂ + T₂) = 𝒢(T₂) ⊕ 𝒢(T₂) = 2 ⊕ 2 = 0,

• T₃, with 𝒢(T₃) = 1,

• T₂ + T₁, with 𝒢(T₂ + T₁) = 𝒢(T₂) ⊕ 𝒢(T₁) = 2 ⊕ 1 = 3,

All in all, T₅ has options with Grundy values 0, 1, 2, 3 but no option of Grundy value 4, so we conclude that 𝒢(T₅) = 4. And once we know 𝒢(T₁), …, 𝒢(T₅), it is straightforward to compute 𝒢(T₆) using a similar computation to the one above.

Continuing in this manner, one could build a table of Grundy values, at each step using the already-known values to compute the next one. Very long tables have in fact already been computed for some similar types of game characterized by removing objects from a strip. The most well-known class of such games are the octal games, so called because their rules can be succinctly expressed with a short octal number. The single-rank optional burn game we have been considering throughout this post can be expressed as the octal game 0.77, and is more commonly known as Kayles.

How does all this tie back to give a strategy for the single-rank optional-burn game? Suppose we are looking at some starting position consisting of a number of strips. If we know the Grundy value of each individual strip, then we now know that we can take the nim-sum of those Grundy values to determine the Grundy value of the whole position. For example, if we were looking at the position T₅ + T₃ + T₁, then we know the whole position has Grundy value 𝒢(T₅ + T₃ + T₁) = 𝒢(T₅) ⊕ 𝒢(T₃) ⊕ 𝒢(T₂) = 4 ⊕ 3 ⊕ 2 = 5.

Now we just need to find a move that will make the Grundy value of the remaining position equal to 0; this is equivalent to handing the computer a 𝒫-position to move in. It can be shown that such a move can always be found in one of the strips having the highest Grundy value. In this case, moving within T₅ to a position of Grundy value 1 would result in the combined position having Grundy value 1 ⊕ 3 ⊕ 2 = 0. We recall that 𝒢(T₄) = 1, so taking one card off the end of the T₅-strip will yield a winning position.

Thus, Grundy values give a full analysis of any position consisting of only a single rank. I will leave it to you to figure out how to use this knowledge to put together a full winning strategy in the optional-burn ruleset.

To conclude this post I would like to say a few words about the mandatory-burn ruleset. The single-rank case of that ruleset also corresponds to a well-known combinatorial game, in this case a variant of Kayles known as Dawson’s Kayles. And, even not knowing about the details of Dawson’s Kayles, the single-rank case can be analyzed using essentially the same techniques discussed here, just with different starting values for the Grundy sequence: writing M_k for a strip of length k in the mandatory-burn ruleset, we can start by observing that 𝒢(M₁) = 0, 𝒢(M₂) = 𝒢(M₃) = 1, and then start computing higher Grundy values as shown above. All the same ideas about nim-sums of Grundy values still go through just fine. But, in contrast to what you might find for the optional-burn ruleset, the strategy for the multiple-rank case of the mandatory-burn ruleset does not follow very easily from the strategy for the single-rank case. I believe there is still a nice theoretical solution of the multiple-rank case, which I may discuss in a later post if there is interest, but it requires some nontrivial extension of the standard theory discussed in this post.

If you have found this post interesting, then I strongly recommend you consider reading Winning Ways for Your Mathematical Plays by Berlekamp, Conway, and Guy, or that you check out Berlekamp’s Youtube channel, which has videos discussing both the theory of impartial games as discussed here, as well as the broader theory of combinatorial games. If you’ve read this far, thank you very much for your attention!