?? chess tree search.htm
字號:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0048)http://www.xs4all.nl/~verhelst/chess/search.html -->
<HTML><HEAD><TITLE>Chess Tree Search</TITLE>
<META content="text/html; charset=gb2312" http-equiv=Content-Type><LINK
href="programming.html" rel=UP><LINK href="sources.html" rel=NEXT><LINK
href="representations.html" rel=PREVIOUS>
<META content="MSHTML 5.00.2614.3500" name=GENERATOR></HEAD>
<BODY>
<SCRIPT language=JavaScript>
<!--
document.write("<img src=\"http://www.nedstat.nl/cgi-bin/referstat.gif?name=pvesearch&refer="+escape(top.document.referrer)+"\" width=1 height=1 alt=\"\">");
// -->
</SCRIPT>
<P><A href="http://www.aescon.com/innoval/everos2/"><IMG align=left
alt="[Ever Onward OS/2]" border=0 height=30
src="Chess Tree Search.files/everos2t.gif" width=143> </A><A
href="http://www.eff.org/blueribbon.html"><IMG align=right
alt="[Free Speech Online]" border=0 height=30
src="Chess Tree Search.files/freesp.gif" width=143> </A>
<CENTER>Last modified: 16 November 1997<BR>Accessed: <IMG
src="Chess Tree Search.files/usercounter.htm"> </CENTER>
<HR>
<!-- SpHyDir -->
<H1>
<CENTER>Chess Tree Search </CENTER></H1>
<P>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.
<P>These pages give an overview of traditional, fixed depth minimax search, with
various refinements such as selective extensions and pruning, as usd 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.
<P>This overview covers the follwoing subjects:
<UL>
<LI><A href="http://www.xs4all.nl/~verhelst/chess/search.html#minimax">MiniMax
and NegaMax</A>
<LI><A
href="http://www.xs4all.nl/~verhelst/chess/search.html#alpha-beta">Alpha-Beta
search</A>
<LI><A
href="http://www.xs4all.nl/~verhelst/chess/search.html#aspiration">Aspiration
search</A>
<LI><A
href="http://www.xs4all.nl/~verhelst/chess/search.html#transposition">Transposition
table</A>
<LI><A
href="http://www.xs4all.nl/~verhelst/chess/search.html#iterative">Iterative
Deepening</A>
<LI><A
href="http://www.xs4all.nl/~verhelst/chess/search.html#principal">Principal
Variation Search</A>
<LI><A
href="http://www.xs4all.nl/~verhelst/chess/search.html#memory-enhanced-test">Memory
Enhanced Test</A>
<LI><A
href="http://www.xs4all.nl/~verhelst/chess/search.html#enhanced-transposition">Enhanced
Transposition Cutoff</A>
<LI><A href="http://www.xs4all.nl/~verhelst/chess/search.html#killer">Killer
heuristic</A>
<LI><A href="http://www.xs4all.nl/~verhelst/chess/search.html#history">History
heuristic</A>
<LI><A href="http://www.xs4all.nl/~verhelst/chess/search.html#null-move">Null
move heuristic</A>
<LI><A
href="http://www.xs4all.nl/~verhelst/chess/search.html#quiescence">Quiescence
search</A>
<LI><A
href="http://www.xs4all.nl/~verhelst/chess/search.html#extensions">Selective
extensions</A> </LI></UL>
<P>The various search algorithms are illustrated in a compact pseudo-C. The
variables and functions used have the following meaning:
<TABLE border=1>
<TBODY>
<TR>
<TD vAlign=top>pos</TD>
<TD>A position in a chess game.</TD></TR>
<TR>
<TD vAlign=top>depth</TD>
<TD>The number of levels in the tree to be searched.</TD></TR>
<TR>
<TD vAlign=top>Evaluate</TD>
<TD>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.</TD></TR>
<TR>
<TD>best</TD>
<TD>The best value seen while searching the next level in the tree.</TD></TR>
<TR>
<TD vAlign=top>Successors</TD>
<TD>A function that determines the set of all positions that can be
reached from a position in one move (move generation).</TD></TR>
<TR>
<TD vAlign=top>succ</TD>
<TD>The set of positions reachable form the input position by doing one
move.</TD></TR></TBODY></TABLE>
<H2><A name=minimax>MiniMax and NegaMax</A></H2>
<P>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: <PRE>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;
}
</PRE>
<P>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.
<H2><A name=alpha-beta>Alpha-Beta search</A></H2>
<P>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).
<P>The AlphaBeta search procedure gets two additional arguments which indicate
the bounds between which we are interested in exact values for a position: <PRE>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;
}
</PRE>
<P>The gain from <CODE>AlphaBeta</CODE> will come form the earlier exit from the
while loop; a value of <CODE>best</CODE> that equals or exceeds
<CODE>beta</CODE> is called a <I>cutoff</I>. 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
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -