On forward pruning in game-tree search

Abstract

This thesis is focused on the theoretical understanding and practical applications of forward pruning in game-tree search, also known as selective search. Our research focuses on three main areas: (1) Solving Tigers and Goats - using forward pruning techniques in addition to other advanced search techniques to prove that Tigers and Goats is a draw using modern desktop computers. (2) Practical Application - developing a domain-independent forward pruning technique called RankCut for game-tree search. We show the effectiveness of RankCut in open source Chess programs, even with implemented together with other forward pruning techniques. (3) Theoretical Understanding - forming theoretical frameworks of forward pruning to identify two factors, the player to move and the depth of a node, that affect the performance of selective search. We also formulate risk-management strategies for forward pruning techniques to maximize performance based on predictions by the theoretical frameworks.