Conspiracy Numbers
The first chapter of my thesis describes this selective search technique, introduced in a 1988 paper by McAllester.
The name stems from the observation that when large game trees are explored,
re-evaluating a leaf node only rarely means that the score of the game is affected;
several nodes are usually required to 'conspire' together to affect the score at
the top of a game tree.
A minimal set of nodes which have the potental to do this
is referred to as a conspiracy.
By contrast with non-selective game tree search, which expolores the game
tree in ascending order of depth, CN search looks at the nodes featured in
conpiracies in ascending order of size. i.e. Any single node conspiracies are examined
first, then 2-node conspiracies, then 3-node conspiracies an so on .
Conspiracy Probabilities
Update 2010-10-25: Not the sort of conspiracies you were looking for? If it's the JFK style you're looking for, try here or here.
The final chapter of my thesis introduces this more powerful alternative to conspiracy numbers.
CN search focusses effort on those moves which have the potential to affect the score
of the game at the root of a game tree. However, this is not actually of prime importance
when playing a game - the agreed goal of search is to work out which move to play,
not to score the game. Consequently, the thesis introduces the idea of a conspiracy to
change the provisionally best move.
By looking for the smallest conspiracy, CN search makes the implicit assumption that
each node is equally likely to conspire. An example from the game of chess should show this
to be a significant weakness - an evaluation of a position when a player is in check is likely
to be more uncertain. The method of
Conspiracy Probabilities gets away from static evaluation to allow each position to be
given a probability distribution rather than just a scalar.
PCN* Search
In the thesis I introduce a search algorithm, PCN*, based on conspiracy probabilities.
It is a more powerful generalisation of CN search. PCN* is designed for situations where node
evaluation has different degrees of certainty and may be well suited to deal with a number of
real world applications where a large branching factor causes problems for traditional approaches.
A simple implementation of PCN* in C++ is included as an appendix to my thesis.
Click here to get back to my Ph.D. page.