25,161
edits
Changes
no edit summary
'''[[Main Page|Home]] * [[Search]] * Conspiracy Number Search'''
[[FILE:Dollarnote siegel hq.jpg|border|right|thumb| [https://en.wikipedia.org/wiki/Eye_of_Providence Eye of Providence] <ref>The [https://en.wikipedia.org/wiki/Eye_of_Providence Eye of Providence] can be seen on the reverse of the [https://en.wikipedia.org/wiki/Great_Seal_of_the_United_States Great Seal of the United States], seen here on the [https://en.wikipedia.org/wiki/United_States_one-dollar_bill US $1 bill]. Popular among [https://en.wikipedia.org/wiki/Conspiracy_theory conspiracy theorists] is the claim that the Eye of Providence shown atop an unfinished pyramid on the Great Seal of the United States indicates the influence of [https://en.wikipedia.org/wiki/Freemasonry Freemasonry] in the [https://en.wikipedia.org/wiki/Founding_Fathers_of_the_United_States founding of the United States], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]
'''Conspiracy Number Search''', (CNS, cns)<br/>
a [[Best-First|best-first search]] algorithm first described by [[David McAllester]] based on [[Conspiracy Numbers]] of the [[Root|root]]<ref>[[David McAllester]] ('''1985'''). ''A New Procedure for Growing Minimax Trees''. Technical Report, Artificial Intelligence Laboratory, [[Massachusetts Institute of Technology|MIT]]</ref>.
[[Search Tree|Trees]] are grown in [[Memory|memory]] - in an often deep and narrow way - that maximizes the conspiracy required to change the root value.
The phases of the best-first search procedure are '''Selection''' of a [[Leaf Node|leaf node]], '''Expansion''' and '''Evaluation''' of that leaf, and to '''Back-up''' the result of that evaluation back to the root.Since the number of conspiracy numbers per [[Node|node]] depends on the number of possible evaluation values, fine grained evaluation, necessary for good positional play, yields to in inefficient and unstable CNS.Further, due to the lack of [[Bound|bounds]], a final [[Alpha-Beta|alpha-beta]] [[Quiescence Search|quiescence search]] in early CNS implementations was quite expensive.
<span id="CCNS"></span>
=Controlled Conspiracy Number Search=
[[Ulf Lorenz|Ulf Lorenz']] and [[Valentin Rottmann|Valentin Rottmann's]] et al. improvement proposed improvements dubbed '''Controlled Conspiracy Number Search''' (CCNS) <ref>[[Ulf Lorenz]], [[Valentin Rottmann]], [[Rainer Feldmann]], [[Peter Mysliwietz]] ('''1995'''). ''Controlled Conspiracy-Number Search.'' [[ICGA Journal#18_3|ICCA Journal, Vol. 18, No. 3]]</ref> addresses address the drawbacks of CNS by introducing general '''CN Targets''' and '''Extended Conspiracy Numbers'''. CN targets (security demands) are splitted over the successors in order to inform each node about the goal of its examination.
Extended Conspiracy Numbers of the root are defined as the least number of leaf nodes that must change their value in order to change the decision at the root to another move.
<span id="PCCNS"></span>
The parallelization procedure aims at a dynamic distribution of the game tree, initiating a worker/employer relationship along with a sophisticated splitting heuristic of CN targets.
The [[Stack|stack]], used to keep the nodes of the best-first search, could be manipulated from outside in order to share work and integrate results from other processors <ref>[[Ulf Lorenz]], [[Valentin Rottmann]] ('''1996'''). ''Parallel Controlled Conspiracy-Number Search.'' [[Advances in Computer Chess 8]]</ref>.
=See also=
* [[Alpha-Beta Conspiracy Search]]
* [[Conspiracy Numbers]]
* [[Proof-Number Search]]
=Chess Programs=
=Publications=
==1985 ...==
* [[David McAllester]] ('''1985'''). ''A New Procedure for Growing Minimax Trees''. Technical Report, Artificial Intelligence Laboratory, [[Massachusetts Institute of Technology|MIT]]
* [[David McAllester]] ('''1988'''). ''Conspiracy Numbers for Min-Max Search''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 35, No. 1
* [[Ingo Althöfer]] ('''1988'''). ''Root Evaluation Errors: How they Arise and Propagate''. [[ICGA Journal#11_23|ICCA Journal, Vol. 11, Nos. 2/3]]
