SSS*

---

title: "SSS*" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["search-algorithms", "articles-with-example-code"] description: "Game tree search algorithm" topic_path: "technology/algorithms" source: "https://en.wikipedia.org/wiki/SSS*" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Game tree search algorithm ::

SSS* is a search algorithm introduced by George Stockman in 1979. It conducts a state space search traversing a game tree in a best-first fashion similar to that of the A* search algorithm.

SSS* is based on the notion of solution 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 made by the opponent. Given a game tree, SSS* searches through the space of partial solution trees, gradually analyzing larger and larger subtrees, eventually producing a single solution tree with the same root and Minimax value as the original game tree. 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, Igor Roizen and Judea 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). However, Aske Plaat, Jonathan Schaeffer, Wim Pijls and Arie de Bruin have shown that a sequence of null-window alpha–beta calls is equivalent to SSS* (i.e., it expands the same nodes in the same order) when alpha–beta is used with a transposition table, as is the case in all game-playing programs for chess, checkers, etc. Now the storing and sorting of the OPEN list were no longer necessary. This allowed the implementation of (an algorithm equivalent to) SSS* in tournament quality game-playing programs. Experiments showed that it did indeed perform better than Alpha–Beta in practice, but that it did not beat NegaScout.

The reformulation of a best-first algorithm as a sequence of depth-first calls prompted the formulation of a class of null-window alpha–beta algorithms, of which MTD(f) is the best known example.

Algorithm

There is a priority queue OPEN that stores states (J, s, h) or the nodes, where J - node identificator (Dot-decimal notation is used to identify nodes, \epsilon is a root), s\in{L,S} - state of the node J (L - the node is live, which means it's not solved yet and S - the node is solved), h\in(-\infty, \infty) - value of the solved node. Items in OPEN queue are sorted descending by their h value. If more than one node has the same value of h, a node left-most in the tree is chosen.

OPEN := { (e, L, inf) } while true do // repeat until stopped pop an element p=(J, s, h) from the head of the OPEN queue if J = e and s = S then STOP the algorithm and return h as a result else apply Gamma operator for p

\Gamma operator for p=(J,s,h) is defined in the following way:

if s = L then if J is a terminal node then (1.) add (J, S, min(h, value(J))) to OPEN else if J is a MIN node then (2.) add (J.1, L, h) to OPEN else (3.) for j=1..number_of_children(J) add (J.j, L, h) to OPEN else if J is a MIN node then (4.) add (parent(J), S, h) to OPEN remove from OPEN all the states that are associated with the children of parent(J) else if is_last_child(J) then // if J is the last child of parent(J) (5.) add (parent(J), S, h) to OPEN else (6.) add (parent(J).(k+1), L, h) to OPEN // add state associated with the next child of parent(J) to OPEN

References

References

1. Roizen, Igor. (March 1983). "A minimax algorithm better than alpha–beta?: Yes and No". Artificial Intelligence.
2. Plaat, Aske. (November 1996). "Best-first Fixed-depth Minimax Algorithms". Artificial Intelligence.

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::