Click here to Skip to main content
Click here to Skip to main content

The Nim Game

, 8 Aug 2007
Rate this:
Please Sign up or sign in to vote.
A two-player mathematical game of strategy
Screenshot - project_1.jpg

Introduction

What is the Nim Game?

Nim is a two-player mathematical game of strategy in which players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap.

Variants of Nim have been played since ancient times. The game is said to have originated in China (it closely resembles the Chinese game of "Jianshizi", or "picking stones"), but the origin is uncertain; the earliest European references to Nim are from the beginning of the 16th century.

Its current name was coined by Charles L. Bouton of Harvard University, who also developed the complete theory of the game in 1901, but the origins of the name were never fully explained. The name is probably derived from German nimm! meaning "take!", or the obsolete English verb nim of the same meaning. Some people have noted that turning the word NIM upside-down and backwards results in WIN.

Nim is usually played as a misere game, in which the player to take the last object loses. Nim can also be played as a normal play game, which means that the person who makes the last move (i.e., who takes the last object) wins. This is called normal play because most games follow this convention, even though Nim usually does not.

XOR Tricks for Winning at Nim

Although it takes some high-level math to find the secret strategy of Nim, employing that strategy really only requires an understanding of binary numbers.

In order to win at Nim, you have to know how to use the binary operation XOR, which stands for "exclusive or". What XOR really means is "x XOR y = 1 if either x or y is 1, but not if they are both 1." So, 0 XOR 0 = 0, 1 XOR 0 = 1, 0 XOR 1 = 1, and 1 XOR 1 = 0. Or, more simply, the result of the XOR operation is 0 if both arguments are the same and 1 if the arguments are different.

For any given situation in Nim there is a number which determines whether or not that situation is a losing one. To find that number, you have to perform the XOR operation on the number of objects in each row successively. For example, the position is:

Screenshot - nim.jpg

So to see if this is a losing position we have to XOR the number of objects in each row, as follows.

1 XOR 3 XOR 5 

which when shown in binary is

001 XOR 011 XOR 101

Now we have to XOR each digit in each number and put each result below the column for that digit. Let's start with the rightmost digits.

1 XOR 1 XOR 1   is the same as   (1 XOR 1) XOR 1

1 XOR 1 = 0, and 0 XOR 1 = 1. So 1 XOR 1 XOR 1 = 1.

Now continue with the rest of the columns until we have a new binary number.

001 XOR 011 XOR 101 = 111 

If all the digits of this final number are zero, the position is a losing position !!!!!!! If it's your turn and the position is a losing position, you're in trouble. However, in this example, the number is non-zero, so we can turn the position into a losing position for our opponent.

Let's take the number 111 that we got from XORing the rows and try to find a row which, when XORed with 111, gives us a lower number than the row previously had. Well, we know if we do 001 XOR 111 it will be greater than 1, and 011 XOR 111 will be greater than 3, so we must do 101 XOR 111, which is 010, or in decimal 2, and is less than 5. So in order to give your opponent a losing position, you just have to remove 3 objects from the row of 5, leaving 2.

SUMMARY

The steps needed to win are:

  1. When it is your turn, convert the number of objects in each row into binary numbers and XOR them.
  2. If the resulting number is 0, there's not much you can do to win. If it isn't 0, XOR it with a row and make a move so as to leave that many objects in that row.

For more information about Mathematical theory of game see Wikipedia.

Using the Code

I'm not going to be detailing the game step by step or anything like that, but I'll talk about a few specific elements.

The code demonstrates the work of the standard widgets in C#. The following code illustrates the process of dynamic creation and initialization of these widgets (for example: buttons, ComboBoxes, image, etc.)

  /**************************************************/
 /* The method creates seven ComboBoxes            */
