Exercise #2: The Game of Nim
◀ Identify Groups on a Board - Step 4▶ The Game of Nim - Step 1 Amazon
There are many variations of the game of Nim. In this program you are to allow the user to play this game with the computer. The game starts with an initial number of marbles, which your program decides, and determines at random who goes first, and then the user and the computer take turns.
The player who goes gets a chance to draw a certain number of marbles which must be at least one and no greater than half of the current number of marbles. For example, if there are 15 marbles currently, the player can draw up to 7 marbles. The player who draws the last marbles loses the game.
To make the program even more interesting and challenging, you will need to devise a stupid approach as well as a smart approach for the computer player. The approach the computer plays is determined at the start of the game at random.
In the stupid approach, the computer simply draws a random legal number of marbles.
In the smart approach, the computer needs to do the following things:
- If the current number of marbles is equal to a power of 2 minus 1, then the computer simply draws a random legal number of marbles.
- Otherwise, the computer takes a number of marbles so that the number of the remaining marbles is equal to a power of 2 minus 1.
If you want to know the logic behind it, do a little experiment and see for yourself. A smart computer should always win unless the first situation occurs (the current number of marbles is equal to a power of 2 minus 1).
For example, if the current number of marbles is 78, the smart computer should take 15 marbles away, leaving 63 marbles, which is 2^6 – 1. The behavior of the program can be seen from the following sample runs.
Here is a sample run when the computer plays dumb:
****** Welcome to the game of Nim ******
The number of marbles you draw must be > 0 and <= half of the total marbles.
The person who gets the last marble loses.
You go first.
Initial number of marbles: 15
The computer is playing stupid.
Enter number of marble(s) to draw: 6
Current number of marble(s): 9
Computer takes off 2 marble(s).
Current number of marble(s): 7
Enter number of marble(s) to draw: 3
Current number of marble(s): 4
Computer takes off 2 marble(s).
Current number of marble(s): 2
Enter number of marble(s) to draw: 2
Enter number of marble(s) to draw: 1
Current number of marble(s): 1
You win!
Here is a sample run when the computer plays smart:
****** Welcome to the game of Nim ******
The number of marbles you draw must be > 0 and <= half of the total marbles.
The person who gets the last marble loses.
You go first.
Initial number of marbles: 98
The computer is playing smart.
Enter number of marble(s) to draw: 1
Current number of marble(s): 97
Computer takes off 34 marble(s).
Current number of marble(s): 63
Enter number of marble(s) to draw: 2
Current number of marble(s): 61
Computer takes off 30 marble(s).
Current number of marble(s): 31
Enter number of marble(s) to draw: 3
Current number of marble(s): 28
Computer takes off 13 marble(s).
Current number of marble(s): 15
Enter number of marble(s) to draw: 4
Current number of marble(s): 11
Computer takes off 4 marble(s).
Current number of marble(s): 7
Enter number of marble(s) to draw: 3
Current number of marble(s): 4
Computer takes off 1 marble(s).
Current number of marble(s): 3
Enter number of marble(s) to draw: 2
Enter number of marble(s) to draw: 1
Current number of marble(s): 2
Computer takes off 1 marble(s).
Current number of marble(s): 1
The computer wins!
The format of the output is not important, but make sure you include the key elements. Now that you have enough information, get started on this program. As usual, refer to my solution only when you’ve racked your brain and still cannot finish the program.
Let's apply the
Four Step Programming Model described in
Chapter 11.8!
◀ Identify Groups on a Board - Step 4▶ The Game of Nim - Step 1