Another view on the SSS* algorithm
January 1990
Research Paper
| Related Files |
|---|
View PDF Version
(eur-few-cs-90-01.pdf, 0.2MB) |
A new version of the SSS* algorithm for searching game trees is presented. This algorithm is built around two recursive procedures. It finds the minimax value of a game tree by first establishing an upper bound to this value and then successively trying in a top down fashion to tighten this bound until the minimax value has been obtained. This approach has several advantages, most notably that the algorithm is more perspicuous. Correctness and several other properties of SSS* can now more easily be proven. As an example we prove Pearl's characterization of the nodes visited by SSS*. Finally the new algorithm is transformed into a practical version, which allows an efficient use of memory.
Keywords
Automatically Extracted Terms
- solution tree
- solution
- game tree t
- lemma
- game tree
- value
- node n
- algorithm
- sss -2
- child
- proof
- procedure
- alpha-beta
- ancestor
- property
- minimax value
- max node
- min node
- version
- terminal
