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⁵). 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.