ProbCut is a selective search enhancement of the alpha-beta algorithm created in 1994 by Michael Buro as introduced in his Ph.D. thesis ^{[1]}. It permits to exclude probably irrelevant subtrees from beeing searched deeply. ProbCut and its improved variant Multi–ProbCut (MPC) have been shown to be effective in Othello^{[2]} and Shogi^{[3]}, and a technique similar to ProbCut is used in the checkers program Chinook. Schaeffer et al. (1992) ^{[4]} described their approach in a footnode: Chinook performs forward cuts in positions with a material deficit, where a shallow search does not show an escape. ProbCut is a generalization of this method in that it is game independent. It was tested by incorporating it in Buro's already strong Othello program Logistello^{[5]} and increased the program's playing strength ^{[6]}. Despite some promising results reported by Albert Xin Jiang and Michael Buro with Crafty^{[7]}, it seemed not that successful in chess programs which already perform Null Move Pruning and Late Move Reductions, until Stockfish prooved otherwise as implemened by Gary Linscott^{[8]}^{[9]}.

Search Trees with two ProbCut generalizations ^{[10]}

ProbCut is based on the idea that the result v' of a shallow search with depthd' is a rough estimate of the result v of a deeper search with depth d > d'. A way to model this relationship is by means of a linear model:

since -e/σ is normally distributed with mean 0 and variance 1 (and distribution function Φ, phi), the condition holds true with probability of at least piff

which is equivalent to

Similar for

the condition becomes

Pseudo Code

This observation immediately leads to the implementation of the ProbCut alpha-beta extension for one depth and reduced depth pair using floats. Before sigma, a and b are estimated by linear regression likely for different game phases, the search depths d and d' < d and cut threshold must be chosen or be determined empirically, by checking the performance of the program with various parameter settings ^{[11]} .

int alphaBetaProbCut(int α, int β, int depth){constfloat T(1.5);constint DP(4);constint D(8);if( depth ==0)return evaluate();if( depth == D ){int bound;/* v >= β with prob. of at least p? yes => cutoff */
bound = round(( T * σ + β - b)/ a );if( alphaBetaProbCut( bound-1, bound, DP)>= bound )return β;/* v <= α with prob. of at least p? yes => cutoff */
bound = round((-T * σ + α - b)/ a );if( alphaBetaProbCut( bound, bound+1, DP)<= bound )return α;}/* the remainder of alpha-beta goes here */
...
}

Multi–ProbCut

Multi–ProbCut (MPC) enhances ProbCut by

Allowing different regression parameters and cut thresholds for different stages of the game

struct Param {int d;/* shallow search depth */float t;/* cut threshold */float a, b, σ;/* slope, offset, standard deviation */} param[MAX_STAGE+1][MAX_HEIGHT+1][NUM_TRY];int alphaBetaMPC(int α, int β, int depth){if( depth ==0)return evaluate();if( depth <= MAX_D ){for(int i=0; i < NUM_TRY; i++){int bound;const Param &pa = param[stage][depth][i];if(pa.d<0)break;/* no more parameters available *//* v >= β with prob. of at least p? yes => cutoff */
bound = round(( pa.t* pa.σ + β - pa.b)/ pa.a);if( alphaBetaMPC( bound-1, bound, pa.d)>= bound )return β;/* v <= α with prob. of at least p? yes => cutoff */
bound = round((-pa.t* pa.σ + α - pa.b)/ pa.a);if( alphaBetaMPC( bound, bound+1, pa.d)<= bound )return α;}}/* the remainder of alpha-beta goes here */
...
}

ProbeCut or MPC in Chess

In 2003, Albert Xin Jiang implemented ProbCut and MPC in Crafty by Robert Hyatt. In his thesis he introductory elaborates on ProbCut in Chess ^{[12]} :

There has been no report of success for ProbCut or MPC in chess thus far. There are at least two reasons for this:

Null-move is available for chess. Null-move and ProbCut are based on similar ideas, as a result they tend to prune the same type of positions. Part of the reason why ProbCut is so successful in Othello is that null-move does not work in Othello. But in chess, ProbCut and MPC have to compete with null-move, which is way better than brute-force alpha-beta.

Chess searches tend to make more mistakes than Othello searches^{[13]} . This leads to a larger standard deviation in the linear relationship between shallow and deep search results, which makes it harder to get ProbCut cuts.

In his research, Albert Xin Jiang further determined following parameters by linear regression. The about 2700 positions were chosen randomly from some computer chess tournament games and some of Crafty’s games against human grandmasters on internet chess servers:

v' versus v for depth pair (4,8) ^{[14]}

Linear regression results. The evaluation function’s scale is 100 = one pawn. r is the regression correlation coefficient, a measure of how good the data fits the linear model:

While ProbCut did not result in better playing strength of Crafty, Albert Xin Jiang and Michael Buro report an improvement with MPC while playing two times three 64-game matches with three Crafty versions and two time controls versus Dieter Bürssner's program Yace^{[15]} :

Pairing

Crafty %

2min+10sec/move

