### sirknightingfail's blog

By sirknightingfail, history, 5 months ago, ,

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 Nimk as the game representation. Since we cannot make a move on an empty heap, Nim0 = {}.

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 Nim0 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(a1, a2, ... , an) denote the combination of games a1, a2, ... , an. Then C(a1, ... an) = C(C(... C(C(a1, a2), a3), ... ), an). 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 2k - 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 by size, i.e., we are asked to count multisets, not ordered tuples, the 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 (1012), 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 = 2d 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(F2) 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 (220)2 = 240 ≈ 1012 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 2d 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.

•
• +248
•

 » 5 months ago, # |   +22 Is it just me or anyone else is not able to make sense of it ?
•  » » 5 months ago, # ^ |   -23 Sprague and Grundy are turning in their graves, after reading this tutorial.
•  » » 5 months ago, # ^ |   -11 This topic is difficult, become stable violet to understand it
•  » » » 5 months ago, # ^ |   -9 the topic is not difficult, become stable yellow and it will be easy for you
 » 5 months ago, # |   -30 Getting contribution 101 :Step 1 : Be >= yellow.Step 2 : Write a shitty lengthy tutorial which no one will bother to read.Step 3 : Sit back and let the greens upvote it without even reading it.
•  » » 5 months ago, # ^ |   +48 I don't think the tutorial was particularly shitty. It definitely is very terse and math-heavy compared to what you normally expect from a Codeforces blog. And I suppose it could have been written in a better way.But at a certain level you can't just expect everything to be spoon-fed to you. You need to work through not-so-simple texts to learn. I think the blog is valuable as it goes to more theory than just a typical "Here is how to use Spargue-Grundy to solve Nim-like problems. Magic!".
•  » » » 5 months ago, # ^ |   -47 You think it is an easy read beacuse you are already well versed in the topic.The blog seems more like he's telling himself about the topic rather than explaining it to someone else.
•  » » » » 5 months ago, # ^ |   +23 No, I am not well-versed in the topic. Please do not make assumptions.Also I am not saying (and have never said) that it is an easy read.However, a mathematical background and being used to reading texts like this is immensely helpful for understanding this blog. And frankly, I think you ought to have some mathematical maturity to understand topics like this.Also, consider the context. He says this was given as a handout during a talk. He probably took a bit more time, gave more examples etc. when explaining this in person.
•  » » » » » 5 months ago, # ^ |   -7 "...mathematical maturity" are you serious? I think this topic is affordable to anyone. I can understand it, and I'm not a mathematician.
•  » » » » » » 5 months ago, # ^ |   -25 Seems like I offended a lot of yellows :P
•  » » » » » » » 5 months ago, # ^ |   +5 You offend me by going here to complain and not to solve any problems, for example.
•  » » » » » » 5 months ago, # ^ |   +26 Eh, you don't need to be a mathematician. But by "mathematical maturity" I mean you are able to parse mathematical text like this without huge confusion, understand what a definition is, understand what a proof is etc.You may consider these to be trivial but they are not. A lot of people get very confused and have a lot of difficulty trying to read texts that don't spoon-feed everything.
 » 5 months ago, # |   +6 A winning game is a game that is not a losing game.Wow.
 » 5 months ago, # |   +18 When I wrote this, it was intended as an introduction to the theory of Sprague-Grundy, rather than the application of it, so I feel that this is not really a tutorial. I am currently working on another blog post that should have more code, as well as examples of actually using it, that can act as a stronger introduction into usage of Sprague-Grundy.The version posted here is an edited version of an accompaniment to a talk to my school's Recreational Math Club, where members research into a topic they are not strongly familiar with, and then deliver a presentation or talk on it to other members. During the talk, we ran out of time before I could get to the section on counting losing positions.A few questions asked during the talk were as follows: Can you give a more concrete example of how the combined game looks? An example is as follows. Consider two games of the form {{}},{{}}. Their combination is as follows. C({{}}, {{}}) = {C({}, {{}}), C({{}}, {})} = {{C({}, {})}, {C({}, {})}} = {{{}}, {{}}} = {{{}}} Can we have an example of Mex? M({0, 1, 2, 4}) = 3M({1, 2, 7}) = 0M({0, 2, 3, 4, 5}) = 1 Can we have an example of XOR? 1111111_2 (127) 1001011_2 (75) _________ 0110100_2 (52)  Can we call the set as Mabumba? Yes. Please let me know if you think any wording is unclear, or would like clarification on any aspects of it.
 » 5 months ago, # |   -21 I am familiar with Sprague-Grundy Theorem and this blog post really helped me with some extra stuff, I don't know why people are offending it. It could be improved by providing extra examples and problems to solve, but overall it's good, thank you Sir for your efforts.