Nimbers and Sprague-Grundy theorem

#	User	Rating
1	jiangly	4039
2	tourist	3841
3	jqdai0815	3682
4	ksun48	3590
5	ecnerwala	3542
6	Benq	3535
7	orzdevinwang	3526
8	gamegame	3477
9	heuristica	3357
10	Radewoosh	3355

#	User	Contrib.
1	cry	168
2	-is-this-fft-	165
3	atcoder_official	160
3	Um_nik	160
5	djm03178	158
6	Dominater069	156
7	adamant	153
8	luogu_official	152
9	awoo	151
10	TheScrasse	147

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
Unable to parse markup [type=CF_MATHJAX]
, 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

Unable to parse markup [type=CF_MATHJAX]

, such that

$$$V$$$ is a set of game states;
Unable to parse markup [type=CF_MATHJAX]
is a move function, meaning that the player can move from $$$v$$$ to $$$u$$$ if and only if
Unable to parse markup [type=CF_MATHJAX]
;
Unable to parse markup [type=CF_MATHJAX]
is the starting state of the game;
Starting in $$$s$$$, two players take turns alternatingly, changing the current state $$$v$$$ to
Unable to parse markup [type=CF_MATHJAX]
;
( 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

Unable to parse markup [type=CF_MATHJAX]

from the vertex $$$v$$$ is same for both players.

Correspondingly, a partisan game would imply that there are two move functions

Unable to parse markup [type=CF_MATHJAX]

and

Unable to parse markup [type=CF_MATHJAX]

, 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

Unable to parse markup [type=CF_MATHJAX]

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

Unable to parse markup [type=CF_MATHJAX]

is empty or all its elements are winning states. The state $$$v$$$ is winning if and only if there is a losing state in

Unable to parse markup [type=CF_MATHJAX]

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

Unable to parse markup [type=CF_MATHJAX]

is reached.

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

Game sum

Def. 4. Let

Unable to parse markup [type=CF_MATHJAX]

and

Unable to parse markup [type=CF_MATHJAX]

be impartial games. The sum of games

Unable to parse markup [type=CF_MATHJAX]

is defined as

Unable to parse markup [type=CF_MATHJAX]

where

Unable to parse markup [type=CF_MATHJAX]

is a joint move function defined as

Unable to parse markup [type=CF_MATHJAX]

Here

Unable to parse markup [type=CF_MATHJAX]

is the Cartesian product of $$$A$$$ and $$$B$$$.

Informally,

Unable to parse markup [type=CF_MATHJAX]

is a game in which players have both $$$G_1$$$ and

Unable to parse markup [type=CF_MATHJAX]

on the table, and in one turn player could do a valid turn either in $$$G_1$$$, or in

Unable to parse markup [type=CF_MATHJAX]

. 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

Unable to parse markup [type=CF_MATHJAX]

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

Unable to parse markup [type=CF_MATHJAX]

Graphic representation of
Unable to parse markup [type=CF_MATHJAX]
,
Unable to parse markup [type=CF_MATHJAX]
and
Unable to parse markup [type=CF_MATHJAX]
.

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

Unable to parse markup [type=CF_MATHJAX]

) if for any impartial progressively bounded game $$$C$$$,

Unable to parse markup [type=CF_MATHJAX]

has the same outcome as

Unable to parse markup [type=CF_MATHJAX]

Claim 5. If $$$B$$$ is losing, then

Unable to parse markup [type=CF_MATHJAX]

Proof. We have to prove that

Unable to parse markup [type=CF_MATHJAX]

has the same outcome as

Unable to parse markup [type=CF_MATHJAX]

when $$$B$$$ is losing. If

Unable to parse markup [type=CF_MATHJAX]

is losing, it follows from claim 4. Otherwise, first player makes a move in

Unable to parse markup [type=CF_MATHJAX]

into losing position

Unable to parse markup [type=CF_MATHJAX]

. Now both

Unable to parse markup [type=CF_MATHJAX]

and $$$B$$$ are losing, hence

Unable to parse markup [type=CF_MATHJAX]

is losing for the second player. $$$\square$$$

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

Unable to parse markup [type=CF_MATHJAX]

is losing.

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

Claim 7. ( Equivalence criterion )

Unable to parse markup [type=CF_MATHJAX]

if and only if $$$A+B$$$ is losing.

Proof. Let

Unable to parse markup [type=CF_MATHJAX]

. Then $$$A+B$$$ has the same outcome as

Unable to parse markup [type=CF_MATHJAX]

, so it is losing. Now assume that $$$A+B$$$ is losing. From claim 5 it follows that

Unable to parse markup [type=CF_MATHJAX]

. On the other hand,

Unable to parse markup [type=CF_MATHJAX]

is losing, so

Unable to parse markup [type=CF_MATHJAX]

and

Unable to parse markup [type=CF_MATHJAX]

. $$$\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

Unable to parse markup [type=CF_MATHJAX]

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

Unable to parse markup [type=CF_MATHJAX]

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

Unable to parse markup [type=CF_MATHJAX]

, where

Unable to parse markup [type=CF_MATHJAX]

