Java Data and Operators

5. Numeric Processing Examples

5.5. Example: A Winning Algorithm for One Row Nim

Now that we have access to numeric data types and operators, lets develop an algorithm that can win the One Row Nim game. Recall that in Chapter 4 we left things such that when the computer moves, it always takes 1 stick. Let's replace that strategy with a more sophisticated approach.

If you have played One Row Nim, you have probably noticed that in a game with 21 sticks, you can always win the game if you leave your opponent with 1, 5, 9, 13, 17, or 21 sticks. This is obvious for the case of 1 stick. For the case where you leave your opponent 5 sticks, no matter what the opponent does, you can make a move that leaves the other player with 1 stick. For example, if your opponent takes 1 stick, you can take 3; if your opponent takes 2, you can take 2; and, if your opponent takes 3, you can take 1. In any case, you can win the game by making the right move, if you have left your opponent with 5 sticks. The same arguments apply for the other values: 9, 13, 17, and 21.

What relationship is common to the numbers in this set? Notice that if you take the remainder after dividing each of these numbers by 4 you always get 1:

1 % 4 == 1
5 % 4 == 1
9 % 4 == 1
13 % 4 == 1
17 % 4 == 1
21 % 4 == 1

Thus, we can base our winning strategy on the goal of leaving the opponent with a number of sticks, N, such that N% 4 equals 1.

To determine how many sticks to take in order to leave the opponent with N, we need to use a little algebra. Let's suppose that sticksLeft represents the number of sticks left before our turn. The first thing we have to acknowledge is that if sticksLeft % 4 == 1, then we have been left with 1, 5, 9, 13, and so on, sticks, so we cannot force a win. In that case, it doesn't matter how many sticks we pick up. Our opponent should win the game.

So, let's suppose that sticksLeft % 4 != 1 , and let M be the number of sticks to pickup in order to leave our opponent with N , such that N % 4 == 1. Then we have the following two equations:

sticksLeft 
- M == N
N% 4 ==
     1

We can combine these into a single equation, which can be simplified as follows:

(sticksLeft - M) %4 == 1
If sticksLeft - M leaves a remainder of 1 when divided by 4, that means that sticksLeft - M is equal some integer quotient, Q times 4 plus 1:

(sticksLeft - M) == (Q * 4) + 1

By adding M to both sides and subtracting 1 from both sides of this equation, we get:

(sticksLeft - 1) == (Q * 4) + M

This equation is saying that (sticksLeft - 1) % 4 == M. That is, that when you divide sticksLeft-1 by 4, you will get a remainder of M, which is the number of sticks you should pick up. Thus, to decide how many sticks to take, we want to compute:

 M 
        == (sticksLeft -1) % 
            4

To verify this, let's look at some examples:

sticksLeft Before	(sticksLeft -1) % 4	sticksLeft After
9	(9-1) % 4 == 0	Illegal Move
8	(8-1) % 4 == 3	5
7	(7-1) % 4 == 2	5
6	(6-1) % 4 == 1	5
5	(5-1) % 4 == 0	Illegal Move

The examples in this table show that when we use (sticksLeft-1 % 4) to calculate our move, we always leave our opponent with a losing situation. Note that when sticksLeft equals 9 or 5, we can't apply this strategy because it would lead to an illegal move.

Let's now convert this algorithm into Java code. In addition to incorporating our winning strategy, this move() method makes use of two important Math class methods:

public int move() 
{ int sticksLeft = nim . getSticks // Get number of sticks 
   if (sticksLeft % (nim.MAXPICKUP + 1) != 1)// If winnable 
     return (sticksLeft — 1) % (nim.MPJCPICKUP +1); 
   else // Else pick random 
     int maxPickup = Math.min(nim.MAX.PICKUP, sticksLeft); 
     return 1 + (int )(Math.random() s maxPickup); 
   }
}

The move() method will return an int representing the best move possible. It begins by getting the number of sticks left from the OneRowNim object, which is referred to as nim in this case. It then checks whether it can win by computing (sticksLeft-1) % 4. However, note that rather than use the literal value 4, we use the named constant MAX PICKUP , which is accessible through the nim object. This is an especially good use for the class constant because it makes our algorithm completely general – that is, our winning strategy will continue to work even if the game is changed so that the maximum pickup is 5 or 6. The then clause computes and returns (sticksLeft-1) % nim.MAX PICKUP+1, but here again it uses the class constant.

The else clause would be used when it is not possible to make a winning move. In this case we want to choose a random number of sticks between 1 and some maximum number. The maximum number depends on how many sticks are left. If there are more than 3 sticks left, then the most we can pick up is 3, so we want a random number between 1 and 3. However, if there are 2 sticks left, then the most we can pick up is 2 and we want a random number between 1 and 2. Note how we use the Math.min() method to decide the maximum number of sticks that can be picked up:

 
                int maxPickup = Math.min(nim
                    .MAX_PICKUP, sticksLeft);

The min() method returns the minimum value between its two arguments.

Finally, note how we use the Math.random() method to calculate a random number between 1 and the maximum:

 1
                         + (int) (Math.
                            random() * maxPickup);

The random() method returns a real number between 0 and 0.999999 – that is, a real number between 0 and 1 but not including 1:

0 <= Math.random () < 1.0

If we multiply Math.random() times 2, the result would be a value between 0 and 1.9999999. Similarly, if we multiplied it by 3, the result would be a value between 0 and 2.9999999. In order to use the random value, we have to convert it into an integer, which is done by using the (int) cast operator:

(int) (Math.random () * maxPickup);

Recall that when a double is cast into an int , Java just throws away the fractional part. Therefore, this expression will give us a value between 0 and maxPickup-1. If maxPickup is 3, this will give a value between 0 and 2, whereas we want a random value between 1 and 3. To achieve this desired value, we merely add 1 to the result. Thus, using the expression

1 + (int) (Math.random () * maxPickup)

gives us a random number between 1 and maxPickup, where maxPickup is either 1, 2, or 3, depending on the situation of the game at that point.

SELF-STUDY EXERCISE

EXERCISE 5.5 Implement a class named NimPlayer that incorporates the move() method designed in this section. The class should implement the design shown in Figure 5.9. That is, in addition to the move() method, it should have an instance variable, nim , which will serve as a reference to the OneRowNim game. Its constructor method should take a OneRowNim parameter, allowing the NimPlayer to be given a reference when it is instantiated.


NimPlayer
`- nim:OneRowNim`
+ NimPlayer(g:OneRowNim) + move():int

Figure 5.9: The NimPlayer class.

EXERCISE 5.6 Modify OneRowNim's command-line interface to play One Row Nim between the user and the computer, where the NimPlayer implemented in the previous exercise represents the computer.