adamant's blog

By adamant, history, 18 months ago, In English

Hi everyone!

Today I'd like to write about the so-called Grundy numbers, or nimbers. I will start by providing a formal recap on the Sprague-Grundy theorem and then will advance to the topic that is rarely covered in competitive programming resources, that is I will write about nimber product and its meaning to the game theory.

I was asked to add the following to the blog: THANK SIR MASTER Adam_GS FOR GREAT AND VALUABLE REVIEW SIR


Familiarity with the following concepts:

Familiarity with formal computational models (e.g. deterministic finite automata) is not required, but would be helpful.

Although the nimbers are typically constructed on top of ordinal numbers and transfinite nim, I will try to stick with natural numbers and classic nim. You may familiarize yourself with transfinite nim in e.g. this article by emorgan5289.

Basic definitions

Def. 1. An impartial game is a game that can be represented as a tuple $$$G=(V, \delta, s)$$$, such that

  • $$$V$$$ is a set of game states;
  • $$$\delta : V \mapsto 2^V$$$ is a move function, meaning that the player can move from $$$v$$$ to $$$u$$$ if and only if $$$u \in \delta(v)$$$;
  • $$$s \in V$$$ is the starting state of the game;
  • Starting in $$$s$$$, two players take turns alternatingly, changing the current state $$$v$$$ to $$$u \in \delta(v)$$$;
  • ( normal play convention ) Player that can't make a move loses or
  • ( misère play convention ) Player that can't make a move wins.

Informally, an impartial game takes place in a directed graph $$$G$$$ with a starting vertex $$$s$$$, while the players always move along the arcs of the graph. The key word impartial here means that the set of possible moves $$$\delta(v)$$$ from the vertex $$$v$$$ is same for both players.

Correspondingly, a partisan game would imply that there are two move functions $$$\delta_1(v)$$$ and $$$\delta_2(v)$$$, defining possible moves for the first and the second players correspondingly. We're not concerned about such games in this article.

Def 2. An impartial game $$$G$$$ is called winning if the first player has a winning strategy under the used play convention. Correspondingly, the game is called losing if the second player has a winning strategy. In a similar manner, states of the game are classified into losing and winning ones, e.g. is the state $$$v$$$ is winning if the game $$$(V, \delta, v)$$$ is winning and vice versa.

Generally, the game might be neither winning, nor losing if the game graph has cycles.

A simple game represented as a directed graph. Losing states are red, winning states are blue.

Claim 1. The state $$$v$$$ is losing if and only if $$$\delta(v)$$$ is empty or all its elements are winning states. The state $$$v$$$ is winning if and only if there is a losing state in $$$\delta(v)$$$.

The result above allows to classify all game states on arbitrary graphs into either winning, losing or drawing (when the game started in the state would go indefinitely) with some kind of reverse breadth-first search.

Def. 3. An impartial game is progressively bounded if there is an upper bound for every state $$$s$$$ on the number of turns that can be made starting in $$$s$$$, until a state $$$v$$$ having $$$\delta(v) = \varnothing$$$ is reached.

Claim 2. Every state in the progressively bounded game is either winning or losing.

Game sum

Def. 4. Let $$$G_1=(V_1, \delta_1, s_1)$$$ and $$$G_2=(V_2, \delta_2, s_2)$$$ be impartial games. The sum of games $$$G=G_1+G_2$$$ is defined as

$$$ G_1 + G_2 = (V_1 \times V_2, \delta, (s_1, s_2)), $$$

where $$$\delta: V_1 \times V_2 \mapsto 2^{V_1 \times V_2}$$$ is a joint move function defined as $$$\delta(v_1, v_2) = \delta(v_1) \times \{v_2\} \cup \{v_1\} \times \delta(v_2)$$$.

Here $$$A \times B = \{(a, b) : a \in A, b \in B\}$$$ is the Cartesian product of $$$A$$$ and $$$B$$$.

