This is a follow-up blog to this talk
I realized that the previous post doesn't exactly explain how to actually work out the solutions to the 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.
Recursive Sprague-Grundy# 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.
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.
Array Sprague-GrundySG = 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] = 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.
Inside the Sprague-Grundy# 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:
Game of Cards
One of the techniques mentioned in the previous post can be used for this problem: 717D - Dexterina’s Lab
In addition, there are a few problems on ProjectEuler that these concepts are also applicable to.
Now, for solutions, or outlines of such, to the problems from the previous blog:
The Simplest Subtraction GameSomething 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.
Slightly More ComplicatedThis 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.
One more for the roadThe 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 = 2ko for some odd number o. Notice that dividing Gn into an even number of piles is a winning move, as the XOR is 0.
