[Home]   [Projects]    [Delphi Techniques]   [Math Topics]   [Library]   [Utilities]

Problem Description

We're looking for a program today that will play the multi-pile version of NIM against a human opponent.  We'll allow up to 8 piles with up to 32 sticks in each pile.  The rules are simple; players take turns removing from 1 to all of the sticks in any one pile he chooses.  The player  taking the last stick wins.    

Background & Techniques

In the previous version of NIM,   we introduced  the single pile version of Nim and introduced the Minimax technique for solving.  The original intent here was to apply Minimax to the multi-pile version as a more interesting exercise.  It turns out, however,  that Minimax is overkill for this game - there is a  technique using "Nim-values"   that's even simpler to implement.    This method was discovered and published nearly a hundred years ago by Harvard mathematics professor, Charles Bouton, the same fellow that named the game.  

First I'll describe the algorithm and then see if we can understand why it works.   A safe position of the game is any position from which we can be assured of a win.  All other positions are  unsafe.   If we write the binary representations of the number of sticks in each pile, and check the parity (odd or even) of the sum of the bits (binary digits) in each column, it turns out that those positions where sum of every column is even are safe, an odd sum in any column makes the position unsafe.    A couple of examples from a 3-pile game.

There are two key facts that make the binary representation method work :

• Any safe position will become unsafe by any move.   By definition every column has an even number of bits.  Removing any stick or sticks will change one or more of the 1's in a row to 0.  This will change the parity of that column from even to odd, so the resulting position will be unsafe.
• Any unsafe position can be made safe with some appropriate move, like this:
  • Find the leftmost column with an odd sum.  
  • Find a row  (pile) that has a 1 in this column.
  • Starting  at this column and moving to the right,  flip every binary digit (0 becomes 1 and 1 becomes 0) for each column whose sum is odd.  This will add or subtract 1 from that column and is guaranteed to make the odd  column sums even again, and thus make the resulting configuration safe again.   The resulting number, converted back to decimal,  is the number of sticks to leave in that pile. 

So our objective is to inherit unsafe positions and use our move to make them safe.  Since the next-to-last move consists of one or more sticks in a single pile (an unsafe position) we will eventually inherit this board and proceed to make it safe (and win!) by removing all remaining sticks in that. 

We don't want want to inherit safe positions since any move will make it unsafe,  but  if we are unlucky enough to do so, the program's strategy is to take a single stick from the largest pile and hope things get better on the next round.   This can occur, for example, if the initial board is safe and we play first,  or a smart (or lucky) human plays first and passes us a safe position. 

The human, by the way, can choose to play first or second in any game - they need every advantage they can get.  To move, the human clicks the up/down arrows in any pile until he is satisfied, then registers the move by clicking the "Computer Move" button.  

As usual, I guess we need a few notes about the programming.   Non-programmers may want to   jump to the download section now.

Programmer's Notes:

The program is a pretty straightforward implementation of the above description.   Three new types are defined:

    TBinary=array[1..bsize] of byte;
    TPiles=array[1..maxpiles]of TBinary;
    TPlayer=(Human, Computer, NewGame);

There are a couple of functions, MakeBinary and MakeDecimal to convert from integer to binary format and back again.    Procedure ComputerBtnClick is the heart of the solving method, examining the  state of the board and making the next move a described above.

The piles themselves are represented in an array of TUpDown controls named Piles.  The controls could have been created dynamically, but in this case I added them at design time and just placed them into the Piles array at startup time.   By the way, this is a excellent demonstration that object references are treated as pointer references.  Piles[1]:=PileUpdown1; merely places a pointer to the design time object PileUpDown1 into array entry Piles[1].

I added a DrawSticks procedure to draw some lines representing the piles of sticks.  There is some slightly tricky code here to space the piles properly based on number of piles in the current game, and to center the sticks remaining in each pile in the image space reserved for that pile.

There's also some slightly complicated code to keep the user from cheating by removing sticks from more than one pile during a turn.  There seem to be no TUpDown exits that occur after the change is made, only while the change is pending, so the associated TEditBox exit is used to actually test if the result was a winning move and to redraw the pile of sticks.  A TUpDown exit is used to prevent cheating by  resetting all stick counts, except the one being changed, back to the values left after the last computer move.     

Just for fun,  I created small arrays of winning messages (one for humans, one for computer) and randomly select the one to display at end of game.  

OK, enough talk, let's have some fun!

Addendum December 10, 2002:  I just posted Nim3, a multi-pile NIM version with four major differences from the previous version.  

• "Sticks" have been replaced  by circular tokens  selected by clicking on the token.  (Click and shift-click may be used to select multiple token).
•  The implementation of the logic described above has been changed to use exclusive or (XOR) operations.  Much more efficient -  50 lines of code required to determine a computer move was reduced to 15 lines!  (But also harder to understand.)  
• The computer will now actively participate in play, rather that just make suggestions.  Options are Human vs. Humans, Computer vs. Human, and Human vs. Computer where order of listing players is the order of play.
• Miseré play (last stick loses) is now supported.

I will confess that this version was developed independently of the version written in April.  In other words, I forgot that I had already solved this problem eight months ago!   A least this one turned out better than the earlier version.     

Running/Exploring the Program 

• Browse source extract
• Download source
• Download  executable

Suggestions for Further Explorations

There are lots of places to go from here:

	The miseré (reversed,  literally misery where  last stick loses) version of the game may be solvable by the same techniques presented here. I haven't investigated yet. (Done - Implemented in Version 3)
	There are many other versions of Nim - a Google search will keep you busy for hours.   And implementing them - busy for days.

  [Feedback]   [Newsletters (subscribe/view)] [About me]

Copyright © 2000-2008, Gary Darby    All rights reserved.