?? negascout algorithm.htm
字號(hào):
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0057)http://www.uni-paderborn.de/pc2/people/homes/ar/r_nsc.htm -->
<HTML><HEAD><TITLE>NegaScout Algorithm</TITLE>
<META content="text/html; charset=gb2312" http-equiv=Content-Type><LINK
href="NegaScout Algorithm.files/default.htm" rel=StyleSheet
title="CSS Default Style" type=text/css><!-- $Id: reinefeld.html,v 1.0 1996/01/07 17:32:38 pk Exp $ -->
<META content="MSHTML 5.00.2614.3500" name=GENERATOR></HEAD>
<BODY bgColor=#ffffff>
<H2>NegaScout</H2>
<H3>"A Minimax Algorithm faster than AlphaBeta"</H3><I>Last modified 5. December
1997</I>
<HR>
<PRE>int NegaScout ( int p, alpha, beta );
{ /* compute minimax value of position p */
int a, b, t, i;
determine successors p_1,...,p_w of p;
if ( w = 0 )
return ( Evaluate(p) ); /* leaf node */
a = alpha;
b = beta;
for ( i = 1; i <= w; i++ ) {
t = -NegaScout ( p_i, -b, -a );
if (t > a) && (t < beta) && (i > 1) && (d < maxdepth-1)
a = -NegaScout ( p_i, -beta, -t ); /* re-search */
a = max( a, t );
if ( a >= beta )
return ( a ); /* cut-off */
b = a + 1; /* set new null window */
}
return ( a );
}
</PRE>Like AlphaBeta, NegaScout is a directional search algorithm for computing
the minimax value of a node.
<UL>
<LI>NegaScout dominates AlphaBeta, i.e. NegaScout never examines a node that
can be pruned by AlphaBeta.
<P></P>
<LI>Neither does NegaScout dominate SSS* nor vice versa: There exist trees in
which NegaScout searches strictly fewer nodes than SSS* and vice versa. On
averagely ordered trees, however, the best-first procedure SSS* usually
searches less nodes than NegaScout.
<P></P>
<LI>The same applies to DUAL*. </LI></UL>The formal proofs can be found in my
monograph on game tree search algorithms <I>A. Reinefeld.
Spielbaum-Suchverfahren. Informatik-Fachberichte 200, Springer-Verlag, Berlin
(1989), ISBN 3-540-50742-6. </I>
<P>A facsimile of the original publication <I>A. Reinefeld. An Improvement of
the Scout Tree Search Algorithm. ICCA Journal, Vol. 6 No. 4, 1983, pp. 4-14
</I>can be found <A
href="http://www.uni-paderborn.de/pc2/services/public/other/nag_scout.pdf">here
(PDF)</A>. </P></BODY></HTML>
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -