Difference between revisions of "Conspiracy Number Search"

From Chessprogramming wiki
Jump to: navigation, search
(Created page with "'''Home * Search * Conspiracy Number Search''' '''Conspiracy Number Search''', (CNS, cns)<br/> a best-first search algorithm first described...")
 
Line 9: Line 9:
 
<span id="CCNS"></span>
 
<span id="CCNS"></span>
 
=Controlled Conspiracy Number Search=  
 
=Controlled Conspiracy Number Search=  
[[Ulf Lorenz|Ulf Lorenz']] and [[Valentin Rottmann|Valentin Rottmann's]] et al. improvement dubbed '''Controlled Conspiracy Number Search''' (CCNS)  
+
[[Ulf Lorenz|Ulf Lorenz']] and [[Valentin Rottmann|Valentin Rottmann's]] et al. improvement 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 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.
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.
 
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>
 
<span id="PCCNS"></span>
Line 36: Line 35:
 
* [[Maarten van der Meulen]] ('''1990'''). ''Conspiracy-Number Search''. [[ICGA Journal#13_1|ICCA Journal, Vol. 13, No. 1]]
 
* [[Maarten van der Meulen]] ('''1990'''). ''Conspiracy-Number Search''. [[ICGA Journal#13_1|ICCA Journal, Vol. 13, No. 1]]
 
* [[Norbert Klingbeil]], [[Jonathan Schaeffer]] ('''1990'''). ''Empirical Results with Conspiracy Numbers.'' Computational Intelligence, Vol. 6, pp. 1-11, [http://webdocs.cs.ualberta.ca/%7Ejonathan/Papers/Papers/compi.ps ps]
 
* [[Norbert Klingbeil]], [[Jonathan Schaeffer]] ('''1990'''). ''Empirical Results with Conspiracy Numbers.'' Computational Intelligence, Vol. 6, pp. 1-11, [http://webdocs.cs.ualberta.ca/%7Ejonathan/Papers/Papers/compi.ps ps]
* <span id="AI"></span>[[Jonathan Schaeffer]] ('''1990'''). ''Conspiracy Numbers''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 43, No. 1, pp. 67-84
+
* <span id="AI"></span>[[Jonathan Schaeffer]] ('''1990'''). ''Conspiracy Numbers''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 43, No. 1
* [[Maarten van der Meulen]], [[Victor Allis]], [[Jaap van den Herik]] ('''1990'''). ''A Comment on `Conspiracy-Number Search'''. [[ICGA Journal#13_2|ICCA Journal, Vol. 13, No. 2]]
+
* [[Maarten van der Meulen]], [[Victor Allis]], [[Jaap van den Herik]] ('''1990'''). ''A Comment on `Conspiracy-Number Search''. [[ICGA Journal#13_2|ICCA Journal, Vol. 13, No. 2]]
 
* [[Victor Allis]], [[Maarten van der Meulen]], [[Jaap van den Herik]] ('''1991'''). ''Conspiracy-Number Search.'' [[Advances in Computer Chess 6]]
 
* [[Victor Allis]], [[Maarten van der Meulen]], [[Jaap van den Herik]] ('''1991'''). ''Conspiracy-Number Search.'' [[Advances in Computer Chess 6]]
 
* [[David McAllester]], [[Deniz Yuret]] ('''1993'''). ''Alpha-Beta Conspiracy Search''. [http://ttic.uchicago.edu/%7Edmcallester/abc.ps ps (draft)]
 
* [[David McAllester]], [[Deniz Yuret]] ('''1993'''). ''Alpha-Beta Conspiracy Search''. [http://ttic.uchicago.edu/%7Edmcallester/abc.ps ps (draft)]

Revision as of 16:07, 8 December 2019

Home * Search * Conspiracy Number Search

Conspiracy Number Search, (CNS, cns)
a best-first search algorithm first described by David McAllester based on Conspiracy Numbers of the root. Trees are grown in 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, 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 depends on the number of possible evaluation values, fine grained evaluation, necessary for good positional play, yields to inefficient and unstable CNS. Further, due to the lack of bounds, a final alpha-beta quiescence search in early CNS implementations was quite expensive.

Controlled Conspiracy Number Search

Ulf Lorenz' and Valentin Rottmann's et al. improvement dubbed Controlled Conspiracy Number Search (CCNS) [1] addresses 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.

Parallel Controlled Conspiracy Number Search

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, 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 [2].

Chess Programs

performing CNS or its improvements:

Publications

1985 ...

1990 ...

1995 ...

2000 ...

2010 ...

References

  1. Ulf Lorenz, Valentin Rottmann, Rainer Feldmann, Peter Mysliwietz (1995). Controlled Conspiracy-Number Search. ICCA Journal, Vol. 18, No. 3
  2. Ulf Lorenz, Valentin Rottmann (1996). Parallel Controlled Conspiracy-Number Search. Advances in Computer Chess 8

Up one level