Catalogue of Artificial Intelligence Techniques

   

Jump to: Top | Entry | References | Comments

View Maths as: Images | MathML

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:


Comments:

Add Comment

No comments.