Catalogue of Artificial Intelligence Techniques
Keywords: games, personal trees, solution trees
Categories: Game Theory , Search
Author(s): Ian Frank
This algorithm, introduced by Stockman in 1979, conducts a `State Space Search' traversing a game tree in a Best-first fashion similar to that of A*. It is based on the notion of solution (or personal) trees. Informally, a solution tree can be formed from any arbitrary Game Tree by pruning the number of branches at each MAX node to one. Such a tree represents a complete strategy for MAX, since it specifies exactly one MAX action for every possible sequence of moves might be made by the opponent. Given a game tree, , SSS* searches through the space of partial solution trees, gradually analysing larger and larger subtrees of , eventually producing a single solution tree with the same root and Minimax value as . SSS* never examines a node that Alpha/Beta Pruning would prune, and may prune some branches that alpha/beta would not. Stockman speculated that SSS* may therefore be a better general algorithm than alpha/beta. However, Rozen and Pearl have shown that the savings in the number of positions that SSS* evaluates relative to alpha/beta is limited and generally not enough to compensate for the increase in other resources (e.g., the storing and sorting of a list of nodes made necessary by the best-first nature of the algorithm). See also DSSS*.
- Shinghal, R., Formal Concepts in Artificial Intelligence
, Chapman and Hall , London, 1992, pp.549--569.