This is a temporary, read-only recovery of the chessprogrammingwiki while a longer-term plan is worked out. Editing is not possible right now, but will be again soon.
Chess Programming Wiki All pages Other namespaces

Conspiracy Numbers

Home * Search * Conspiracy Numbers

Jonathan Schaeffer on Conspiracy Numbers. 1Jonathan Schaeffer on Conspiracy Numbers. 1

  1. Photo from Advances in Computer Chess 5 by László Lindner, ICCA Journal, Vol. 10, No. 3, pp. 138↩︎

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

Contents
  1. Sample
    1. Minimax Tree
    2. Conspiracy Numbers
  2. Recursive Definition
  3. Conspiracy Theory
  4. Search Algorithms
  5. Publications
    1. 1985 ...
    2. 1990 ...
    3. 1995 ...
    4. 2000 ...
    5. 2010 ...
  6. External Links
    1. Conspiracy Numbers
    2. Conspiracy
  7. References

Sample

Minimax Tree

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

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

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 6. Conspiracy theory can be formulated using the following definition 7:

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

9

1985 ...

1990 ...

1995 ...

2000 ...

2010 ...

Conspiracy Numbers

Conspiracy

Watch on YouTube

References

Up one Level

  1. Definition, Sample, and Pseudo code taken from Maarten van der Meulen (1990). Conspiracy-Number Search. ICCA Journal, Vol. 13, No. 1↩︎

  2. David McAllester (1988). Conspiracy Numbers for Min-Max Search. Artificial Intelligence, Vol. 35, No. 1, pp. 287-310. ISSN 0004-3702↩︎

  3. due to Jonathan Schaeffer (1989). Conspiracy Numbers. Advances in Computer Chess 5↩︎

  4. Maarten van der Meulen (1990). Conspiracy-Number Search. ICCA Journal, Vol. 13, No. 1↩︎

  5. Norbert Klingbeil, Jonathan Schaeffer (1988). Search Strategies for Conspiracy Numbers. Canadian Artificial Intelligence Conference, pp. 133-139↩︎

  6. The term singular margin comes from the singular extension algorithm (Anantharaman et al. 1990)↩︎

  7. David McAllester, Deniz Yuret (1993). Alpha-Beta Conspiracy Search. ps (draft)↩︎

  8. Ulf Lorenz, Valentin Rottmann (1996). Parallel Controlled Conspiracy-Number Search. Advances in Computer Chess 8↩︎

  9. ICGA Reference Database↩︎

Categories: Chris Squire

What links here

Contributors: GerdIsenberg.