Does SSS* return a different minimax value from full minimax?

A correct complete search of the same finite tree and leaf values returns the same value.

Does it always run faster than alpha-beta?

No. Comparisons depend on the implementation and experimental conditions; fewer evaluated leaves alone do not settle elapsed time.

Can it use heuristic leaf scores?

Yes in a depth-limited search model, but the resulting value is then the minimax value of that evaluated tree, not a proof of the full game's outcome.

AI Glossary / Graphs and symbolic AI / Advanced

SSS*

Definition

SSS* is a best-first game-tree search algorithm for computing a minimax value. Introduced by George Stockman, it explores and refines partial solution trees rather than simply completing one ordinary depth-first traversal. Its central idea is to focus work on the partial result most relevant to establishing the game's value under the specified search model.

What it means

In a minimax tree, MAX chooses the alternative with the highest value and MIN chooses the alternative with the lowest value. A search algorithm must account for both kinds of choice. Finding one attractive leaf is insufficient because an opponent may choose another continuation.
SSS* can be understood through a sequence of upper bounds on the root value. It refines the parts of the search that currently determine the bound until the minimax value is established. The result is exact for the supplied finite search tree and leaf values; if those leaves are heuristic evaluations at a depth limit, the result remains relative to that limited model.

How it works

One useful explanation uses a max solution tree: retain all children at MAX nodes but only one child at each MIN node. Restricting MIN's choices can only make the result at least as favorable to MAX as the full tree, so the backed-up value is an upper bound.
SSS* refines this bound by investigating relevant alternatives at MIN nodes, tracking live or solved search information in a prioritized structure. Its original formulation uses an OPEN list. Later research expresses equivalent search behavior through repeated narrow-window alpha-beta calls with stored search information. The precise bookkeeping is essential; an arbitrary best-first traversal is not automatically SSS*.

Three practical examples

A game-search course can compare best-first bound refinement with a depth-first alpha-beta trace on the same small tree.
A researcher can study how stored bounds affect repeated game-tree searches.
A deterministic adversarial-planning experiment can examine minimax alternatives, provided its MAX/MIN assumptions actually match the modeled interaction.

Think of it this way

Think of evaluating a set of proposals against an opponent's possible objections. Initially considering only one objection per proposal gives an optimistic assessment. You investigate the proposal currently setting the optimistic best result until you know what can really be guaranteed. The analogy is limited because SSS* follows exact tree and bound rules, whereas human objections may not form a known finite zero-sum model.

Worked example

Consider an original two-level game tree. The root is MAX with three children A, B, and C, all MIN nodes. A's leaf values, from left to right, are 8 and 5. B's are 7 and 2. C's are 4 and 9. Larger numbers are better for MAX.
An initial max solution tree includes all three root alternatives but only the first leaf under each MIN node. Its backed-up value is max(8, 7, 4) = 8. This is an upper bound because MIN has not yet been allowed every reply.
Refine the currently highest branch A by examining its other leaf, 5. A's exact value is min(8, 5) = 5. The root upper bound becomes max(5, 7, 4) = 7, now determined by B.
Examine B's second leaf, 2. B's exact value becomes min(7, 2) = 2. The root upper bound is now max(5, 2, 4) = 5. Choosing A guarantees 5 because both of A's replies have been evaluated. Meanwhile C cannot exceed 4: MIN already has the available reply worth 4, regardless of what its other leaf contains.
Thus the root value is established as 5 without needing C's second leaf. Full minimax calculation confirms max(min(8, 5), min(7, 2), min(4, 9)) = max(5, 2, 4) = 5.
This is a conceptual bound-refinement trace with the stated child order, not a complete listing of OPEN-list operations. Five leaves suffice here; this does not establish a general runtime advantage.

Illustrative case study

In a fictional game-engine seminar, two teams implement different minimax searches. One reports that its SSS* experiment evaluates fewer leaves on a chosen tree. The reviewers also ask for elapsed time, memory use, move ordering, and whether both implementations use comparable stored information.
The teams distinguish the search's mathematical result from its engineering performance. They also state whether terminal outcomes or heuristic depth-limited scores are being evaluated. This case illustrates a comparison method, not a claim that SSS* is the best choice for every game or that it produces unbeatable play.

Common misconceptions and mistakes

SSS* is not ordinary A* pathfinding despite the shared star notation. Its search concerns adversarial solution trees and minimax bounds, rather than finding a minimum-cost path to a goal.
Do not turn a leaf-expansion comparison into an unconditional speed claim. Data-structure operations, memory, ordering, and reuse of search results matter. Also avoid confusing an upper bound with a promised outcome: before the bound is matched by a sufficient lower bound, MAX may not be able to guarantee it. Solution-tree naming conventions should be defined explicitly because descriptions in the literature can differ.

Business use

The practical business connection is chiefly through understanding adversarial search and evaluating specialized planning or game systems. It provides an example of directing computation toward information that can change a decision, rather than exhaustively inspecting every possibility.
Before transferring the idea, check whether the problem really has the required adversarial structure. Uncertain demand, cooperative negotiation, and partially observed interactions are not automatically finite deterministic minimax trees. The model's assumptions and evaluation horizon remain as important as the search algorithm.

Check your understanding

A MIN node has one known child worth 3 and another unexplored child. Can its final minimax value exceed 3?

Answer: No. MIN can select the known child, so 3 is an upper bound. The other child may lower the value but cannot force MIN to take something larger.

Related terms

Minimax
Alpha-beta pruning
Best-first search
Transposition table
Solution tree
Upper bound
Null-window search

Learn next

Next, change A's second leaf in the example from 5 to 1. After refining A and B, C's upper bound of 4 can still determine the root, so its remaining reply matters. Compute the full result: max(1, 2, min(4, 9)) = 4.

Sources

Stockman, A minimax algorithm better than alpha-beta?: https://www.sciencedirect.com/science/article/abs/pii/000437027990016X Plaat and colleagues, SSS* = Alpha-Beta + TT: https://arxiv.org/pdf/1404.1517 Plaat and colleagues, A Minimax Algorithm Better Than Alpha-beta? No and Yes: https://arxiv.org/abs/1702.03401

Previous: Squared ranks test Next: Stability