Understanding the Game of Nim

Steven Goldman
Sgoldman101@qc.cuny.edu
Math 213 -- Mathematics with Mathematica, Fall 2009 
December 2009

Abstract

My project deals with the impartial game of Nim.  In this project, I will explain how the game is played and also show how a player can win using a winning strategy depending upon the initial conditions of the game.  I will then show a way to represent this winning strategy in Mathematica.

Section 1. Introduction

1.1 Background

Nim is a combinatorial game that is played with two players.  The game starts off with n piles of stones (or jellybeans, if you like).  Each of the n piles can have a different amount of stones.  The rules of the game are as follows: the two players alternate turns.  Each turn, a player must choose one of the piles and take one or more stones from that pile (a player is allowed to take all of the pieces in a pile if he so chooses).  The winner of the game is the person who takes the very last stone.

1.2 Problem Statement

The problem statement I answer is:

Can I use Mathematica to show how to win using a winning strategy based on the initial state of the game?

1.3 Useful Code

In order to get Mathematica  to play the game of Nim for us, I will use code from GamesEngine as well as from nim.nb created by Professors Cowen and Dickau.  First, we need to create a way for Mathematica to represent each pile as a list.  This can be done by making each pile a list of 1's where the length of the list is the number of pieces in the pile.  In order to do this, we will define the rep and nimrep functions.  Nimrep takes as it's input the number of pieces in each pile and outputs the list of 1's:

rep[x_]:=Table[1,{i,x}]
nimrep[x_]:=Table[rep[x[[i]]],{i,Length[x]}]

Next, in order to represent the removing of pieces from a pile, we define the PossibleMoves function.  This works by selecting one of the piles and removing a certain amount of 1's (or pieces) from it:

PossibleMoves[pos_]:=ReplaceList[pos,{X___,{Y___,Z__,W___},U___}->{X,{Y,W},U}]

Finally, we define the function nim, which takes as its input the number of pieces in each pile, and outputs the entire game until the end using the Sprague-Grundy Algorithm.

nim[piles_]:=PlayTheGame[nimrep[piles]]

Some other useful Mathematica commands that I used were Prepend, Append and Grid.

1.4 File Structure

In Section 2, I explain the code that I used to investigate my problem and in Section 3, I discuss my findings and mention topics for future work.

Section 2. Main Work

2.1 Investigating Nim with 1 pile and 2 piles (n=1 and n=2)

It can immediately be seen that when there is only one pile, Player 1 will always win by simply taking all of the stones.  But what about when there are 2 piles?  In this case, as in the case when n=1, it doesn't really matter how many pieces are in the two piles; all that matters is whether or not the two piles have an equal number of pieces.  For example, let's say that the two initial piles are unequal.  All Player 1 has to do in order to win is to take enough pieces from the bigger pile so that the two piles are equal.  Then, when Player 2 goes, no matter how many pieces he takes, he will make the two piles unequal.  Then, in order to win, Player one has to continue to even out the two piles by "mimicking" Player 2's previous move.  Eventually, following this strategy, Player 2 will be left with two equal piles of size 1 each (or {1,1}); he will be forced to take one piece, allowing Player 1 to make the winning move.  Therefore, starting with two unequal piles, Player 1 can always win, while starting with two equal piles, Player two can always win.  The following example demonstrates this with initial piles of size {3,2}:

{3,2}(Overscript[->, I]){2,2}(Overscript[->, II]){2,1}(Overscript[->, I]){1,1}(Overscript[->, II]){1,0}(Overscript[->, I]){0,0}
(* Player I wins! *)

2.2 Expanding to More Piles

Now that we understand how to win with a pile of size two, we can expand this same idea to bigger piles.  In order to generalize this to more piles, we need to deal with binary numbers (numbers in base 2).  If we represent the number of pieces in each pile as a binary number, then in order to win, one again must make certain piles "equal".  However, instead of making all three or more piles equal to each other, all you have to do is make each  binary digit "equal".  In order to do this, when you add up the piles in their binary representations, you want there to be an even number of every power of 2 (note, when adding in binary, we will add Mod 2.  Therefore, when there are an even or "equal" amount of something, we will represent it with a "0", and when there are an odd amount of something, we will represent it with a "1").  We will call a game "balanced" if the number of powers of 2 is even, and "unbalanced" if the number of powers of two are odd.  Then, for a player to win, all he has to do is continuously "balance" the game by removing the necessary pieces.  Therefore, if the game starts off unbalanced, it is the same as if the piles are unequal, and Player 1 can win by balancing the piles; otherwise, Player 2 can win by balancing the piles.  Following this strategy, eventually you will be left with two piles of {1,1}, as before.  
Following is an example that will demonstrate this more clearly, but before that, we must define functions that will transform numbers into a binary representation and then add them up.  The function Binary will take as its input the number of pieces in the piles and output them in binary, while BinaryAdd will add those numbers together in binary (note, we will only deal with a maximum pile size of 10 for this example).  The function data2 takes as its input the number of pieces in each pile and outputs a table of their binary representation, their normal representation, and their binary sum:

Binary[{x___}]:=Map[IntegerDigits[#,2,4]&,{x}]
BinaryAdd[{x___}]:=Mod[Apply[Plus,Binary[{x}]],2]
data2[{x___}]:=Table[Prepend[Part[Append[Binary[{x}],BinaryAdd[{x}]],i],FromDigits[Part[Append[Binary[{x}],BinaryAdd[{x}]],i],2]],{i,1,4}]

Now, for our example, we will use 3 piles of sizes {3,4,5}:

MakeGrid[{x___}]:=Text@Grid[Prepend[data2[{x}],{"Pile Size","(2^3) = 8","(2^2) = 4","(2^1) = 2","(2^0) = 1"}],Background->{None,{Lighter[Red,.9],{White,Lighter[Blue,.8]}}},Dividers->{{Darker[Gray,.5],Darker[Gray,.5],{Lighter[Gray,.5]},Darker[Gray,.5]},{Darker[Gray,.5],Darker[Gray,.5],{False},Darker[Gray,.5],Darker[Gray,.5]}},
Alignment->{Center},
ItemSize->{{7,7,7,7,7}},
Frame->Darker[Gray,.8],
ItemStyle->14,
Spacings->{Automatic,1}];
MakeGrid[{3,4,5}]

The above table shows each pile and its binary representation.  Adding the digits vertically (by their units), we see that their is an even amount of every power of 2 except for  (2^1).  This means that the piles are unbalanced.  In order for Player 1 to win, he must balance the board by removing the necessary pieces; in this case, he must remove the first one (or two pieces) from the pile of size 3, which will change its binary representation to {0,0,0,1}.  Then, when we add all the units together, we will see that the piles are balanced and the sum will be {0,0,0,0}.  (This nim-sum is the same as the Grundy number for this game in that it tells us how we need to move).  In the next move, Player 2 must unbalance the game.  If Player 1 continues to follow the given strategy, he will constantly be pushing the game to {0,0,0,0} until he makes the last move and wins.  
The following is a representation of an entire game (code thanks to Cowen and Dickau).  The functions pile and showpile take as their input the number of piles and the number of pieces in each pile and proceed to output an entire game:

pile[n_Integer?NonNegative,{i_Integer}]:=Table[{RGBColor[1,0,0],Line[{{i,j},{i+4/5,j},{i+4/5,j+1/5},{i,j+1/5},{i,j}}]},{j,0,(n-1)/5,1/5}];
showpiles[L_List]:=With[{len=Length[L]},Show[Graphics[{MapIndexed[pile,Map[Length,L]],{Thickness[0.015],Line[{{4/5,0},{len+1,0}}]}}],AspectRatio->Automatic,PlotRange->{{0,len+1},{0,Automatic}}]];

Our example will deal with the three piles of size {3,4,5}:

(* If the length-1 of nim[] is odd, Player 1 is the winner; otherwise, the winner is Player 2 *)
Length[nim[{3,4,5}]]-1

Map[showpiles,nim[{3,4,5}]]

Player 1 will win because the game starts off unbalanced.  We can represent the entire game in its binary representation.  The following functions will create a table of the game.  The function TT takes as it's input the initial state of the game and outputs an entire game.  The function Game takes as input the initial pile sizes and creates a table with each pile represented in binary and the nim-sum/Grundy number.  MakeGrid2 takes this table and turns it into a grid.:

TT[{x___}]:=Table[Map[Length,Part[nim[{x}],i]],{i,1,Length[nim[{x}]]}];
TT[{3,4,5}]
Game[{x___}]:=Table[Prepend[Append[Part[Map[Binary,TT[{x}]],i],Part[Table[Mod[Apply[Plus,Part[Map[Binary,TT[{x}]],i]],2],{i,1,Length[Map[Binary,TT[{x}]]]}],i]],i],{i,1,Length[Map[Binary,TT[{x}]]]}]
MakeGrid2[{x___}]:=Text@Grid[Prepend[Game[{x}],{"Turn","Pile 1","Pile 2","Pile 3","Nim-Sum/Grundy number"}],Background->{None,{Lighter[Red,.9],{White,Lighter[Blue,.8]}}},Dividers->{{Darker[Gray,.6],{Lighter[Gray,.5]},Darker[Gray,.6]},{Darker[Gray,.6],Darker[Gray,.6],{False},Darker[Gray,.6]}},Alignment->{{Center}},
ItemSize->{{5,10,10,10,15}},
Frame->Darker[Gray,.6],
ItemStyle->14,
Spacings->{Automatic,.8}];
MakeGrid2[{3,4,5}]

Section 3. Conclusion and Future Work

3.1 Summary and Discussion

We conclude that there is a winning strategy in the game of Nim and that we can represent it in Mathematica.  Given more time, I would have liked to put this into a manipulate where you would be able to change the size of the piles.  I would also have liked to come up with a way for two people to actually play the game in Mathematica where the game tells you whether or not you made a good move (and whether or not you will win/lose) and also shows you the numbers in binary.

Section 4. References

Brualdi, Richard.  Introductory Combinatorics.  Prentice Hall.  New Jersey, 2004.

Cowen, Robert and Kennedy, John.  Discovering Mathematics with Mathematica.  Copley Custom TextBooks.  New York, 2009.

Cowen, Robert.  Mathematica file "nim.nb".  <http://qcpages.qc.cuny.edu/~cowen/>.