Difference between revisions of "Conspiracy Numbers"

From Chessprogramming wiki
Jump to: navigation, search
Line 3: Line 3:
 
[[FILE:ACC5Schaeffer.jpg|border|right|thumb|[[Jonathan Schaeffer]] on ''Conspiracy Numbers.'' <ref>Photo from [[Advances in Computer Chess 5]] by  [[László Lindner]], [[ICGA Journal#10_3|ICCA Journal, Vol. 10, No. 3]], pp. 138</ref> ]]
 
[[FILE:ACC5Schaeffer.jpg|border|right|thumb|[[Jonathan Schaeffer]] on ''Conspiracy Numbers.'' <ref>Photo from [[Advances in Computer Chess 5]] by  [[László Lindner]], [[ICGA Journal#10_3|ICCA Journal, Vol. 10, No. 3]], pp. 138</ref> ]]
  
'''Conspiracy Numbers''' of the [[Root|root]] or [[Interior Node|interior nodes]] of a [[Search Tree|search tree]] for some value '''v''' are defined as the least number of conspirators, that are [[Leaf Node|leaves]] that must change their evaluation value to '''v''' in order to change the minimax value of the interior node or root <ref>Definition, Sample, and Pseudo code taken from [[Maarten van der Meulen]] ('''1990'''). ''Conspiracy-Number Search''. [[ICGA Journal#13_1|ICCA Journal, Vol. 13, No. 1]]</ref>. Conspiracy Numbers and their possible application for [[Minimax]] search within a [[Best-First|best-first search]] algorithm was first described by [[David McAllester]] <ref>[[David McAllester]] ('''1988'''). ''Conspiracy Numbers for Min-Max Search''. Artificial Intelligence, Vol. 35, No. 1, pp. 287-310. ISSN 0004-3702</ref>.
+
'''Conspiracy Numbers''' of the [[Root|root]] or [[Interior Node|interior nodes]] of a [[Search Tree|search tree]] for some value '''v''' are defined as the least number of conspirators, that are [[Leaf Node|leaves]] that must change their evaluation value to '''v''' in order to change the minimax value of the interior node or root <ref>Definition, Sample, and Pseudo code taken from [[Maarten van der Meulen]] ('''1990'''). ''Conspiracy-Number Search''. [[ICGA Journal#13_1|ICCA Journal, Vol. 13, No. 1]]</ref>. Conspiracy Numbers and their possible application for [[Minimax]] search within a [[Best-First|best-first search]] algorithm was first described by [[David McAllester]] <ref>[[David McAllester]] ('''1988'''). ''Conspiracy Numbers for Min-Max Search''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 35, No. 1, pp. 287-310. ISSN 0004-3702</ref>.
  
 
=Sample=  
 
=Sample=  
Line 142: Line 142:
 
==1985 ...==  
 
==1985 ...==  
 
* [[David McAllester]] ('''1985'''). ''A New Procedure for Growing Minimax Trees''. Technical Report, Artificial Intelligence Laboratory, MIT
 
* [[David McAllester]] ('''1985'''). ''A New Procedure for Growing Minimax Trees''. Technical Report, Artificial Intelligence Laboratory, MIT
* [[David McAllester]] ('''1988'''). ''Conspiracy Numbers for Min-Max Search''. Artificial Intelligence, Vol. 35, No. 1, pp. 287-310. ISSN 0004-3702
+
* [[David McAllester]] ('''1988'''). ''Conspiracy Numbers for Min-Max Search''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 35, No. 1
 
* [[Ingo Althöfer]] ('''1988'''). ''Root Evaluation Errors: How they Arise and Propagate''. [[ICGA Journal#11_23|ICCA Journal, Vol. 11, Nos. 2/3]]
 
* [[Ingo Althöfer]] ('''1988'''). ''Root Evaluation Errors: How they Arise and Propagate''. [[ICGA Journal#11_23|ICCA Journal, Vol. 11, Nos. 2/3]]
 
* [[Maarten van der Meulen]] ('''1988'''). ''Parallel Conspiracy-Number Search''. M.Sc. thesis, Faculty of Mathematics and Computer Science, [https://en.wikipedia.org/wiki/Vrije_Universiteit Vrije Universteit, Amsterdam]
 
* [[Maarten van der Meulen]] ('''1988'''). ''Parallel Conspiracy-Number Search''. M.Sc. thesis, Faculty of Mathematics and Computer Science, [https://en.wikipedia.org/wiki/Vrije_Universiteit Vrije Universteit, Amsterdam]

Revision as of 10:54, 8 December 2019

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;
}

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 [7]. 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

[8]

1985 ...

1990 ...

1995 ...

2000 ...

2010 ...

External Links

Conspiracy Numbers

Conspiracy

feat.: Jack Gregg, Mark Whitecage, Steve McCall, Gunter Hampel, Sam Rivers, Marty Cook

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. Ulf Lorenz, Valentin Rottmann (1996). Parallel Controlled Conspiracy-Number Search. Advances in Computer Chess 8
  8. ICGA Reference Database(pdf)

Up one Level