25,161
edits
Changes
m
* [[Controlled Conspiracy Number Search]]
* [[Parallel Controlled Conspiracy Number Search]]
no edit summary
'''[[Main Page|Home]] * [[Search]] * Conspiracy Numbers'''
[[FILE:ACC5Schaeffer.jpg|border|right|thumb|link=Advances in Computer Chess 5| [[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>.
=Sample=
==Minimax Tree==
A sample minimax tree T with some arbitrary values of the leaves <ref>due to [[Jonathan Schaeffer]] ('''1989'''). ''Conspiracy Numbers.'' [[Advances in Computer Chess 5]]</ref></ref>:
<pre>
root ┌───────┐
max node │ 1 A │
└───────┘
/ 3 \
┌───────┐ ┌───────┐
min nodes │ 1.1 B │ │ 1.2 C │
└───────┘ └───────┘
/ 2 \ / 3 \
┌───────┐ ┌───────┐ ┌───────┐ ┌───────┐
│ 1.1.1 D │ │ 1.1.2 E │ │ 1.2.1 F │ │ 1.2.2 G │
└───────┘ └───────┘ └───────┘ └───────┘
5 2 3 4
==Conspiracy Numbers==
The conspiracy numbers for all possible value values of the root of tree T
{| class="wikitable"
|-
| colspan="3" | The conspiracy numbers for all possible values of the root of tree T
|-
! v
! cn(rootA, v)
! conspirators
|-
| style="text-align:center;" | <= 1
! 2
| style="text-align:center;" | (1.1.1 D or 1.1.2E) and (1.2.1 F or 1.2.2G)
|-
| style="text-align:center;" | 2
! 1
| style="text-align:center;" | (1.2.1 F or 1.2.2G)
|-
| style="text-align:center;" | 3
| style="text-align:center;" | 4
! 1
| style="text-align:center;" | (1.1.2 E or 1.2.1F)
|-
| style="text-align:center;" | 5
! 1
| style="text-align:center;" | 1.1.2 E
|-
| style="text-align:center;" | >= 6
! 2
| style="text-align:center;" | (1.1.1 D and 1.1.2E) or (1.2.1 F and 1.2.2G) |}-| colspan="3" | The conspiracy numbers for all possible value values of node 1.1 B of tree T{| class="wikitable"
|-
! v
! cn(1.1B, v)
! conspirators
|-
| style="text-align:center;" | <= 1
! 1
| style="text-align:center;" | (1.1.1 D or 1.1.2E)
|-
| style="text-align:center;" | 2
| style="text-align:center;" | 3,4,5
! 1
| style="text-align:center;" | 1.1.2 E
|-
| style="text-align:center;" | >= 6
! 2
| style="text-align:center;" | (1.1.1 D and 1.1.2E) |}-| colspan="3" | The conspiracy numbers for all possible value values of node 1.2 C of tree T{| class="wikitable"
|-
! v
! cn(1.2C, v)
! conspirators
|-
| style="text-align:center;" | <= 2
! 1
| style="text-align:center;" | (1.2.1 F or 1.2.2G)
|-
| style="text-align:center;" | 3
| style="text-align:center;" | 4
! 1
| style="text-align:center;" | 1.2.1 F
|-
| style="text-align:center;" | >= 5
! 2
| style="text-align:center;" | (1.2.1 F and 1.2.2G)
|}
* [[Alpha-Beta Conspiracy Search]]
* [[Conspiracy Number Search]]
* [[Proof-Number Search]]
