Peg Game - Coach

It would be nice if our Peg Game application could keep the player from painting herself into a corner. Take the board to the right. The correct sequence of moves are: 7 to 9, 13 to 6, 10 to 3, and 1 to 6. If the player chooses 13 to 4 instead; then 7 can jump to 2, and 1 to 4. That would result in two pegs remaining: 4 and 10. So, our game needs to sound an alarm (e.g. draw a red dot) when the user asks for the 13 to 4 move.

Other interesting activities would include questions like:

The project

Write a quick-and-dirty program to find random solutions to the game. Write a second program that exhaustively searches for all solutions to the game. Finally, integrate the second program into the current model, DOS view, and Swing view.

Three iterations:

  1. Write a program that uses random moves to find solutions
  2. Write a program that uses depth first search to find every possible solution
  3. Integrate the second program into the results from the last chapter

Iteration 1

Write a program that can find as many solutions to the game as possible in a finite amount of time (like 40 or 50 thousand games). Produce output like the following. The initial hole position is listed first, followed by the 13 moves. Do not report duplicate moves. Sort the output before presenting it.

For this iteration, lets be exceedingly simple-minded. Randomly pick an initial hole position, and then randomly pick one random move after another.

Instructions and issues:

Iteration 2

Write a program that finds every possible solution to the Peg Game puzzle. Have the user specify where the initial space is located when she invokes the program. The following output is desirable. How can you algorithmically enumerate and test every possible pathway through the game? How do people do it when they play the game? A person could write down each move taken, and then when a dead-end is reached, backtrack one of more moves, and make a different choice.

A more methodical approach would be to create a tree that records all possible moves as the state of the game advances. Solutions are then found by identifying traversals of the tree that are 13 moves long (you start with 14 pegs and end with 1).

       

Here is an alternate representation that demonstrates four non-solutions. After 7 moves, the board has reached the state shown at the top. Four moves are now possible. If the 3-8 move is chosen, then two moves are possible. The 13-4 move eventually leads to three pegs remaining, and the 1-4 move leads to an end state of five pegs.

A graphical representation is optimal for carbon-based intelligence (i.e. people), but it doesnt map directly to silicon-based intelligence (computers). If we had a representation that was more sequential in nature (like a computers memory), then we could perhaps kill two birds with one stone: discuss a solution strategy for the problem, and, lay the foundation for the eventual algorithm.

Another issue with the graphical representation above is overhead. Modeling all the possible moves of a game as separate nodes in a fully populated tree consumes a lot of memory. As we come up with a more sequential encoding of the game, is there a way we could accommodate some kind of just in time representation? The motivation is to maintain as little game state as possible.

Instead of building a full-grown tree, perhaps a step-by-step list of lists representation will provide sufficient bookkeepping for: testing one specific game, backtracking to alternate games, and ultimately testing every possible game. How about the following procedure and data structure?

  1. generate a list of all possible initial moves
  2. execute the last move on the list, and replace it with a new list of all currently possible moves
  3. go to step 2
Here is a representation for the sequence of moves: 6-1, 15-6, 8-3, 14-5, 2-9 The board now looks like -  

To eliminate some clutter, let's focus only on the last list of moves. The steps remain: move, generate, replace.

At this point, the pegs remaining are 1, 6, 11; and there are no more possible moves.

We've hit a dead-end, and need to backtrack to an alternate pathway. Lets add a new step 3 to our procedure.

  1. generate a list of all possible initial moves
  2. execute the last move on the list, and replace it with a new list of all currently possible moves
  3. when a solution or dead-end is reached, backtrack (undo and remove moves) until a parent list with an unused move is found
  4. go to step 2
In our example, we need to undo the 4-6 move, and backtrack to the parent list. That list has no more unused moves, so we must repeat the process by undoing the 14-5 move and backtracking. Again, there are no more unused moves in the parent list, so the 7-9 move is undone as well. Finally, we have found an unused move - 7 to 2.

The top line below looks like the fourth line above - except - the 7-9 move at the end has been removed. We are ready to proceed forward again. As each last move of the last list is executed, there is only one possible move on the board. So, each replacement is performed with a list composed of a single move.

We now have a "sequential" representation of our puzzle. It should give us a good start on a search algorithm. Notice how the list demonstrates last in, first out behavior.

Our 4-step procedure seems to suggest a loop where step 4 feeds back to step 2. Would recursion be more, or less, useful?

