Difference between revisions of "Conspiracy Number Search"

From Chessprogramming wiki
Jump to: navigation, search
 
(7 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
'''[[Main Page|Home]] * [[Search]] * Conspiracy Number Search'''
 
'''[[Main Page|Home]] * [[Search]] * Conspiracy Number Search'''
 +
 +
[[FILE:Dollarnote siegel hq.jpg|border|right|thumb| [https://en.wikipedia.org/wiki/Eye_of_Providence Eye of Providence] <ref>The [https://en.wikipedia.org/wiki/Eye_of_Providence Eye of Providence] can be seen on the reverse of the [https://en.wikipedia.org/wiki/Great_Seal_of_the_United_States Great Seal of the United States], seen here on the [https://en.wikipedia.org/wiki/United_States_one-dollar_bill US $1 bill]. Popular among [https://en.wikipedia.org/wiki/Conspiracy_theory conspiracy theorists] is the claim that the Eye of Providence shown atop an unfinished pyramid on the Great Seal of the United States indicates the influence of [https://en.wikipedia.org/wiki/Freemasonry Freemasonry] in the [https://en.wikipedia.org/wiki/Founding_Fathers_of_the_United_States founding of the United States], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]
  
 
'''Conspiracy Number Search''', (CNS, cns)<br/>
 
'''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]].
+
a [[Best-First|best-first search]] algorithm first described by [[David McAllester]] based on [[Conspiracy Numbers]] of the [[Root|root]] <ref>[[David McAllester]] ('''1985'''). ''A New Procedure for Growing Minimax Trees''. Technical Report, Artificial Intelligence Laboratory, [[Massachusetts Institute of Technology|MIT]]</ref>.
 
[[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.  
 
[[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.
+
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.
+
=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 '''W''' depends on the number of possible evaluation values, fine grained evaluation, considered necessary for good positional play, yields 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>
 
<span id="CCNS"></span>
=Controlled Conspiracy Number Search=  
+
=CCNS=  
[[Ulf Lorenz|Ulf Lorenz']] and [[Valentin Rottmann|Valentin Rottmann's]] et al. improvement dubbed '''Controlled Conspiracy Number Search''' (CCNS) <ref>[[Ulf Lorenz]], [[Valentin Rottmann]], [[Rainer Feldmann]], [[Peter Mysliwietz]] ('''1995'''). ''Controlled Conspiracy-Number Search.'' [[ICGA Journal#18_3|ICCA Journal, Vol. 18, No. 3]]</ref> addresses 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.
+
[[Ulf Lorenz|Ulf Lorenz']] and [[Valentin Rottmann|Valentin Rottmann's]] et al. proposed improvements dubbed '''Controlled Conspiracy Number Search''' (CCNS) <ref>[[Ulf Lorenz]], [[Valentin Rottmann]], [[Rainer Feldmann]], [[Peter Mysliwietz]] ('''1995'''). ''Controlled Conspiracy-Number Search.'' [[ICGA Journal#18_3|ICCA Journal, Vol. 18, No. 3]]</ref> 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.
 
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>
 
<span id="PCCNS"></span>
=Parallel Controlled Conspiracy Number Search=
+
=PCCNS=
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.
+
'''Parallel Controlled Conspiracy Number Search''' (PCCNS) 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>.
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>.
+
 
 +
=See also=
 +
* [[:Category:CNS]]
 +
* [[Alpha-Beta Conspiracy Search]]
 +
* [[Conspiracy Numbers]]
 +
* [[Proof-Number Search]]
  
 
=Chess Programs=  
 
=Chess Programs=  
Line 24: Line 33:
 
=Publications=  
 
=Publications=  
 
==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, [[Massachusetts Institute of Technology|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 34: Line 43:
 
==1990 ...==  
 
==1990 ...==  
 
* [[Maarten van der Meulen]] ('''1990'''). ''Conspiracy-Number Search''. [[ICGA Journal#13_1|ICCA Journal, Vol. 13, No. 1]]
 
* [[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]
+
* [[Norbert Klingbeil]], [[Jonathan Schaeffer]] ('''1990'''). ''[https://www.semanticscholar.org/paper/Empirical-results-with-conspiracy-numbers-Klingbeil-Schaeffer/5fc0f8a0901c5e85c04ec813b6e11a7acf32143f Empirical Results with Conspiracy Numbers].'' [https://en.wikipedia.org/wiki/Computational_Intelligence_(journal) Computational Intelligence], Vol. 6
 
* <span id="AI"></span>[[Jonathan Schaeffer]] ('''1990'''). ''Conspiracy Numbers''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 43, No. 1
 
* <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]]
+
* [[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)]
Line 49: Line 58:
 
* [[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'''). ''[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)
 
* [[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'''). ''[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]
 
* [[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 ...==
Line 55: Line 64:
 
* [[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]
 
* [[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]]
 
* [[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=  
 +
* [https://en.wikipedia.org/wiki/Conspiracy Conspiracy from Wikipedia]
 +
* [https://en.wikipedia.org/wiki/Conspiracy_(disambiguation) Conspiracy (disambiguation) from Wikipedia]
 +
* [https://en.wikipedia.org/wiki/Conspiracy_(board_game) Conspiracy (board game) from Wikipedia]
 
* [[:Category:Jeanne Lee|Jeanne Lee]] - Sundance, [https://www.discogs.com/de/Jeanne-Lee-Conspiracy/release/687632 Conspiracy] (1975), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
 
* [[:Category:Jeanne Lee|Jeanne Lee]] - Sundance, [https://www.discogs.com/de/Jeanne-Lee-Conspiracy/release/687632 Conspiracy] (1975), [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], [[:Category:Gunter Hampel|Gunter Hampel]], [https://en.wikipedia.org/wiki/Sam_Rivers Sam Rivers], [https://en.wikipedia.org/wiki/Marty_Cook Marty Cook]
 
: 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], [[:Category:Gunter Hampel|Gunter Hampel]], [https://en.wikipedia.org/wiki/Sam_Rivers Sam Rivers], [https://en.wikipedia.org/wiki/Marty_Cook Marty Cook]

Latest revision as of 21:48, 9 September 2020

Home * Search * Conspiracy Number Search

Conspiracy Number Search, (CNS, cns)
a best-first search algorithm first described by David McAllester based on Conspiracy Numbers of the root [2]. Trees are grown in 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, Expansion and Evaluation of that leaf, and to Back-up the result of that evaluation back to the root.

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 [3]. Since W depends on the number of possible evaluation values, fine grained evaluation, considered necessary for good positional play, yields into additional computation and thus inefficient search. Further, a final alpha-beta quiescence search in early CNS implementations was quite expensive due to the lack of bounds.

CCNS

Ulf Lorenz' and Valentin Rottmann's et al. proposed improvements dubbed Controlled Conspiracy Number Search (CCNS) [4] 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.

PCCNS

Parallel Controlled Conspiracy Number Search (PCCNS) 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, 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 [5].

See also

Chess Programs

performing CNS or its improvements:

Publications

1985 ...

1990 ...

1995 ...

2000 ...

2010 ...

External Links

feat.: Jack Gregg, Mark Whitecage, Steve McCall, Gunter Hampel, Sam Rivers, Marty Cook

References

  1. The Eye of Providence can be seen on the reverse of the Great Seal of the United States, seen here on the US $1 bill. Popular among conspiracy theorists is the claim that the Eye of Providence shown atop an unfinished pyramid on the Great Seal of the United States indicates the influence of Freemasonry in the founding of the United States, Wikimedia Commons
  2. David McAllester (1985). A New Procedure for Growing Minimax Trees. Technical Report, Artificial Intelligence Laboratory, MIT
  3. Quang Vu, Taichi Ishitobi, Jean-Christophe Terrillon, Hiroyuki Iida (2016). Using Conspiracy Numbers for Improving Move Selection in Minimax Game-Tree Search. ICAART 2016, pdf
  4. Ulf Lorenz, Valentin Rottmann, Rainer Feldmann, Peter Mysliwietz (1995). Controlled Conspiracy-Number Search. ICCA Journal, Vol. 18, No. 3
  5. Ulf Lorenz, Valentin Rottmann (1996). Parallel Controlled Conspiracy-Number Search. Advances in Computer Chess 8

Up one level