25,161
edits
Changes
no edit summary
=CNS=
CNS maintains a range of possible values and keeps expanding the tree until a certain degree of confidence is reached. The confidence is measured by the width of a possible values’ range '''W ''' and a minimum value for conspiracy numbers '''T'''. The purpose of the search is to raise the conspiracy numbers of unlikely values to greater than '''T ''' in order to reduce the range of possible values to below '''W'''. At each turn, CNS tries to disprove either the highest or lowest possible value, which has the highest conspiracy numbers, by expanding one of its conspirators. Then, it recalculates conspiracy numbers and repeats the process until the desired confidence is obtained <ref>[[Quang Vu]], [[Taichi Ishitobi]], [[Jean-Christophe Terrillon]], [[Hiroyuki Iida]] ('''2016'''). ''Using Conspiracy Numbers for Improving Move Selection in Minimax Game-Tree Search''. [http://www.icaart.org/?y=2016 ICAART 2016], [https://pdfs.semanticscholar.org/1bcf/bd2047bc1d74affda11bf2007cac442dd6f4.pdf pdf]</ref>.Since the number of conspiracy numbers per [[Node|node]] '''W''' depends on the number of possible evaluation values, fine grained evaluation, considered necessary for good positional play, yields in into additional computation and thus inefficient search. Further, a final [[Alpha-Beta|alpha-beta]] [[Quiescence Search|quiescence search]] in early CNS implementations was quite expensive due to the lack of [[Bound|bounds]].
<span id="CCNS"></span>
=CCNS=
=See also=
* [[:Category:CNS]]
* [[Alpha-Beta Conspiracy Search]]
* [[Conspiracy Numbers]]
==1990 ...==
* [[Maarten van der Meulen]] ('''1990'''). ''Conspiracy-Number Search''. [[ICGA Journal#13_1|ICCA Journal, Vol. 13, No. 1]]
* [[Norbert Klingbeil]], [[Jonathan Schaeffer]] ('''1990'''). ''[https://www.semanticscholar.org/paper/Empirical-results-with-conspiracy-numbers-Klingbeil-Schaeffer/5fc0f8a0901c5e85c04ec813b6e11a7acf32143f Empirical Results with Conspiracy Numbers].'' Computational Intelligence, Vol. 6, pp. 1-11, [httphttps://webdocsen.cswikipedia.ualberta.caorg/%7Ejonathanwiki/Papers/Papers/compiComputational_Intelligence_(journal) Computational Intelligence], Vol.ps ps]6
* <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]]
* [[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)]
* [[Ulf Lorenz]] ('''2000'''). ''[http://digital.ub.uni-paderborn.de/hsmig/content/titleinfo/2460 Controlled Conspiracy Number Search]''. [[Paderborn University]], Dissertation, advisor [[Burkhard Monien]] (German)
* [[Ulf Lorenz]] ('''2000'''). ''Controlled Conspiracy-2 Search''. Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science (STACS)
* [[David McAllester]], [[Deniz Yuret]] ('''2002'''). ''[[https://www.semanticscholar.org/paper/Alpha-Beta-Conspiracy-Search-McAllester-Yuret/7538bf85b5110207c2925ee8781c69826ad2a425 Alpha-Beta Conspiracy Search]]''. [[ICGA Journal#25_1|ICGA Journal, Vol. 25, No. 1]]
* [[Ulf Lorenz]] ('''2002'''). ''[https://link.springer.com/chapter/10.1007/3-540-45706-2_57 Parallel Controlled Conspiracy Number Search]''. [https://dblp1.uni-trier.de/db/conf/europar/europar2002.html Euro-Par 2002], [https://en.wikipedia.org/wiki/Lecture_Notes_in_Computer_Science LNCS] 2400, [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer]
==2010 ...==
* [[Mohd Nor Akmal Khalid]], [[E. Mei Ang]], [[Umi Kalsom Yusof]], [[Hiroyuki Iida]], [[Taichi Ishitobi]] ('''2015'''). ''[http://link.springer.com/chapter/10.1007%2F978-3-319-27947-3_6 Identifying Critical Positions Based on Conspiracy Numbers]''. [http://link.springer.com/book/10.1007/978-3-319-27947-3 Agents and Artificial Intelligence], [http://dblp.uni-trier.de/db/conf/icaart/icaart2015s.html#KhalidAYII15 ICAART 2015 - Revised Selected Papers]
* [[Jakub Pawlewicz]], [[Ryan Hayward]] ('''2015'''). ''[https://www.aaai.org/ocs/index.php/SOCS/SOCS15/paper/view/11040 Sibling Conspiracy Number Search]''. [https://en.wikipedia.org/wiki/Symposium_on_Combinatorial_Search SoCS 2015]
* [[Jakub Pawlewicz]], [[Ryan Hayward]] ('''2016'''). ''[https://www.sciencedirect.com/science/article/pii/S0304397516302729 Conspiracy number search with relative sibling scores]''. [https://en.wikipedia.org/wiki/Theoretical_Computer_Science_(journal) Theoretical Computer Science], Vol. 644
* [[Quang Vu]], [[Taichi Ishitobi]], [[Jean-Christophe Terrillon]], [[Hiroyuki Iida]] ('''2016'''). ''Using Conspiracy Numbers for Improving Move Selection in Minimax Game-Tree Search''. [http://www.icaart.org/?y=2016 ICAART 2016], [https://pdfs.semanticscholar.org/1bcf/bd2047bc1d74affda11bf2007cac442dd6f4.pdf pdf]
* [[Zhang Song]], [[Hiroyuki Iida]] ('''2018'''). ''Using single conspiracy number for long term position evaluation''. [[CG 2018]], [[ICGA Journal#40_3|ICGA Journal, Vol. 40, No. 3]]
