Transposition table-driven scheduling for two-player games

Game-tree search is an important research topic in Artificial Intelligence. Because it is computationally intensive, researchers have turned their attention to parallel game-tree search algorithms in order to improve running time. However, achieving high parallel performance remains a difficult task on distributed-memory systems. Many high-performance systems for two-player games use the αβ search algorithm, enhanced with transposition tables. Transposition tables store useful information about game-trees from previous searches. When parallelizing the αβ algorithm, a major problem is sharing transposition table information efficiently among the processors. A processor must communicate in order to look up table entries on other processors, which hurts the performance of the parallel search.; TDS (Transposition-table Driven Scheduling) was recently proposed to overcome this difficulty. TDS was implemented for single-agent search and achieved remarkable results. It is an open question as to whether applying this idea to αβ can yield good performance, because of the greater complexity of the αβ algorithm.; This thesis explains why it has been considered hard to combine TDS, with αβ. We then develop TDSAB, a parallel algorithm that contains important new techniques which enable TDS to be used with αβ. TDSAB has been tested in two games which have different search characteristics—Awari and Amazons. The performance of TDSAB is evaluated on a network of workstations. TDSAB achieved satisfactory speedups for both games.