. All such vertices $$$u$$$ must have a lower distance to the furthest losing state than $$$v$$$, hence by induction

Unable to parse markup [type=CF_MATHJAX]

, 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

Unable to parse markup [type=CF_MATHJAX]

. Core result discovered by Sprague and Grundy is that

Unable to parse markup [type=CF_MATHJAX]

where

Unable to parse markup [type=CF_MATHJAX]

( minimum excluded ) is the smallest non-negative integer that does not belong to $$$S$$$.

Let's prove that

Unable to parse markup [type=CF_MATHJAX]

, where

Unable to parse markup [type=CF_MATHJAX]

is, indeed, a losing game.

If the first player moves from

Unable to parse markup [type=CF_MATHJAX]

to $$$N_x$$$ with

Unable to parse markup [type=CF_MATHJAX]

, the second one can move into $$$N_x$$$ in

Unable to parse markup [type=CF_MATHJAX]

, as there is $$$u$$$ such that

Unable to parse markup [type=CF_MATHJAX]

. If the first player moves from

Unable to parse markup [type=CF_MATHJAX]

into

Unable to parse markup [type=CF_MATHJAX]

, we end up with the game

Unable to parse markup [type=CF_MATHJAX]

, where

Unable to parse markup [type=CF_MATHJAX]

, hence the second player may match the sizes of the heaps. In both cases after second player moves, the resulting game looks like

Unable to parse markup [type=CF_MATHJAX]

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

Unable to parse markup [type=CF_MATHJAX]

From the definition it follows that the nimber of

Unable to parse markup [type=CF_MATHJAX]

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

Unable to parse markup [type=CF_MATHJAX]

, that is

Unable to parse markup [type=CF_MATHJAX]

Note that from

Unable to parse markup [type=CF_MATHJAX]

it is possible to move to any

Unable to parse markup [type=CF_MATHJAX]

such that

Unable to parse markup [type=CF_MATHJAX]

, thus from Sprague-Grundy theorem it follows that

Unable to parse markup [type=CF_MATHJAX]

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

Proof. We have to prove that

Unable to parse markup [type=CF_MATHJAX]

is a losing game. After the first move we will have three heaps $$$N_x$$$,

Unable to parse markup [type=CF_MATHJAX]

and

Unable to parse markup [type=CF_MATHJAX]

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

Unable to parse markup [type=CF_MATHJAX]

for

Unable to parse markup [type=CF_MATHJAX]

and

Unable to parse markup [type=CF_MATHJAX]

. 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

Unable to parse markup [type=CF_MATHJAX]

for

Unable to parse markup [type=CF_MATHJAX]

and

Unable to parse markup [type=CF_MATHJAX]

. Again, taking the smallest possible value of

Unable to parse markup [type=CF_MATHJAX]

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

Unable to parse markup [type=CF_MATHJAX]

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
Unable to parse markup [type=CF_MATHJAX]
and there is a stone on $$$(x, y)$$$;
pick a pair of non-negative integers $$$x'$$$ and $$$y'$$$ such that
Unable to parse markup [type=CF_MATHJAX]
and
Unable to parse markup [type=CF_MATHJAX]
;
remove a stone from the point $$$(x, y)$$$ and place one stone in each of points
Unable to parse markup [type=CF_MATHJAX]
,
Unable to parse markup [type=CF_MATHJAX]
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

Unable to parse markup [type=CF_MATHJAX]

, 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

Unable to parse markup [type=CF_MATHJAX]

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
Unable to parse markup [type=CF_MATHJAX]
and the coin in $$$(x, y)$$$ is heads up;
pick a pair
Unable to parse markup [type=CF_MATHJAX]
and
Unable to parse markup [type=CF_MATHJAX]
;
flip all the coins in the rectangle formed by $$$(x', y')$$$,
Unable to parse markup [type=CF_MATHJAX]
,
Unable to parse markup [type=CF_MATHJAX]
and $$$(x, y)$$$.

The game continues on until all cells with

Unable to parse markup [type=CF_MATHJAX]

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

Unable to parse markup [type=CF_MATHJAX]

and

Unable to parse markup [type=CF_MATHJAX]

be impartial games. The product of games

Unable to parse markup [type=CF_MATHJAX]

is defined as

Unable to parse markup [type=CF_MATHJAX]

where

Unable to parse markup [type=CF_MATHJAX]

is defined as

Unable to parse markup [type=CF_MATHJAX]

where

Unable to parse markup [type=CF_MATHJAX]

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

Unable to parse markup [type=CF_MATHJAX]

, compute

Unable to parse markup [type=CF_MATHJAX]

for each $$$i$$$, where

Unable to parse markup [type=CF_MATHJAX]

and

Unable to parse markup [type=CF_MATHJAX]

Any non-negative integer $$$n$$$ can be decomposed as

Unable to parse markup [type=CF_MATHJAX]

, where

Unable to parse markup [type=CF_MATHJAX]

are integers. Let

Unable to parse markup [type=CF_MATHJAX]

, where

Unable to parse markup [type=CF_MATHJAX]

