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

Sample

Minimax Tree

A sample minimax tree T with some arbitrary values of the leaves:
root                    ┌───────┐
max node                │   1   │
                        └───────┘
                     /      3      \
           ┌───────┐                 ┌───────┐
min nodes  │  1.1  │                 │  1.2  │
           └───────┘                 └───────┘
          /    2    \               /    3    \
  ┌───────┐       ┌───────┐   ┌───────┐       ┌───────┐
  │ 1.1.1 │       │ 1.1.2 │   │ 1.2.1 │       │ 1.2.2 │
  └───────┘       └───────┘   └───────┘       └───────┘
      5               2           3               4

Conspiracy Numbers

The conspiracy numbers for all possible value of the root of tree T
v
cn(root, v)
conspirators
<= 1
2
(1.1.1 or 1.1.2) and (1.2.1 or 1.2.2)
2
1
(1.2.1 or 1.2.2)
3
0
none
4
1
(1.1.2 or 1.2.1)
5
1
1.1.2
>= 6
2
(1.1.1 and 1.1.2) or (1.2.1 and 1.2.2)

The conspiracy numbers for all possible value of node 1.1 of tree T
v
cn(1.1, v)
conspirators
<= 1
1
(1.1.1 or 1.1.2)
2
0
none
3,4,5
1
1.1.2
>= 6
2
(1.1.1 and 1.1.2)

The conspiracy numbers for all possible value of node 1.2 of tree T
v
cn(1.2, v)
conspirators
<= 2
1
(1.2.1 or 1.2.2)
3
0
none
4
1
1.2.1
>= 5
2
(1.2.1 and 1.2.2)

Recursive Definition

Following recursive definition in pseudo C is based on Van der Meulen's code [3]. 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 [4]:
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 [5]. 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.


Chess Programs


Publications

[6]

1985 ...

1990 ...

1995 ...

2000 ...

2010 ...


External Links

Conspiracy Numbers


Conspiracy


References

  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. ^ Maarten van der Meulen (1990). Conspiracy-Number Search. ICCA Journal, Vol. 13, No. 1
  4. ^ Norbert Klingbeil, Jonathan Schaeffer (1988). Search Strategies for Conspiracy Numbers. Canadian Artificial Intelligence Conference, pp. 133-139
  5. ^ Ulf Lorenz, Valentin Rottmann (1996). Parallel Controlled Conspiracy-Number Search. Advances in Computer Chess 8
  6. ^ ICGA Reference Database(pdf)

What links here?


Up one Level