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||algorithms, alpha-beta, game tree search, solution trees|
de Bruin, A., Pijls, W.H.L.M., & Plaat, A.. (1994). Solution trees as a basis for game tree search. Retrieved from http://hdl.handle.net/1765/1456