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

Article type: Research Article

Authors: Buro, Michael^{; *}

Affiliations: Paderborn, Germany

Note: [*] University of Paderborn, Department of Mathematics and Computer Science, 33095 Paderborn, Germany. E-mail: buro@uni-paderborn.de.

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.

DOI: 10.3233/ICG-1995-18202

Journal: ICGA Journal, vol. 18, no. 2, pp. 71-76, 1995