Informally, $$$G_1 + G_2$$$ is a game in which players have both $$$G_1$$$ and $$$G_2$$$ on the table, and in one turn player could do a valid turn either in $$$G_1$$$, or in $$$G_2$$$. Correspondingly, player which can't make a move in both games loses.

Def. 5. Nim is a game in which two players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap. The player that can't make a move loses.

Let $$$N_a$$$ be a game of nim consisting of the only heap of size $$$a$$$. Then the game of nim on heaps of sizes $$$a_1, a_2, \dots, a_n$$$ is represented as

$$$ N = N_{a_1} + N_{a_2} + \dots + N_{a_n}. $$$

Graphic representation of $$$N_2$$$, $$$N_3$$$ and $$$N_2+N_3$$$.

Claim 3. If $$$A$$$ and $$$B$$$ are impartial progressively bounded games, then so is $$$A+B$$$.

Claim 4. If $$$A$$$ and $$$B$$$ are losing, then so is $$$A+B$$$.

Proof. Second player can just respond to any turn with the corresponding second player winning strategy in that game. $$$\square$$$

Sprague-Grundy theorem

Def 6. Impartial progressively bounded games $$$A$$$ and $$$B$$$ are equivalent (denoted $$$A \sim B$$$) if for any impartial progressively bounded game $$$C$$$, $$$A+C$$$ has the same outcome as $$$B+C$$$.

Claim 5. If $$$B$$$ is losing, then $$$A \sim A+B$$$.

Proof. We have to prove that $$$A+C$$$ has the same outcome as $$$(A+C)+B$$$ when $$$B$$$ is losing. If $$$A+C$$$ is losing, it follows from claim 4. Otherwise, first player makes a move in $$$A+C$$$ into losing position $$$(A+C)'$$$. Now both $$$(A+C)'$$$ and $$$B$$$ are losing, hence $$$(A+C)'+B$$$ is losing for the second player. $$$\square$$$

Claim 6. For any game $$$A$$$, its sum with itself $$$A+A$$$ is losing.

Proof. Second player can symmetrically repeat the moves of the first one in the second game. $$$\square$$$

Claim 7. ( Equivalence criterion ) $$$A \sim B$$$ if and only if $$$A+B$$$ is losing.

Proof. Let $$$A \sim B$$$. Then $$$A+B$$$ has the same outcome as $$$B+B$$$, so it is losing. Now assume that $$$A+B$$$ is losing. From claim 5 it follows that $$$(A+B)+B \sim B$$$. On the other hand, $$$B+B$$$ is losing, so $$$A+(B+B) \sim A$$$ and $$$A \sim B$$$. $$$\square$$$

Claim 8. ( Sprague-Grundy theorem ) Every impartial progressively bounded game is equivalent to a one-heap game of nim.

Proof. The game in which $$$\delta(s)=\varnothing$$$ is equivalent to a game of nim on the heap of size $$$0$$$. On the other hand, in progressively bounded games we will always reach state $$$v$$$ such that $$$\delta(v)=\varnothing$$$ after finite amount of turns, so we can prove the result with a backwards induction on the distance to the furthest blocked state.

Essentially, in each move we change our game from $$$(V, \delta, v)$$$ to $$$(V, \delta, u)$$$, where $$$u \in \delta(v)$$$. All such vertices $$$u$$$ must have a lower distance to the furthest losing state than $$$v$$$, hence by induction $$$(V, \delta, u) \sim N_{a_u}$$$, where $$$a_u$$$ is the size of the one-heap nim for $$$u$$$.

What we need to prove now is that there is $$$a_v$$$ such that $$$(V, \delta, v) \sim N_{a_v}$$$. Core result discovered by Sprague and Grundy is that

$$$ a_v = \operatorname{mex}(\{a_u : u \in \delta(v)\}), $$$

where $$$\operatorname{mex}(S)$$$ ( minimum excluded ) is the smallest non-negative integer that does not belong to $$$S$$$.