Instructions and issues:

Iteration 3

Integrate the result from iteration 2 into the model and two views from the previous chapter. The DOS view should now alert the user of moves that are not legal, and moves that will result in a game that cannot be won. The Swing view should display a red dot in response to a bad move.

                <A>
    
             <B>   <C>
    
          <D>   <E>    f
    
        g     h    <I>    j
    
    <K>    l    <M>   <N>   <O>
    
    Move (from to): c e
    
    NOT A LEGAL MOVE
    
                <A>
    
             <B>   <C>
    
          <D>   <E>    f
    
        g     h    <I>    j
    
    <K>    l    <M>   <N>   <O>
    
    Move (from to): c h
    
    NOT A GOOD IDEA - TRY A BETTER MOVE
    
   
Instructions and issues:

Iteration 1 - implementation

The design chosen here is so simple-minded that no object-oriented leverage is necessary. A few functions and global variables are all that is required. Each attempt to generate a solution consists of: re-initialize all data structures, randomly select the location for the initial blank, randomly select moves until no more moves are possible. If the number of pegs remaining is one, record the sequence of moves. After 50 thousand games, quit. The TreeSet class is a very useful component. It is a collection resource that enforces a single instance of each contained object. If the user attempts to add the same solution string more than once, all subsequent add requests simply overwrite the original string. This property will allow us to screen out all duplicate solutions. Another useful property of TreeSet is that it maintains its elements in sorted order. Once the main processing loop has completed, the solutions object can be examined by using the standard idiom for traversing all Java collection classes. The pickHole() function above simply picks a random number between 0 and 15. The findMove() function is more interesting. The jumpTable data structure provides remarkable leverage with its linear representation of all candidate moves. We can use a random number to grab random moves. For the sake of efficiency, if we havent found a move after 15 tries, then resort to brute force and search the array from beginning to end.

We've seen the legalMove() function in previous chapters. What has been added here is storing each legal move in the moveList data structure.

Running the program in listing 6.1 many times produced a total number of solutions ranging from 231 to 288. Its amazing how hard it is for a person to find just one solution! Another interesting observation is: the initial hole can start in any position and the game can still be won.

If these questions were all we were interested in, this solution would be entirely sufficient. Depending on the projects requirements, a quick-and-dirty solution using random moves and sheer brute force could be more desirable than a vigorous solution.

Start stupid and evolve.   [Kent Beck]
Listing 6.1

Iteration 2 - implementation

Our first stab at a search algorithm is repeated here.
  1. generate a list of all possible initial moves
  2. execute the last move on the list, and replace it with a new list of all currently possible moves
  3. when a solution or dead-end is reached, backtrack (undo and remove moves) until a parent list with an unused move is found
  4. go to step 2
Step 1 refers to a list of initial moves, lets put that in a constructor. The notion of backtracking, or undoing and returning from whense we came, feels like a perfect opportunity for recursion. Steps 2 through 4 can be encapsulated in a recursive function depthFirstSearch().

Another indicator for the appropriateness of recursion is nested data. Our list data structure may contain any combination of atomic moves, or other lists. The definition of a list inextricably refers to itself.

Consider using recursion when the data contains instances of itself (i.e. is recursively-defined).
Finding all currently available moves is a simple matter of trying every move in the jumpTable data structure. Well append each move found to the end of an ArrayList attribute. Distinguishing each lower level list from its parent can be accomplished by remembering the number of sibling elements at each level. That knowledge is initiated by returning the number of moves pushed on the deferredMoveStack by the pushPossibleMovesOnDeferredMoveStack() methods. The last move pushed to the deferredMoveStack should be the first move removed and executed. Every recursive function needs a test to determine if recursion should stop. The recursion in depthFirstSearch() should not proceed in two situations: when there is a single peg left on the board, or, when all the moves pushed by pushPossibleMovesOnDeferredMoveStack() have been exhausted.

Because we want to traverse all possible pathways through the game; as the algorithm reverses itself in anticipation of processing unexplored sub-trees, the move done at the beginning of depthFirstSearch() must be undone.

The total number of games attempted can be computed by counting the number of leaf nodes in a tree representation like that at the start of this chapter. Leaf nodes represent solutions (one peg remaining) and dead-ends. If pushPossibleMovesOnDeferredMoveStack() identified one or more possible moves, that situation would represent an interior node in the tree, and should not be counted.