/**************************************************/
void CreateNew_ComboBoxes()
{
    int i,x=31;
    try
    {
        cmbbox =  new  ComboBox[7];
        for ( i = 0; i < 7; i++)
        {   
            cmbbox[i] = new ComboBox();
            cmbbox[i].Parent=this;
            cmbbox[i].Width=40;
            cmbbox[i].Location=new Point(x,5);
            x+=107;
            cmbbox[i].ForeColor=Color.Blue;
            cmbbox[i].MaxDropDownItems=30;
            cmbbox[i].Tag=i;
            cmbbox[i].DropDownStyle=ComboBoxStyle.DropDownList;
            cmbbox[i].Visible=true;
            cmbbox[i].SelectedValueChanged += new System.EventHandler(
                this.Change_Select_Data_ComboBox);
        }
        FlagColor = true;
    }
    catch (System.IndexOutOfRangeException exc)
    {
        MessageBox.Show(exc.Message,"Overloaded");
        return;
    }
}         
  /**************************************************/
 /* The method enters numbers in ComboBoxes        */
/**************************************************/

void Fill_ComboBoxes()
{
    Random rdm; 
    int Number_Members_In_One_Row;
    SumOfImages=0; // sum of all pencils
    for (int i =
        0;  i <  7; i++)
    {   
        rdm = new Random(unchecked((int)DateTime.Now.Ticks));
        // get random number of elements for one heap
        Number_Members_In_One_Row = (rdm.Next(30)+1); 
        SumOfImages+=Number_Members_In_One_Row;
        if(cmbbox[i].Items.Count!=0)
        {
            cmbbox[i].Items.Clear();
        }
        for(int k=1; k<=Number_Members_In_One_Row; k++)
        {
            cmbbox[i].Items.Add(k);

        }
        cmbbox[i].Text=Number_Members_In_One_Row.ToString();
        num_choos_pens=0;
        System.Threading.Thread.Sleep(35);
    }
}

After the above-stated code we shall see 7 ComboBoxes

Screenshot - combobox.jpg

In the same way methods CreateNew_Images() and Fill_Images() create "heaps" with pencils.

  /*******************************************************************/
 /* The method creates a matrix in the size 7 on 30 for the pencils */
/*******************************************************************/
void CreateNew_Images()
{
    int y;
    int x=0;
    Image image = Image.FromFile("GrayPen.bmp");  
    images = new PictureBox[7][];
    for(int i=0; i<7; i++,x+=107)
    {
        y=this.Height-(int)(6*(image.Height));
        images[i] = new PictureBox [30];

        for(int j=0; j<30; j++)
        {
            images[i][j]= new PictureBox();
            images[i][j].Parent=this;
            images[i][j].Height=15;
            images[i][j].Width=104;
            images[i][j].Anchor=AnchorStyles.Bottom|AnchorStyles.Left;
            images[i][j].Location=new Point(x,y);
            y-=16;
        }
    }            
}
            
  /*************************************************************/
 /* The method fills in a matrix gray pencils                 */
/*************************************************************/
void Fill_Images()
{
    int new_number_elements;
    int old_number_elements;

    Image image = Image.FromFile("GrayPen.bmp"); 

    for(int i=0; i<7; i++)
    {
        new_number_elements = cmbbox[i].Items.Count;
        old_number_elements=(int)numberLoadImages[i];

        // if you must insert images
        if(old_number_elements < new_number_elements)
        {
            for(int j=old_number_elements; j < new_number_elements; 
                j++)
            {
                images[i][j].Image=image;
            }
            numberLoadImages.SetValue(new_number_elements,i);

        }
        // if you must remove images

        else if(old_number_elements > new_number_elements)
        {
            PictureBox img = new PictureBox();

            for(int j=old_number_elements-1; 
                j>=new_number_elements; j--)
            {
                images[i][j].Image=img.Image; 
            }
            numberLoadImages.SetValue(new_number_elements,i);
        }
    }
}

The program supports an opportunity for game of two players (one against another), and a mode of game of the person with a computer. The following code illustrates strategy of a computer (if we have, of course, chosen an option to play with a computer):

  /*******************************************************/
 /* Computer's game strategy                            */
