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.