Solution Trees as a Basis for Game-Tree Search

Abstract

A game-tree algorithm is an algorithm computing the minimax value of the root of a game tree. Two well-known game-tree-search algorithms are alpha-beta and SSS*. We show that there exists a relation between these algorithms, which are commonly regarded as quite different. Many algorithms use the no tion of establishing proofs that the game value lies above or below some bound. We show that this is equivalent to the construction of a solution tree. We discuss the role of solution trees and critical trees in the following algorithms: alpha-beta, PVS, SSS-2 and Proof-Number Search. A general procedure for the construction of a solution tree, based on alpha-beta and Null-Window Search, is given.