Solution Trees as a Basis for Game Tree Search

A game tree algorithm is an algorithm computing the minimax value of the root of a game tree. Many algorithms use the notion of establishing proofs that this value lies above or below some boundary value. We show that this amounts to the construction of a solution tree. We discuss the role of solution trees and critical trees in the following algorithms: Principal Variation Search, alpha-beta, and SSS-2. A general procedure for the construction of a solution tree, based on alpha-beta and Null-Window-Search, is given. Furthermore two new examples of solution tree based-algorithms are presented, that surpass alpha-beta---i.e., never visit more nodes than alpha-beta, and often less. Keywords: Game tree search, alpha-beta, solution trees, algorithms. 1 Introduction Game trees are related to two person zero sum games with perfect information like TicTac -Toe, Checkers, Chess, and Go. Each node in a game tree represents a game position. The root represents a position of the game, for which..