25,161
edits
Changes
Created page with "'''Home * Search * NegaC'''* border|right|thumb|285px|link=http://www.microbotic.org/skull5.htm|[[Arts#Conte|Christopher Conte, Bis..."
'''[[Main Page|Home]] * [[Search]] * NegaC'''*
[[FILE:Bronze_Half.jpg|border|right|thumb|285px|link=http://www.microbotic.org/skull5.htm|[[Arts#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 [[Arts#Conte|Christopher Conte]]</ref> ]]
'''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.'' 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, [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=
<pre>
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;
}
</pre>
=See also=
* [[Alpha-Beta]]
* [[Fail-Soft]]
* [[MTD(f)]]
* [[Negamax]]
* [[NegaScout]]
* [[Null Window]]
* [[Principal Variation Search]]
* [[Scout]]
* [[SSS* and Dual*#SSStarandDualStarAsMT|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.'' [[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]]
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=57560&start=15 Re: Interesting ideas] by [[Dann Corbit]], [[CCC]], September 09, 2015
=References=
<references />
'''[[Search|Up one level]]'''
[[FILE:Bronze_Half.jpg|border|right|thumb|285px|link=http://www.microbotic.org/skull5.htm|[[Arts#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 [[Arts#Conte|Christopher Conte]]</ref> ]]
'''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.'' 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, [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=
<pre>
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;
}
</pre>
=See also=
* [[Alpha-Beta]]
* [[Fail-Soft]]
* [[MTD(f)]]
* [[Negamax]]
* [[NegaScout]]
* [[Null Window]]
* [[Principal Variation Search]]
* [[Scout]]
* [[SSS* and Dual*#SSStarandDualStarAsMT|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.'' [[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]]
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=57560&start=15 Re: Interesting ideas] by [[Dann Corbit]], [[CCC]], September 09, 2015
=References=
<references />
'''[[Search|Up one level]]'''
