PROBCUT - AN EFFECTIVE SELECTIVE EXTENSION OF THE ALPHA-BETA ALGORITHM

This article presents a new, game-independent selective extension of the alpha-beta 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.