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