In this section we will describe some basic aspects of what constitutes a good chess program on a sequential computer. Having done this, we will be able to intelligently discuss the parallel algorithm.
At present, all competitive chess programs work by searching a tree of possible moves and countermoves. A program starts with the current board position and generates all legal moves, all legal responses to these moves, and so on until a fixed depth is reached. At each leaf node, an evaluation function is applied which assigns a numerical score to that board position. These scores are then ``backed up'' by a process called minimaxing, which is simply the assumption that each side will choose the line of play most favorable to it at all times. If positive scores favor white, then white picks the move of maximum score and black picks the move of minimum score. These concepts are illustrated in Figure 14.3.
Figure 14.3: Game Playing by Tree Searching. The top half of the figure
illustrates the general idea: Develop a full-width tree to some
depth, then score the leaves with the evaluation function, f. The
second half shows minimaxing-the reasonable supposition that white
(black) chooses lines of play which maximize (minimize) the score.
The evaluation function employed is a combination of simple material balance and several terms which represent positional factors. The positional terms are small in magnitude but are important since material balance rarely changes in tournament chess games.
The problem with this brute-force approach is that the size of the tree
explodes exponentially. The ``branching factor'' or number of legal moves
in a typical position is about 35. In order to play master-level chess
a search of depth eight appears necessary, which would involve a tree of
or about 
leaf nodes.
Fortunately, there is a better way. Alpha-beta pruning is a technique which always gives the same answer as brute-force searching without looking at so many nodes of the tree. Intuitively, alpha-beta pruning works by ignoring subtrees which it knows cannot be reached by best play (on the part of both sides). This reduces the effective branching factor from 35 to about 6, which makes strong play possible.
The idea of alpha-beta pruning is illustrated in Figure 14.4.
Assume that all child nodes are searched in the order of left to right in the
figure. On the left side of the tree (the first subtree searched), we have
minimaxed and found a score of +4 at depth one. Now, start to analyze the
next subtree. The children report back scores of +5, -1, 
. The
pruning happens after the score of -1 is returned: since we are taking
the minimum of the scores +5, -1, 
, we immediately have a bound on
the scores of this subtree-we know the score will be no larger than -1.
Since we are taking the maximum at the next level up (the root of the tree)
and we already have a line of play better than -1 (namely, the +4
subtree), we need not explore this second subtree any further. Pruning
occurs, as denoted by the dashed branch of the second subtree. The process
continues through the rest of the subtrees.
Figure: Alpha-Beta Pruning for the Same Tree as
Figure 14.3. The tree is generated in left-to-right
order. As soon as the score -1 is computed, we immediately have a
bound on the level above (
) which is below the score of the +4
subtree. A cutoff occurs, meaning no more descents of the 
node
need to be searched.
The amount of work saved in this small tree was insignificant but alpha-beta becomes very important for large trees. From the nature of the pruning method, one sees that the tree is not evolved evenly downward. Instead, the algorithm pursues one branch all the way to the bottom, gets a ``score to beat'' (the alpha-beta bounds), and then sweeps across the tree sideways. How well the pruning works depends crucially on move ordering. If the best line of play is searched first, then all other branches will prune rapidly.
Actually, what we have discussed so far is not full alpha-beta pruning, but merely ``pruning without deep cutoffs.'' Full alpha-beta pruning shows up only in trees of depth four or greater. A thorough discussion of alpha-beta with some interesting historical comments can be found in Knuth and Moore [Knuth:75a].