ISSN: 2996-671X
Authors: Wheeler SF*
The purpose of this paper is to report the results of a study of a method for improving the performance of the quiescence phase of Alpha-Beta (α-β) search. The α-β enhancement to the Minimax algorithm optimizes the performance of depth-first search when the solutions being searched are arranged in near best-first order reducing the computational effort from O(bd) to O(√bd), where b is the branching factor of the game-tree and d is the depth of the search, Knuth and Moore. To postpone the asymptotic behaviour of the combinatorial explosion, a full breath search is only carried out to 5 levels of depth in this research. A narrow width search expanding only solutions involving the exchange of material, a pawn promotion or kingin- check situation is then expanded until the position reaches quiescence where no material exchanges or promotions are present. When quiescence is reached, the evaluation function is called to score the leaf node of the game-tree. For chessplaying programs, it has long been held that material exchanges should be explored first before other solutions are expanded to ensure optimum performance of α-β pruning, Gillogly. The research reported in this paper has established statistically that α-β pruning is improved if a solution not involving an exchange of material or promotion is tried first rather than a material exchange solution during the quiescence phase of α-β search.
Keywords: Alpha-Beta; Minimax; Negamax; Optimization; Quiescence
