On the parallel complexity of evaluating game trees

Abstract

We consider efficient parallel algorithms for the evaluation of game trees. We prove an inherent limitation on the speedup achievable, and give an algorithm that achieves its best performance bounds on trees of the sort that are likely to arise in game-playing programs.