25,161
edits
Changes
no edit summary
[[FILE:ACC5Schaeffer.jpg|border|right|thumb|[[Jonathan Schaeffer]] on ''Conspiracy Numbers.'' <ref>Photo from [[Advances in Computer Chess 5]] by [[László Lindner]], [[ICGA Journal#10_3|ICCA Journal, Vol. 10, No. 3]], pp. 138</ref> ]]
'''Conspiracy Numbers''' of the [[Root|root]] or [[Interior Node|interior nodes]] of a [[Search Tree|search tree]] for some value '''vV''' are defined as the least number of conspirators, that are [[Leaf Node|leaves]] that must change their evaluation value to '''vV''' in order to change the minimax value of the interior node or root <ref>Definition, Sample, and Pseudo code taken from [[Maarten van der Meulen]] ('''1990'''). ''Conspiracy-Number Search''. [[ICGA Journal#13_1|ICCA Journal, Vol. 13, No. 1]]</ref>. Conspiracy Numbers and their possible application for [[Minimax]] search within a [[Best-First|best-first search]] algorithm was first described by [[David McAllester]] <ref>[[David McAllester]] ('''1988'''). ''Conspiracy Numbers for Min-Max Search''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 35, No. 1, pp. 287-310. ISSN 0004-3702</ref>.
=Sample=
}
</pre>
=Conspiracy Theory=
Let δ be a number called the singular margin <ref>The term ''singular margin'' comes from the [[Singular Extensions|singular extension]] algorithm ([[Thomas Anantharaman|Anantharaman]] et al. 1990)</ref>. '''Conspiracy theory''' can be formulated using the following definition <ref>[[David McAllester]], [[Deniz Yuret]] ('''1993'''). ''Alpha-Beta Conspiracy Search''. [http://ttic.uchicago.edu/%7Edmcallester/abc.ps ps (draft)]</ref>:
'''Definition''': Let '''T''' be a search tree with min-max value '''<nowiki>V[T]</nowiki>'''. The [[Lower Bound|lower boand]] conspiracy number of '''T''', denoted '''C<sub><</sub><nowiki>[T]</nowiki>''', is the number of leaf static values that must be changed to bring the root min-max value down to '''<nowiki>V[T]</nowiki>-δ'''. The [[Upper Bound|upper boand]] conspiracy number of '''T''', denoted '''C<sub>></sub><nowiki>[T]</nowiki>''', is the number of leaves that must be changed to bring the root value up to '''<nowiki>V[T]</nowiki>+δ'''.
'''C<sub><</sub><nowiki>[T]</nowiki>''' expresses the confidence that the lower bound [[Alpha|α]] will hold by further expansion of the search tree.
=Search Algorithms=
=Publications=
<ref>[http://ilk.uvt.nl/icga/journal/docs/References.pdf [ICGA Journal#RefDB|ICGA Reference Database](pdf)]</ref>
==1985 ...==
* [[David McAllester]] ('''1985'''). ''A New Procedure for Growing Minimax Trees''. Technical Report, Artificial Intelligence Laboratory, MIT
* [[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
* [[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]]
