A game tree with distinct leaf values which is easy for the alpha-beta algorithm

摘要

The alpha-beta algorithm is an efficient technique for searching game trees. As parallel computers become more available, it is important to have good parallel game tree search algorithms. Until now it is an open problem whether a linear speedup can be achieved with respect to sequential alpha-beta. This note presents a sample of game trees with distinct leaf values, which are easy for sequential alpha-beta—independently of the move ordering in the trees. We conjecture that these trees are difficult test cases for parallel algorithms.