Recursion - Data Structures and Problem Solving Using Java - page 334

figure 7.26
Class to store an
evaluated move

1 final class Best
2 {
3 int row;
4 int column;
5 int val;
6
7 public Best( int v )
8 { this( v, 0, 0 ); }
9
10 public Best( int v, int r, int c )
11 { val = v; row = r; column = c; }
12 }

including routines to clear the board, to test whether a square is occupied, to
place something on a square, and to test whether a win has been achieved. The
implementation details are provided in the online code.
The challenge is to decide, for any position, what the best move is. The
routine used is chooseMove . The general strategy involves the use of a back-
tracking algorithm. A backtracking algorithm uses recursion to try all the pos-
sibilities.

The basis for making this decision is positionValue , which is shown in
Figure 7.28. The method positionValue returns HUMAN_WIN , DRAW , COMPUTER_WIN ,
or UNCLEAR , depending on what the board represents.
The strategy used is the minimax strategy, which is based on the assump-
tion of optimal play by both players. The value of a position is a COMPUTER_WIN
if optimal play implies that the computer can force a win. If the computer can
force a draw but not a win, the value is DRAW ; if the human player can force a
win, the value is HUMAN_WIN . We want the computer to win, so we have
HUMAN_WIN < DRAW < COMPUTER_WIN .
For the computer, the value of the position is the maximum of all the val-
ues of the positions that can result from making a move. Suppose that one
move leads to a winning position, two moves lead to a drawing position, and
six moves lead to a losing position. Then the starting position is a winning
position because the computer can force the win. Moreover, the move that
leads to the winning position is the move to make. For the human player we
use the minimum instead of the maximum.
This approach suggests a recursive algorithm to determine the value of a
position. Keeping track of the best move is a matter of bookkeeping once the
basic algorithm to find the value of the position has been written. If the posi-
tion is a terminal position (i.e., we can see right away that Tic-Tac-Toe has
been achieved or the board is full without Tic-Tac-Toe), the position's value is
immediate. Otherwise, we recursively try all moves, computing the value of

The minimax strat-
egy is used for Tic-
Tac-Toe. It is based
on the assumption
of optimal play by
both sides.