Difference between revisions of "NegaC*"

From Chessprogramming wiki
Jump to: navigation, search
Line 4: Line 4:
  
 
'''C'''* and '''NegaC'''*,<br/>
 
'''C'''* and '''NegaC'''*,<br/>
an idea to turn a [[Depth-First]] to a [[Best-First]] search, like [[MTD(f)]] to utilize [[Null Window|null window]] searches of a [[Fail-Soft|fail-soft]] [[Alpha-Beta]] routine, and to use the [[Bound|bounds]] that are returned in a [https://en.wikipedia.org/wiki/Bisection bisection] scheme. This yields in the '''C'''* algorithm, already proposed by [[Kevin Coplan]] in 1981 <ref>[[Kevin Coplan]] ('''1982'''). ''A special-purpose machine for an improved search algorithm for deep chess combinations.'' [[Advances in Computer Chess 3]]</ref> and '''NegaC'''*, a [[NegaMax]] implementation of '''C'''*, introduced by [[Jean-Christophe Weill]] in 1991 <ref>[[Jean-Christophe Weill]] ('''1991'''). ''Experiments With the NegaC* Search - An Alternative for Othello Endgame Search.'' [[2nd Computer Olympiad#Workshop|Heuristic Programming in AI 2]], [http://www.recherche.enac.fr/%7Eweill/publications/negac.ps.gz zipped postscript] and [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.39.3189&rep=rep1&type=pdf pdf] from [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.3189 CiteSeerX]</ref>.  
+
an idea to turn a [[Depth-First]] to a [[Best-First]] search, like [[MTD(f)]] to utilize [[Null Window|null window]] searches of a [[Fail-Soft|fail-soft]] [[Alpha-Beta]] routine, and to use the [[Bound|bounds]] that are returned in a [https://en.wikipedia.org/wiki/Bisection bisection] scheme. This yields in the '''C'''* algorithm, already proposed by [[Kevin Coplan]] in 1981 <ref>[[Kevin Coplan]] ('''1982'''). ''A special-purpose machine for an improved search algorithm for deep chess combinations.'' [[Advances in Computer Chess 3]]</ref> and '''NegaC'''*, a [[Negamax]] implementation of '''C'''*, introduced by [[Jean-Christophe Weill]] in 1991 <ref>[[Jean-Christophe Weill]] ('''1991'''). ''Experiments With the NegaC* Search - An Alternative for Othello Endgame Search.'' [[2nd Computer Olympiad#Workshop|Heuristic Programming in AI 2]], [http://www.recherche.enac.fr/%7Eweill/publications/negac.ps.gz zipped postscript] and [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.39.3189&rep=rep1&type=pdf pdf] from [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.3189 CiteSeerX]</ref>.  
  
 
=NegaC* Pseudo Code=  
 
=NegaC* Pseudo Code=  

Revision as of 11:30, 4 May 2019

Home * Search * NegaC*

Christopher Conte, Bisected Half Skull [1]

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

Publications

Forum Posts

References

  1. Bisected Half Skull - Bronce from The Sculpture of Christopher Conte
  2. Kevin Coplan (1982). A special-purpose machine for an improved search algorithm for deep chess combinations. Advances in Computer Chess 3
  3. Jean-Christophe Weill (1991). Experiments With the NegaC* Search - An Alternative for Othello Endgame Search. Heuristic Programming in AI 2, zipped postscript and pdf from CiteSeerX

Up one level