First steps on strategy (part 2/3)

This is the second post in a series; you can find the first one here. As with the first post 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.

At the end of the first post in this devlog I posed the following question: is T₁ = T₄? There are two ways to see that the answer to this question is "yes". The most direct way is to use the definition of equality directly and argue that T₁ + T₄ is a 𝒫-position. Let’s imagine that we are playing second and convince ourselves that we have a winning reply to any move that our opponent, playing first, could make:

• The first player could start by collecting the sole card from the T₁ strip so that the remaining board is just T₄. We can reply by taking the middle two cards, so that what remains is T₁ + T₁, which we will clearly now win in by mirroring.

• The first player could start by collecting a single end card from the T₄ strip, resulting in T₁ + T₃. Then we can collect one end card from the T₃ strip and burn the other, resulting in a T₁ + T₁ board for our opponent, which we again know to be a 𝒫-position.

• The first player could collect an end card from the T₄ strip and burn its neighbor (or vice versa), resulting in T₁ + T₂. Now collecting a single card from the T₂ results in T₁ + T₁ again, so we win.

• The first player could collect a middle card from the T₄ strip and burn nothing, resulting in T₁ + T₁ + T₂. Then we can collect one card from the T₂ and burn the other, wiping it out entirely and resulting in T₁ + T₁.

• The first player could collect and burn both middle cards from the T₄ strip, resulting in T₁ + T₁ + T₁. Collecting a single T₁ again yields T₁ + T₁ so that we win.

This exhaustive analysis confirms that T₁ + T₄ is indeed a 𝒫-position, but already in this small case it is quite tedious. A better way of determining that these positions are equal is to use a concept called Grundy values.

For our purposes, we will define the Grundy value 𝒢(X) of a position X as follows:

• If no moves are possible from X, then 𝒢(X) = 0.

• Otherwise, let Y₁, Y₂, …Y_k be the positions that are reachable from X in one move (also called the options of X). Then we define 𝒢(X) to be the smallest nonnegative integer not contained among 𝒢(Y₁), …, 𝒢(Y_k) (which we can compute recursively using this definition).

An equivalent formulation of this definition is: to compute 𝒢(X), we start counting up candidate values starting from zero. At each possible candidate value k, we check whether some option having value k. As soon as we find a candidate value not represented among the moves from X, we can stop checking and declare that candidate value to be the Grundy value of X.

To illustrate, a few small examples:

• Since 0, the board with no cards, has no options, 𝒢(0) = 0.

• From the position T₁, the only possible move is to 0. So 𝒢(T₁) is the smallest nonnegative integer not equal to 𝒢(0), i.e., not equal to 0. Thus 𝒢(T₁) = 1.

• From the position T₂ it is possible to move either to 0 (by collecting one card and burning the other) or to T₁ (by collecting a card and burning nothing). So 𝒢(T₂) is the smallest nonnegative integer not among 𝒢(0) and 𝒢(T₁), i.e., not equal to 0 or 1. Thus 𝒢(T₂) = 2.

• From the position T₁ + T₁ we have essentially only option, namely T₁. (Strictly speaking we have a choice between collecting the "left copy" or the "right copy" of T₁, but either way, the remaining board is just a single card.) So 𝒢(T₁ + T₁) is the smallest nonnegative integer not equal to 𝒢(𝒯₁), i.e., not equal to 1. That means that 𝒢(T₁ + T₁) = 0.

It turns out that Grundy values give us a convenient way to tell if two positions are equal: they are equal if and only if they have the same Grundy value. (In fact our presentation here is somewhat backwards compared to the usual presentation in the literature: usually Grundy values are defined in terms of equality and then the recursive calculation is a theorem derived from that definition. In the literature that recursive calculation is usually called the mex rule, short for "Minimal EXcludant".)

This gives us a somewhat faster way to reach our conclusion that T₁ = T₄. We already know that 𝒢(T₁) = 1, so we can go ahead and try to compute 𝒢(T₄) using the recursive definition:

• The options of T₄ are T₂, T₃, T₂ + T₁, and T₁ + T₁. We already saw above that 𝒢(T₁ + T₁) = 0 and that 𝒢(T₂) = 2, so we just need to work out 𝒢(T₃) and 𝒢(T₂ + T₁).

  • The options of T₃ are T₁, T₂, and T₁ + T₁. We already know the Grundy values of each of these options: we have 𝒢(T₁) = 1, 𝒢(T₂) = 2, and 𝒢(T₁ + T₁) = 0. So the first value not represented among these options is 3, and we have 𝒢(T₃) = 3.

  • From T₂ + T₁, we have two options corresponding to a move in the left side – to T₁ + T₁ and to T₁ – and a single option corresponding to a move in the right side, to T₂. We already know that 𝒢(T₁ + T₁) = 0, that 𝒢(T₁) = 1, and that 𝒢(T₂) = 2. So again the values of our options are 0, 1, and 2, and the first value not represented among them is 3. Thus 𝒢(T₁ + T₂) = 3.

• Now we know the Grundy values of all options of T₄: the values of the options are 2, 3, 3, and 0. In particular, since there is an option of value 0 but no option of value 1, the smallest candidate value not represented among the values of the options is 1, so we have 𝒢(T₄) = 1.

On the face of it this might not seem to be much less work than the brute-force argument we saw at the beginning of this post. But an advantage of this approach is that the work we did here is reusable: just as we used the fact that we’d already worked out, say 𝒢(T₂) as part of our calculations here, so also can we reuse the values of 𝒢(T₃) and 𝒢(T₄) to work out the Grundy values of longer strips.

It’s tempting to notice that 𝒢(T₁ + T₂) = 3 = 1 + 2 = 𝒢(T₁) + 𝒢(T₂) and hazard a guess that maybe always 𝒢(X + Y) = 𝒢(X) + 𝒢(Y). But recall that X + X = 0 for every X, so that 𝒢(X + X) = 0 for any position X. It turns out that there is a nice addition rule for Grundy values that allows us to compute 𝒢(X + Y) knowing only 𝒢(X) and 𝒢(Y), without having to "open the black box" and start looking at subpositions of X and Y. That addition rule will be the topic of the third part of this post.

A question you might want to chew on in the meantime: what is 𝒢(T₅)?

Continue to part 3