chess tree search.htm

这是博弈论算法全集第八部分:综合论述,其它算法将陆续推出.以便与大家共享

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. 
<P>Under optimal circumstances <CODE>AlphaBeta</CODE> still has to search 
W^((D+1)/2) + W^(D/2) - 1 positions. This is much less than 
<CODE>MiniMax</CODE>, 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. 
<P><B>Note</B>: The version of <CODE>AlphaBeta</CODE> shown above is also known 
as fail-soft alpha-beta. It can return values outside the range 
<CODE>alpha...beta</CODE>, which can be used as upper or lower bounds if a 
re-search has to be done. 
<H2><A name=aspiration>Aspiration search</A></H2>
<P>Aspiration search is a small improvement on Alpha-Beta search. Normally the 
top level call would be <CODE>AlphaBeta(pos, depth, -INFINITY, 
+INFINITY)</CODE>. Aspiration search changes this to <CODE>AlphaBeta(pos, depth, 
value-window, value+window)</CODE>, where <CODE>value</CODE> is an estimate for 
the expected result and <CODE>window</CODE> is a measure for the deviations we 
expect from this value. 
<P>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 <CODE>window</CODE> variable will still give an 
average net gain. 
<H2><A name=transposition>Transposition table</A></H2>
<P>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. 
<P>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. 
<P>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. 
<H2><A name=iterative>Iterative Deepening</A></H2>
<P>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. 
<H2><A name=principal>Principal Variation Search</A></H2>
<P>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. 
<P>Has this been proven somewhere? <PRE>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) &amp;&amp; best &lt; beta)
    {
        pos = RemoveOne(succ);
        if (best &gt; alpha) alpha = best;
        value = -PrincipalVariation(pos, depth-1, -alpha-1, -alpha);
        if (value &gt; alpha &amp;&amp; value &lt; beta) 
            best = -PrincipalVariation(pos, depth-1, -beta, -value);
        else if (value &gt; best)
            best = value;
    }
    return best;
}
</PRE>
<P>A further refinement of this is known as NegaScout. See Alexander Reinefeld's 
on-line <A 
href="http://www.uni-paderborn.de/pc2/people/homes/ar/r_nsc.htm">description</A> 
. 
<H2><A name=memory-enhanced-test>Memory Enhanced Test</A></H2>
<P>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 <A 
href="http://theory.lcs.mit.edu/~plaat/mtdf.html">description</A> . 
<H2><A name=enhanced-transposition>Enhanced Transposition Cutoff</A></H2>
<P>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. 
<H2><A name=killer>Killer heuristic</A></H2>
<P>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. 
<H2><A name=history>History heuristic</A></H2>
<P>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). 
<H2><A name=null-move>Null move heuristic</A></H2>
<P>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. 
<P>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. 
<H2><A name=quiescence>Quiescense search</A></H2>
<P>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. 
<H2><A name=extensions>Selective extensions</A></H2>
<P>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. 
<P>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. 
<P>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. 
<HR>

<P><A href="http://www.nedstat.nl/cgi-bin/viewstat?name=pvesearch"><IMG 
align=left alt="[NedStat counter]" border=0 height=32 
src="Chess Tree Search.files/nedstat.gif" width=32> </A><A 
href="http://www.xs4all.nl/~verhelst/lynx-enhanced.html"><IMG align=right 
alt="[Enhanced for Lynx]" border=0 height=45 
src="Chess Tree Search.files/lynx-enhanced.gif" width=115> </A>
<CENTER>[<A href="http://www.xs4all.nl/">XS4ALL</A>] [<A 
href="http://www.xs4all.nl/~verhelst/">Home</A>] [<A 
href="http://www.xs4all.nl/~verhelst/stats/today.html">Statistics</A>] [<A 
href="http://www.xs4all.nl/~verhelst/chess/programming.html">Up</A>] [<A 
href="http://www.xs4all.nl/~verhelst/chess/representations.html">Previous</A>] 
[<A 
href="http://www.xs4all.nl/~verhelst/chess/sources.html">Next</A>]<BR>Comments 
to: Paul Verhelst (<A href="mailto:[e-mail]">[e-mail]</A>) 
</CENTER>
<HR>
</BODY></HTML>