E-mail    Print    Discuss    Blog

Java Tech: An Intelligent Nim Computer Game, Part 2

Contents Console-Based Nim    Numeric Input GUI-Based NIM    Match Drag-and-Drop Special Effects    Sound Effects    Image Effects Conclusion Answers to Previous Homework

Last time, I introduced the game of Nim and explored the game tree and minimax tools. You learned how those tools work together, in a computerized version of Nim, to help the computer player make the optimal move. This article takes those tools out of the toolbox and puts them to work, as we develop console-based and GUI-based Java versions of Nim. You learn how each version gets the human player to select how many matches to take -- and how to achieve some special effects for the GUI-based version.

Console-Based Nim

I prefer to develop the console-based version first. That way, we focus on the essentials of how to make a computerized Nim game work, without getting bogged down with GUI details. The version that I have in mind will involve an initial pile of eleven matches. Also, the human player will always make the first move. Why? If the computer player (which always tries to make the optimal move) goes first, the human player would most likely never win. And that would make for a very boring game!

The following source code, which I excerpted from the main method in the ConNim application (see the nim2.zip file that accompanies this article), describes the essence of the console-based Nim game:

// Build a game tree to keep track of all possible
// game configurations that could occur during
// games of Nim with an initial pile of eleven
// matches. The first move is made by player A.

Node root = buildGameTree (11, 'A');

// Display startup information banner.

System.out.println ("WELCOME TO THE GAME OF " +
                    "NIM: 11 MATCHES IN PILE");

// Play the game until either player A (the human
// player) or player B (the computer player) wins.

while (true)
{
   // Obtain number of matches that are taken by
   // player A.

   int takenmatches = 0;

   do
   {
      System.out.print ("How many matches do " +
                        "you want? ");

      takenmatches = inputInteger ();

      if (takenmatches >= 1 &&
          takenmatches <= 3 &&
          root.nmatches-takenmatches >= 0)
          break;

      System.out.println ("That's an illegal " +
                          "move. Choose 1, 2, " +
                          "or 3 matches.");
   }
   while (true);

   // Based on number of taken matches, move to
   // appropriate game tree node.

   switch (takenmatches)
   {
      case 1: root = root.left;
              break;

      case 2: root = root.center;
              break;

      case 3: root = root.right;
   }

   System.out.println ("Human player takes " +
                       takenmatches +
                       ((takenmatches == 1) ?
                       " match, " : " matches, ") +
                       "leaving " + root.nmatches);

   // If a leaf node is reached, the computer
   // player has won the game.

   if (root.nmatches == 0)
   {
       System.out.println ("Computer player " +
                           "wins the game!");
       break;
   }

   // Use the minimax algorithm to determine if
   // the computer player's optimal move is the
   // child node left of the current root node,
   // the child node below the current root node,
   // or the child node right of the current root
   // node.

   int v1 = computeMinimax (root.left);
   int v2 = (root.center != null) ?
            computeMinimax (root.center) : 2;
   int v3 = (root.right != null) ?
            computeMinimax (root.right) : 2;

   if (v1 < v2 && v1 < v3)
       takenmatches = 1;
   else
   if (v2 < v1 && v2 < v3)
       takenmatches = 2;
   else
   if (v3 < v1 && v3 < v2)
       takenmatches = 3;
   else
       takenmatches = (int) (Math.random () * 3) +
                      1;

   // Based on number of taken matches, move to
   // appropriate game tree node.

   switch (takenmatches)
   {
      case 1: root = root.left;
              break;

      case 2: root = root.center;
              break;

      case 3: root = root.right;
   }

   System.out.println ("Computer player takes " +
                       takenmatches +
                       ((takenmatches == 1) ?
                       " match, " : " matches, ") +
                       "leaving " + root.nmatches);

   // If a leaf node is reached, the human player
   // has won the game.

   if (root.nmatches == 0)
   {
       System.out.println ("Human player wins " +
                           "the game!");
       break;
   }
}

