ProbCut: An Effective Selective Extension of the α - β Algorithm

Abstract

This article presents a new, game-independent selective extension of the α-β algorithm. Based on the strong correlation between evaluations obtained from searches at different depths, it is shown how the result of a shallow search can be used to decide with a prescribed likelihood whether a deep search would yield a value outside the current search window. In its application to Othello, the technique is shown to be effective in investigating the relevant variations more deeply. It significantly increases the playing strength of an already strong brute-force Othello program.