This is a follow-up blog to this talk Please let me know if there are any errors. I might not be able to reply rapidly as it is finals week for me.\
The previous post doesn't exactly explain how to actually work out the solutions to Sprague-Grundy problems, or how to code them. Within this follow-up blog, I shall attempt to explain some of my thought process on working through Sprague-Grundy and similar problems, as well as including some code.
First, some pseudo-code of calculating the Sprague-Grundy, and how to find the MEX.
# g is defined as a game (set of games), MAX is the maximum possible Sprague-Grundy value. define SG(g): # Make a set of sprague-grundy values seen = new boolean[MAX+1] for x in g: # It is important to also check if SG(x) fits inside of the bounds of the array, # And to ignore it if it does not. seen[SG(x)]=true curr = 0 while seen[curr]: curr += 1 return curr
However, this implementation is inefficient, as it's not memoized, and we might recompute Sprague-Grundy of certain games quite a lot. Usually, if the game is just in terms of stack size, we can just go in increasing order to evaluate, since each move reduces the stack size, and we would have stored the values for smaller stacks into an array. This is a fairly simple example of dynamic programming.
Consider a game where we're given a set S of numbers by which we can reduce the size of a pile. The following outlines how to use an array to calculate the Sprague-Grundy of a single pile.
SG = new int[N+1] # In this instance of this game, since the stack size always decreases, # 0 cannot have any moves, and is thus 0 Sprague-Grundy. SG = 0 for g in 1..N: # the number of moves, one of the bounds on the SG, cannot exceed the stack size, as it must decrease. seen = new boolean[g] for x in S: if g >= x: seen[SG[g-x]] = true curr = 0 while seen[curr]: curr += 1 SG[g] = curr
Now, since we've computed the Sprague-Grundy for any given pile, we can determine who wins given a list of piles in the starting position in linear time. The S-Nim problem on kattis is basically these.
Sometimes, a turn on a game results in a combination of games of the same type. This is usually a strong indication for the usage of Sprague-Grundy. As an example, let us consider the Cuboid Slicing Game.
Each move can result in up to 8 different games of the same type. We consider any 0-volume cuboid as a losing position, as no further moves can be made upon it.
However, calculating the set of all possible next games might seem intimidating, but we can compute the Sprague-Grundy of game combinations using the Sprague-Grundy of the original games!
Let us first consider a pseudo-code of the recursion.
# x,y,z are the dimensions of the cuboid in this case. def SG(x,y,z): # The upper bound can be determined through experimentation, for this one, 1000 was more than sufficient seen = new boolean[<sufficiently large number>] for a in 0..x for b in 0..y for c in 0..z # the sprague-grundy of cutting the 0-indexed cell (a,b,c) is as follows # There are 8 games that result, some of which are over. seen[ SG(a,b,c) ^ SG(a,b, z-1-c) ^ SG(a,y-1-b,c) ^ SG(a,y-1-b,z-1-c) ^ SG(x-1-a,b,c) ^ SG(x-1-a,b, z-1-c)^ SG(x-1-a,y-1-b,c) ^ SG(x-1-a,y-1-b,z-1-c)] = True mex = 0 while seen[mex]: mex += 1 return mex
Converting this recursive definition to a solution that runs fast enough is left as an exercise. Additionally, some constant-factor optimizations may be needed.
Some further problems I could find are as follows:
One of the techniques mentioned in the previous post can be used for this problem: 717D - Dexterina’s Lab
In addition, there are quite a few problems on ProjectEuler that these concepts are also applicable to.
Now, for outlines of solutions to the problems from the previous blog:
Something to quickly work through with this sort of game, is to try to calculate the function for some small values, and look for a pattern. Say someone brute forced the SG function for k = 4, the first 20 values look like:
0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4
There's a really strong pattern here! If Pn is defined as a pile of size n in this game, . This can be proven by strong induction.
This game is harder to wrap one's head around, but since we're given the Sprague-Grundy function, we just need to prove the function holds. What we need to prove is that every number x < 2k - 2 can be written as a xor of j ≤ k - 1 different stacks of size at most k - 1. This can be done by noticing that x can be written as a binary number with at most k - 2 ones, and we can then construct the stacks from the based on which ones are present in the binary representation. Additionally, you should prove that no combination of smaller games can XOR to 2k - 2, which can be seen from the number of digits present in the binary representation.
The reason I recommended to first deal with the odd version of the game is that odd games can only produce odd games.
Note that since dividing an odd pile into an odd number of piles creates an odd number of equivalent games, we take the repeated XOR an odd number of times, so the odd case is equivalent to allowing one to take a pile, and decrease its size to any proper divisor of the pile.
Notice then, that every move in that game decreases the count of prime factors of the size by at least one, and at most, reduces the number of factors to 0.
The game on any odd n is then just equivalent to a Nim heap with as many stones as there are prime factors in n.
As an example, , .
Now, consider any even number n, then n = o2k for some odd number o. Notice that dividing Gn into an even number of piles is a winning move, as the XOR is 0. Now, consider any other move, which must divide n into b piles of size 2ko / b, for some b that divides o. This is equivalent to turning the pile of size n into a single pile of size 2ko / b. Thus, we can either move the game to a losing position (SG of 0), or reduce the number of odd prime factors of n. This analysis leads us to the idea that the Sprague-Grundy of a pile with an even number of stones is 1 more than the number of odd prime factors.
Since someone was asking for the proof of the Sprague-Grundy Theorem, since it was omitted for brevity in the previous post, here is one.
We prove inductively on the maximum total number of moves in a game. This is obviously true for a game with no moves remaining, as , and . Let MT(X) represent the maximum number of turns X can take. Note that MT(C(A, B)) = MT(A) + MT(B). Now, if we assume for induction that the theorem is true for all A, B such that together MT(A) + MT(B) < n.
Then, if MT(A) + MT(B) = n, note that Since C(A, B) has at most n turns, MT(C(a, B)) < n, and similar for MT(C(A, b)). Therefore, Hence,
If we let , then . Also, the above becomes.
Thus by the property of the MEX function that was proved,
This concludes the inductive step, and hence the theoerem is true for all finite games.