RankCut - A Domain Independent Forward Pruning Method for Games

Abstract

Forward pruning, also known as selective search, is now em-ployed in many strong game-playing programs. In this paper, we introduce RankCut – a domain independent forward prun-ing technique which makes use of move ordering, and prunes once no better move is likely to be available. Since game-playing programs already perform move ordering to improve the performance of αβ search, this information is available at no extra cost. As RankCut uses additional information un-tapped by current forward pruning techniques, RankCut is a complementary forward pruning method that can be used with existing methods, and is able to achieve improvements even when conventional pruning techniques are simultane-ously employed. We implemented RankCut in a modern open-source chess program, CRAFTY. RankCut reduces the game-tree size by approximately 10%-40 % for search depths 8-12 while retaining tactical reliability, when implemented alongside CRAFTY’s existing forward pruning techniques.