Alpha-beta pruning

If the average number of legal moves from any position in a game of chess is 35 then doing
a complete search of a game tree of depth 5 would require the generation of over 50 million
positions (35^{5}).
Rival reduces the enormous amount of work that the negamax procedure must carry out by using
the technique of alpha-beta pruning.

There are many positions in a game tree that can be safely ignored without affecting the value of the root node.

In figure 2, once node *b* has been fully examined, the player at ply 1 knows that a move
is available that is worth at least -3. When the search moves to node *c*, it is known
that any score that is greater than or equal to +3 will not be adequate when negated at
node *a*. If then, such a value is discovered, no more branches from node *c* need
be examined.

When node *c* receives the value -4 from node *d* and negates this to +4, it is known
that the value at node *c* will be at least +4. From the viewpoint of node *a*,
this equates to a value of no more than -4. Therefore, node *e* need not be evaluated.
In a larger tree, this would cut off the many sub branches that may grow from node *e*.

Also, in larger trees, the values that cause cut-offs can be passed the full depth of the
tree. For example, once node *c* is informed that it must gain a value of <+3 to be
of interest to node *a*, it can inform nodes *d* and *e* that they must score
more than -3. This would not cause any immediate cut-offs as all moves would need to be
examined before determining whether a value of more than -3 is available. However, this
value could be passed to any children of nodes *d* and *e* where a cut-off would
then occur if a value greater than or equal to +3 was discovered.

The term alpha-beta pruning was originally applied to the minimax algorithm with alpha and beta representing the best values found so far in the tree for each of the two players. Rival implements the procedure within a negamax framework as follows:

At the beginning of the search the values of two function parameters, *lowest* and
*highest*, are set to -infinity and +infinity respectively. If ever a move scores
higher than the value of *lowest*, that value is placed in *lowest*. The negated
value of *lowest* is passed to the next level of the tree as *highest*.
If any move scores higher than or equal to *highest* then no more moves are searched
from the position at the current depth. The negated value of *highest* is passed to
the next level of the tree as *lowest* so that it may be negated and passed as
*highest* to the level yet one ply deeper.

Concisely, *lowest* starts as the
negated value of the previous ply's *highest* and is used to calculate the value of
the next ply's *highest*.

Alpha-beta pruning is massively effective in reducing the number of nodes that need to be searched in a game tree. It becomes clear that if better moves are considered first at every node, more cutoffs will occur. Knuth & Moore (1975) proved that if the best move is considered first at each node, the number of nodes that will be searched in a game tree of depth D with a branching factor of B, is.

B^{[D/2]} + B^{[D/2]} - 1

Although we do not expect to achieve perfect move ordering, the reduction in tree size is considerable.

The program keeps a record of the best move at each position visited during the search. At each ply in the tree, the program has access to the best sequence of moves examined below the position currently being examined at that ply. This information is primarily used for display purposes, although it is useful when ordering moves at a later stage in the search in an attempt to maximise the number of alpha-beta cut-offs.

In early versions of Rival it was noted that the function that determines whether a side is in check in a given position was slowing the search down significantly due to the number of times it was being called. In particular, the function was being called every time a move was generated to see if the move left the side making the move in check. Due to alpha-beta cut-offs, many generated moves are never used and for this reason Rival leaves the responsibility of certain time-intensive move verifications to the function that makes a move to create a new position in the tree.