Conspiracy_Numbers - peregrineshahin/ChessProgrammingWiki GitHub Wiki

title: Conspiracy Numbers

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](Lower_Bound "Lower Bound") 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](Upper_Bound "Upper Bound") 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