New advances in Alpha-Beta searching
Jonathan Schaeffer, Aske Plaat · 1996
Alpha-Beta has been the algorithm of choice for game-tree search for over three decades.Its success is largely attributable to a variety of enhancements to the basic algorithm that can dramatically improve the search efficiency.Although state-ofthe-art game-playing programs build trees that are close in size to the minimal Alpha-Beta search tree, this paper shows that there is still room for improvement.Three new enhancements are presented: best-first Alpha-Beta search, better use of transpositions, and improving aspiration search under real-time constraints.Measurements show that these improvements can reduce search effort by 35%.