Solution Trees as a Basis for Game-Tree Search

Article type: Research Article

Authors: de Bruin, Arie | Pijls, Wim | Plaat, Aske^{; *}

Affiliations: Rotterdam, The Netherlands

Note: [*] Erasmus University, Department of Computer Science, P.O. Box 1738, 3000 DR Rotterdam, The Netherlands. E-mail: [email protected]. Aske Plaat is at present at the University of Alberta, Department of Computing Science, Edmonton, Alberta, T6G 2H1 Canada.

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 notion 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.

DOI: 10.3233/ICG-1994-17404

Journal: ICGA Journal, vol. 17, no. 4, pp. 207-219, 1994