So, I ended up making a talk on Sprague-Grundy as part of a club at my school, and thought that the denizens of codeforces would appreciate it. As follows is roughly what was on the handout, which goes over Sprague-Grundy along with the application of its theory to Nim. As this is my first blog post on Codeforces, please do let me know if there are any mistakes in formatting.

I hope you find this interesting, as writing and explaining this helped me understand how to apply it to problems. This handout was written as more math-oriented, so it may be a bit heavy. The exercises are left unsolved, as they are intended to be worked through by the reader.

If you just want to get to what the Sprague-Grundy is defined as, search for "The Sprague-Grundy function of a game" after reading how games were defined.

Way too much theory

A necessary definition of games

For this talk, a game will be a two-player sequential game of perfect information, where a player who cannot move loses. Any position in the game can be represented as the set of positions to which a player can move. An empty set is thus a losing position, and a losing game is a game wherein regardless of what the current player does, they will lose. A winning game is a game that is not a losing game.

A casual definition of a Nim heap

A heap in nim is a game where any positive number of stones can be removed from the heap on any turn.

Formal definition of a Nim heap

We want to represent a Nim heap as a game by the definition above. Let us define Nim_k as the game representation. Since we cannot make a move on an empty heap, Nim₀ = {}.

Note that

Examine why the following recursive definition meets the definitions defined above:

While this definition isn't apparently useful, it shows some of how the structure of the set notation of games can get really large for relatively simple games.

Definition of XOR

Some more definitions need to be examined before we can get to the guts of this theorem. The exclusive or, xor, takes two nonnegative integers a and b and results in the nonnegative integer n where the k-th bit in the binary representation of n is 1 if and only if it is 1 in exactly one of a, b. An important thing to notice is that , where & is defined similar to , except the bit is 1 if and only if both bits are 1. We can see this by noting that shifting left in binary is equivalent to multiplying by 2, and in this way we have performed the traditional addition algorithm, as the a&b represents the locations where carries occur, and represents where carries do not need to occur.

The Mex function

Let us define the Mex, minimum excludant, function as , where N is the natural numbers (nonnegative integers). The definition is as follows: Equivalently stated, M(S) is the least nonnegative integer x such that x is not in S.

Properties of the mex function, with XOR

Let be the scalar XOR operator, which takes a set and XORs every element of it with an integer to obtain another set. Additionally, let . Then, let C be .

Lemma: .

Proof: We shall prove this by first proving that cannot be in C, then we shall prove that every nonnegative integer less than is in C.

Assume for contradiction that is in C, then or . Assume WLOG, that it is at least in , then for some . Thus, , which is a contradiction. Therefore, is not in C.

Now, we must prove that all nonnegative integers less than are in C. Let . Let . x cannot be zero as . Consider the largest bit that is set in x. Give it value k. Assume for contradiction that this bit is set in z. Then, , as the most significant bit that differs is larger in z. This is a contradiction. Thus, this bit must be set in either M(A) or M(B). Without loss of generality, assume k is set in M(A). Then, since k is x's most significant bit, 2k > x. Hence, , so . Let . Then, , as desired.

Therefore, since every nonnegative integer less than is in C, and is not in C, is thus the mex of C.

The Sprague-Grundy function of a game

Definition

Now, consider a state S in the set notation of a game. Then, define the Sprague-Grundy function as follows:

Sprague-Grundy of Nim

That can be proven through strong induction. Since Nim₀ is the empty game, . Now, if we assume that for all j < k, then This completes the inductive step, so

Losing states

Let be the maximum number of moves a game S can take. I shall prove inductively on that a game S is losing if and only if . Note that if , then there are no moves, so we have a lost game and , so the base case is finished.

The inductive hypothesis assumes that for all , it is true. Consider a game S with . If , then, for all possible next states , , from the definition of the Sprague-Grundy function. Thus, since , all turns in this game lead to a winning games for the next player by the inductive hypothesis. Thus, S is a losing game.

Now, if , then there is a game s' in S such that is 0, and since , s' is a losing game, and thus S is a winning game.

Combining games

It is necessary to consider how simultaneous play of multiple games work to apply this to NIM, and other NIM-like games.

Combining two games

Consider two games, A and B. Let C(A, B) be the combination of these two games, where a move consists of a move in either game. since no moves can be made from either game. We can recursively define the game C(A, B): Theorem: . Proof omitted for brevity, but it can be proven inductively on the value of from the property of the MEX function with respect to .

Combining more than two games

Let C(a₁, a₂, ... , a_n) denote the combination of games a₁, a₂, ... , a_n. Then C(a₁, ... a_n) = C(C(... C(C(a₁, a₂), a₃), ... ), a_n). The Sprague-Grundy of the combination of these games is thus

Back to Nim

Typically, a game of Nim is defined as a multiset of heaps of a given size. Combining previous statements, a game of Nim is losing if and only if the XOR of its stack sizes is 0.

Some bounds on

