Chess Tree Search
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.
Possibly related entries:
February 19th, 2005 at 17:44
A nice web page on the various techniques used in chess programming. I enjoyed reading up. I hope such gems will come up further from the author of the page and he shall help us novices understand easily the nitty gritties of programming in this field. looking forward to more articles.
March 3rd, 2006 at 14:41
Though I have just begun reading the web page but i feel it’s a good source to gain information about the kind of heuristic techniques & algorithms used in the chess programming. especially for novices like me its a good site to increase my chess programming skills.
August 2nd, 2006 at 3:01
thanks man, this info help me a lot to do my studies
September 26th, 2007 at 4:25
I personally tried my hand at computer chess programing. But it became so complex I lost track lol. anyways nice site.
December 11th, 2007 at 7:31
This has been very useful – thank you.
December 11th, 2007 at 15:55
A good chess program and how it works, including the use of fractional ply, I have found at http://members.home.nl/matador/chess840.htm