The "magic" in this program resides in the depthFirstSearch() method. What remains to be discussed is a little housekeeping. As moves are done, they are remembered in a queue called currentMoveList. When they are "undone", they are removed from the queue. When a solution is found, the queue is traversed, and the sequence of moves reported to a file and to standard out. Let's consider questions that were asked at the beginning of this chapter: Because of the symmetry of the board, we only need to consider 4 types of pegs:
  1. corner pegs (1, 11, 15)
  2. corner-adjacent pegs (2, 3, 7, 10, 12, 14)
  3. exterior middle pegs (4, 6, 13)
  4. interior pegs (5, 8, 9)
The total number of solutions exceeds 131,000. Granted, many (if not most) of these solutions are fairly simple variations of other solutions. But, it is remarkable to learn that the total number found in iteration 1 was entirely too small. We can easily confirm our symmetry assumption by specifying the initial hole positions of interest. The exterior middle positions can be utilized by twice as many moves as the other types of positions (they support four jumps, while the other position types only support two). Intuition might suggest that they should yield twice as many solutions. This is not the case. Intuition might also speculate that the interior peg positions are no less likely to yield a solution than their neighbors. And again, this is not true.
Intuition is serviceable for everything, sufficient for nothing.   [Adaptation of a quote from Henri-Frederic Amiel]
Listing 6.2

Iteration 3 - implementation

The goal is to enhance our game by warning the user when a poor move is requested. In the last chapter, the logic for determining a legal move was moved to the model component. Lets do the same for the logic that determines a poor move.

A good place to start is where the view asks the model to attemptMove(). The model will compute if the requested move has a successful future, and the view needs to know if the requested move is destined to fail. Lets change the return type of attemptMove() from void to String. The value of the returned string can then be displayed directly by the DOS view.

The code that processed the jumpTable data structure has been put in its own method - legalMove().

The requested move needs to be executed before a determination can be made on whether the success of the game is at risk. The code that manipulated the model's pegsPresent data structure has been encapsulated in a new method called doMove().

We are now ready to test if: the game has been won, or the game is capable of being won. For the former, the pegCount attribute was added. For the latter, the aSolutionIsPossible() method was created. For now, lets believe that this method is capable of unadulterated magic returning true if a solution is possible, and false otherwise.

Any sufficiently refined abstraction is indistinguishable from magic.   [Variation on Clarke's Third Law: "Any sufficiently advanced technology is indistinguishable from magic."]
If the requested move is valid and good, there is no error message to return to the view, so return null. Otherwise, the move needs to be undone, and the user needs to be politely slapped on the wrist. Lets return to the aSolutionIsPossible() method. It needs to return true if a solution is possible, and false otherwise. The attemptMove() method has already executed the requested move, so we are ready to identify the list of possible moves and launch the recursive search algorithm. This method is basically the constructor from the PegGameSolveSearch program.

Unlike the program in the last chapter, we are only interested in the first solution found - not trying to collect all possible solutions. As a result, depthFirstSearch() has been modified to return true or false as appropriate. This method needs the deferredMoveStack data structure, and that stack needs to be emptied out before aSolutionIsPossible() is called the next time.

The "magic" method - depthFirstSearch() - changes very little. When a solution is found, it needs to return true immediately. Otherwise, false is returned. In the for loop, whenever a recursive invocation of itself returns, one of two things has happened: a solution was found, or a dead-end was found. Regardless, the current invocation of the method should immediately clean-up and return. The pushPossibleMovesOnDeferredMoveStack() and possibleMove() methods from the previous chapter can be copied with no changes. The currentMoveList data structure is no longer needed, so the doMove() and undoMove() methods no longer need to update it.

The signature of the attemptMove() method has changed - so - both views need to be adapted. The DOS view needs to accept the string returned from the model and print it to standard out if it is not null.

In the Swing view, when a non-null string is returned by attemptMove(), a red dot needs to be thrown in the users face. The actual drawing could be done in the mousePressed() method, but what would happen if the Peg Game window is covered with another window, and then uncovered? The only part of the user interface that is reinstated is that which is drawn in the paint() method.

So, lets try this: add a new attribute (boolean redFlag), set it in mousePressed(), and get it in paint(). Because of the additional user interface wrinkle introduced by the red dot, life would be simpler if we removed all the drawPeg() calls in mousePressed(), and added a single repaint() call at the bottom.

Listing 6.3