Conspiracy Numbers
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=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
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
- 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, Paderborn University, 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
- Ulf Lorenz (2002). Parallel Controlled Conspiracy Number Search. Euro-Par 2002, LNCS 2400, Springer
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
- Jakub Pawlewicz, Ryan Hayward (2016). Conspiracy number search with relative sibling scores. 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. ICAART 2016, pdf
- Zhang Song, Hiroyuki Iida (2018). Using single conspiracy number for long term position evaluation. CG 2018, ICGA Journal, Vol. 40, No. 3
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
- 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
- ↑ The term singular margin comes from the singular extension algorithm (Anantharaman et al. 1990)
- ↑ David McAllester, Deniz Yuret (1993). Alpha-Beta Conspiracy Search. ps (draft)
- ↑ Ulf Lorenz, Valentin Rottmann (1996). Parallel Controlled Conspiracy-Number Search. Advances in Computer Chess 8
- ↑ ICGA Reference Database