NegaC*

Home * Search * NegaC*

Christopher Conte, Bisected Half Skull

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 and NegaC*, a Negamax implementation of C*, introduced by Jean-Christophe Weill in 1991 .

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
• Kevin Coplan (1984). The experimental and theoretical validation of a new search algorithm with a note on the automatic generation of causal explanations. Ph.D. thesis, University of Edinburgh, pdf
• Wolfgang Nagl (1989). Best-Move Proving: A Fast Game Tree Searching Program. Heuristic Programming in AI 1
• 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

Up one level