Problems in Sequential and Parallel Game Tree Search

The ff---fi-- 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 -- independent of the move ordering in the trees. We conjecture that these trees are difficult test cases for parallel algorithms. email:bernhard@mathematik.uni-bielefeld.de CONTENTS 2 Contents 1 Introduction 2 2 Description of the problem 3 3 Motivation and known results 3 3.1 Bivalued trees : : : : : : : : : : : : : : : : : : : : : : : : : : 4 3.1.1 S--Solve and P--Solve : : : : : : : : : : : : : : : : : : 4 3.1.2 Known results on speedups for bivalued trees : : : : 6 3.2 Minimax trees : : : : : : : : : : : : : : : : : : : : : : : : : : 6 3.2.1 The sequential algorithm : :..