Let's prove that $$$N_{a_v}+G_v$$$, where $$$G_v = (V, \delta, v)$$$ is, indeed, a losing game.

If the first player moves from $$$N_{a_v}$$$ to $$$N_x$$$ with $$$x < a_v$$$, the second one can move into $$$N_x$$$ in $$$G_v$$$, as there is $$$u$$$ such that $$$a_u=x$$$. If the first player moves from $$$G_v$$$ into $$$N_{a_u}$$$, we end up with the game $$$N_{a_v} + N_{a_u}$$$, where $$$a_u \neq a_v$$$, hence the second player may match the sizes of the heaps. In both cases after second player moves, the resulting game looks like $$$N_x+N_x$$$ and it is a losing game. $$$\square$$$

Def. 7. A nimber $$$x$$$ of the game $$$G$$$ is the size of its one-heap equivalent, that is $$$G \sim N_x$$$.

From the definition it follows that the nimber of $$$N_a$$$ is $$$a$$$.

Nimber sum

You can use this Lenstra's publication as a further reference for the stuff mentioned below

Def. 8. The nimber sum $$$a \oplus b$$$ is a nimber of $$$N_a + N_b$$$, that is $$$N_{a \oplus b} \sim N_a + N_b$$$.

Note that from $$$N_v$$$ it is possible to move to any $$$N_u$$$ such that $$$0 \leq u < v$$$, thus from Sprague-Grundy theorem it follows that

$$$ a \oplus b = \operatorname{mex}\left(\{a' \oplus b : a' < a\} \cup \{a \oplus b' : b' < b\}\right). $$$

Claim. 9. $$$a \oplus b$$$ is the xor of $$$a$$$ and $$$b$$$.

Proof. We have to prove that $$$N_{a \operatorname{xor} b} + N_a + N_b$$$ is a losing game. After the first move we will have three heaps $$$N_x$$$, $$$N_y$$$ and $$$N_z$$$ such that the xor of $$$x$$$, $$$y$$$ and $$$z$$$ will not be equal to $$$0$$$. It is always possible to reduce one of the heaps, so that their xor becomes $$$0$$$ again, which yields a winning strategy for the second player. $$$\square$$$

Algebraic rationale

One can check that nimbers with the nimber sum operation form up a group. Conway pointed out that, in a sense, it is the simplest group that can be defined on the set of non-negative integers.

Indeed, for any group operation it must hold that

$$$ a' \oplus b \neq a \oplus b \text{ and } a \oplus b' \neq a \oplus b $$$

for $$$a \neq a'$$$ and $$$b \neq b'$$$. Otherwise, the operation wouldn't form a group. Now $$$a \oplus b$$$ is the smallest value not violating these rules.

Nimber product

Using the algebraic rationale above, it is also possible to define a "simplest" operation $$$\cdot$$$ such that nimbers with operations $$$\oplus$$$ and $$$\cdot$$$ form up a field. Specifically, there must not be any non-trivial divisors of zero in a field, hence

$$$ (a-a') \otimes (b-b') \neq 0 \iff ab \neq a'b + ab' - a'b' $$$

for $$$a' \neq a$$$ and $$$b' \neq b$$$. Again, taking the smallest possible value of $$$a b$$$ that wouldn't violate the rule above, we arrive to the following definition of the nimber product:

Def. 9. The nimber product $$$ab$$$ is defined recursively as

$$$ ab = \operatorname{mex}\left(\{a'b \oplus ab' \oplus a'b' : a'<a, b'<b\}\right). $$$

Conway proved that nimbers with $$$\oplus$$$ and $$$\cdot$$$ operations form a field of characteristic $$$2$$$ that is algebraically closed if nimbers are constructed on top of the proper class of ordinal numbers (this part goes a bit beyond the scope of the article).

Which is nice, but we'd also like to see some game theoretic implications of the nimber product, right?

