Subtraction Game Solver

Subtraction Game Solver

How do we compute the Sprague-Grundy values for a subtraction game?

The simple answer is we use the mex function of the subtraction set, S. That is, mex{S} is the smallest ordinal which is not an element of S. parity. We begin with the fact that G(0) = 0 and then build our way up to an arbitrary n.

Compute SG-values:

Specify the subtraction set (see examples below):

n value to compute:			Make Table



Sprague-Grundy Value

Examples of Subtraction Sets:

Note: S can be finite or it can be described by a function. However, if using a function, make sure that S[0] is initialized.

To specify the (finite) subtraction set S = {1, 2, 3} use the following:

S = [1,2,3]

To specify the (infinite) subtraction set S = {1, 2, 4, 8, ...} use the following:

var j=0;
while(Math.pow(2,j)<=n) {
S[j] = Math.pow(2,j);
j++;
}

To specify the (infinite) subtraction set S = {1, 4, 9, 16, ...} use the following:

var j=1;
while(j*j<=n) {
S[j-1] = j*j;
j++;
}