Many developers like to play computer games. They entertain us and help reduce the stress caused by our jobs. Have you ever wanted to create your own version of a computer game? I have. This Java Tech article begins a two-part series on developing two versions of an intelligent computer game, Nim.

In this article, you learn how to play Nim, and discover tools for creating an intelligent computer player. In the next article, you apply those tools to the creation of that player, while building console and GUI Nim games. As you create the GUI version, you'll examine a technique for dragging and dropping game objects.

Introducing Nim

The game of Nim typically involves two players and a pile of matches, stones, marbles, or some other kind of objects. Each player alternately makes a move by taking one, two, or three objects from the pile. The player who takes the last object(s) loses -- and the other player wins. For example, suppose there's a pile of five matches. Player A takes two matches, leaving three. Player B then takes two matches, leaving one. Player A must take the final match, and loses. Player B wins.

Note: The paragraph above describes one way to play Nim; I use that technique in this article. To learn about other ways to play Nim, and to find out where that name comes from, consult the Wikipedia entry for Nim.

An Intelligent Computer Player

We could create a Nim computer game that requires two human players. However, if one player was absent, the game would certainly lose its appeal. To solve that problem, we will design a computer player to challenge the human player. In a nutshell, the computer player will be intelligent.

How do we create an intelligent computer player? For starters, we need to know a little game theory. According to game theory, Nim is an example of a zero-sum game of perfect information. (Chess, tic-tac-toe, Othello, and checkers are other examples.) "Zero-sum" means that the interests of the players are exactly opposed. Regardless of the game's outcome, the winnings of one player are exactly balanced by the losses of the other(s). For example, only one player wins and only one player loses in a two-player Nim game. "Perfect information" means that, at every move, each player knows all of the moves that have already been made. For example, each player in a two-player Nim game knows all moves made by the other player, along with the player's own moves.

Zero-sum games of perfect information imply that there exists a best strategy for each player, to help that player win or to minimize that player's loss. A pair of tools help intelligent computer players find that best strategy: game trees and the minimax algorithm.

Game Trees

A game tree describes all possible moves, via its branches, and resulting game configurations, via its nodes, in a two-player game. The root node represents the initial game configuration and the leaf nodes represent the terminal configurations: win, lose, or draw. There is only one terminal configuration in Nim -- no matches are left in the pile. That configuration represents a win for Player A if Player B makes the last move, or a win for Player B if Player A makes the last move. Figure 1 reveals a game tree for a two-player Nim game, with an initial game configuration specifying four matches.

Figure 1. Game tree for a two-player Nim game, with an initial pile of four matches

In Figure 1, square pink nodes represent Player A, round green nodes represent Player B, and triangular blue nodes represent the terminal configuration -- a win for Player A or Player B, depending on the parent node (green or pink, respectively). Each branch has a numeric label that indicates how many matches have been taken from the pile, and each node has a numeric label indicating how many matches remain in the pile. The pink square node with numeric label 4 is the root node, and indicates that the pile initially contains four matches and that Player A makes the first move.

Suppose Player A takes one match from the pile. The game tree displays this move via the branch (with label 1) from the root node to the Player B node with the 3 label. Now suppose Player B counters Player A's move by taking two matches from the pile. The game tree reveals this move via the branch (with label 2) from the Player B node with the 3 label to the Player A node with label 1. Player A has no choice but to take the final match, and Player B wins. The game tree presents this move via the branch (labeled 1) from the Player A node with label 1 to the terminal configuration node directly below.

We can easily create a game tree that completely describes a Nim game, with an initial game configuration that specifies n matches. To accomplish that task, we use both a Node class and a recursive game-tree-building method. The Node class appears below:

class Node
{
   int nmatches; // Number of matches remaining
                 // after a move to this Node
                 // from the parent Node.
   char player;  // Game configuration from which
                 // player (A - player A, B -
                 // player B) makes a move.
   Node left;    // Link to left child Node -- a
                 // move is made to left Node
                 // when 1 match is taken. (This
                 // link is only null when the
                 // current Node is a leaf.)
   Node center;  // Link to center child Node --
                 // a move is made to this Node
                 // when 2 matches are taken.
                 // (This link may be null, even
                 // if the current Node is not a
                 // leaf.)
   Node right;   // Link to right child Node -- a
                 // move is made to this Node
                 // when three matches are taken.
                 // (This link may be null, even
                 // if the current Node is not a
                 // leaf.)
}

Each Node object describes a game configuration in terms of the number of matches left on the pile (nmatches), the player whose turn it is to make the next move (player), and links to the left, center, and right immediate child Nodes. The following recursive buildGameTree method combines Node objects into a game tree:

static Node buildGameTree (int nmatches,
                           char player)
{
   Node n = new Node ();
   n.nmatches = nmatches;
   n.player = player;
   if (nmatches >= 1)
       n.left = buildGameTree (nmatches-1,
                               (player == 'A')
                               ? 'B' : 'A');
   if (nmatches >= 2)
       n.center = buildGameTree (nmatches-2,
                                 (player == 'A')
                                 ? 'B' : 'A');
   if (nmatches >= 3)
       n.right = buildGameTree (nmatches-3,
                                (player == 'A')
                                ? 'B' : 'A');
   return n;
}

buildGameTree recursively builds a game tree that fully describes a Nim game, with a starting pile specified by nmatches prior to the recursion. This method uses if statements to ensure that Node objects are not created for those scenarios where the number of taken matches would exceed the number of matches currently in the pile (attempting to take three matches from a two-match pile, for example). For each terminal configuration Node object, buildGameTree assigns the winning player's name to that object's player field.

We can combine the Node class and the buildGameTree method to create Figure 1's game tree: Node root = buildGameTree (4, 'A');. That line of code specifies an initial pile of four matches, and that Player A goes first. (Note: These code fragments are excerpted from a GameTree application I built for this article. To access that application's source code, unzip the code.zip file.)

Storing an entire game tree's nodes in memory is not practical for large game trees -- thousands or millions of nodes. However, with an initial pile of four (or even 11) matches, the resulting Nim game tree can be completely stored in memory.

Minimax Algorithm

The minimax algorithm determines a player's optimal move by assigning a number to each node that is an immediate child of the player's node. The optimal move for Player A is to follow the branch to the immediate child node with the maximum number. In a similar fashion, the optimal move for Player B is to follow the branch to the immediate child node with the minimum number. Although the optimal move doesn't guarantee a win for the player, it indicates the best possible outcome that the player can hope to achieve.

Node numbers are first determined at the terminal configuration node level. An evaluation function calculates these numbers. In Nim, this function is simple: return 1 if a terminal configuration node indicates Player A to be the winner, or -1 if Player B is shown to be the winner. Moving up one level, minimax then determines either the maximum or the minimum of all child numbers -- maximum if the parent node represents Player A's turn, or minimum if the parent node represents Player B's turn -- and assigns the result to the parent node. With each level that minimax moves up, it alternately determines the maximum or minimum prior to the assignment (which is how minimax gets its name). Figure 2 illustrates minimax being applied to Figure 1's game tree.

Figure 2. Game tree with a minimax value assigned to each node

In Figure 2, suppose the current node is the pink square node that contains 1, and is located two levels down and on the left side. That node indicates that it is Player A's turn to make a move. Should Player A take 1 match or 2? Here is what minimax determines: The leftmost terminal configuration node (at the lowest level) is assigned 1 because that node indicates a win for Player A -- Player B has just removed the last match and loses. Minimax assigns that value as the minimum to the parent Player B node. The terminal configuration node to the right of (and at the same level as) the Player B node (which contains 1) is assigned -1, because it indicates a win for Player B -- Player A has just removed the last two matches and loses. The maximum of 1 and -1 then assigns to the Player A parent node, which means Player A's optimal move is to take one match.

Earlier, you saw how Java was used to create a game tree. You will now see how Java is used to implement the minimax algorithm to search the game tree for Player A's optimal opening move. Examine the following code fragment, taken from the Minimax application that accompanies this article (see the code.zip file).

// Build a game tree to keep track of all possible
// game configurations that could occur during
// games of Nim with an initial pile of four
// matches. The first move is made by player A.
Node root = buildGameTree (4, 'A');

// Use the minimax algorithm to determine if
// player A's optimal move is the child node to
// the left of the current root node, the child
// node directly below the current root node, or
// the child node to the right of the current root
// node.
int v1 = computeMinimax (root.left);
int v2 = computeMinimax (root.center);
int v3 = computeMinimax (root.right);
if (v1 > v2 && v1 > v3)
    System.out.println ("Move to the left node.");
else
if (v2 > v1 && v2 > v3)
    System.out.println ("Move to the center node.");
else
if (v3 > v1 && v3 > v2)
    System.out.println ("Move to the right node.");
else
    System.out.println ("?");
}

After building the game tree (shown in Figures 1 and 2), the code fragment invokes the computeMinimax method on the left, center, and right child nodes of the root node. Those numbers are then compared with each other to determine the maximum, and an appropriate message outputs to indicate which move to take. When you run this program, you'll discover that the optimal move is to the right node.

Note: The observant reader will notice something strange about the code fragment: System.out.println ("?");. Although that method call is not chosen when the code fragment executes, it illustrates an important point that must be considered in the console-based and GUI-based versions of Nim: scenarios exist where all child nodes have the same minimax number. For example, consider a Nim game with an initial pile of six matches. Suppose you remove one match, leaving five. The three immediate child nodes of the node representing five matches all have the same minimax number. What is the optimal move in this and similar scenarios? Part 2 of this series answers that question.

What does computeMinimax look like? Check out the following code fragment:

static int computeMinimax (Node n)
{
   int ans;
   if (n.nmatches == 0)
       return (n.player == 'A') ? 1 : -1;
   else
   if (n.player == 'A')
   {
       ans = Math.max (-1,
                       computeMinimax (n.left));
       if (n.center != null)
       {
           ans = Math.max (ans,
                     computeMinimax (n.center));
           if (n.right != null)
               ans = Math.max (ans,
                      computeMinimax (n.right));
       }
   }
   else
   {
       ans = Math.min (1,
                       computeMinimax (n.left));
       if (n.center != null)
       {
           ans = Math.min (ans,
                       computeMinimax (n.center));
           if (n.right != null)
               ans = Math.min (ans,
                       computeMinimax (n.right));
       }
   }
   return ans;
}

The computeMinimax method is recursive in nature. It begins with code that determines if its Node argument represents a terminal configuration node. If that is the case (n.matches contains 0), the evaluation function, which consists of a simple statement that returns 1 if the player field contains A or -1 if that field contains B, executes. Otherwise, the method "knows" it is dealing with some parent node.

If the parent node's player field contains A, the method recursively obtains the maximum of the parent node's child node numbers. Care is taken to ensure that only existing child nodes are examined, to avoid a NullPointerException object being thrown. That maximum is then returned. Similarly, if the player field contains B, the method recursively obtains the minimum of the parent node's child node numbers and returns the result.

Conclusion

Computer games are entertaining and can reduce stress. If you have ever wanted to create your own version of a computer game, the simplicity of Nim makes it an excellent choice. In this article, after learning how to play Nim, you discovered game trees and the minimax algorithm for creating an intelligent computer player.

As usual, there is some homework for you to accomplish:

• The number of nodes in Nim's game tree grows quite rapidly as the initial number of matches increases slightly. For example, one match yields two nodes, two matches yield four nodes, three matches yield eight nodes, and four matches yield 15 nodes. For 21 matches, how many nodes are created?

• If you cannot store an entire game tree in memory because of its size, how could you adapt minimax to work with such a game tree?

Next month's Java Tech creates console-based and GUI-based Nim computer games. Each game applies this article's knowledge to its intelligent computer player.

Answers to Previous Homework

The previous Java Tech article presented you with some challenging homework on variable arguments. Let's revisit that homework and investigate solutions.

Problem 1
Is void foo (String ... args, int x) { } legal Java code? Why or why not?

Solution
void foo (String ... args, int x) { } is not legal Java code. It is not legal because args must be the rightmost parameter. Why? Consider a slightly different method header: void foo (int ... args, int x). Furthermore, consider the method call foo (10, 20, 30). Should 30 belong to args or to x? Obviously, we must assign 30 to x because each parameter must have a matching argument (or arguments, as in the case of a variable arguments parameter). However, the comma-delimited list implies that 30 belongs to args. Because Java cannot tolerate ambiguities, it enforces the rule that the variable arguments parameter must be the rightmost parameter.

Problem 2
Create a PrintFDemo application that demonstrates many of the formatting options made available by Formatter.

Solution
Consult the PrintDemo.java source code in this article's nim1.zip file.

Jeff Friesen is a freelance software developer and educator specializing in Java technology. Check out his site at javajeff.mb.ca.