25,161
edits
Changes
no edit summary
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.
=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
* [[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]]
