An Efficient Speedup Strategy for Constant Sum Game Computations

Large classes of game theoretic problems seem to defy attempts of finding polynomial-time al-gorithms while analyzing large amounts of data. This premise leads naturally to the possibility of using efficient parallel computing implementations when seeking exact solutions to some of these problems. Although alpha beta algorithms for more than one-player game-tree searches show moderate parallel performance, this paper sets forth an alpha beta strategy enhanced with transposition tables in order to offer satisfactory speedups on high performance servers. When the access to the transposition tables is done in low constant delay time, the achieved speedups should approach the theoretical upper bounds of the code parallelism. We tested the strategy on a well-known combinatorial game.