Catalogue of Artificial Intelligence Techniques


Jump to: Top | Entry | References | Comments

View Maths as: Images | MathML


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.



Add Comment

No comments.