A SURVEY OF ENHANCEMENTS TO THE ALPHA-BETA ALGORITHM

Current game-playing programs have developed numerous move ordering and search reduction techniques in order to improve the effectiveness of the alpha-beta algorithm. A c r i t i c a l review of these search modifications is provided, and a recursive formula to estimate the search time is proposed, one which re f lec ts the character ist ics of the strongly ordered trees produced through use of improved search enhancements. I. THE ALPHA-BETA ALGORITHM With few exceptions [NEWB], much of the exist ing theoretical work on sequential game tree searching.has been rest r ic ted to random trees. However, in practice, t ru ly random trees are quite uncommon. In addition, special techniques have been developed to improve the effectiveness of the principal searching method, the alpha-beta algorithm. Thus, we w i l l assess these enhancements and show why s t r o n g l y o rdered t rees are mor