Def. 10. The diminishing rectangles game is described as follows:

Let's represent a nimbers product $$$nm$$$ as a stone in the point $$$(n, m)$$$ on $$$2$$$-dimensional plane.

Then the definition of the nimber product corresponds to the following set of moves:

  • pick a point $$$(x, y)$$$ such that $$$x, y \geq 1$$$ and there is a stone on $$$(x, y)$$$;
  • pick a pair of non-negative integers $$$x'$$$ and $$$y'$$$ such that $$$0 \leq x' < x$$$ and $$$0 \leq y' < y$$$;
  • remove a stone from the point $$$(x, y)$$$ and place one stone in each of points $$$(x', y)$$$, $$$(x, y')$$$ and $$$(x', y')$$$.

The game continues on until there is no stone with positive coordinates left.

A move in the diminishing rectangles game.

Note that $$$A \oplus A=0$$$, hence, we may take the number of stones modulo $$$2$$$, which results in the following game:

Def. 11. The coin turning game is described as follows:

There is an $$$(n+1) \times (m+1)$$$ sized rectangular table. In each table cell there is a coin. All coins are initially tails up, except for the coin in the cell $$$(n, m)$$$, which is heads up. In a turn, the player can do the following:

  • pick a cell $$$(x, y)$$$ such that $$$x, y \geq 1$$$ and the coin in $$$(x, y)$$$ is heads up;
  • pick a pair $$$0 \leq x' < x$$$ and $$$0 \leq y' < y$$$;
  • flip all the coins in the rectangle formed by $$$(x', y')$$$, $$$(x', y)$$$, $$$(x, y')$$$ and $$$(x, y)$$$.

The game continues on until all cells with $$$x, y \geq 1$$$ have only coins facing tails up.

Game product

Now, having a bit more of intuition on the product of nim game, we may define a product of arbitrary games:

Def. 12. Let $$$G_1 = (V_1, \delta_1, s_1)$$$ and $$$G_2=(V_2, \delta_2, s_2)$$$ be impartial games. The product of games $$$G_1 \cdot G_2$$$ is defined as

$$$ G_1 \cdot G_2 = (2^{V_1 \times V_2}, \delta, \{(s_1, s_2)\}), $$$

where $$$\delta : 2^{V_1 \times V_2} \mapsto 2^{2^{V_1 \times V_2}}$$$ is defined as

$$$ \delta(S) = \big\{S \triangle \{(u_1, u_2), (u_1, v_2), (v_1, u_2), (v_1, v_2)\} : (v_1, v_2) \in S, u_1 \in \delta_1(v_1), u_2 \in \delta_2(v_2) \big\}, $$$

where $$$A \triangle B$$$ is the symmetric difference of two sets.

Informally, there is nothing I can say really to explain what's going on here.


Library Checker — Nim product. Given $$$a_1, \dots, a_n$$$ and $$$b_1, \dots, b_n$$$, compute $$$a_i \cdot b_i$$$ for each $$$i$$$, where $$$a_i, b_i < 2^{64}$$$ and $$$n \leq 10^6$$$.

Any non-negative integer $$$n$$$ can be decomposed as $$$n = 2^{a_1} \oplus 2^{a_2} \oplus \dots$$$, where $$$0 \leq a_1 < a_2 < \dots$$$ are integers. Let $$$m=2^{b_1} \oplus 2^{b_2} \oplus \dots$$$, where $$$0 \leq b_1 < b_2 < \dots$$$, then using the distributivity of $$$\oplus$$$ and $$$\cdot$$$, we may rewrite the nimber product $$$nm$$$ as

$$$ n \cdot m = \bigoplus\limits_{i,j} 2^{a_i} \cdot 2^{b_j}. $$$

In other words, knowing how to compute the nim product $$$2^a \cdot 2^b$$$ would allow us to compute the nim product for arbitrary $$$n$$$ and $$$m$$$.

