NegaC*
Revision as of 16:27, 2 May 2018 by GerdIsenberg (talk | contribs) (Created page with "'''Home * Search * NegaC'''* border|right|thumb|285px|link=http://www.microbotic.org/skull5.htm|[[Arts#Conte|Christopher Conte, Bis...")
C* and NegaC*,
an idea to turn a Depth-First to a Best-First search, like MTD(f) to utilize null window searches of a fail-soft Alpha-Beta routine, and to use the bounds that are returned in a bisection scheme. This yields in the C* algorithm, already proposed by Kevin Coplan in 1981 [2] and NegaC*, a NegaMax implementation of C*, introduced by Jean-Christophe Weill in 1991 [3].
NegaC* Pseudo Code
int negaCStar (int min, int max, int depth) {
int score = min;
while (min != max) {
alpha = (min + max) / 2;
score = failSoftAlphaBeta (alpha, alpha + 1, depth);
if ( score > alpha)
min = score;
else
max = score;
}
return score;
}
See also
- Alpha-Beta
- Fail-Soft
- MTD(f)
- Negamax
- NegaScout
- Null Window
- Principal Variation Search
- Scout
- SSS* and Dual* as MT
Publications
- Kevin Coplan (1982). A special-purpose machine for an improved search algorithm for deep chess combinations. Advances in Computer Chess 3
- Jean-Christophe Weill (1991). Experiments With the NegaC* Search - An Alternative for Othello Endgame Search. Heuristic Programming in AI 2
- Jean-Christophe Weill (1992). The NegaC* Search. ICCA Journal, Vol. 15, No. 1
Forum Posts
- Re: Interesting ideas by Dann Corbit, CCC, September 09, 2015
References
- ↑ Bisected Half Skull - Bronce from The Sculpture of Christopher Conte
- ↑ Kevin Coplan (1982). A special-purpose machine for an improved search algorithm for deep chess combinations. Advances in Computer Chess 3
- ↑ Jean-Christophe Weill (1991). Experiments With the NegaC* Search - An Alternative for Othello Endgame Search. Heuristic Programming in Artificial Intelligence 2: the second computer olympiad (eds. David Levy and Don Beal), pp. 174-188. Ellis Horwood, Chichester. ISBN 0-13-382615-5, zipped postscript and pdf from CiteSeerX
