Java Tech: An Intelligent Nim Computer Game, Part 2 Blog


    Console-Based Nim
       Numeric Input
    GUI-Based NIM
       Match Drag-and-Drop
    Special Effects
       Sound Effects
       Image Effects
    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 themain method in the ConNim application (see the nim2.zipfile 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 =; 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 = ( != null) ? computeMinimax ( : 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 =; 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 ( != 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'sjava.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 = (); 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 theStringBuffer 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 withIOException objects that are thrown 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 anIOException), Java requires this class of exception to be handled (or declared in a throws clause).

    GUI-Based NIM

    Let's face it: after a few rounds, console-based Nim loses its appeal. Some of that loss is due to the predictable nature of the game, which results from the small number of matches (11) in the initial pile. Although a larger initial pile would make game play less predictable, the resulting game tree would require more memory. At some point, we wouldn't be able to fit the entire game tree into memory, and would need to redesign console-based Nim's game tree and minimax logic.

    I believe most of console-based Nim's loss of appeal is due to its lack of a GUI. GUIs are fun to look at and interact with: they invite users to play, which is why a GUI-based version of Nim is needed. Figure 1 shows that version's GUI.

    Figure 1's GUI is more interesting than ConNim's console output. It reveals two match-pile images and a draggable grid of matches. The human player uses the mouse to select 1, 2, or 3 matches; and then drags the matches to the human player's match pile, where they are dropped (and disappear). The computer player then selects 1, 2, or 3 matches, and they also disappear. (We can assume the matches were dragged to the computer player's match pile before vanishing.) After the last match has been taken,GuiNim presents a message box that announces the winning player and lets the human player make a choice to continue the game or not.

    Figure 1
    Figure 1. GUI-based Nim reveals a draggable grid of matches and match pile images

    The GUI shown in Figure 1 was built by the GuiNimapplication. (See the file for that application's source code.) The application consists of four classes: the GuiNim driver, the GamePanelcomponent, and Match and Node component support classes. GuiNim's source code appears below:

    public class GuiNim extends JFrame { public GuiNim (String title) { // Display title in frame window's title // bar. super (title); // Exit program when user clicks the X // button in the title bar. setDefaultCloseOperation (EXIT_ON_CLOSE); // Create the game panel. Add it to the // frame window's content pane, so that it // occupies the entire client area. getContentPane ().add (new GamePanel (this)); // Pack all components to their preferred // sizes. pack (); // Prevent user from resizing frame window. setResizable (false); // Display frame window and all contained // components. setVisible (true); } public static void main (String [] args) { // Create GUI and start the game. new GuiNim ("Gui-based Nim"); } }

    GuiNim's source code reveals a Swing application. The constructor adds a GamePanel component to the non-resizable frame window's content pane.

    GamePanel is a big class. Its constructor builds an eleven-match game tree, loads the logo and match pile images, creates an eleven-element array of Match objects, and installs listeners that detect "mouse button pressed," "mouse button released," and "mouse dragged" events. (I examine these listeners in the next section.) GamePanel also introduces methods to build the game tree, compute a minimax value, ask the user if they want to continue the game, return theGamePanel component's preferred size (that is used by the content pane's layout manager), paint the component, reorderMatch objects (so that onscreen matches drag over and not under other onscreen matches), and reset the game (if the user chooses to play another round). The source code toGamePanel's paint method appears below:

    public void paint (Graphics g) { super.paint (g); // Clear background to white. g.setColor (Color.white); g.fillRect (0, 0, getWidth (), getHeight ()); // Establish text color and font. g.setColor (; g.setFont (new Font ("Arial", Font.BOLD, 14)); // Get font metrics for centering labels. FontMetrics fm = g.getFontMetrics (); // Draw centered labels. String s = "Computer Player's Pile"; g.drawString (s, (pilew-fm.stringWidth (s))/2, 30); s = "Human Player's Pile"; g.drawString (s, getWidth ()-pilew+ (pilew-fm.stringWidth (s))/2, 30); // Draw match-pile images. g.drawImage (pile.getImage (), 0, 50, this); g.drawImage (pile.getImage (), width-pilew, 50, this); // Draw logo image. g.drawImage (logo.getImage (), (width-logow)/2, 50, this); // Draw all non-dropped matches. for (int i = NMATCHES-1; i >= 0; i--) if (!matches [i].isDropped ()) matches [i].draw (g); }

    There is a definite order to the way paint works: images and text are painted before the onscreen versions of all non-dropped Match objects. (After all, we don't want to hide onscreen matches behind images or text.)

    Onscreen matches are backed by Match objects. That class provides a constructor, and methods to determine if the mouse coordinates locate within the boundaries of an onscreen match, draw the match, and handle match dropping and selection.Match's draw method, which draws the associated onscreen match, appears below:

    void draw (Graphics g) { // Draw a match's outline. g.setColor (; g.drawRect (ox, oy, MATCHWIDTH, MATCHHEIGHT); // Fill a match's interior with white pixels // (if selected is false). Otherwise, fill the // interior with cyan pixels. g.setColor ((!selected) ? Color.white : Color.cyan); g.fillRect (ox+1, oy+1, MATCHWIDTH-1, MATCHHEIGHT-1); // Fill the top of the match (outline and // interior) with red pixels. g.setColor (; g.fillRect (ox, oy, MATCHWIDTH+1, 5); }

    The ox and oy variables identify the origin for the onscreen match. That origin is the upper-left corner. If the match hasn't been selected, the variableselected is false, and a white onscreen match is drawn. But if that variable is true, the onscreen match is colored cyan, to emphasize that it has been selected by the human player.

    Note: because you've seen the Node class in the last installment, I have nothing to say about that class.

    Compile GuiNim's source code and run the resulting application to play GUI-based Nim. Figure 2 reveals a pair of selected matches being dragged to the human player's pile.

    Figure 2
    Figure 2. Dragging matches to the human player's pile of matches

    Match Drag-and-Drop

    GuiNim features a more intuitive way thanConNim for obtaining, from the human player, the number of matches to take from the pile: match drag-and-drop. That input technique involves selecting 1, 2, or 3 onscreen matches, dragging them to some destination, and dropping them at that destination.

    Match drag-and-drop is implemented as a pair of listeners created in GamePanel's constructor: a mouse listener and a mouse motion listener. For simplicity, match drag-and-drop does not rely on the Abstract Windowing Toolkit's drag-and-drop API. If you would like to learn about the AWT's drag-and-drop API, consult the Java 2 SDK documentation on thejava.awt.dnd package.

    The mouse listener is an object created from an anonymous inner class that subclasses java.awt.event.MouseAdapter. Similarly, the mouse motion listener is an object created from an anonymous inner class that subclassesjava.awt.event.MouseMotionAdapter. Certain methods in each listener are overridden to achieve match drag-and-drop:

    • MouseAdapter's mousePressed method handles selection. It first obtains the current mouse pointer coordinates, then locates the Match object corresponding to the onscreen match over which the mouse pointer is hovering, and finally uses that object to select the associated onscreen match. If the Shift key is not being held down, the previously selected onscreen match is deselected prior to the new onscreen match being selected. But if Shift is held down, the newly selected onscreen match is added to a group of (at most) three selected onscreen matches, possibly replacing the most recently selected onscreen match (if the group is full). When an onscreen match is selected, its color changes to cyan, to provide positive visual feedback to the user.

    • MouseAdapter's mouseReleased method handles dropping. It checks if the Shift key is being held down. If so, no drop is performed. The reason: the human player may still be selecting onscreen matches in preparation for a drag operation. If Shift is not being held down, the drop operation occurs, provided at least one of the selected matches is droppable: it locates over (or near) the human player's pile.

    • MouseMotionAdapter's mouseDraggedmethod handles dragging. If at least one onscreen match has been selected, it obtains the current mouse pointer coordinates and moves each selected onscreen match to the new location specified by its associated Match object, provided all onscreen matches would lie completely within the bounds of theGamePanel component after the move. (We don't want to move onscreen matches past the component's boundaries, because that would likely confuse the user.)

    Match drag-and-drop also keeps track of a drag origin and reorders Match objects as necessary. The drag origin creates a relative displacement during dragging, so that each onscreen match moves the same relative amount. ReorderingMatch objects causes onscreen matches to drag over (instead of under) other onscreen matches. Furthermore, reordering ensures that moving the mouse pointer over an onscreen match, that locates on top of another onscreen match, and then pressing the mouse button, results in the top onscreen match (instead of the bottom onscreen match) being selected.

    Note: the match drag-and-drop technique can be generalized to drag any kind of graphics shape (which is backed by an object) around the screen, and then drop the shape at a destination. Before you can do that, however, it's important to understand that technique. Because the GamePanel class is big and contains unrelated code, it might be difficult to fully understand match drag-and-drop. For that reason, I'm providing twoMatchDrag applets, whose source codes are completely specific to the match drag-and-drop technique.MatchDrag1 focuses on selecting and dragging one match around the applet's drawing area; MatchDrag2, whose logic I used in GuiNim, focuses on selecting 1, 2, or 3 matches, dragging them around the drawing area, and finally dropping them. (See this article's file for the source code of both applets.) If you'd like to adapt match drag-and-drop to other graphics shapes, I recommend that you first study both applets.

    Special Effects

    GuiNim is much more fun to play thanConNim. And yet GuiNim is still somewhat lacking in aesthetics that would make it even more entertaining. In this section, I propose two enhancements to improve game play: sound effects and image effects.

    Note: you can add further enhancements to GuiNim, such as letting the user enter his or her name, displaying the user's name along with a number that identifies the current round and the number of rounds the user has won, saving user information to a file, and loading/displaying info associated with the user who has achieved the highest number of won rounds. Because these improvements aren't difficult to achieve, I leave it to you to supply them for your own version of GuiNim.

    Sound Effects

    When the human player drops one or more matches onto his or her match pile, we should hear a sound that positively reinforces that action. The simplest way to accomplish that task is to employjava.awt.Toolkit's public abstract void beep() method. Because hearing a simple beep isn't that entertaining, I think we should play some arbitrary .wav file, such as drop.wav.

    How do we play the .wav file? The traditional approach (from an applet perspective) is to use java.applet.Applet'spublic static final AudioClip newAudioClip(URL r)method. However, that approach means the application is tied to applet functionality, and that functionality is not guaranteed to be present on all platforms. A better approach is to use the JavaSound API, which was first integrated into version 1.3 of the core Java platform.

    I've created a playSound method that fully encapsulates the JavaSound logic needed to play the drop.wavfile that accompanies this article. That method's source code appears below:

    import*; import javax.sound.sampled.*; // ... private void playSound (File file) { try { // Get an AudioInputStream from the // specified file (which must be a // valid audio file, otherwise an // UnsupportedAudioFileException // object is thrown). AudioInputStream ais = AudioSystem.getAudioInputStream (file); // Get the AudioFormat for the sound data // in the AudioInputStream. AudioFormat af = ais.getFormat (); // Create a DataLine.Info object that // describes the format for data to be // output over a Line. DataLine.Info dli = new DataLine.Info (SourceDataLine.class, af); // Do any installed Mixers support the // Line? If not, we cannot play a sound // file. if (AudioSystem.isLineSupported (dli)) { // Obtain matching Line as a // SourceDataLine (a Line to which // sound data may be written). SourceDataLine sdl = (SourceDataLine) AudioSystem.getLine (dli); // Acquire system resources and make // the SourceDataLine operational. (af); // Initiate output over the // SourceDataLine. sdl.start (); // Size and create buffer for holding // bytes read and written. int frameSize = af.getFrameSize (); int bufferLenInFrames = sdl.getBufferSize () / 8; int bufferLenInBytes = bufferLenInFrames * frameSize; byte [] buffer = new byte [bufferLenInBytes]; // Read data from the AudioInputStream // into the buffer and then copy that // buffer's contents to the // SourceDataLine. int numBytesRead; while ((numBytesRead = (buffer)) != -1) sdl.write (buffer, 0, numBytesRead); } } catch (LineUnavailableException e) { } catch (UnsupportedAudioFileException e) { } catch (IOException e) { } }

    Because the method is fully commented, I won't elaborate further on what is happening. (For more information, please consult the SDK documentation on the various classes and interfaces that make up JavaSound.) However, note that the three exception handlers are empty: the user is only notified that there's a problem if a sound cannot be heard. I chose not to pop up a message box, because the user really doesn't want to see that box pop up each time he or she drags one or more matches to his or her match pile (and drops them).

    The playSound method requires argument that identifies the .wav file to play. To avoid the excessive creation of File objects, I've created a DROP_SOUND constant, which is passed toplaySound, as follows:

    private final static File DROP_SOUND = new File ("drop.wav"); // ... playSound (DROP_SOUND);
    Image Effects

    Is the display of a message box that announces the winner enough feedback when a player wins? Why not make the screen ripple, shoot off some fireworks, or offer some other kind of visual pizzazz? To keep this article from becoming too large, I've settled on something simple: flash both match pile images. To accomplish that task, we first need to create a negative match pile image. The following code fragment does just that:

    private ImageIcon pileNeg; // ... int [] pixels = new int [pilew*pileh]; java.awt.image.PixelGrabber pg; pg = new java.awt.image.PixelGrabber (pile.getImage (), 0, 0, pilew, pileh, pixels, 0, pilew); try { pg.grabPixels (); } catch (InterruptedException e) { } for (int i = 0; i < pixels.length; i++) pixels [i] = pixels [i] ^ 0xffffff; java.awt.image.MemoryImageSource mis; mis = new java.awt.image.MemoryImageSource (pilew, pileh, pixels, 0, pilew); pileNeg = new ImageIcon (createImage (mis));

    The code fragment above grabs the pile-referenced image's pixels and stores them in a pixels array. Each array element's RGB (red, green, blue) value is then inverted via the exclusive or operator. Finally, those RGB values are combined into a brand-new image that pileNeg references.

    Flashing the match pile images requires animation logic, which must appear in two places within GamePanel's mouse released listener -- before both calls to thecontinueGame method. The animation logic is provided by the code fragment below:

    final ImageIcon oldPile = pile; ActionListener al; al = new ActionListener () { public void actionPerformed (ActionEvent e) { repaint (); if (pile == oldPile) pile = pileNeg; else pile = oldPile; } }; Timer t = new Timer (ANIM_DELAY, al); t.start (); boolean continuePlay; continuePlay = continueGame ("Computer player " + "wins. Play again?"); t.stop (); pile = oldPile; repaint ();

    The animation logic begins by saving pile'sImageIcon reference, so that the original image can be restored following the animation. (When we stop the animation, we don't want the negative image to be displayed. Not only is that unsightly, pile is referencing the negative match pile image. If we don't restore pile to the original image's reference, we lose that reference and no more animations are visible.)

    The logic next creates an object from an anonymous inner class that implements the java.awt.event.ActionListenerinterface. Each call to that object's actionPerformedmethod generates one frame of animation: first it repaints theGamePanel's drawing surface (in response to therepaint (); method call), and then it sets thepile variable to either the original image's reference (which was previously saved in oldPile) or the negative image's reference (in pileNeg). This is done because GamePanel's paint method (which is responsible for painting that component's drawing surface) displays whatever image is referenced by pile.

    A timer is created, by way of javax.swing.Timer, after creating the ActionListener object. That timer handles the animation, once its start method is called. Each timer event invokes the listener'sactionPerformed method. Following the call, the timer pauses for the number of milliseconds specified by theANIM_DELAY constant -- to give the user a chance to view the animation.

    Subsequent to the display of the "continue game" message box and the retrieval of the user's continuation choice, the animation is stopped, pile is reset to the reference previously stored in oldPile (in case pile contains the pileNeg reference), and a final repaint occurs (in case the negative match pile image is currently displayed).


    We put the game tree and minimax tools to good use as we created console-based and GUI-based Java versions of Nim. We learned how those versions work and how they obtain their "number of matches" input from the user: simple integer input or match drag-and-drop (also applicable to other kinds of game objects, such as chess or checker pieces). What is a game without special effects? We added a sound effect and an image effect to the GUI-based Nim game, to make it more entertaining.

    Once again, there is some homework for you to accomplish:

    • Modify ConNim, so that it uses theScanner class to handle input from the user.

    • GuiNim's onscreen match drag-and-drop logic reveals a quirk. You've selected 1, 2, or 3 onscreen matches while pressing the Shift key, released that key after releasing the mouse button, and noticed that all selected onscreen matches still appear cyan (meaning they are selected). You can deal with the quirk by moving the mouse pointer to a blank area of the screen and then clicking the mouse button, or by releasing the Shift key before releasing the mouse button. Can you think of some better way to handle this quirk?

    Next month's Java Tech explores the basics of thread synchronization and looks at Java 1.5'sjava.util.concurrent.Semaphore class.

    Answers to Previous Homework

    The previous Java Tech article presented you with some challenging homework on the game tree and minimax tools. Let's revisit that homework and investigate solutions.

    1. The number of nodes in Nim's game tree grows quite rapidly as the initial number of matches increases slightly. For example, 1 match yields 2 nodes, 2 matches yield 4 nodes, 3 matches yield 8 nodes, and 4 matches yield 15 nodes. For 21 matches, how many nodes are created?

      For 21 matches, the number of nodes in Nim's game tree equals 489,396. How did I obtain this number? One technique: place the expression count++ at the start of the methodbuildGameTree, and output count's value after calling that method. Another (somewhat cumbersome) technique: take advantage of the Nim game tree property where the number of nodes associated with the number of matches x (x must be greater than 3) is 1 plus the sum of the node counts forx-1, x-2, and x-3 matches. For example, 1+15+8+4 (28) nodes are created when the number of matches is 5.

    2. 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?

      When an entire game tree cannot be stored in memory, minimax can be adapted to work with part of the game tree by integrating thealpha-beta pruning technique into that algorithm. I will explore the alpha-beta pruning technique in a future installment of Java Tech.