It may become the case that we want to know the maximum value of the Sprague-Grundy function for the case when studying a game. There are a few easy bounds. We shall mention two. is obvious from the definition of Mex. In addition, , as from any state with Sprague-Grundy value of x, there exists a sequence of reachable games Sprague-Grundy values x, x - 1, x - 2, ..., 0, thus , as desired.

Let's solve some problems

Now that we have a working definition of Sprague-Grundy, let's solve some games with it!

Simple Exercises

The simplest subtraction game

Consider the subtraction game, where on any given turn, a player takes away a positive integer that is at most k stones from a single heap. Calculate, in closed form, the Sprague-Grundy function of a heap of n stones in this game.

Slightly more complicated

Consider a game where a player is able to replace any heap of size k with up to k - 1 heaps of any positive size strictly less than k. Prove that in this game, the Sprague-Grundy function of a heap of size k is 0 if k = 1, and 2^k - 2 otherwise

One more for the road

Consider a game on heaps, where a turn consists of taking a heap of size n, and a positive integer d that divides n, where 1 ≤ d < n, and splits it into n / d heaps of size d.

Analyze the Sprague-Grundy function of this game. (Try doing it with just the odd heap sizes first)

Counting losing positions

Sometimes, it is useful to count the number of losing positions given a bound on the size of a stack. Assume we've already computed the Sprague-Grundy function for all stack sizes that we are allowed.

1 stack

If there is only one stack, then the number of losing positions within the bounds is the number of losing positions.

2 stacks, order matters

If there are two stacks, then the number of positions gets more complicated. From the theorems proved earlier, a combined position is losing if and only if its XOR is 0. Thus, we can just find all pairs of stack sizes where the XOR of their Sprague-Grundys is 0. We can do this by counting how many stacks within the bounds have a Sprague-Grundy value of x for all x, and summing the square of that count across all x will give us the answer.

2 stacks, order does not matter

All stack pairs are double counted except for the pairs of two identical stacks, which are all valid, so the answer in this case is half the sum of the previous case and the number of stacks.

3 stacks

Sum across all possible set of 3 Sprague-Grundy values that XOR to 0. The third can be computed in terms of the first and second. In the instance where the stacks are ordered, principle of inclusion-exclusion can be used to finish counting.

Harder counting (But they need way more stacks!)

Sometimes, one may happen upon a problem asking to count the number of losing positions for a given game with a large number of stacks (10¹²), modulo some odd number o. The number of stacks is too many for a computer to handle by generating all the combinations. For this, we should attempt to calculate the counts of how many games with k stacks have any given Sprague-Grundy function. The number with 1 stack is fairly easy to calculate from the Sprague-Grundy function of all stack sizes. In addition, let F = 2^d be the smallest power of 2 greater than the Sprague-Grundy function of the stacks. It is then the case that the Sprague-Grundy function of any combinations of stacks cannot be at least F, as no bit with value at least F can be set.

Note that a game with k stacks is just a game with k - 1 stacks appended to a 1-stack game. Let be the number of valid lists of k stacks where the XOR of their Sprague-Grundy is x. Then,

.

i, j are bounded within [0, F). This is just XOR-convolution of and , which we will denote as . Since XOR-convolution is associative, we want to actually compute . The number of losing positions is . can thus be calculated in XOR-convolutions by binary exponentiation.

However, a naive implementation of XOR-Convolution takes O(F²) time per convolution. This could be fast enough for some problems, but when the Sprague-Grundy value gets large, this isn't enough.

A simple example of a game where this becomes a problem is a subtraction game where we can subtract between 1 and 1000000 from any stack, and we are given stack sizes between 1 and 12983567378251, and want exactly 98670634123 stacks.

Calculating the Sprague-Grundy is fast because it is periodic, and even calculating the values within can be done relatively quickly O(1000000) due to this periodicity.

However, it is not really fast to perform (2²⁰)² = 2⁴⁰ ≈ 10¹² operations per convolution, which we to perform on the order of tens of times.

We thus need a faster way to perform XOR-convolutions. Note that the space of numbers on which the values operate is equivalent to , where XOR becomes bitwise addition. Thus convolution can be performed with a normal d-dimensional FFT. However, adding the dimensionality is unnecessary, as we can perform the FFT along each dimension in linear time with respect to the size of the signal. Convolving Fourier Transformed values takes linear time with respect to the size of the signal, as it just becomes element-wise multiplication.

The following pseudo-code performs the FFT in O(dF) time. Inverse is, as usual with FFTs, the same, except dividing by 2^d afterward, or by 2 on the inside at every step. This reverse step requires an odd modulus, which is why it was mentioned earlier.

Begin with D[i] being an array of F elements representing
the values of a function to be transformed.
for i = 0..d:
    for j = 0..F:
        if the bit with value 2^i is not set in j:
            D[j],D[j+2^i] = D[j]+D[j+2^i],D[j]-D[j+2^i]

Each convolution then takes O(F) time, and so we only need time to finish it overall. This is much smaller than , and should be enough to solve it for most problems we would come across, if we can calculate the counts of each value of the Sprague-Grundy quickly.

Note that if the totient function of the modulus is easily calculated, the power to which we take the convolution can be reduced modulo the totient function.