Claim 10. Let $$$a=2^{2^\alpha}$$$ and $$$b = 2^{2^\beta}$$$, where $$$\alpha \neq \beta$$$. Then $$$a \cdot b = 2^{2^\alpha+2^\beta}$$$ and $$$a \cdot a = \frac{3}{2} 2^{2^{\alpha}}$$$.

Now, let $$$a = 2^{\alpha_1}+2^{\alpha_2}+\dots$$$ and $$$b=2^{\beta_1}+2^{\beta_2}+\dots$$$, where $$$0 \leq \alpha_1 < \alpha_2 < \dots$$$ and $$$0 \leq \beta_1 < \beta_2 < \dots$$$ then

$$$ 2^a \cdot 2^b = (2^{2^{\alpha_1}} \cdot 2^{2^{\alpha_2}} \cdot \dots)(2^{2^{\beta_1}} \cdot 2^{2^{\beta_2}}\cdot \dots) = (2^{2^{\alpha_1}} \cdot 2^{2^{\beta_1}}) \cdot (2^{a-2^{\alpha_1}} \cdot 2^{b-2^{\beta_1}}). $$$

This reduction allows to compute $$$2^a \cdot 2^b$$$ as $$$x \cdot y$$$, where $$$x \leq 2^{a-1}$$$ and $$$y \leq 2^{b-1}$$$, so it will sooner or later reach $$$x=1$$$ or $$$y=1$$$.

When $$$a, b < 2^{2^n}$$$, it also holds that $$$a \cdot b < 2^{2^n}$$$, so $$$\oplus$$$ and $$$\cdot$$$ define a field on the set of non-negative integers less than $$$2^{2^n}$$$ for any $$$n$$$. It also holds for $$$2^{64}=2^{2^6}$$$, so if all $$$2^a \cdot 2^b$$$ are precomputed, one could find the nim product of any $$$64$$$-bit numbers in $$$64^2$$$ operations:


It is also possible to significantly improve the running time of the nimber multiplication using Karatsuba-like scheme:

$$$ (a_0 \oplus 2^{2^k} \cdot a_1) \cdot (b_0 \oplus 2^{2^k} \cdot b_1) = (a_0 \cdot b_0) \oplus (a_0 \cdot b_1 \oplus a_1 \cdot b_0)\cdot 2^{2^k} \oplus (a_1 \cdot b_1) \cdot \frac{3}{2}{2^{2^k}}, $$$


$$$ a_0 \cdot b_1 \oplus a_1 \cdot b_0 = (a_0 \oplus a_1) \cdot (b_0 \oplus b_1) \oplus a_0 \cdot b_0 \oplus a_1 \cdot b_1 $$$

and $$$\frac{3}{2} 2^{2^k} = 2^{2^k} \oplus 2^{2^k - 1}$$$. Here's my implementation that takes 1.4s on the Library Judge.

UPD: With exploitation of nimber product properties (see the comments below), it's possible to reduce the running time further to ~410 ms.

Problem examples

Left to the reader as an exercise.

1310F - Bad Cryptography. Given $$$a_1, \dots, a_n$$$ and $$$b_1, \dots, b_n$$$, solve $$$a_i^x = b_i$$$ for each $$$i$$$, where $$$a_i, b_i < 2^{64}$$$ and $$$n \leq 100$$$.

1338C - Perfect Triples. It is related to nimber product somehow, right?

  • Vote: I like it
  • +204
  • Vote: I do not like it

18 months ago, # |
  Vote: I like it +29 Vote: I do not like it

Another adamant classic.

18 months ago, # |
  Vote: I like it +32 Vote: I do not like it

Conway proved that nimbers with ⊕ and ⋅ operations form an algebraically closed field of characteristic $$$2$$$.

