Home * Search * NegaC*

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 [1] and NegaC*, a NegaMax implementation of C*, introduced by Jean-Christophe Weill in 1991 [2].
Christopher Conte, Bisected Half Skull [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;
         max = score;
   return score;

See also


Forum Posts


  1. ^ Kevin Coplan (1982). A special-purpose machine for an improved search algorithm for deep chess combinations. Advances in Computer Chess 3
  2. ^ 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
  3. ^ Bisected Half Skull - Bronce from The Sculpture of Christopher Conte

What links here?

Up one level