Random Numbers, Games, and Simulation - Advanced Topics in Java: Core Concepts in Data Structures - page 170

For example, if startAmount is 20 and maxPick is 3 , the game may proceed as follows:
A picks up 2, leaving 18 on the table.
B picks up 1, leaving 17 on the table.
A picks up 3, leaving 14 on the table.
B picks up 1, leaving 13 on the table.
A picks up 2, leaving 11 on the table.
B picks up 2, leaving 9 on the table.
A picks up 1, leaving 8 on the table.
B picks up 3, leaving 5 on the table.
A picks up 1, leaving 4 on the table.
B picks up 3, leaving 1 on the table.
A is forced to pick up the last match and, therefore, loses the game.
What is the best way to play the game? Obviously, the goal should be to leave your opponent with one match
remaining on the table. Let's call this a losing position . The next question to answer is, how many matches must you
leave so that, no matter how many he picks up (within the rules of the game), you can leave him with one?
In this example, the answer is 5. Whether he picks up 1, 2, or 3, you can always leave him with 1. If he picks up 1,
you pick up 3; if he picks up 2, you pick up 2; if he picks up 3, you pick up 1. So, therefore, 5 is the next losing position.
The next question is, how many matches must you leave so that, no matter how many he picks up (within the
rules of the game), you can leave him with 5? The answer is 9. Try it!
And so on. Reasoning this way, we discover that 1, 5, 9, 13, 17, and so on, are all losing positions. In other words,
if you can leave your opponent with any of these number of matches, you can force a win.
In this example, the moment B left A with 17 matches, B was in a position from which he could not lose, unless he
became careless.
In general, losing positions are obtained by adding 1 to multiples of maxPick+1 . If maxPick is 3 , multiples of 4 are
4, 8, 12, 16, and so on. Adding 1 gives the losing positions 5, 9, 13, 17, and so on.
We will write a program in which the computer plays the best possible game of Nim. If it can force the user into a
losing position, it will. If the user has forced it into a losing position, it will pick up a random number of matches and
hope that the user makes a mistake.
If remain is the number of matches remaining on the table, how can the computer determine what is the best
move to make?
If remain is less than or equal to maxPick , the computer picks up remain-1 matches, leaving the user with 1.
Otherwise, we perform this calculation:
r = remain % (maxPick + 1)
If r is 0 , remain is a multiple of maxPick+1 ; the computer picks up maxPick matches, leaving the user in a losing
position. In this example, if remain is 16 (a multiple of 4), the computer picks up 3, leaving the user with 13—a losing
position.
If r is 1 , the computer is in a losing position and picks up a random number of matches.
Otherwise, the computer picks up r-1 matches, leaving the user in a losing position. In this example, if remain is 18,
r would be 2. The computer picks up 1, leaving the user with 17—a losing position.
This strategy is implemented in the function bestPick , part of Program P6.4, which pits the computer against a
user in our version of Nim.