8min+20sec/move

Crafty - Yace

42.0%

50.8%

MPC Crafty(1.2, 1.0) - Yace

53.1%

56.3%

MPC Crafty(1.0, 1.0) - Yace

57.0%

55.5%

However, Robert Hyatt first stated results were inconclusive ^{[16]} , and later that MPC was somewhat worse in every test he tried ^{[17]} , also confirmed by Robert Allgeuer, who performed Crafty MPC tests with following conclusion in CCC^{[18]} :

My tests indicate that the overall playing strength of Crafty 18.15 remains more or less unchanged by the addition of Multi-ProbCut. However, the characteristic of the engine changes significantly due to ProbCut: Even though nominal search depth is increased by one to two plies, tactical strength is severely reduced.

Furthermore with ProbCut match results become more unpredictable and inconsistent: Apparently there are types of opponents against which ProbCut works very well and results in significantly improved results, but there are also other opponents (the tactically stronger ones?) where ProbCut has exactly the opposite effect.

Michael Buro (1994). Techniken für die Bewertung von Spielsituationen anhand von Beispielen. Ph.D. Thesis. University of Paderborn, Paderborn, Germany. (German), pdf

Michael Buro (1995). ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm.ICCA Journal, Vol. 18, No. 2, pp. 71-76, pdf

Michael Buro (1997). Experiments with Multi-ProbCut and a New High-quality Evaluation Function for Othello. Technical Report No. 96, NEC Research Institute, Princeton, N.J. pdf

Maarten Schadd, Mark Winands, Jos Uiterwijk (2009). ChanceProbCut: Forward Pruning in Chance Nodes. in IEEE Symposium on Computational Intelligence and Games (CIG 2009), pdf

^Michael Buro (1994). Techniken für die Bewertung von Spielsituationen anhand von Beispielen. Ph.D. Thesis. University of Paderborn, Paderborn, Germany. (German), pdf, Kapitel 4. Selektive Suche

^Michael Buro (1997). Experiments with Multi-ProbCut and a New High-quality Evaluation Function for Othello. Technical Report No. 96, NEC Research Institute, Princeton, N.J. pdf

^ Illustrations of the first two ProbCut generalizations: a) allowing forward cuts at several heights and b) performing a sequence of check searches of increasing depth from Michael Buro (1997). Experiments with Multi-ProbCut and a New High-quality Evaluation Function for Othello. Technical Report No. 96, NEC Research Institute, Princeton, N.J. pdf, 8 Multi-ProbCut, pp 7.

^Michael Buro (1995). ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm.ICCA Journal, Vol. 18, No. 2, pp. 71-76, pdf

^Albert Xin Jiang (2003). Implementation of Multi-ProbCut and Chess. CPSC 449 Thesis, pdf, 2.5 ProbeCut in Chess, pp. 6

Home * Search * Selectivity * Pruning * ProbCutProbCutis a selective search enhancement of the alpha-beta algorithm created in 1994 by Michael Buro as introduced in his Ph.D. thesis^{[1]}. It permits to exclude probably irrelevant subtrees from beeing searched deeply. ProbCut and its improved variantMulti–ProbCut(MPC) have been shown to be effective in Othello^{[2]}and Shogi^{[3]}, and a technique similar to ProbCut is used in the checkers program Chinook. Schaeffer et al. (1992)^{[4]}described their approach in a footnode: Chinook performs forward cuts in positions with a material deficit, where a shallow search does not show an escape. ProbCut is a generalization of this method in that it is game independent. It was tested by incorporating it in Buro's already strong Othello programLogistello^{[5]}and increased the program's playing strength^{[6]}. Despite some promising results reported by Albert Xin Jiang and Michael Buro with Crafty^{[7]}, it seemed not that successful in chess programs which already perform Null Move Pruning and Late Move Reductions, until Stockfish prooved otherwise as implemened by Gary Linscott^{[8]}^{[9]}.^{[10]}## Table of Contents

## The Idea

ProbCut is based on the idea that the resultv'of a shallow search with depthd'is a rough estimate of the resultvof a deeper search with depthd > d'. A way to model this relationship is by means of a linear model:where e is a normally distributed error variable with mean 0 and standard deviation σ (sigma) or variance σ². If the evaluation function is relative stable, the slope a is about 1.0, offset b about 0.0 and a small variance σ². The cutoff condition of depth d

becomes

since -e/σ is normally distributed with mean 0 and variance 1 (and distribution function Φ, phi), the condition holds true with probability of at least

piffwhich is equivalent to

Similar for

the condition becomes

## Pseudo Code

This observation immediately leads to the implementation of the ProbCut alpha-beta extension for one depth and reduced depth pair using floats. Before sigma, a and b are estimated by linear regression likely for different game phases, the search depths d and d' < d and cut threshold must be chosen or be determined empirically, by checking the performance of the program with various parameter settings^{[11]}.## Multi–ProbCut

Multi–ProbCut (MPC) enhances ProbCut by## ProbeCut or MPC in Chess

