Tree search is one of the central algorithms of any game playing program. The term is based on looking at all possible game positions as a tree, with the legal game moves forming the branches of this tree. The leaves of the tree are all final positions, where the outcome of the game is known. The problem for most interesting games is that the size of this tree is tremendously huge, something like W^D, where W is the average number of moves per position and D is the depth of the tree, Searching the whole tree is impossible, mainly due to lack of time, even on the fastest computers. All practical search algorithms are approximations of doing such a full tree search.
These pages give an overview of traditional, fixed depth minimax search, with various refinements such as selective extensions and pruning, as used in most modern chess programs. There are other, more experimental, game tree search techniques that take a different approach, like e.g. B* and conspiracy numbers, which I hope to describe at a later time.
This overview covers the follwoing subjects:
-
- MiniMax and NegaMax
- Alpha-Beta search
- Aspiration search
- Transposition table
- Iterative Deepening
- Principal Variation Search
- Memory Enhanced Test
- Enhanced Transposition Cutoff
- Killer heuristic
- History heuristic
- Null move heuristic
- Quiescence search
- Selective extensions
The various search algorithms are illustrated in a compact pseudo-C. The
variables and functions used have the following meaning:
| pos | A position in a chess game. |
| depth | The number of levels in the tree to be searched. |
| Evaluate | A function that determines a value for a position as seen for the side to move. In practice such a function will be composed of the difference in material values and a large number of positional terms. Results lie between –INFINITY and INFINITY. |
| best | The best value seen while searching the next level in the tree. |
| Successors | A function that determines the set of all positions that can be reached from a position in one move (move generation). |
| succ | The set of positions reachable form the input position by doing one move. |
MiniMax and NegaMax
Finding the best move for some position on the chess board means searching through a tree of positions. At the root of the tree we search for the best successor position for the player to move, at the next level we search for the best succesor position from the standpoint of the opponent, and so on. Chess tree search is an alternation between maximizing and minimizing the value of the positions in the tree; this is often abbreviated to minimaxing. To remove the distinction between own and opponent position, the value
of a position is always evaluated from the standpoint of the player to move, i.e by negating the value as seen by the opponent; this is called negamaxing. This is illustrated by the following C-like pseudo code:
int NegaMax (pos, depth)
{
if (depth 0) return Evaluate(pos);
best = -INFINITY;
succ = Successors(pos);
while (not Empty(succ))
{
pos = RemoveOne(succ);
value = -NegaMax(pos, depth-1);
if (value > best) best = value;
}
return best;
}
The number of positions that has to be searched by this algorithm is W^D, where W is the width of the tree (average number of moves possible in each position) and D is the depth of the tree (^ indicates exponentiation). This is extremely ineffcient and would even hold back a supercomputer from reaching greater depths.
Alpha-Beta search
Alpha-Beta search is the first major refinement for reducing the number of positions that has to be searched and thus making greater depths possible in the same amount of time. The idea is that in large parts of the tree we are not interested in the exact value of a position, but are just interested if it is better or worse than what we have found before. Only the value of the psoition along the principal variation has to be determined exactly (the principle variation is the alternation of best own moves and best opponent moves from the root to the depth of the tree).
The AlphaBeta search procedure gets two additional arguments which indicate the bounds between which we are interested in exact values for a position:
int AlphaBeta (pos, depth, alpha, beta)
{
if (depth 0) return Evaluate(pos);
best = -INFINITY;
succ = Successors(pos);
while (not Empty(succ) && best < beta)
{
pos = RemoveOne(succ);
if (best > alpha) alpha = best;
value = -AlphaBeta(pos, depth-1, -beta, -alpha);
if (value > best) best = value;
}
return best;
}
The gain from AlphaBeta will come form the earlier exit from the while loop; a value of best that equals or exceeds beta is called a cutoff. These cutoffs are completely safe because they mean that this branch of the tree is worse than the prinicpal variation. The largest gain is reached when at each level of the tree the best successor position is searched first, because this position will either be part of the principal variation (which we want to establish as early as possible) or it will cause a cutoff to be as early as possible.
Under optimal circumstances AlphaBeta still has to search W^((D+1)/2) + W^(D/2) – 1 positions. This is much less than MiniMax, but still exponential. It allows to reach about twice the depth in the same amount of time. More positions will have to be searched if move ordering is not perfect.
Note: The version of AlphaBeta shown above is also known as fail-soft alpha-beta. It can return values outside the range alpha...beta, which can be used as upper or lower bounds if a re-search has to be done.
Aspiration search
Aspiration search is a small improvement on Alpha-Beta search. Normally the top level call would be AlphaBeta(pos, depth, -INFINITY, +INFINITY). Aspiration search changes this to AlphaBeta(pos, depth, value-window, value+window), where value is an estimate for the expected result and window is a measure for the deviations we expect from this value.
Aspiration search will search less positions because it uses alpha/beta limits already at the root of the tree. The danger is that the search result will fall outside the aspiration window, in which case a re-search has to be done. A good choice of the window variable will still give an average net gain.
Transposition table
The transposition table is a hashing scheme to detect positions in different branches of the search tree that are identical. If a search arrives at a position that has been reached before and if the value obtained can be used, the position does not have to be searched again. If the value cannot be used, it is still possible to use the best move that was used previously at that position to improve the move ordering.
A transposition table is a safe optimization that can save much time. The only danger is that mistakes can be made with respect to draw by repetition of moves because two positions will not share the same move history.
A transposition table can save up to a factor 4 on tree size and thus on search time. Because of the exponential nature of tree growth, this means that maybe one level deeper can be searched in the same amount of time.
Iterative Deepening
Iterative deepening means repeatedly calling a fixed depth search routine with increasing depth until a time limit is exceeded or maximum search depth has been reached. The advantage of doing this is that you do not have to choose a search depth in advance; you can always use the result of the last completed search. Also because many position evaluations and best moves are stored in the transposition table, the deeper search trees can have a much better move ordering than when starting immediately searching at a deep level. Also the values returned from each search can be used to adjust the aspiration search window of the next search, if this technique is used.
Principal Variation Search
Principal variation search is a variation of alpha-beta search where all nodes outside the principal variation are searched with a minimal window beta = alpha + 1. The idea is that with perfect move ordening all moves outside the principal variation will be worse than the principal variation; this can be proven by the minimal window search failing low. If the move ordening is imperfect, fail high may be encountered and in such a case a re-search has to be done with the full alpha-beta window. The expectation is that the gain of the minimal window search is higher than the loss of these occasional re-searches.
Has this been proven somewhere?
int PrincipalVariation (pos, depth, alpha, beta)
{
if (depth == 0) return Evaluate(pos);
succ = Successors(pos);
pos = RemoveOne(succ);
best = -PrincipalVariation(pos, depth-1, -beta, -alpha);
while (not Empty(succ) && best < beta)
{
pos = RemoveOne(succ);
if (best > alpha) alpha = best;
value = -PrincipalVariation(pos, depth-1, -alpha-1, -alpha);
if (value > alpha && value < beta)
best = -PrincipalVariation(pos, depth-1, -beta, -value);
else if (value > best)
best = value;
}
return best;
}
A further refinement of this is known as NegaScout. See Alexander Reinefeld’s on-line description (and article).
Memory Enhanced Test
Memory enhanced test is a family of search algorithms that have in common that at the top level an alpha-beta search is done with a minimal window beta = alpha+1. Differences can be found in the sequence of alpha-beta values that is tried. Because the top level search is called repeatedly with different alpha-beta parameters and the same depth, it is important to have a large transposition table in order to re-use partial search results from previous searches. See [TS95c] or Aske Plaat’s on-line description.
Enhanced Transposition Cutoff
Move ordering is important in tree search because it increases the chance of getting a cutoff on the first successor position searched. This is not always optimal; there may be several successors causing a cutoff and we want to use the one with the smalles search tree. One idea that has been tried is to look at all successor positions and see if they are in the transposition table and cause a cutoff. If one such position is found, no further serach has to be done. This can save about 20-25% in total tree size.
Killer heuristic
The killer heuristic is used to improve the move ordering. The idea is that a good move in one branch of the tree is also good at another branch at the same depth. For this purpose at each ply we maintain one or two killer moves that are searched before other moves are searched. A successful cutoff by a non-killer move overwrites one of the killer moves for that ply.
History heuristic
The history heuristic is another improvement method for the move ordering. In a table indexed by from and to square statistics are maintained of good cutoff moves. This table is used in the move ordering sort (together with other information such as capture gains/losses).
Null move heuristic
The null move heuristic is a method of skipping searches in parts of the tree where the position is good enoigh. This is tested by doing a null move (i.e. passing, doing no move at all) and then seraching with reduced depth. If the result of this is higher than beta, no further search is done; if the result is lower than beta we do a normal search.
The null move heuristic has big dangers because it can fail to detect deep combinations. On the other hand it can save a lot of time by skipping large parts of the search tree.
Quiescense search
Instead of calling Evaluate when depth=0 it is customary to call a quiescence search routime. Its purpose is to prevent horizon effects, where a bad move hides an even worse threat because the threat is pushed beyond the search horizon. This is done by making sure that evaluations are done at stable positions, i.e. positions where there are no direct threats (e.g. hanging pieces, checkmate, promotion). A quiescence search does not take all possible moves into account, but restricts itself e.g. to captures, checks, check evasions, and promotion threats. The art is to restrict the quiescence search in such a way that it does not add too much to the search time. Major debates are possible about whether it is better to have one more level in the full width search tree at the risk of overlooking deeper threats in the quiescence search.
Selective extensions
In the full width part of the tree, search depth can be increased in forced variations. Different criteria can be used to decide if a variation is forced; examples are check evasions, capturing a piece that has just captured another piece, promotion threats. The danger if used carelessly is an explosion in tree size.
A special case of selective extensions is the singular extension heuristic introduced in the Deep Thought chess program. The idea here is to detect forced variations by one successor position being sgnificantly better than the others. Implementation is tricky because in alpha-beta search exact evaluations are often not available.
It is said that the commercial chess programs use fractional depth increments to distiguish the quality of different moves; moves with high probabbility of being good get a lower depth increment than moves that seem bad. I have no direct references to this; the commercial chess programmers do not publish their techniques.
