Branch & bound formulation for sequential and parallel game tree searching: preliminary results
Laveen N. Kanal, Vipin Kumar · International Joint Conference on Artificial Intelligence · 1981
In this paper we present a Branch and Bound (B&B) formulation for finding the minlmax value of a game tree and show, that in case a subset with the best bound is chosen for branching, the resulting algorithm is identical to the SSS* algorithm which Stockman [1] has shown to be better than the Alpha-Beta algorithm for game tree searching. We propose parallel Implementations of B&B search for the minimax evaluation of game trees which lead to a parallel implementation of SSS*. The Branch and Bound approach provides a unified way of formulating and analyzing tree searching algorithms such as SSS* and Alpha-Beta. Viewing SSS* this way, its correctness proof is much easier than given in Stockman, as is a correctness proof for parallel Implementations of SSS*.