/*******************************************************/    
private void ComputerGame()
{ 
    int [] arr = new int[7];
    //Array numbers of "gray" pens in each column
    for(int i= 0;i<7; i++ )
    {
        arr[i]=((int)numberLoadImages[i]-BlueRedImages[i]);
    }
    int tryResultElements=-1;
    int numElements;
    int n;
    //////////////////////////////////////////////////////////////////
    // 3 cycles  for find column and number elements                //
    //////////////////////////////////////////////////////////////////
    //for k times
    for(int k= 0;k<7 && tryResultElements!=0 ; k++)
    {
        numElements=arr[k];
        for (n=1; n<=numElements; n++)
        {   
            num_choos_pens=n; 
            index=k;
            ////////////////////////////////////////////////////
            tryResultElements = numElements-n;
            //for m columns 
            for(int m= 0;m<7; m++)
            {
                if(k!=m)
                    tryResultElements^=arr[m];
            }
            if(tryResultElements==0)
            {  
                num_choos_pens=n; 
                index=k;
                break;
            }
        }     
    }
    //////////////////////////////////////////////////////////////////
    // from (k+1) column computer must get n elements               //
    //////////////////////////////////////////////////////////////////
    int j;
    int count;

    Image imageRed = Image.FromFile("RedPen.bmp"); 
    SumOfImages = SumOfImages-num_choos_pens;
    count=num_choos_pens;
    j=  
        ((int)numberLoadImages[index]-BlueRedImages[index]-1);while(
        count>0)
    {
        cmbbox[index].Items.Remove(cmbbox[index].Items.Count);
        count--;
    }
    //Save blue/red items in array images[index][]...
    BlueRedImages[index]=BlueRedImages[index]+ num_choos_pens;
    for(int 
        i= 
        0;i <  num_choos_pens; i++, j--)
    {
        images[index][j].Image=imageRed;
    }

    if(SumOfImages==0)
    {
        switch(MessageBox.Show("New Game?","The game" +
            "is over.Red won",MessageBoxButtons.YesNo))
        {
        case DialogResult.Yes: //New Game
            this.winBlue=true;
            this.winRed=false;
            this.UpdateGameWin();
            this.Fill_ComboBoxes();
            this.Fill_Images();
            this.btnOK.Focus();
            this.num_choos_pens=0;
            this.index=-1;
            this.FlagColor=false;
            return;
        case DialogResult.No: //Finish Game
            this.Close(); 
            break;
        }
    }
    int newNumElementsInComboBox;
    newNumElementsInComboBox=cmbbox[index].Items.Count;
    cmbbox[index].Text=(
        newNumElementsInComboBox>0)? Convert.ToString(
        newNumElementsInComboBox):"";
    winBlue=!winBlue;
    winRed=!winRed;
    num_choos_pens=0;
    index=-1;           
}

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

About the Author

Volynsky Alex
Software Developer
Israel Israel
Mr.Volynsky Alex is a Software Engineer in a leading software company. Alex is skilled in many areas of computer science. He has over 13 years of experience in the design & development of applications using C/C++/STL, Qt, MFC, COM/ActiveX, DirectShow, JavaScript, VBScript, Tcl/Tk and of course - C#/.NET.
 
Overall, Alex is very easy to work with. He adapts to new systems and technology while performing complete problem definition research.
 
His hobbies include yacht racing, photography and reading in multiple genres.
He is also fascinated by attending computer meetings in general, loves traveling, and also takes pleasure in exercising and relaxing with friends.
 
Visit his C++ 11 blog

Comments and Discussions

 
GeneralMy vote of 5 Pinmembermk4you713-Jun-12 5:06 
GeneralRe: My vote of 5 PinmemberVolynsky Alex14-Jun-12 15:13 
GeneralMy vote of 5 PinmemberSteph_Iv28-May-12 10:38 
GeneralRe: My vote of 5 PinmemberVolynsky Alex14-Jun-12 15:14 
GeneralMy vote of 5 PinmemberEMogilevsky26-May-12 4:31 
GeneralRe: My vote of 5 PinmemberVolynsky Alex14-Jun-12 15:14 
GeneralMy vote of 5 PinmemberGerard Forestier24-May-12 22:18 
GeneralRe: My vote of 5 PinmemberVolynsky Alex14-Jun-12 15:15 
GeneralMy vote of 5 Pinmemberjfriedman20-May-12 8:44 
GeneralMy vote of 5 PinmemberY.Desros6-May-12 5:36 
GeneralRe: My vote of 5 PinmemberVolynsky Alex14-Jun-12 15:15 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web03 | 2.8.140709.1 | Last Updated 8 Aug 2007
Article Copyright 2007 by Volynsky Alex
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid