25,161
edits
Changes
Created page with "'''Home * Search * Conspiracy Number Search''' '''Conspiracy Number Search''', (CNS, cns)<br/> a best-first search algorithm first described..."
'''[[Main Page|Home]] * [[Search]] * Conspiracy Number Search'''
'''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]].
[[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 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 dubbed '''Controlled Conspiracy Number Search''' (CCNS)
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>
=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|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>.
=Chess Programs=
performing CNS or its improvements:
* [[Arachne]] (CNS)
* [[P.ConNerS]] (PCCNS)
* [[Ulysses]] (CCNS)
=Publications=
==1985 ...==
* [[David McAllester]] ('''1985'''). ''A New Procedure for Growing Minimax Trees''. Technical Report, Artificial Intelligence Laboratory, MIT
* [[David McAllester]] ('''1988'''). ''Conspiracy Numbers for Min-Max Search''. Artificial Intelligence, Vol. 35, No. 1, pp. 287-310. ISSN 0004-3702
* [[Ingo Althöfer]] ('''1988'''). ''Root Evaluation Errors: How they Arise and Propagate''. [[ICGA Journal#11_23|ICCA Journal, Vol. 11, Nos. 2/3]]
* [[Maarten van der Meulen]] ('''1988'''). ''Parallel Conspiracy-Number Search''. M.Sc. thesis, Faculty of Mathematics and Computer Science, [https://en.wikipedia.org/wiki/Vrije_Universiteit Vrije Universteit, Amsterdam]
* [[Norbert Klingbeil]] ('''1988'''). ''Search Strategies for Conspiracy Numbers''. M.Sc. thesis
* [[Norbert Klingbeil]], [[Jonathan Schaeffer]] ('''1988'''). ''Search Strategies for Conspiracy Numbers.'' Canadian Artificial Intelligence Conference, pp. 133-139
* [[Jonathan Schaeffer]] ('''1989'''). ''Conspiracy Numbers.'' [[Advances in Computer Chess 5]] » [[Conspiracy Numbers#AI|also published in AI]]
* [[Charles Elkan]] ('''1989'''). ''Conspiracy Numbers and Caching for Searching And/Or Trees and Theorem-Proving''. [[Conferences#IJCAI|IJCAI 1989]], [http://ijcai.org/Past%20Proceedings/IJCAI-89-VOL1/PDF/054.pdf pdf]
==1990 ...==
* [[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]
* <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
* [[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)]
* [[Lisa Lister]], [[Jonathan Schaeffer]] ('''1994'''). ''An Analysis of the Conspiracy Numbers Algorithm''. [https://en.wikipedia.org/wiki/Computers_and_Mathematics_with_Applications Computers & Mathematics with Applications] Vol. 27, No. 1, [https://en.wikipedia.org/wiki/Elsevier Elsevier], [http://webdocs.cs.ualberta.ca/%7Ejonathan/publications/ai_publications/icn.pdf pdf]
* [[Deniz Yuret]] ('''1994'''). ''[https://scholar.google.com/citations?view_op=view_citation&hl=en&user=EJurXJ4AAAAJ&cstart=40&citation_for_view=EJurXJ4AAAAJ:TQgYirikUcIC The Principle of Pressure in Chess]''. TAINN 1994
==1995 ...==
* [[Ulf Lorenz]], [[Valentin Rottmann]], [[Rainer Feldmann]], [[Peter Mysliwietz]] ('''1995'''). ''Controlled Conspiracy-Number Search.'' [[ICGA Journal#18_3|ICCA Journal, Vol. 18, No. 3]]
* [[Ulf Lorenz]], [[Valentin Rottmann]] ('''1996'''). ''Parallel Controlled Conspiracy-Number Search.'' [[Advances in Computer Chess 8]]
* [[Ulf Lorenz]] ('''1999'''). ''Controlled Conspiracy-2 Search''. Technical Report, [[Paderborn University]], [http://www2.cs.upb.de/cs/ag-monien/PUBLICATIONS/POSTSCRIPTS/Falgo.ps ps]
* [[Robin Upton]] ('''1999'''). ''[http://www.robinupton.com/research/phd/ Dynamic Stochastic Control - A New Approach to Game Tree Searching]''. Ph.D. thesis, [https://en.wikipedia.org/wiki/University_of_Warwick University of Warwick]
==2000 ...==
* [[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'''). ''[[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]], [[Umi Kalsom Yusof]], [[Hiroyuki Iida]], [[Taichi Ishitobi]] ('''2015'''). ''[https://www.researchgate.net/publication/281152992_Critical_Position_Identification_in_Games_and_Its_Application_to_Speculative_Play Critical Position Identification in Games and Its Application to Speculative Play]''. [http://www.scitepress.org/DigitalLibrary/ProceedingsDetails.aspx?ID=+mGlly8Sp00=&t=1 ICAART 2015]
* [[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]
* [[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]]
=References=
<references />
'''[[Search|Up one level]]'''
'''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]].
[[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 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 dubbed '''Controlled Conspiracy Number Search''' (CCNS)
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>
=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|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>.
=Chess Programs=
performing CNS or its improvements:
* [[Arachne]] (CNS)
* [[P.ConNerS]] (PCCNS)
* [[Ulysses]] (CCNS)
=Publications=
==1985 ...==
* [[David McAllester]] ('''1985'''). ''A New Procedure for Growing Minimax Trees''. Technical Report, Artificial Intelligence Laboratory, MIT
* [[David McAllester]] ('''1988'''). ''Conspiracy Numbers for Min-Max Search''. Artificial Intelligence, Vol. 35, No. 1, pp. 287-310. ISSN 0004-3702
* [[Ingo Althöfer]] ('''1988'''). ''Root Evaluation Errors: How they Arise and Propagate''. [[ICGA Journal#11_23|ICCA Journal, Vol. 11, Nos. 2/3]]
* [[Maarten van der Meulen]] ('''1988'''). ''Parallel Conspiracy-Number Search''. M.Sc. thesis, Faculty of Mathematics and Computer Science, [https://en.wikipedia.org/wiki/Vrije_Universiteit Vrije Universteit, Amsterdam]
* [[Norbert Klingbeil]] ('''1988'''). ''Search Strategies for Conspiracy Numbers''. M.Sc. thesis
* [[Norbert Klingbeil]], [[Jonathan Schaeffer]] ('''1988'''). ''Search Strategies for Conspiracy Numbers.'' Canadian Artificial Intelligence Conference, pp. 133-139
* [[Jonathan Schaeffer]] ('''1989'''). ''Conspiracy Numbers.'' [[Advances in Computer Chess 5]] » [[Conspiracy Numbers#AI|also published in AI]]
* [[Charles Elkan]] ('''1989'''). ''Conspiracy Numbers and Caching for Searching And/Or Trees and Theorem-Proving''. [[Conferences#IJCAI|IJCAI 1989]], [http://ijcai.org/Past%20Proceedings/IJCAI-89-VOL1/PDF/054.pdf pdf]
==1990 ...==
* [[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]
* <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
* [[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)]
* [[Lisa Lister]], [[Jonathan Schaeffer]] ('''1994'''). ''An Analysis of the Conspiracy Numbers Algorithm''. [https://en.wikipedia.org/wiki/Computers_and_Mathematics_with_Applications Computers & Mathematics with Applications] Vol. 27, No. 1, [https://en.wikipedia.org/wiki/Elsevier Elsevier], [http://webdocs.cs.ualberta.ca/%7Ejonathan/publications/ai_publications/icn.pdf pdf]
* [[Deniz Yuret]] ('''1994'''). ''[https://scholar.google.com/citations?view_op=view_citation&hl=en&user=EJurXJ4AAAAJ&cstart=40&citation_for_view=EJurXJ4AAAAJ:TQgYirikUcIC The Principle of Pressure in Chess]''. TAINN 1994
==1995 ...==
* [[Ulf Lorenz]], [[Valentin Rottmann]], [[Rainer Feldmann]], [[Peter Mysliwietz]] ('''1995'''). ''Controlled Conspiracy-Number Search.'' [[ICGA Journal#18_3|ICCA Journal, Vol. 18, No. 3]]
* [[Ulf Lorenz]], [[Valentin Rottmann]] ('''1996'''). ''Parallel Controlled Conspiracy-Number Search.'' [[Advances in Computer Chess 8]]
* [[Ulf Lorenz]] ('''1999'''). ''Controlled Conspiracy-2 Search''. Technical Report, [[Paderborn University]], [http://www2.cs.upb.de/cs/ag-monien/PUBLICATIONS/POSTSCRIPTS/Falgo.ps ps]
* [[Robin Upton]] ('''1999'''). ''[http://www.robinupton.com/research/phd/ Dynamic Stochastic Control - A New Approach to Game Tree Searching]''. Ph.D. thesis, [https://en.wikipedia.org/wiki/University_of_Warwick University of Warwick]
==2000 ...==
* [[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'''). ''[[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]], [[Umi Kalsom Yusof]], [[Hiroyuki Iida]], [[Taichi Ishitobi]] ('''2015'''). ''[https://www.researchgate.net/publication/281152992_Critical_Position_Identification_in_Games_and_Its_Application_to_Speculative_Play Critical Position Identification in Games and Its Application to Speculative Play]''. [http://www.scitepress.org/DigitalLibrary/ProceedingsDetails.aspx?ID=+mGlly8Sp00=&t=1 ICAART 2015]
* [[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]
* [[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]]
=References=
<references />
'''[[Search|Up one level]]'''
