What is Combinatorial Explosion

This chapter presents the results of a study for improving the performance of the quiescence phase of Alpha-Beta (α-β) search. The Minimax algorithm's α-β enhancement enhances depth-first search performance by optimizing solutions in near best-first order, thereby 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. This research uses a full breath search to delay the asymptotic behavior of the combinatorial explosion to five levels of depth. A narrow width search involves expanding solutions involving material exchange, pawn promotion, or king-in-check until the position reaches quiescence without any material exchanges or promotions. When quiescence is reached, the evaluation function scores the leaf nodes of the game-tree. This chapter's research shows that α-β pruning is enhanced when a solution without material exchange or promotion is attempted first during the quiescence phase of α-β search which applies to chess playing programs as well.