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 [3]:
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 [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;}elseif( isTerminal(J)){
c =+oo;/* checkmate, stalemate, tablebase score, etc. */}elseif( isLeaf(J)){
c =1;}elseif(isMaxNode(J)&& v < V(J)){
c =0;for(all childs J.j)if(v < V(J.j)) c += cn(J.j, v);/* sum */}elseif(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 [6]. 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.
Table of Contents
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 [3]: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 4Conspiracy Numbers
The conspiracy numbers for all possible value of the root of tree TThe conspiracy numbers for all possible value of node 1.1 of tree T
The conspiracy numbers for all possible value of node 1.2 of tree T
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]: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 [6]. 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
[7]1985 ...
1990 ...
1995 ...
2000 ...
2010 ...
External Links
Conspiracy Numbers
Conspiracy
feat.: Jack Gregg, Mark Whitecage, Steve McCall, Gunter Hampel, Sam Rivers, Marty Cook
References
Photo by László Lindner, ICCA Journal, Vol. 10, No. 3, pp. 138
What links here?
Up one Level