Difference between revisions of "Conspiracy Numbers"
GerdIsenberg (talk | contribs) (Created page with "'''Home * Search * Conspiracy Numbers''' border|right|thumb|link=Advances in Computer Chess 5| [[Jonathan Schaeffer on ''Conspira...") |
GerdIsenberg (talk | contribs) m |
||
Line 1: | Line 1: | ||
'''[[Main Page|Home]] * [[Search]] * Conspiracy Numbers''' | '''[[Main Page|Home]] * [[Search]] * Conspiracy Numbers''' | ||
− | [[FILE:ACC5Schaeffer.jpg|border|right|thumb | + | [[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''. 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>. | ||
Line 9: | Line 7: | ||
=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]] | + | 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 │ | + | max node │ A │ |
└───────┘ | └───────┘ | ||
/ 3 \ | / 3 \ | ||
┌───────┐ ┌───────┐ | ┌───────┐ ┌───────┐ | ||
− | min nodes │ | + | min nodes │ B │ │ C │ |
└───────┘ └───────┘ | └───────┘ └───────┘ | ||
/ 2 \ / 3 \ | / 2 \ / 3 \ | ||
┌───────┐ ┌───────┐ ┌───────┐ ┌───────┐ | ┌───────┐ ┌───────┐ ┌───────┐ ┌───────┐ | ||
− | │ | + | │ D │ │ E │ │ F │ │ G │ |
└───────┘ └───────┘ └───────┘ └───────┘ | └───────┘ └───────┘ └───────┘ └───────┘ | ||
5 2 3 4 | 5 2 3 4 | ||
Line 27: | Line 24: | ||
==Conspiracy Numbers== | ==Conspiracy Numbers== | ||
− | The conspiracy numbers for all possible | + | The conspiracy numbers for all possible values of the root of tree T |
{| class="wikitable" | {| class="wikitable" | ||
+ | |- | ||
+ | | colspan="3" | The conspiracy numbers for all possible values of the root of tree T | ||
|- | |- | ||
! v | ! v | ||
− | ! cn( | + | ! cn(A, v) |
! conspirators | ! conspirators | ||
|- | |- | ||
| style="text-align:center;" | <= 1 | | style="text-align:center;" | <= 1 | ||
! 2 | ! 2 | ||
− | | style="text-align:center;" | ( | + | | 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;" | ( | + | | style="text-align:center;" | (F or G) |
|- | |- | ||
| style="text-align:center;" | 3 | | style="text-align:center;" | 3 | ||
Line 48: | Line 47: | ||
| style="text-align:center;" | 4 | | style="text-align:center;" | 4 | ||
! 1 | ! 1 | ||
− | | style="text-align:center;" | ( | + | | style="text-align:center;" | (E or F) |
|- | |- | ||
| style="text-align:center;" | 5 | | style="text-align:center;" | 5 | ||
! 1 | ! 1 | ||
− | | style="text-align:center;" | | + | | style="text-align:center;" | E |
|- | |- | ||
| style="text-align:center;" | >= 6 | | style="text-align:center;" | >= 6 | ||
! 2 | ! 2 | ||
− | | style="text-align:center;" | ( | + | | style="text-align:center;" | (D and E) or (F and G) |
− | | | + | |- |
− | + | | colspan="3" | The conspiracy numbers for all possible values of node B of tree T | |
− | The conspiracy numbers for all possible | ||
− | |||
|- | |- | ||
! v | ! v | ||
− | ! cn( | + | ! cn(B, v) |
! conspirators | ! conspirators | ||
|- | |- | ||
| style="text-align:center;" | <= 1 | | style="text-align:center;" | <= 1 | ||
! 1 | ! 1 | ||
− | | style="text-align:center;" | ( | + | | style="text-align:center;" | (D or E) |
|- | |- | ||
| style="text-align:center;" | 2 | | style="text-align:center;" | 2 | ||
Line 76: | Line 73: | ||
| style="text-align:center;" | 3,4,5 | | style="text-align:center;" | 3,4,5 | ||
! 1 | ! 1 | ||
− | | style="text-align:center;" | | + | | style="text-align:center;" | E |
|- | |- | ||
| style="text-align:center;" | >= 6 | | style="text-align:center;" | >= 6 | ||
! 2 | ! 2 | ||
− | | style="text-align:center;" | ( | + | | style="text-align:center;" | (D and E) |
− | | | + | |- |
− | + | | colspan="3" | The conspiracy numbers for all possible values of node C of tree T | |
− | The conspiracy numbers for all possible | ||
− | |||
|- | |- | ||
! v | ! v | ||
− | ! cn( | + | ! cn(C, v) |
! conspirators | ! conspirators | ||
|- | |- | ||
| style="text-align:center;" | <= 2 | | style="text-align:center;" | <= 2 | ||
! 1 | ! 1 | ||
− | | style="text-align:center;" | ( | + | | style="text-align:center;" | (F or G) |
|- | |- | ||
| style="text-align:center;" | 3 | | style="text-align:center;" | 3 | ||
Line 100: | Line 95: | ||
| style="text-align:center;" | 4 | | style="text-align:center;" | 4 | ||
! 1 | ! 1 | ||
− | | style="text-align:center;" | | + | | style="text-align:center;" | F |
|- | |- | ||
| style="text-align:center;" | >= 5 | | style="text-align:center;" | >= 5 | ||
! 2 | ! 2 | ||
− | | style="text-align:center;" | ( | + | | style="text-align:center;" | (F and G) |
|} | |} | ||
Line 140: | Line 135: | ||
* [[Alpha-Beta Conspiracy Search]] | * [[Alpha-Beta Conspiracy Search]] | ||
* [[Conspiracy Number Search]] | * [[Conspiracy Number Search]] | ||
− | |||
− | |||
* [[Proof-Number Search]] | * [[Proof-Number Search]] | ||
Revision as of 15:02, 3 May 2018
Home * Search * Conspiracy Numbers
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].
Contents
Sample
Minimax Tree
A sample minimax tree T with some arbitrary values of the leaves [4]:
root ┌───────┐ max node │ A │ └───────┘ / 3 \ ┌───────┐ ┌───────┐ min nodes │ B │ │ C │ └───────┘ └───────┘ / 2 \ / 3 \ ┌───────┐ ┌───────┐ ┌───────┐ ┌───────┐ │ D │ │ E │ │ F │ │ G │ └───────┘ └───────┘ └───────┘ └───────┘ 5 2 3 4
Conspiracy Numbers
The conspiracy numbers for all possible values of the root of tree T
The conspiracy numbers for all possible values of the root of tree T | ||
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) |
The conspiracy numbers for all possible values of node B of tree T | ||
v | cn(B, v) | conspirators |
<= 1 | 1 | (D or E) |
2 | 0 | none |
3,4,5 | 1 | E |
>= 6 | 2 | (D and E) |
The conspiracy numbers for all possible values of node C of tree T | ||
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; }
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 [7]. 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.
Chess Programs
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. 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, 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. » also published
- Charles Elkan (1989). Conspiracy Numbers and Caching for Searching And/Or Trees and Theorem-Proving. IJCAI 1989, pdf
1990 ...
- Maarten van der Meulen (1990). Conspiracy-Number Search. ICCA Journal, Vol. 13, No. 1
- Norbert Klingbeil, Jonathan Schaeffer (1990). Empirical Results with Conspiracy Numbers. Computational Intelligence, Vol. 6, pp. 1-11, ps
- Jonathan Schaeffer (1990). Conspiracy Numbers. 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. 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. ps (draft)
- Lisa Lister, Jonathan Schaeffer (1994). An Analysis of the Conspiracy Numbers Algorithm. Computers & Mathematics with Applications Vol. 27, No. 1, Elsevier, pdf
- Deniz Yuret (1994). The Principle of Pressure in Chess. TAINN 1994
1995 ...
- Ulf Lorenz, Valentin Rottmann, Rainer Feldmann, Peter Mysliwietz (1995). Controlled Conspiracy-Number Search. 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, University of Paderborn, ps
- Robin Upton (1999). Dynamic Stochastic Control - A New Approach to Game Tree Searching. Ph.D. thesis, 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, Vol. 25, No. 1
2010 ...
- Mohd Nor Akmal Khalid, Umi Kalsom Yusof, Hiroyuki Iida, Taichi Ishitobi (2015). Critical Position Identification in Games and Its Application to Speculative Play. ICAART 2015
- Mohd Nor Akmal Khalid, E. Mei Ang, Umi Kalsom Yusof, Hiroyuki Iida, Taichi Ishitobi (2015). Identifying Critical Positions Based on Conspiracy Numbers. Agents and Artificial Intelligence, ICAART 2015 - Revised Selected Papers
- Jakub Pawlewicz, Ryan Hayward (2015). Sibling Conspiracy Number Search. SoCS 2015
External Links
Conspiracy Numbers
- Conspiracy Numbers, Conspiracy Probailities & PCN* Search by Robin Upton
- Reading: McAllister paper on "Consipracy Theory"? by Bruce Donald
Conspiracy
- Conspiracy (disambiguation) from Wikipedia
- Conspiracy theory from Wikipedia
- List of conspiracy theories from Wikipedia
- Conspiracy theory (disambiguation) from Wikipedia
- Jeanne Lee - Sundance, Conspiracy (1975), YouTube Video
- Squire & Sherwood, Conspiracy - Conspiracy, YouTube Video
References
- ↑ Photo from Advances in Computer Chess 5 by László Lindner, ICCA Journal, Vol. 10, No. 3, pp. 138
- ↑ Definition, Sample, and Pseudo code taken from Maarten van der Meulen (1990). Conspiracy-Number Search. ICCA Journal, Vol. 13, No. 1
- ↑ David McAllester (1988). Conspiracy Numbers for Min-Max Search. Artificial Intelligence, Vol. 35, No. 1, pp. 287-310. ISSN 0004-3702
- ↑ due to Jonathan Schaeffer (1989). Conspiracy Numbers. Advances in Computer Chess 5
- ↑ Maarten van der Meulen (1990). Conspiracy-Number Search. ICCA Journal, Vol. 13, No. 1
- ↑ Norbert Klingbeil, Jonathan Schaeffer (1988). Search Strategies for Conspiracy Numbers. Canadian Artificial Intelligence Conference, pp. 133-139
- ↑ Ulf Lorenz, Valentin Rottmann (1996). Parallel Controlled Conspiracy-Number Search. Advances in Computer Chess 8
- ↑ ICGA Reference Database(pdf)