[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
|
|
|
Sticks in pile | Binary Representation | Safe/Unsafe? |
Column Values | ||
8 4 2 1 | ||
3 | 0 0 1 1 | |
4 | 0 1 0 0 | |
7 | 0 1 1 1 | |
Column Sums | 0 2 2 2 | Safe |
5 | 0 1 0 1 | |
1 | 0 0 0 1 | |
6 | 0 1 1 0 | |
Column Sums | 0 2 1 2 | Unsafe (2's column is odd) |
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:
|
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.
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.
![]() | Browse source extract |
![]() | Download source |
![]() | Download executable |
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. |
Originally posted: April 28, 2002 |
Modified: May 15, 2018 |
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 2000-2018, Gary Darby All rights reserved. |