Difference between revisions of "Conspiracy Numbers"

From Chessprogramming wiki
Jump to: navigation, search
(Created page with "'''Home * Search * Conspiracy Numbers''' border|right|thumb|link=Advances in Computer Chess 5| [[Jonathan Schaeffer on ''Conspira...")
 
 
(17 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
'''[[Main Page|Home]] * [[Search]] * Conspiracy Numbers'''
 
'''[[Main Page|Home]] * [[Search]] * Conspiracy Numbers'''
  
[[FILE:ACC5Schaeffer.jpg|border|right|thumb|link=Advances in Computer Chess 5| [[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> ]]
+
[[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 '''V''' are defined as the least number of conspirators, that are [[Leaf Node|leaves]] that must change their evaluation value to '''V''' 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>.
 
 
'''Conspiracy Numbers''' of the [[Root|root]] or [[Interior Node|interior nodes]] of a [[Search Tree|search tree]] for some value '''v''' are defined as the least number of conspirators, that are [[Leaf Node|leaves]] that must change their evaluation value to '''v''' 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''. Artificial Intelligence, Vol. 35, No. 1, pp. 287-310. ISSN 0004-3702</ref>.
 
  
 
=Sample=  
 
=Sample=  
 
==Minimax Tree==  
 
==Minimax Tree==  
A sample minimax tree T with some arbitrary values of the leaves <ref>due to [[Jonathan Schaeffer]] ('''1989'''). ''Conspiracy Numbers.'' [[Advances in Computer Chess 5]]</ref>
+
A sample minimax tree T with some arbitrary values of the leaves <ref>due to [[Jonathan Schaeffer]] ('''1989'''). ''Conspiracy Numbers.'' [[Advances in Computer Chess 5]]</ref>:
</ref>:
 
 
<pre>
 
<pre>
 
root                    ┌───────┐
 
root                    ┌───────┐
max node                │   1 
+
max node                │ A=3 
 
                         └───────┘
 
                         └───────┘
                    /      3      \
 
 
           ┌───────┐                ┌───────┐
 
           ┌───────┐                ┌───────┐
min nodes  │  1.1 │                │  1.2
+
min nodes  │  B=2 │                │  C=3
 
           └───────┘                └───────┘
 
           └───────┘                └───────┘
          /    2    \              /    3    \
 
 
   ┌───────┐      ┌───────┐  ┌───────┐      ┌───────┐
 
   ┌───────┐      ┌───────┐  ┌───────┐      ┌───────┐
   │ 1.1.1 │      │ 1.1.2 │  │ 1.2.1 │      │ 1.2.2
+
   │ D=5  │      │ E=2 │  │ F=3  │      │ G=4 
 
   └───────┘      └───────┘  └───────┘      └───────┘
 
   └───────┘      └───────┘  └───────┘      └───────┘
      5              2          3              4
 
 
</pre>
 
</pre>
  
 
==Conspiracy Numbers==  
 
==Conspiracy Numbers==  
The conspiracy numbers for all possible value of the root of tree T
 
 
{| class="wikitable"
 
{| class="wikitable"
 +
|-
 +
! colspan="3" | Conspiracy numbers for all possible values of the root A
 
|-
 
|-
 
! v  
 
! v  
! cn(root, v)  
+
! cn(A, v)  
 
! conspirators  
 
! conspirators  
 
|-
 
|-
 
| style="text-align:center;" | <= 1  
 
| style="text-align:center;" | <= 1  
 
! 2  
 
! 2  
| style="text-align:center;" | (1.1.1 or 1.1.2) and (1.2.1 or 1.2.2)  
+
| style="text-align:center;" | (D or E) and (F or G)  
 
|-
 
|-
 
| style="text-align:center;" | 2  
 
| style="text-align:center;" | 2  
 
! 1  
 
! 1  
| style="text-align:center;" | (1.2.1 or 1.2.2)  
+
| style="text-align:center;" | (F or G)  
 
|-
 
|-
 
| style="text-align:center;" | 3  
 
| style="text-align:center;" | 3  
Line 48: Line 43:
 
| style="text-align:center;" | 4  
 
| style="text-align:center;" | 4  
 
! 1  
 
! 1  
| style="text-align:center;" | (1.1.2 or 1.2.1)  
+
| style="text-align:center;" | (E or F)  
 
|-
 
|-
 
| style="text-align:center;" | 5  
 
| style="text-align:center;" | 5  
 
! 1  
 
! 1  
| style="text-align:center;" | 1.1.2
+
| style="text-align:center;" | E
 
|-
 
|-
 
| style="text-align:center;" | >= 6  
 
| style="text-align:center;" | >= 6  
 
! 2  
 
! 2  
| style="text-align:center;" | (1.1.1 and 1.1.2) or (1.2.1 and 1.2.2)  
+
| style="text-align:center;" | (D and E) or (F and G)  
|}
+
|-
 
+
! colspan="3" | Conspiracy numbers for all possible values of node B
The conspiracy numbers for all possible value of node 1.1 of tree T
 
{| class="wikitable"
 
 
|-
 
|-
 
! v  
 
! v  
! cn(1.1, v)  
+
! cn(B, v)  
 
! conspirators  
 
! conspirators  
 
|-
 
|-
 
| style="text-align:center;" | <= 1  
 
| style="text-align:center;" | <= 1  
 
! 1  
 
! 1  
| style="text-align:center;" | (1.1.1 or 1.1.2)  
+
| style="text-align:center;" | (D or E)  
 
|-
 
|-
 
| style="text-align:center;" | 2  
 
| style="text-align:center;" | 2  
Line 76: Line 69:
 
| style="text-align:center;" | 3,4,5  
 
| style="text-align:center;" | 3,4,5  
 
! 1  
 
! 1  
| style="text-align:center;" | 1.1.2
+
| style="text-align:center;" | E
 
|-
 
|-
 
| style="text-align:center;" | >= 6  
 
| style="text-align:center;" | >= 6  
 
! 2  
 
! 2  
| style="text-align:center;" | (1.1.1 and 1.1.2)  
+
| style="text-align:center;" | (D and E)  
|}
+
|-
 
+
! colspan="3" | Conspiracy numbers for all possible values of node C
The conspiracy numbers for all possible value of node 1.2 of tree T
 
{| class="wikitable"
 
 
|-
 
|-
 
! v  
 
! v  
! cn(1.2, v)  
+
! cn(C, v)  
 
! conspirators  
 
! conspirators  
 
|-
 
|-
 
| style="text-align:center;" | <= 2  
 
| style="text-align:center;" | <= 2  
 
! 1  
 
! 1  
| style="text-align:center;" | (1.2.1 or 1.2.2)  
+
| style="text-align:center;" | (F or G)  
 
|-
 
|-
 
| style="text-align:center;" | 3  
 
| style="text-align:center;" | 3  
Line 100: Line 91:
 
| style="text-align:center;" | 4  
 
| style="text-align:center;" | 4  
 
! 1  
 
! 1  
| style="text-align:center;" | 1.2.1
+
| style="text-align:center;" | F
 
|-
 
|-
 
| style="text-align:center;" | >= 5  
 
| style="text-align:center;" | >= 5  
 
! 2  
 
! 2  
| style="text-align:center;" | (1.2.1 and 1.2.2)  
+
| style="text-align:center;" | (F and G)  
 
|}
 
|}
  
Line 134: Line 125:
 
}
 
}
 
</pre>
 
</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=  
 
=Search Algorithms=  
Line 140: Line 137:
 
* [[Alpha-Beta Conspiracy Search]]
 
* [[Alpha-Beta Conspiracy Search]]
 
* [[Conspiracy Number Search]]
 
* [[Conspiracy Number Search]]
* [[Controlled Conspiracy Number Search]]
 
* [[Parallel Controlled Conspiracy Number Search]]
 
 
* [[Proof-Number Search]]
 
* [[Proof-Number Search]]
 
=Chess Programs=
 
* [[Arachne]]
 
* [[P.ConNerS]]
 
* [[Ulysses]]
 
  
 
=Publications=  
 
=Publications=  
<ref>[http://ilk.uvt.nl/icga/journal/docs/References.pdf ICGA Reference Database](pdf)</ref>
+
<ref>[[ICGA Journal#RefDB|ICGA Reference Database]]</ref>
 
==1985 ...==  
 
==1985 ...==  
 
* [[David McAllester]] ('''1985'''). ''A New Procedure for Growing Minimax Trees''. Technical Report, Artificial Intelligence Laboratory, MIT
 
* [[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
+
* [[David McAllester]] ('''1988'''). ''Conspiracy Numbers for Min-Max Search''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 35, No. 1
 
* [[Ingo Althöfer]] ('''1988'''). ''Root Evaluation Errors: How they Arise and Propagate''. [[ICGA Journal#11_23|ICCA Journal, Vol. 11, Nos. 2/3]]
 
* [[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]
 
* [[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]
Line 164: Line 154:
 
* [[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, 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]]
+
* [[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)]
 
* [[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]
 
* [[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
 
* [[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
Line 172: Line 162:
 
* [[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]], [[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]], [[Valentin Rottmann]] ('''1996'''). ''Parallel Controlled Conspiracy-Number Search.'' [[Advances in Computer Chess 8]]
* [[Ulf Lorenz]] ('''1999'''). ''Controlled Conspiracy-2 Search''. Technical Report, [[University of Paderborn]], [http://www2.cs.upb.de/cs/ag-monien/PUBLICATIONS/POSTSCRIPTS/Falgo.ps ps]
+
* [[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]
 
* [[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 ...==  
 
==2000 ...==  
 
* [[Ulf Lorenz]] ('''2000'''). ''Controlled Conspiracy-2 Search''. Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science (STACS)
 
* [[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]]
+
* [[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 ...==
 
==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]], [[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]
 
* [[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]] ('''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]]
  
 
=External Links=  
 
=External Links=  
Line 192: Line 186:
 
* [https://en.wikipedia.org/wiki/List_of_conspiracy_theories List of conspiracy theories from Wikipedia]
 
* [https://en.wikipedia.org/wiki/List_of_conspiracy_theories List of conspiracy theories from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Conspiracy_theory_%28disambiguation%29 Conspiracy theory (disambiguation) from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Conspiracy_theory_%28disambiguation%29 Conspiracy theory (disambiguation) from Wikipedia]
* [[Videos#JeanneLee|Jeanne Lee]] - Sundance, [https://www.discogs.com/de/Jeanne-Lee-Conspiracy/release/687632 Conspiracy] (1975), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
+
* [[:Category:Chris Squire|Squire]] & [https://en.wikipedia.org/wiki/Billy_Sherwood Sherwood], [https://en.wikipedia.org/wiki/Conspiracy_%28band%29 Conspiracy] - [https://en.wikipedia.org/wiki/Conspiracy_(band)#Conspiracy Conspiracy], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: feat.:  [https://fr.wikipedia.org/wiki/Jack_Gregg Jack Gregg], [https://en.wikipedia.org/wiki/Mark_Whitecage Mark Whitecage], [https://en.wikipedia.org/wiki/Steve_McCall_(drummer) Steve McCall], [[Videos#GunterHampel|Gunter Hampel]], [https://en.wikipedia.org/wiki/Sam_Rivers Sam Rivers], [https://en.wikipedia.org/wiki/Marty_Cook Marty Cook]
 
: {{#evu:https://www.youtube.com/watch?v=CRqGVLEYbUc|alignment=left|valignment=top}}
 
* [[Videos#ChrisSquire|Squire]] & [https://en.wikipedia.org/wiki/Billy_Sherwood Sherwood], [https://en.wikipedia.org/wiki/Conspiracy_%28band%29 Conspiracy] - [https://en.wikipedia.org/wiki/Conspiracy_(band)#Conspiracy Conspiracy], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
 
 
: {{#evu:https://www.youtube.com/watch?v=af-8Of_uBxw|alignment=left|valignment=top}}
 
: {{#evu:https://www.youtube.com/watch?v=af-8Of_uBxw|alignment=left|valignment=top}}
  
Line 202: Line 193:
  
 
'''[[Search|Up one Level]]'''
 
'''[[Search|Up one Level]]'''
 +
[[Category:Chris Squire]]

Latest revision as of 16:10, 16 November 2020

Home * Search * Conspiracy Numbers

Jonathan Schaeffer on Conspiracy Numbers. [1]

Conspiracy Numbers of the root or interior nodes of a search tree for some value V are defined as the least number of conspirators, that are leaves that must change their evaluation value to V in order to change the minimax value of the interior node or root [2]. Conspiracy Numbers and their possible application for Minimax search within a best-first search algorithm was first described by David McAllester [3].

Sample

Minimax Tree

A sample minimax tree T with some arbitrary values of the leaves [4]:

root                    ┌───────┐
max node                │  A=3  │
                        └───────┘
           ┌───────┐                 ┌───────┐
min nodes  │  B=2  │                 │  C=3  │
           └───────┘                 └───────┘
  ┌───────┐       ┌───────┐   ┌───────┐       ┌───────┐
  │  D=5  │       │  E=2  │   │  F=3  │       │  G=4  │
  └───────┘       └───────┘   └───────┘       └───────┘

Conspiracy Numbers

Conspiracy numbers for all possible values of the root A
v cn(A, v) conspirators
<= 1 2 (D or E) and (F or G)
2 1 (F or G)
3 0 none
4 1 (E or F)
5 1 E
>= 6 2 (D and E) or (F and G)
Conspiracy numbers for all possible values of node B
v cn(B, v) conspirators
<= 1 1 (D or E)
2 0 none
3,4,5 1 E
>= 6 2 (D and E)
Conspiracy numbers for all possible values of node C
v cn(C, v) conspirators
<= 2 1 (F or G)
3 0 none
4 1 F
>= 5 2 (F and G)

Recursive Definition

Following recursive definition in pseudo C is based on Van der Meulen's code [5]. V(J) represents the minimaxed value of node J. Opposed to McAllester's original definition which deals with pure game theoretic values, Van der Meulen's distinguished non terminal leaves with cn = 1 for values different of v from game theoretic terminal nodes to assign +oo, since it is impossible to change their value, independently been arrived at by Norbert Klingbeil and Jonathan Schaeffer [6]:

int cn(CNode J, int v) {
   int c;
   if ( V(J) == v ) {
      c = 0;
   } else if ( isTerminal(J) ) { 
      c = +oo; /* checkmate, stalemate, tablebase score, etc. */
   } else if ( isLeaf(J) ) {
      c = 1; 
   } else if (isMaxNode(J) && v < V(J) ) {
      c = 0;
      for (all childs J.j)
         if (v < V(J.j) ) c += cn(J.j, v); /* sum */
   } else if (isMinNode(J) && v > V(J) ) {
      c = 0;
      for (all childs J.j)
         if (v > V(J.j) ) c += cn(J.j, v); /* sum */
   } else {
      c = +oo;
      for (all childs J.j)
         c = min( cn(J.j, v), c);
   }
   return c;
}

Conspiracy Theory

Let δ be a number called the singular margin [7]. Conspiracy theory can be formulated using the following definition [8]:

Definition: Let T be a search tree with min-max value V[T]. The lower boand conspiracy number of T, denoted C<[T], is the number of leaf static values that must be changed to bring the root min-max value down to V[T]-δ. The upper boand conspiracy number of T, denoted C>[T], is the number of leaves that must be changed to bring the root value up to V[T]+δ. 

C<[T] expresses the confidence that the lower bound α will hold by further expansion of the search tree.

Search Algorithms

McAllester's aim was related to some drawbacks of alpha-beta, at the worst, the decision at the root is based on a single evaluation of one leaf. If that leaf has assigned an erroneous value, the decision may be disastrous [9]. The idea of Conspiracy Number Search (cn-search) and its variants is to continue until it is unlikely that the minimax value at the root will change.

Publications

[10]

1985 ...

1990 ...

1995 ...

2000 ...

2010 ...

External Links

Conspiracy Numbers

Conspiracy

References

  1. Photo from Advances in Computer Chess 5 by László Lindner, ICCA Journal, Vol. 10, No. 3, pp. 138
  2. Definition, Sample, and Pseudo code taken from Maarten van der Meulen (1990). Conspiracy-Number Search. ICCA Journal, Vol. 13, No. 1
  3. David McAllester (1988). Conspiracy Numbers for Min-Max Search. Artificial Intelligence, Vol. 35, No. 1, pp. 287-310. ISSN 0004-3702
  4. due to Jonathan Schaeffer (1989). Conspiracy Numbers. Advances in Computer Chess 5
  5. Maarten van der Meulen (1990). Conspiracy-Number Search. ICCA Journal, Vol. 13, No. 1
  6. Norbert Klingbeil, Jonathan Schaeffer (1988). Search Strategies for Conspiracy Numbers. Canadian Artificial Intelligence Conference, pp. 133-139
  7. The term singular margin comes from the singular extension algorithm (Anantharaman et al. 1990)
  8. David McAllester, Deniz Yuret (1993). Alpha-Beta Conspiracy Search. ps (draft)
  9. Ulf Lorenz, Valentin Rottmann (1996). Parallel Controlled Conspiracy-Number Search. Advances in Computer Chess 8
  10. ICGA Reference Database

Up one Level