⭐ SSS* Algorithm

1. 🎯 Learning Objectives

• Explain SSS* as a best-first alternative to Alpha-Beta
• Trace SSS* with initial clusters and refinement
• Understand the SOLVED status and termination condition
• Compare SSS* to Alpha-Beta in terms of nodes inspected

2. 📖 Core Content

3.1 Intuition: Best-First Game Tree Search

3.2 Key Concepts

• Cluster: A set of leaf nodes that form a complete strategy for one player
• Initial cluster: The leftmost leaf of the game tree (most optimistic assumption)
• Refinement: Expanding a cluster by replacing a leaf with its sibling
• SOLVED: When the exact game value of a node is determined

3.3 SSS* Algorithm

text
SSSStar(root):
    OPEN = priority_queue ordered by value (highest first)
    OPEN.add((root, LIVE, +infinity))
    while OPEN is not empty:
        (N, type, value) = OPEN.extract_max()
        if type == SOLVED:
            if N == root: return value
            update parent with solved value
        elif N is a leaf:
            OPEN.add((N, SOLVED, evaluate(N)))
        elif N is a MAX node:
            expand first unprocessed child with same bound
        elif N is a MIN node:
            expand children; when one returns, may prune others

3.4 SSS* vs Alpha-Beta

4. 📝 Practice Questions

Q1: What is a "cluster" in SSS?*

Answer: A cluster is a set of leaf nodes that defines a complete Min/Max strategy. The initial cluster is the leftmost leaf. SSS* iteratively refines clusters by expanding MAX nodes and pruning MIN nodes. Join Discord PreviousMinimax & Alpha-BetaNextAutomated Planning