Although this claim is generally true, it is not as simple as it stated. What do you think are the solutions to the equation $$$x^3 = 2$$$? It is clear that the answers can't be finite because every finite number lies in a field $$$\mathbb{F}_{2^{2^k}}$$$. So, if you guessed $$$\omega$$$, you got it right! I intentionally don't want to prove that it is exactly $$$\omega$$$ and to spoil what two remaining solutions are, because I am lazy and these problems are nice exercises on nimbers.

So, the thing is, it is not algebraically closed for nimbers built on top of $$$\mathbb{N}$$$. But it will be, if you consider the "set" of all ordinals or, alternatively, all ordinals less than $$$\omega^{\omega^\omega}$$$ (and this is what Conway proved, as far as I know). And here we see another problem. The "set" of ordinals is not a set. And this is a problem for the common definition of a field. However, in fact, if we trust Conway, we don't really need this requirement.

Therefore, it is indeed an algebraically closed field, but with a bit more general notion of a field, which does not break any properties you may need. Or, if we consider only finite numbers, then nimbers form a field (in a regular sense), but not algebraically closed.

  • »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for pointing that out! I amended the wording, so I hope that it reflects the actual state of things better.

  • »
    18 months ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    I don't think you encounter any set-theoretical obstacles at $$$\omega^{\omega^\omega}$$$, which is quite tame as far as ordinals go.

    • »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are absolutely right! It was my turn to choose imprecise wordings. I meant this problem specifically to the class of all ordinals.

      Nimbers less than $$$\omega^{\omega^\omega}$$$ form a normal algebraically closed field indeed, but you don't really define nimbers over such set. You either choose $$$\mathbb{N}$$$ or all ordinals, depending on whether you want to use regular induction or transfinite.

      Fun fact: $$$\omega^{\omega^\omega}$$$ in not a special one. In fact, almost any good limit ordinal (e.g. $$$\omega^{\omega^{\omega^\omega}}$$$) works as well, $$$\omega^{\omega^\omega}$$$ is just the smallest one, as far as I remember.

18 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Adam_GS master sir is nutella master soon orz

18 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Here's a potentially faster way to compute nimber multiplication: because the nimbers below $$$2^{2^k}$$$ are isomorphic to $$$F_{2^{2^k}}$$$, their multiplication (excluding 0) necessarily forms a cyclic group. Thus, we can pick a generator and precompute a lookup table of discrete logs of size $$$2^{2^k}$$$, and then do a single addition, then use a lookup table of exponents. We can easily do this for values up to $$$2^16$$$.

For bigger values, we can use the fact that $$$x \cdot y = x \otimes y$$$ for any $$$x < 2^{2^k}$$$ and $$$2^{2^k} \mid y$$$, so given $$$a = a_0 + a_1 2^{16} + a_2 2^{32} + a_3 2^{48}$$$, we know this equals $$$a_0 \oplus a_1 \otimes 2^{16} \oplus a_2 \otimes 2^{32} \oplus a_3 \otimes 2^{48}$$$. Then, we can do the distributing trick but this time in base $$$2^16$$$ instead of base 2.

I believe this is roughly what the fastest solutions on library checker do.

  • »
    18 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    Hey, thanks! I didn't know the $$$x \cdot y = x \otimes y$$$ for $$$x < 2^{2^k}$$$ and $$$y \equiv 0 \pmod{2^{2^k}}$$$.

    Just using this (without resorting to logarithms) allowed me to reduce the running time from ~1350 ms to 775 ms.

    Finally, on top of that we should note that the generator of nimbers below $$$2^{2^k}$$$ is $$$2^{2^k}-1$$$, which we may use to find the isomorphism and precompute logarithms... So, it further reduces the execution time to 414 ms and the implementation itself also seems short and simple enough:


    It doesn't seem possible to optimize much further at the moment, as just adding fastio reduces it to ~150ms, which is already among top submissions.

18 months ago, # |
  Vote: I like it +19 Vote: I do not like it

What a beautiful post with some awesome intuition! And really, the intuition can't be understated — I couldn't understand the motivation behind any of this, from reading the Wikipedia articles.

Thanks so much