In 2003, Albert Xin Jiang implemented ProbCut and MPC in Crafty by Robert Hyatt. In his thesis he introductory elaborates on ProbCut in Chess^{[12]}:There has been no report of success for ProbCut or MPC in chess thus far. There are at least two reasons for this:Null-move is available for chess. Null-move and ProbCut are based on similar ideas, as a result they tend to prune the same type of positions. Part of the reason why ProbCut is so successful in Othello is that null-move does not work in Othello. But in chess, ProbCut and MPC have to compete with null-move, which is way better than brute-force alpha-beta.Chess searches tend to make more mistakes than Othello searches^{[13]}.This leads to a larger standard deviation in the linear relationship between shallow and deep search results, which makes it harder to get ProbCut cuts.In his research, Albert Xin Jiang further determined following parameters by linear regression. The about 2700 positions were chosen randomly from some computer chess tournament games and some of Crafty’s games against human grandmasters on internet chess servers:

^{[14]}Linear regression results. The evaluation function’s scale is 100 = one pawn. r is the regression correlation coefficient, a measure of how good the data fits the linear model:

While ProbCut did not result in better playing strength of Crafty, Albert Xin Jiang and Michael Buro report an improvement with MPC while playing two times three 64-game matches with three Crafty versions and two time controls versus Dieter Bürssner's program Yace

^{[15]}:However, Robert Hyatt first stated results were inconclusive

^{[16]}, and later that MPC was somewhat worse in every test he tried^{[17]}, also confirmed by Robert Allgeuer, who performed Crafty MPC tests with following conclusion in CCC^{[18]}:My tests indicate that the overall playing strength of Crafty 18.15 remains more or less unchanged by the addition of Multi-ProbCut. However, the characteristic of the engine changes significantly due to ProbCut: Even though nominal search depth is increased by one to two plies, tactical strength is severely reduced.Furthermore with ProbCut match results become more unpredictable and inconsistent: Apparently there are types of opponents against which ProbCut works very well and results in significantly improved results, but there are also other opponents (the tactically stronger ones?) where ProbCut has exactly the opposite effect.## See also

## Publications

^{[19]}^{[20]}1994).Techniken für die Bewertung von Spielsituationen anhand von Beispielen.Ph.D. Thesis. University of Paderborn, Paderborn, Germany. (German), pdf1995).ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm.ICCA Journal, Vol. 18, No. 2, pp. 71-76, pdf1997).Experiments with Multi-ProbCut and a New High-quality Evaluation Function for Othello.Technical Report No. 96, NEC Research Institute, Princeton, N.J. pdf2000).Experiments with Multi-ProbCut and a new High-Quality Evaluation Function for Othello.Games in AI Research (eds. Jaap van den Herik and Hiroyuki Iida), pp. 77-96. Universiteit Maastricht, Maastricht, The Netherlands. ISBN 90-621-6416-1.2002).Effect of ProbCut in Shogi - by changing parameters according to position category. 7th Game Programming Workshop2002).Multi-ProbCut Search. slides as pdf2003).Implementation of Multi-ProbCut in Chess. CPSC 449 Thesis, pdf2003).First Experimental Results of ProbCut Applied to Chess. Advances in Computer Games 10, pdf2009).ChanceProbCut: Forward Pruning in Chance Nodes. in IEEE Symposium on Computational Intelligence and Games (CIG 2009), pdf## Forum Posts

## External Links

^{[21]}Ron Miles, Greg Tardy, Tony Scherr, Kenny Wollesen

## References

1994).Techniken für die Bewertung von Spielsituationen anhand von Beispielen.Ph.D. Thesis. University of Paderborn, Paderborn, Germany. (German), pdf, Kapitel 4. Selektive Suche1997).Experiments with Multi-ProbCut and a New High-quality Evaluation Function for Othello.Technical Report No. 96, NEC Research Institute, Princeton, N.J. pdf2002).Effect of ProbCut in Shogi - by changing parameters according to position category. 7th Game Programming Workshop1992).A World Championship Caliber Checkers Program. Artificial Intelligence, Vol. 53, Nos. 2-3, pp. 273-289. ISSN 0004-37021995).ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm.ICCA Journal, Vol. 18, No. 2, pp. 71-76, pdf2003).First Experimental Results of ProbCut Applied to Chess. Advances in Computer Games 10, pdf1997).Experiments with Multi-ProbCut and a New High-quality Evaluation Function for Othello.Technical Report No. 96, NEC Research Institute, Princeton, N.J. pdf, 8 Multi-ProbCut, pp 7.1995).ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm.ICCA Journal, Vol. 18, No. 2, pp. 71-76, pdf2003).Implementation of Multi-ProbCut and Chess. CPSC 449 Thesis, pdf, 2.5 ProbeCut in Chess, pp. 61997).Diminishing Returns for Additional Search in Chess.Advances in Computer Chess 82003).Implementation of Multi-ProbCut in Chess. CPSC 449 Thesis, pdf2003).First Experimental Results of ProbCut Applied to Chess. Advances in Computer Games 10, pdf## What links here?

Up one Level