, then using the distributivity of $$$\oplus$$$ and $$$\cdot$$$, we may rewrite the nimber product $$$nm$$$ as

Unable to parse markup [type=CF_MATHJAX]

In other words, knowing how to compute the nim product

Unable to parse markup [type=CF_MATHJAX]

would allow us to compute the nim product for arbitrary $$$n$$$ and $$$m$$$.

Claim 10. Let

Unable to parse markup [type=CF_MATHJAX]

and

Unable to parse markup [type=CF_MATHJAX]

, where

Unable to parse markup [type=CF_MATHJAX]

. Then

Unable to parse markup [type=CF_MATHJAX]

and

Unable to parse markup [type=CF_MATHJAX]

Now, let

Unable to parse markup [type=CF_MATHJAX]

and

Unable to parse markup [type=CF_MATHJAX]

, where

Unable to parse markup [type=CF_MATHJAX]

and

Unable to parse markup [type=CF_MATHJAX]

then

Unable to parse markup [type=CF_MATHJAX]

This reduction allows to compute

Unable to parse markup [type=CF_MATHJAX]

, where

Unable to parse markup [type=CF_MATHJAX]

and

Unable to parse markup [type=CF_MATHJAX]

, so it will sooner or later reach $$$x=1$$$ or $$$y=1$$$.

When

Unable to parse markup [type=CF_MATHJAX]

, it also holds that

Unable to parse markup [type=CF_MATHJAX]

, so $$$\oplus$$$ and $$$\cdot$$$ define a field on the set of non-negative integers less than

Unable to parse markup [type=CF_MATHJAX]

for any $$$n$$$. It also holds for

Unable to parse markup [type=CF_MATHJAX]

, so if all

Unable to parse markup [type=CF_MATHJAX]

are precomputed, one could find the nim product of any $$$64$$$-bit numbers in

Unable to parse markup [type=CF_MATHJAX]

operations:

Code

#define int uint64_t

int mul(int a, int b);

int P[64][64];
 

// Compute the nim product of 2^a and 2^b
int mul2(int a, int b) {
    if(a == 0 || b == 0) {
        return 1LL << (a + b);
    } else if(P[a][b]) {
        return P[a][b];
    } else {
        int n = 1;
        while(2 * n <= max(a, b)) {
            n *= 2;
        }
        if (a >= n && b >= n) {
            return P[a][b] = mul((3ULL << (n - 1)), mul2(a - n, b - n));
        } else if (a >= n) {
            return P[a][b] = mul2(a - n, b) << n;
        } else {
            return P[a][b] = mul2(a, b - n) << n;
        }
    }
}

// Compute the nim product of a and b
int mul(int a, int b) {
    int ans = 0;
    int A[64], B[64];
    int sza = 0, szb = 0;
    for(int i = 0; i < 64; i++) {
        if((a >> i) & 1) {
            A[sza++] = i;
        }
        if((b >> i) & 1) {
            B[szb++] = i;
        }
    }
    for(int i = 0; i < sza; i++) {
        for(int j = 0; j < szb; j++) {
            ans ^= mul2(A[i], B[j]);
        }
    }
    return ans;
}

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

Unable to parse markup [type=CF_MATHJAX]

because

Unable to parse markup [type=CF_MATHJAX]

and

Unable to parse markup [type=CF_MATHJAX]

. Here's my implementation on Library Judge.

Problem examples

Left to the reader as an exercise.

1310F - Плохая криптография. Given $$$a_1, \dots, a_n$$$ and

Unable to parse markup [type=CF_MATHJAX]

, solve

Unable to parse markup [type=CF_MATHJAX]

for each $$$i$$$, where

Unable to parse markup [type=CF_MATHJAX]

and $$$n \leq 100$$$.

1338C - Прекрасные тройки. It is related to nimber product somehow, right?

Rev.	By	When	Δ	Comment
en12	adamant	2022-06-15 00:07:08	21
en11	adamant	2022-06-15 00:05:53	205
en10	adamant	2022-06-14 21:41:25	20	Tiny change: 'on/92233) on Library J' -> 'on/92233) that takes 1.4s on the Library J'
en9	adamant	2022-06-14 18:08:20	26
en8	adamant	2022-06-14 17:59:34	91
en7	adamant	2022-06-12 23:14:24	351
en6	adamant	2022-06-12 23:08:29	197	Tiny change: 's are considered on top ' -> 's are constructed on top '
en5	adamant	2022-06-12 22:34:21	129
en4	adamant	2022-06-12 20:24:58	425	Tiny change: '2} 2^{2^k}} = 2^{2^k' -> '2} 2^{2^k} = 2^{2^k'
en3	adamant	2022-06-12 18:38:24	4
en2	adamant	2022-06-12 18:37:25	5	Tiny change: 'lus b$ is an xor of $a' -> 'lus b$ is the xor of $a'
en1	adamant	2022-06-12 17:08:39	16857	Initial revision (published)

Prerequisites

Basic definitions

Game sum

Sprague-Grundy theorem

Nimber sum

Algebraic rationale

Nimber product

Game product

Computation

Problem examples

History