• ### Popular Now

• 13
• 16
• 27
• 9
• 9

#### Archived

This topic is now archived and is closed to further replies.

# Can anyone help me with the NIM Game ?

This topic is 5245 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello everyone I'm a new member and i am trying to program the NIM Game in C++ but i have a little difficulty. First, let me explain how i must make the game. I have to make the player choose between 11 and 31 sticks for each game, and then make him choose how many sticks he and the cpu can take by turn (it has to be between 3 and half of the numbers of sticks he chose earlier). Also, i ABSOLUTELY have to make the computer find a way to win, a strategy so he'll never lose. Thats where im stuck.. (btw, im French speaking so dont mind the french words, but i've translated the "cout" for you). Here's where i'm stuck in my code #include <iostream> using namespace std; int main () { unsigned maxNbSticks, maxSticksByTurn, minSticksByTurn = 1, score, nbSticksTaken, unsigned nbSticksTakenByCPU, nbSticksRemaining; cout << "Welcome to the NIM Game!" << endl << endl; cout << "With how many sticks will we play ? (Min 11 Max 31) "; cin >> maxNbSticks; while(maxNbSticks < 11 || maxNbSticks > 31) { cout << "\nInvalid number !" << endl << endl; cout << "With how many sticks will we play ? (Min 11 Max 31) "; cin >> maxNbSticks; } cout << "\nMaximum sticks by turn ? "; cout << "(Min 3 Max " << maxNbSticks / 2 << ") "; cin >> priseMax; while(maxSticksByTurn < 3 || maxSticksByTurn > maxNbSticks/2) { cout << "\nInvalid number !" << endl << endl; cout << "Maximum sticks by turn ? "; cout << "(Min 3 Max " << maxNbSticks / 2 << ") "; cin >> maxSticksByTurn; } cout << "\We will then play with " << maxNbSticks << " sticks "; cout << "and we'll take from 1 to " << maxSticksByTurn << " sticks by turn !" << endl << endl; while (nbSticksRemaining != 0) { cout << "\nThere are presently " << maxNbSticks << " sticks remaining" << endl; cout << "\nHow many sticks do you take ? "; cin >> nbSticksTaken; } return 0; } So i'm stuck there...i know what the strategy is, but now how to implement it. The strategy is that the Computer should make "rows" of sticks and divide them by the same number, to make blocks, and always "finish" the block so that the player is always stuck with the last stick. Here's an exemple: Suppose the player chooses 13 sticks to play with, and a maximum number of 3 sticks by turn. The Computer then tells to himself "Ok, we have 13 sticks, so if we remove the last one, we have 12. 12 can be divided by 3 blocks of 4 sticks, so i can do it like this: [ / / / / ] [ / / / / ] [ / / / / ] / If the player takes 2 sticks, then the Computer takes 2, to fisnish the first block. If the player chose 3 instead, then the Computer takes 1. So the computer will ALWAYS win this way. What i'm stucks with is "how to tell this strategy to the computer for EVERY combination possible. Can anyone help me ? [edited by - DarkMageX on November 6, 2003 7:56:56 PM]

##### Share on other sites
I think what you are looking for is called a minimax algorithm. There has been plenty written on the subject, so just Google for it.

##### Share on other sites
"Suppose the player chooses 13 sticks to play with, and a maximum number of 3 sticks by turn."

Player takes 2 sticks, 11 left.

11 is more than 7 (max sticks per turn * 2 +1) so cpu can take maximum
number of sticks. So cpu takes 3 sticks, 8 left.

Player takes 1 stick, 7 left.

7 is more than 4 (max sticks per turn + 1) so cpu takes
2 sticks (7 - max sticks + 2), 5 left.

Player takes 3 sticks, 2 left.

There´s amount of sticks that cpu can take all except one that
he will leave to player and that´s it.

if (sticks > sticksByTurn+1)   sticks -= (sticks - sticksByTurn+2)if (sticks > 2*sticksByTurn+1)   sticks -= sticksByTurnelse    sticks = 1[/CODE]

##### Share on other sites
Thanks a lot !!

But i''m trying to implement the code you gave me in mine, but it doesnt really work..where should i put it ?

##### Share on other sites

2) don''t crosspost.

##### Share on other sites
quote:
Original post by Anonymous Poster
Thanks a lot !!

But i''m trying to implement the code you gave me in mine, but it doesnt really work..where should i put it ?

First you should fix some errors that you have in your code.

That code I gave goes to the same loop where your players "turn" is handled. If you want that player starts then put cpu´s "turn" after player´s one and if you want cpu´s to start then put cpu´s "turn" above player´s one. And always when player took sticks you should check that he/she won´t take more than there really is left to take.

Also I think that it would be better to change that condition:

while (nbSticksRemaining != 0)
{
...
}

To never ending loop:

while(3)
{
...
}

Because otherwise there can be situation where player takes last stick and if cpu´s turn is after player´s one, the turn will still go to the cpu even if there isn´t any sticks left.

And now always when player takes sticks, check
if nbSticksRemaining is 0 and if it is, get out of loop with break;