# Catalogue of Artificial Intelligence Techniques

## SSS*

**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, $G$ , SSS* searches through the space of partial solution trees, gradually analysing larger and larger subtrees of $G$ , eventually producing a single solution tree with the same root and Minimax value as $G$ . 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*.

### References:

- Shinghal, R.,
*Formal Concepts in Artificial Intelligence*, Chapman and Hall , London, 1992, pp.549--569.

### Comments:

No comments.