Nim With a Pass: a computational analysis​
​by Arul Kolla
The game of Nim With a Pass is the same as the traditional game of Nim, but with a single pass move that can be used by either player up to the final move. Unlike Nim, whose solution is classical, Nim With a Pass has a much more complex and chaotic structure. We first look at these structures, and then prove an upper and lower bound. We then analyze the multiway graphs for Nim and Nim With a Pass.

Introduction

The game of Nim is played on several heaps of objects (typically, stones). On their turn, a player can remove any number of stones from a single pile. The player who is unable to move loses (equivalently, the player who takes the last stone wins). The game of Nim is well studied, and a general solution is known to exist. However, its variant Nim With a Pass, has yet to be resolved. Nim With a Pass is the same game as Nim, played with the option of a single pass by either of the players, which may be made at any time up to the penultimate move. It may not be made at the end of the game. Once a player has passed, the game is as in ordinary Nim. The game ends when all heaps are empty.
​
The key challenge of Nim With a Pass is the fact that one can’t pass when all piles are empty. Otherwise, the problem is easy, since the pass is equivalent to a pile with 1 stone. This change causes a completely different game to emerge, one with apparent randomness and a highly complex structure.

Definitions and the Sprague-Grundy Theorem

First, let’s roughly define an impartial combinatorial game as a finite game in which both players have the same moves available at all times. The outcome of the game is thus based on which player starts. A game is said to be in  if the first player wins, and in  otherwise. Two games
G
and
H
are equal if, for every game
X
, the outcome of
G+X
(that is, the game made by playing
G
and
X
, and the person who is unable to move on either game loses) equals the outcome of
H+X
.​
​​
​The Sprague-Grundy Theorem states that every impartial game is equal to a Nim pile with a single heap. Thus, we can come up with a single Grundy value
g(G)
for each game
G
, equivalent to the number of stones in its equal Nim heap. In particular, the Sprague-Grundy Theorem tells us that the value
g(G)
can be computed as
mex(
G
1
,
G
2
,…,
G
n
)
, where
G
1
,
G
2
,…,
G
n
are the Grundy values of the possible moves from
G
, and the function “
mex
” is the minimal excluded positive integer from the list.

Setup and Visualizations

