# Message Boards

Answer
(Unmark)

GROUPS:

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 H X G+X G X 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) G g(G) mex( G 1 G 2 G n G 1 G 2 G n G mex
Setup and Visualizations Implement the mex 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 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: In[]:= Grid[NimPTable[16]] Out[]=
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],ColorFunctionHue] In[]:= Visualize the structure of Grundy values for Nim With a Pass: In[]:= ArrayPlot[NimPTable[900],ColorFunctionHue] In[]:=
Why 1023 and 900? Traditional Nim is known to just be the table of a⊕b 10 2 The Nim With a Pass code is rather slow, mainly because computing the mex 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: In[]:= 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: In[]:= 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: In[]:= Row[Table[With[{n=127},Table[If[NimP[i,j]==k,1,0],{i,0,n},{j,0,n},{k,0,2*n}]//ArrayPlot3D],{l,1,3}]] Out[]= 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? Draw lines with slopes 1, 1 2 1 3 1 7 In[]:= Show[ArrayPlot[NimPTable[900],ColorFunctionHue],Plot[Table[-x*1/t+900,{t,1,7,1}],{x,0,900},PlotStyleWhite]] Out[]= It does appear that, in general, the lines of slopes 1 n Find all Nim With A Pass games that have a certain Grundy value: In[]:= NimPEqList[n_Integer,b_Integer]:=Flatten[Table[If[NimP[i,j]==b,{i,j},Nothing],{i,0,n},{j,0,n}],1] 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[]:= ListPlot[NimPEqList[100,17]] Out[]= Conjecture: The Grundy value for Nim With A Pass on two piles a b [a-b-1,a+b+1] In[]:= Manipulate[Show[ListPlot[NimPEqList[100,n]],Plot[{x+n+1,x-n-1},{x,0,100}]],{n,1,16,1},SaveDefinitionsTrue] Out[]=
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 Define ℊ (a,b) P a b Claim. ℊ (a,b) P Proof. The statement is true for ab0 a,b (a,b) P ( ′ a ′ b P a+b+1 a⊕b≤a+b ⊕ ⊕ + (a,b) P a+b+1 mex Claim. ℊ (a,b) P Proof. Suppose otherwise; fix b a ′ a ′ b (a,b) P ′ a ( ′ a P ′ a a First, suppose ℊ ( ′ a P k ′ a ′ b ( ′ a ′ b P ′ b b ( ′ a P ′ a ( ′ a ′ a mex k k+b+1 k+b+1≥a⟹k≥a-b-1 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. Claim. Nim With A Pass is additively periodic along a single row (that is, a fixed a (a,b)g(a,b)-a+b+1 (a,b) [0,2b+2] ( ′ a ′ a (a, ′ b ′ b a⊕b {f(a,b):b≥0} {x:a-b-1≤x≤a+b+1} ′ ′ \ \ 2b+2 2b+2 ′ ′ f(a,b) a b b
Similar Games
Subtraction Games The subtraction game is a finite version of Nim: on a players’ turn, they can remove up to Find the Grundy values for the subtraction game, without a pass: In[]:= Sub[a_,b_,mx_]:=Sub[a,b,mx]=Mex[Flatten[{Table[Sub[i,b,mx],{i,Max[0,a-mx],a-1}],Table[Sub[a,j,mx],{j,Max[0,b-mx],b-1}]}]] Find the Grundy values for the subtraction game, with a pass: In[]:= SubP[a_,b_,mx_]:=SubP[a,b,mx]=If[a==0&&b==0,0,Mex[Flatten[{Sub[a,b,mx],Table[SubP[i,b,mx],{i,Max[0,a-mx],a-1}],Table[SubP[a,j,mx],{j,Max[0,b-mx],b-1}]}]]] Set up tables for the subtraction game with and without a pass: In[]:= SubTable[n_Integer,mx_]:=Table[Sub[i,j,mx],{i,0,n},{j,0,n}] In[]:= SubPTable[n_Integer,mx_]:=Table[SubP[i,j,mx],{i,0,n},{j,0,n}] 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: In[]:= ArrayPlot[SubPTable[150,127],ColorFunctionHue] Out[]= 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: In[]:= ArrayPlot[SubPTable[155,31],ColorFunctionHue] Out[]= 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: In[]:= Wythoff[a_,b_]:=Wythoff[a,b]=Mex[Flatten[{Table[Wythoff[a-i,b],{i,1,a}],Table[Wythoff[a,b-j],{j,1,b}],Table[Wythoff[a-k,b-k],{k,1,Min[a,b]}]}]] In[]:= WytTable[n_Integer]:=Table[Wythoff[i,j],{i,0,n},{j,0,n}] Plot the Grundy values of Wythoff: In[]:= ArrayPlot[WytTable[200],ColorFunctionHue] Out[]= 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: In[]:= NimMoves[l_]:=Catenate[Table[Thread[MapAt[Range[0,#-1]&,k]@l],{k,Length[l]}]] Find the moves from a given position for Nim With a Pass: In[]:= NimPMoves[l_]:=Catenate[{Append[Last[l]]/@NimMoves[Drop[l,-1]],If[Last[l]>=1&&!MatchQ[Drop[l,-1],{0..}],{Append[Drop[l,-1],Last[l]-1]},Nothing]}] Display the graph for two-pile games of size at most 2 for Nim: In[]:= SetPropert |