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
Prerequisites
Familiarity with the following concepts:
- Basic set theory notion: union, cartesian product and symmetric difference of sets, set of all subsets denoted as $$$2^A$$$, etc;
- Groups and fields: definitions, basic facts, most well-known examples (e.g. $$$\mathbb R$$$, $$$\mathbb Z_p$$$);
- Familiarity with the xor operation and its properties;
- Notion of equivalence relations.
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 emorgan.
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
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
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
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
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
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
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
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
where $$$\delta : 2^{V_1 \times V_2} \mapsto 2^{2^{V_1 \times V_2}}$$$ is defined as
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.
Computation
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
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
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:
because
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 some further exploitation nimber product properties (see the comments below), it's possible to reduce the running time even further to ~410 ms.
Problem examples
Left to the reader as an exercise.
1310F - Плохая криптография. 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 - Прекрасные тройки. It is related to nimber product somehow, right?