Implement the
mex
function:
In[]:=
Mex[l_]:=If[{}===l,0,Complement[Range[0,Length[l]+1],l]//First]
For now, we will only deal with finding the Grundy value of the two-pile game. This allows us to solve the three pile game by another theorem in combinatorial game theory: if
g(G)0
, then the second player wins. Otherwise, the first player wins.
Implement the two-pile game, with the knowledge that the Grundy value of two piles in Nim is their bitwise XOR:
In[]:=
NimP[a_,b_]:=​​NimP[a,b]=​​If[a==0&&b==0,0,​​Mex[​​Flatten[{​​BitXor[a,b],​​Table[NimP[i,b],{i,0,a-1}],​​Table[NimP[a,j],{j,0,b-1}]​​}]]]
Make shorthands for tables of Grundy values for Nim:
In[]:=
NimTable[n_Integer]:=Table[BitXor[i,j],{i,0,n},{j,0,n}]
Make shorthands for tables of Grundy values for Nim With a Pass:
In[]:=
NimPTable[n_Integer]:=Table[NimP[i,j],{i,0,n},{j,0,n}]
Output the table of Grundy values for small two-pile games:
Grid[NimPTable[16]]
Out[]=
0
2
1
4
3
6
5
8
7
10
9
12
11
14
13
16
15
2
1
0
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1
0
2
5
7
3
8
4
6
12
11
10
9
16
15
14
13
4
3
5
1
0
2
7
6
9
8
12
13
10
11
16
17
14
3
4
7
0
1
8
9
2
5
6
13
14
15
10
11
12
17
6
5
3
2
8
1
0
9
4
7
14
15
13
12
10
11
18
5
6
8
7
9
0
1
3
2
4
15
16
14
17
12
10
11
8
7
4
6
2
9
3
1
0
5
16
17
18
15
19
13
10
7
8
6
9
5
4
2
0
1
3
17
18
16
19
20
21
12
10
9
12
8
6
7
4
5
3
1
0
19
2
18
17
20
21
9
10
11
12
13
14
15
16
17
0
1
2
3
4
5
6
7
12
11
10
13
14
15
16
17
18
19
2
1
0
3
4
5
6
11
12
9
10
15
13
14
18
16
2
3
0
1
5
6
4
8
14
13
16
11
10
12
17
15
19
18
4
3
5
1
0
7
2
13
14
15
16
11
10
12
19
20
17
5
4
6
0
1
2
3
16
15
14
17
12
11
10
13
21
20
6
5
4
7
2
1
0
15
16
13
14
17
18
11
10
12
21
7
6
8
2
3
0
1
Just from this table, we can already see a structure starting to emerge: the small and large numbers are sort of "clumped" together; the small numbers in the upper left and bottom right corners, and the larger numbers in the upper right and bottom left corners.
Visualize the structure of Grundy values for Nim:
In[]:=
ArrayPlot[NimTable[1023],ColorFunctionHue]
In[]:=
Visualize the structure of Grundy values for Nim With a Pass:
In[]:=
ArrayPlot[NimPTable[900],ColorFunctionHue]
In[]:=

Why 1023 and 900?

Traditional Nim is known to just be the table of
a⊕b
, so the values are heavily dependent on powers of 2. Hence the table goes up to
10
2
-1
.
​
​The Nim With a Pass code is rather slow, mainly because computing the
mex
and the recursive calls takes a long time. Therefore, I was only able to visualize it up to 900. However, it can already be seen that no general pattern appears to be taking place.
As we can see, the jarring change from Nim to Nim With a Pass results in a huge amount of complexity. The "organic" ribbons of Nim With a Pass have no clear pattern, unlike the evidently recursive nature of ordinary Nim.

A Deeper Look at the Grundy Values of Nim With a Pass

Plots and Conjectures

Plot the table for Nim in three dimensions:
With[{n=127},ArrayPlot3D[Table[If[BitXor[i,j]==k,1,0],{i,0,n},{j,0,n},{k,0,2*n}]]]
Out[]=
This has a very recursive nature. In fact, it is almost identical to the Sierpinski tetrahedron.
Display the Sierpinski mesh:
SierpinskiMesh[6,3]
Out[]=
On the other hand, Nim With a Pass doesn't have this sort of recursive structure.
Plot the table for Nim With a Pass in three dimensions:
The pictures above show three different visualizations of the same plot.
These three-dimensional plots, again, show the complicated structure of Nim With a Pass. While there does appear to be some regularity, and various views of the second plot display some patterns, the system as a whole is rather chaotic. In the absence of regularity, can we establish any rough patterns?
Find all Nim With A Pass games that have a certain Grundy value:
When we plot these values for a fixed Grundy value, it appears that the values are bounded in some range.
Plot the games of Nim With a Pass that have Grundy value 17 (chosen arbitrarily):
In fact, the above plots appears to show that along any row of the Grundy table for Nim With a Pass, the Grundy values are arithmetic periodic.

Full Proof of Nim With a Pass Bounds and Additive Periodicity

The picture below is a visualization of this proof. The three colors represent the three cases mentioned above.
Now we can finally prove the initial statement.

Similar Games

Subtraction Games

Find the Grundy values for the subtraction game, without a pass:
Find the Grundy values for the subtraction game, with a pass:
Set up tables for the subtraction game with and without a pass:
Now, we can visualize the subtraction game with a pass.
Plot the Grundy values of the 127-subtraction game with a pass (number chosen arbitrarily), and see how the pattern is slightly periodic:
We can see the periodicity better if we pick a smaller limit.
Plot the Grundy values of the 31-subtraction game with a pass (number chosen arbitrarily), and see how the pattern is very periodic:
As one can see, the periodicity is evident. In addition, as one moves along the row and column of the periods, we can see more and more blue spots appearing, which we'll call "anomalies". These anomalies represent higher and higher Grundy values.

Wythoff

Wythoff’s game (or just Wythoff) is the same as Nim, but is typically only played on two piles. On their turn, a player may remove some stones from either pile, or remove the same number of stones from both piles. The game of Wythoff is well-studied (although the calculation of Grundy values is not solved), but it has a complex nature not too dissimilar from Nim With a Pass.
Find the Grundy values for Wythoff:
Plot the Grundy values of Wythoff:
It may be possible to apply the lessons learned from analyzing Wythoff to Nim With a Pass. Indeed, the proofs given about additive periodicity above are based off of the proofs given for Wythoff. More progress on the problem can likely be made in this way.

Multiway Graphs

Moving away from combinatorial game theory a little bit, let’s look at the multiway graphs of Nim and Nim With A Pass. A multiway graph is a graph representing the possible states in a game of Nim, and an edge from one state to another if it is possible to move from the first state to the second.
Find the moves from a given position for Nim:
Find the moves from a given position for Nim With a Pass:
Display the graph for two-pile games of size at most 2 for Nim:
Thus, in this graph, the game is equivalent to (i.e. you can play the game by) placing a counter on any vertex, and on each turn a player can move along an edge. The player who is unable to move loses.
Display the graph for two-pile games of size at most 2 for Nim With a Pass:
As you can see, the multiway graph for Nim With a Pass is the same as that of Nim, but with an extra copy and an edge from each vertex of the copy to the corresponding vertex in the original graph. However, one of these edges is missing: the one from the “all zero” position, since you can’t pass when all piles are empty.
In three dimensions, this is easier to visualize, since we can "extend" the graph into the third dimension.
Plot the multiway graph of two-pile Nim with SpringElectricalEmbedding:
Plot the multiway graph of two-pile Nim With a Pass with SpringElectricalEmbedding:
Arrange the graph for Nim on the coordinate plane, and label the vertices:
Note that the edges of the graph overlap: each vertex is actually connected to all vertices below it and to its right.
Arrange the graph for Nim With a Pass on the coordinate plane:
The exception of the pass from the zero position is what distinguishes Nim with an extra pile with 1 stone from Nim With a Pass. We can see this in the multiway graph.
As we can see, the only difference between the two graphs is the presence of the edge between the two zero positions. Therefore, despite it looking like at insignificant difference, this single edge removal in Nim With a Pass causes its chaotic, almost unpredictable behavior.
While we can also plot the multiway graph for Nim with 3 piles, it is rather complicated.
Display the graphs for three-pile games of size at most 2 for Nim:
It may be interesting to analyze if there is a nice structure for these graphs, as well as the "extend and connect" operation on general graphs.

Future Work

References

◼
  • Nivasch, Gabriel. “More on the Sprague–Grundy Function for Wythoff's Game.” Games of No Chance 3, 2009, pp. 377–410., doi:10.1017/cbo9780511807251.019.
    • ◼
  • Siegel, Aaron N. Combinatorial Game Theory. American Mathematical Society, 2013.