Difference between revisions of "NegaC*"
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...") |
GerdIsenberg (talk | contribs) |
||
| (6 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
'''[[Main Page|Home]] * [[Search]] * NegaC'''* | '''[[Main Page|Home]] * [[Search]] * NegaC'''* | ||
| − | [[FILE:Bronze_Half.jpg|border|right|thumb|285px|link=http://www.microbotic.org/skull5.htm|[[ | + | [[FILE:Bronze_Half.jpg|border|right|thumb|285px|link=http://www.microbotic.org/skull5.htm|[[:Category:Christopher Conte|Christopher Conte]], Bisected Half Skull <ref>[http://www.microbotic.org/skull5.htm Bisected Half Skull - Bronce] from [http://www.microbotic.org/portfolio.htm The Sculpture] of [[:Category:Christopher Conte|Christopher Conte]]</ref> ]] |
'''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 [[ | + | 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= | ||
| Line 34: | Line 34: | ||
=Publications= | =Publications= | ||
| − | * [[Kevin Coplan]] ('''1982'''). ''A | + | * [[Kevin Coplan]] ('''1982'''). ''[https://www.sciencedirect.com/science/article/pii/B9780080268989500061 A Special-Purpose Machine for an Improved Search Algorithm for Deep Chess Combinations]''. [[Advances in Computer Chess 3]] |
| + | * [[Kevin Coplan]] ('''1984'''). ''[https://www.era.lib.ed.ac.uk/handle/1842/6645 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]], [https://www.era.lib.ed.ac.uk/bitstream/handle/1842/6645/Coplan1984.pdf pdf] | ||
| + | * [[Wolfgang Nagl]] ('''1989'''). ''Best-Move Proving: A Fast Game Tree Searching Program''. [[1st Computer Olympiad#Workshop|Heuristic Programming in AI 1]] | ||
* [[Jean-Christophe Weill]] ('''1991'''). ''Experiments With the NegaC* Search - An Alternative for Othello Endgame Search.'' [[2nd Computer Olympiad#Workshop|Heuristic Programming in AI 2]] | * [[Jean-Christophe Weill]] ('''1991'''). ''Experiments With the NegaC* Search - An Alternative for Othello Endgame Search.'' [[2nd Computer Olympiad#Workshop|Heuristic Programming in AI 2]] | ||
* [[Jean-Christophe Weill]] ('''1992'''). ''The NegaC* Search.'' [[ICGA Journal#15_1|ICCA Journal, Vol. 15, No. 1]] | * [[Jean-Christophe Weill]] ('''1992'''). ''The NegaC* Search.'' [[ICGA Journal#15_1|ICCA Journal, Vol. 15, No. 1]] | ||
| Line 43: | Line 45: | ||
=References= | =References= | ||
<references /> | <references /> | ||
| − | |||
'''[[Search|Up one level]]''' | '''[[Search|Up one level]]''' | ||
| + | [[Category:Christopher Conte]] | ||
Latest revision as of 18:56, 4 May 2019
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
- 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
- ↑ 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 AI 2, zipped postscript and pdf from CiteSeerX
