Catalogue of Artificial Intelligence Techniques
Keywords: adversary trees, games, personal trees, solution trees
Categories: Game Theory , Search
Author(s): Ian Frank
DSSS* is the Dual of the SSS* algorithm. Whereas SSS* searches through the space of partial solution (or personal) trees, DSSS* searches through the space of partial adversary trees. An adversary tree can be formed from an arbitrary Game Tree by pruning the number of branches at each MIN node to one. Such a tree represents a complete strategy for MIN, since it specifies exactly one MIN action for every possible sequence of moves that might be made by MAX. Like SSS*, DSSS* never examines a node that Alpha/beta Pruning would prune, and may prune some branches that alpha/beta would not, but it suffers from the same increased memory and storage requirements.
- Shinghal, R., Formal Concepts in Artificial Intelligence
, Chapman and Hall , London, 1992, pp.549--569.