Conspiracy Numbers

Home * Search * Conspiracy Numbers

Jonathan Schaeffer on 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 . Conspiracy Numbers and their possible application for Minimax search within a best-first search algorithm was first described by David McAllester .

Sample

Minimax Tree

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

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 . 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 :

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 . 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.

• Alpha-Beta Conspiracy Search
• Conspiracy Number Search
• Proof-Number Search

Chess Programs

• Arachne
• P.ConNerS
• Ulysses

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

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

• Squire & Sherwood, Conspiracy - Conspiracy, YouTube Video

References

Up one Level