After building the eleven-match game tree and outputting a startup banner, the code above enters the main game loop. That loop accomplishes these tasks:

1. The human player -- player A -- inputs the number of matches to take. This number is then validated: only 1, 2, or 3 is valid, and this number must not exceed the number of remaining matches.

2. The number of matches chosen by the human player is used to select the new root node. If the new root node's number-of-matches variable contains 0, a terminal configuration node has been reached, the human player loses, and the computer player -- player B -- wins. The program exits at this point. Otherwise, the new root node represents the position from which the computer player makes its move.

3. A minimax number is computed on the root node's left child. If the root node also has center and right child nodes, minimax numbers are computed on those nodes. Because the root node may not have center or right child nodes (look at Figures 1 and 2 in the previous Java Tech installment for examples), care is taken to avoid a NullPointerException (root.center != null, for example). If there is no center or right node, 2 is selected as the minimax number for that nonexistent node. That way, the nonexistent node won't be chosen in subsequent comparison logic.

4. The minimax numbers are compared to find the minimum, which is then used to identify the number of matches for the computer player to take. In some cases, there may be no minimum: all of the minimax numbers may be the same. Because there is no optimal move in those situations, a random number generator selects 1, 2, or 3 matches to take. (Note: Selecting a random number of matches to take will not result in an exception, because this situation only occurs in areas of the game tree where there are immediate left, center, and right child nodes.)

5. The number of matches chosen by the computer player is used to select the new root node. If the new root node's number-of-matches variable contains 0, a terminal configuration node has been reached, the computer player loses, and the human player wins. The program exits at this point. Otherwise, the new root node represents the position from which the human player makes a move.

6. The main game loop continues.

Compile ConNim's source code and run the resulting application to play console-based Nim. A sample session appears below:

WELCOME TO THE GAME OF NIM: 11 MATCHES IN PILE
How many matches do you want? 1
Human player takes 1 match, leaving 10
Computer player takes 1 match, leaving 9
How many matches do you want? 1
Human player takes 1 match, leaving 8
Computer player takes 3 matches, leaving 5
How many matches do you want? 1
Human player takes 1 match, leaving 4
Computer player takes 3 matches, leaving 1
How many matches do you want? 1
Human player takes 1 match, leaving 0
Computer player wins the game!

Numeric Input

ConNim features an inputInteger method for obtaining numeric input from the human player: 1, 2, or 3 matches. Although I could have used Java 1.5's java.util.Scanner class for input, I decided upon a customized inputInteger method, to support previous versions of Java. That method's source code appears below:

static int inputInteger ()
{
   StringBuffer sb = new StringBuffer ();

   int value = 0;

   try
   {
       boolean done = false;
       char c;

       while (!done)
       {
          int i = System.in.read ();
          if (i == -1)
              c = '\n';
          else
              c = (char) i;

          if (c == '\n')
              done = true;
          else
          if (c == '\r')
          {
              // do nothing because next iteration
              // detects '\n'.
          }
          else
              sb.append (c);
       }

       value = Integer.parseInt (sb.toString ()
                                   .trim ());
   }
   catch (IOException e)
   {
       System.err.println ("I/O problem");
       System.exit (0);
   }
   catch (NumberFormatException e)
   {
       System.out.println ("Number expected");
       System.exit (0);
   }

   return value;
}

inputInteger reads its input, on a character-by-character basis, until a new-line character is read. Each character, except for new-line and carriage return (on Windows platforms), is stored in a StringBuffer object. When new-line is seen, the contents of the StringBuffer are parsed and the resulting value returns. But if the contents of the StringBuffer do not represent a number, the parsing logic throws a NumberFormatException object, which is caught by a catch clause that outputs a message and immediately terminates the program.

A second catch clause is present to deal with IOException objects that are thrown when System.in.read is redirected to a file and something goes wrong during file I/O. Although it is unlikely that you will ever see an I/O Problem message (that outputs in response to the catch clause handling an IOException), Java requires this class of exception to be handled (or declared in a throws clause).

View all java.net Articles.