25,161
edits
Changes
Created page with "'''Home * Search * Selectivity * Pruning * ProbCut''' border|right|thumb|[[Search Tree|Search Trees with two ProbCut generali..."
'''[[Main Page|Home]] * [[Search]] * [[Selectivity]] * [[Pruning]] * ProbCut'''
[[FILE:MProbeCut.JPG|border|right|thumb|[[Search Tree|Search Trees]] with two ProbCut generalizations <ref>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. [http://skatgame.net/mburo/ps/improve.pdf pdf], 8 Multi-ProbCut, pp 7.</ref> ]]
'''ProbCut''',<br/>
a selective search enhancement of the [[Alpha-Beta|alpha-beta]] algorithm created in 1994 by [[Michael Buro]] as introduced in his Ph.D. thesis <ref>[[Michael Buro]] ('''1994'''). ''Techniken für die Bewertung von Spielsituationen anhand von Beispielen.'' Ph.D. Thesis. [[University of Paderborn]], Paderborn, Germany. (German), [http://www.cs.ualberta.ca/%7Emburo/ps/mics_dis.pdf pdf], Kapitel 4. Selektive Suche</ref>. 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]] <ref>[[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. [http://skatgame.net/mburo/ps/improve.pdf pdf]</ref> and [[Shogi]] <ref>[[Kazutomo Shibahara]], [[Nobuo Inui]], [[Yoshiyuki Kotani]] ('''2002'''). ''Effect of ProbCut in Shogi - by changing parameters according to position category''. [[Conferences#GPW|7th Game Programming Workshop]]</ref>, and a technique similar to ProbCut is used in the [[Checkers|checkers]] program [https://en.wikipedia.org/wiki/Chinook_%28draughts_player%29 Chinook]. [[Jonathan Schaeffer|Schaeffer]] et al. (1992) <ref>[[Jonathan Schaeffer]], [[Joe Culberson]], [[Norman Treloar]], [[Brent Knight]], [[Paul Lu]], and [[Duane Szafron]] ('''1992'''). ''A World Championship Caliber Checkers Program''. Artificial Intelligence, Vol. 53, Nos. 2-3, pp. 273-289. ISSN 0004-3702</ref> described their approach in a footnode: Chinook performs forward cuts in positions with a [[Material|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'' <ref>[http://skatgame.net/mburo/log.html LOGISTELLO's Homepage]</ref> and increased the program's playing strength <ref>[[Michael Buro]] ('''1995'''). ''ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm.'' [[ICGA Journal|ICCA Journal]], Vol. 18, No. 2, pp. 71-76, [http://www.cs.ualberta.ca/%7Emburo/ps/probcut.pdf pdf]</ref>. Despite some promising results reported by [[Albert Xin Jiang]] and Michael Buro with [[Crafty]] <ref>[[Albert Xin Jiang]], [[Michael Buro]] ('''2003'''). ''First Experimental Results of ProbCut Applied to Chess''. [[Advances in Computer Games 10]], [http://cs.ubc.ca/%7Ejiang/papers/mpc_main.pdf pdf]</ref>, 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]] <ref>[http://www.talkchess.com/forum/viewtopic.php?p=518426 Probcut] by [[Gary Linscott|Gary]], [[CCC]], May 24, 2013</ref> <ref>[https://github.com/official-stockfish/Stockfish/blob/master/src/search.cpp Stockfish/search.cpp at master · official-stockfish/Stockfish · GitHub], Step 9. ProbCut</ref>.
=The Idea=
ProbCut is based on the idea that the result ''v''' of a shallow search with [[Depth|depth]] ''d''' 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 [https://en.wikipedia.org/wiki/Linear_model linear model]:
v = a*v' + b + e
where e is a [https://en.wikipedia.org/wiki/Normal_distribution normally distributed] [https://en.wikipedia.org/wiki/Standard_error_%28statistics%29 error variable] with [https://en.wikipedia.org/wiki/Mean mean] 0 and [https://en.wikipedia.org/wiki/Standard_deviation standard deviation] σ ([https://en.wikipedia.org/wiki/Sigma sigma]) or [https://en.wikipedia.org/wiki/Variance variance] σ². If the evaluation function is relative stable, the [https://en.wikipedia.org/wiki/Slope slope] a is about 1.0, offset b about 0.0 and a small variance σ². The cutoff condition of depth d
v ≥ β
becomes
(v' + b - β)/σ ≥ -e/σ
since -e/σ is normally distributed with mean 0 and variance 1 (and [https://en.wikipedia.org/wiki/Cumulative_distribution_function distribution function] Φ, [https://en.wikipedia.org/wiki/Phi phi]), the condition holds true with [https://en.wikipedia.org/wiki/Probability probability] of at least ''p'' [https://en.wikipedia.org/wiki/If_and_only_if iff]
(v' + b - β)/σ ≥ Φ<span style="vertical-align: super;">-1</span>(p)
which is equivalent to
v' ≥ (Φ<span style="vertical-align: super;">-1</span>(p) * σ + β - b) / a
Similar for
v ≤ α
the condition becomes
v' ≤ (-Φ<span style="vertical-align: super;">-1</span>(p) * σ + α - b) / a
=Pseudo Code=
This observation immediately leads to the implementation of the ProbCut alpha-beta extension for one depth and reduced depth pair using [[Float|floats]]. Before [https://en.wikipedia.org/wiki/Sigma sigma], a and b are estimated by [https://en.wikipedia.org/wiki/Linear_regression linear regression] likely for different [[Game Phases|game phases]], the search depths d and d' < d and cut threshold must be chosen or be determined [https://en.wikipedia.org/wiki/Empirical empirically], by checking the performance of the program with various parameter settings <ref>[[Michael Buro]] ('''1995'''). ''ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm.'' [[ICGA Journal|ICCA Journal]], Vol. 18, No. 2, pp. 71-76, [http://www.cs.ualberta.ca/%7Emburo/ps/probcut.pdf pdf]</ref> .
<pre>
int alphaBetaProbCut(int α, int β, int depth) {
const float T(1.5);
const int DP(4);
const int 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 */
...
}
</pre>
<span id="MPC"></span>
=Multi–ProbCut=
Multi–ProbCut (MPC) enhances ProbCut by
* Allowing different regression parameters and cut thresholds for different stages of the game
* Using more than one depth pair
* Using [[Internal Iterative Deepening|internal iterative deepening]] for shallow searches
<pre>
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 */
...
}
</pre>
=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 <ref>[[Albert Xin Jiang]] ('''2003'''). ''Implementation of Multi-ProbCut and Chess''. CPSC 449 Thesis, [http://www.cs.ubc.ca/%7Ejiang/papers/thesis.pdf pdf], 2.5 ProbeCut in Chess, pp. 6</ref> :
There has been no report of success for ProbCut or MPC in chess thus far. There are at least two reasons for this:
# <code>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.</code>
# <code>Chess searches tend to make more mistakes than Othello searches</code> <ref>[[Andreas Junghanns]], [[Jonathan Schaeffer]], [[Mark Brockington]], [[Yngvi Björnsson]], [[Tony Marsland]] ('''1997'''). ''Diminishing Returns for Additional Search in Chess.'' [[Advances in Computer Chess 8]]</ref><code>. 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</code>.
In his research, Albert Xin Jiang further determined following parameters by [https://en.wikipedia.org/wiki/Linear_regression 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:
[[FILE:CraftyLinearReg.JPG|none|border|text-bottom]]
v' versus v for depth pair (4,8) <ref>Image from [[Albert Xin Jiang]] ('''2003'''). ''Implementation of Multi-ProbCut in Chess''. CPSC 449 Thesis, [http://www.cs.ubc.ca/%7Ejiang/papers/thesis.pdf pdf]</ref>
Linear regression results. The evaluation function’s scale is 100 = one pawn. r is the [https://en.wikipedia.org/wiki/Correlation_and_dependence regression correlation coefficient], a measure of how good the data fits the linear model:
{| class="wikitable"
|-
! Pairs
! Stage
! a
! b
! σ
! r
|-
| (3,5)
| [[Middlegame]]
| 0.998
| style="text-align:right;" | -7.000
| 55.80
| 0.90
|-
| (3,5)
| [[Endgame]]
| 1.026
| style="text-align:right;" | -4.100
| 51.80
| 0.94
|-
| (4,8)
| Middlegame
| 1.020
| style="text-align:right;" | 2.360
| 82.00
| 0.82
|-
| (4,8)
| Endgame
| 1.110
| style="text-align:right;" | 1.750
| 75.00
| 0.90
|}
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 [[Match Statistics|matches]] with three Crafty versions and two time controls versus [[Dieter Bürssner|Dieter Bürssner's]] program [[Yace]] <ref>Page 30 in [[Albert Xin Jiang]], [[Michael Buro]] ('''2003'''). ''First Experimental Results of ProbCut Applied to Chess''. [[Advances in Computer Games 10]], [http://cs.ubc.ca/%7Ejiang/papers/mpc_main.pdf pdf]</ref> :
{| class="wikitable"
|-
! rowspan="2" | Pairing
! colspan="2" | Crafty %
|-
! 2min + <br/>10sec/move
! 8min + <br/>20sec/move
|-
! Crafty - Yace
| style="text-align:right;" | 42.0
| style="text-align:right;" | 50.8
|-
! MPC Crafty(1.2, 1.0) - Yace
| style="text-align:right;" | 53.1
| style="text-align:right;" | 56.3
|-
! MPC Crafty(1.0, 1.0) - Yace
| style="text-align:right;" | 57.0
| style="text-align:right;" | 55.5
|}
However, [[Robert Hyatt]] first stated results were inconclusive <ref>[https://www.stmintz.com/ccc/index.php?id=303565 Re: Multi-ProbCut and Crafty : does it work ?] by [[Robert Hyatt]], [[CCC]], June 28, 2003</ref> , and later that MPC was somewhat worse in every test he tried <ref>[https://www.stmintz.com/ccc/index.php?id=378374 Re: ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm] by [[Robert Hyatt]], [[CCC]], July 21, 2004</ref> , also confirmed by [[Robert Allgeuer]], who performed Crafty MPC tests with following conclusion in [[CCC]] <ref>[https://www.stmintz.com/ccc/index.php?id=322133 Crafty MPC tests (long post)] by [[Robert Allgeuer]], [[CCC]], October 18, 2003</ref> :
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=
* [[Enhanced Forward Pruning]]
* [[Futility Pruning]]
* [[Late Move Reductions]]
* [[Match Statistics]]
* [[Multi-Cut]]
* [[Null Move Pruning]]
=Publications=
<ref>[http://skatgame.net/mburo/publications.html Michael Buro's Publication List]</ref> <ref>[http://www.cs.ubc.ca/%7Ejiang/ Albert Xin Jiang - publications]</ref>
* [[Michael Buro]] ('''1994'''). ''Techniken für die Bewertung von Spielsituationen anhand von Beispielen.'' Ph.D. Thesis. [[University of Paderborn]], Paderborn, Germany. (German), [http://www.cs.ualberta.ca/%7Emburo/ps/mics_dis.pdf pdf]
* [[Michael Buro]] ('''1995'''). ''ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm.'' [[ICGA Journal|ICCA Journal]], Vol. 18, No. 2, pp. 71-76, [http://www.cs.ualberta.ca/%7Emburo/ps/probcut.pdf 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. [http://skatgame.net/mburo/ps/improve.pdf pdf]
* [[Michael Buro]] ('''2000'''). ''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. [[Maastricht University|Universiteit Maastricht]], Maastricht, The Netherlands. ISBN 90-621-6416-1.
* [[Kazutomo Shibahara]], [[Nobuo Inui]], [[Yoshiyuki Kotani]] ('''2002'''). ''Effect of ProbCut in Shogi - by changing parameters according to position category''. [[Conferences#GPW|7th Game Programming Workshop]]
* [[Michael Buro]] ('''2002'''). ''Multi-ProbCut Search''. slides as [http://skatgame.net/mburo/ps/mpc.pdf pdf]
* [[Albert Xin Jiang]] ('''2003'''). ''Implementation of Multi-ProbCut in Chess''. CPSC 449 Thesis, [http://www.cs.ubc.ca/%7Ejiang/papers/thesis.pdf pdf]
* [[Albert Xin Jiang]], [[Michael Buro]] ('''2003'''). ''First Experimental Results of ProbCut Applied to Chess''. [[Advances in Computer Games 10]], [http://cs.ubc.ca/%7Ejiang/papers/mpc_main.pdf pdf]
* [[Maarten Schadd]], [[Mark Winands]], [[Jos Uiterwijk]] ('''2009'''). ''ChanceProbCut: Forward Pruning in Chance Nodes''. in IEEE Symposium on Computational Intelligence and Games (CIG 2009), [http://www.personeel.unimaas.nl/Maarten-Schadd/Papers/2009StrategoCIG.pdf pdf]
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=66467 whats probcut?] by vitor, [[CCC]], August 29, 1999
* [https://www.stmintz.com/ccc/index.php?id=178124 muliti probcut] by [[Martin Fierz]], [[CCC]], July 04, 2001
* [https://www.stmintz.com/ccc/index.php?id=303536 Multi-ProbCut and Crafty : does it work ?] by [[Frédéric Louguet]], [[CCC]], June 28, 2003
* [https://www.stmintz.com/ccc/index.php?id=322133 Crafty MPC tests (long post)] by [[Robert Allgeuer]], [[CCC]], October 18, 2003
* [https://www.stmintz.com/ccc/index.php?id=378283 ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm] by [[Albert Silver]], [[CCC]], July 21, 2004
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=274486&t=28459 Re: Possible search improvment] by [[Ryan Benitez]], [[CCC]], June 17, 2009 » [[History Leaf Pruning]]
* [http://www.talkchess.com/forum/viewtopic.php?t=38407 Bad Pruning] by [[Onno Garms]], [[CCC]], March 13, 2011
* [http://www.talkchess.com/forum/viewtopic.php?p=518426 Probcut] by [[Gary Linscott|Gary]], [[CCC]], May 24, 2013 » [[Stockfish]]
=External Links=
* [http://radagast.se/othello/howto.html Writing an Othello program] by [[Gunnar Andersson]]
* [http://fuego.sourceforge.net/fuego-doc-1.1/smartgame-doc/SgProbCut_8h.html#_details SmartGame Library: SgProbCut.h File Reference], [http://fuego.sourceforge.net/fuego-doc-1.1/ Fuego Documentation] <ref>[http://www.grappa.univ-lille3.fr/icga/program.php?id=535 Fuego], [[Go]] playing program by [[Markus Enzenberger]], [[Martin Müller]], [[Broderick Arneson]], [[Richard Segal]], [[Gerald Tesauro]] and [[Arpad Rimmel]]</ref>
=References=
<references />
'''[[Pruning|Up one Level]]'''
[[FILE:MProbeCut.JPG|border|right|thumb|[[Search Tree|Search Trees]] with two ProbCut generalizations <ref>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. [http://skatgame.net/mburo/ps/improve.pdf pdf], 8 Multi-ProbCut, pp 7.</ref> ]]
'''ProbCut''',<br/>
a selective search enhancement of the [[Alpha-Beta|alpha-beta]] algorithm created in 1994 by [[Michael Buro]] as introduced in his Ph.D. thesis <ref>[[Michael Buro]] ('''1994'''). ''Techniken für die Bewertung von Spielsituationen anhand von Beispielen.'' Ph.D. Thesis. [[University of Paderborn]], Paderborn, Germany. (German), [http://www.cs.ualberta.ca/%7Emburo/ps/mics_dis.pdf pdf], Kapitel 4. Selektive Suche</ref>. 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]] <ref>[[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. [http://skatgame.net/mburo/ps/improve.pdf pdf]</ref> and [[Shogi]] <ref>[[Kazutomo Shibahara]], [[Nobuo Inui]], [[Yoshiyuki Kotani]] ('''2002'''). ''Effect of ProbCut in Shogi - by changing parameters according to position category''. [[Conferences#GPW|7th Game Programming Workshop]]</ref>, and a technique similar to ProbCut is used in the [[Checkers|checkers]] program [https://en.wikipedia.org/wiki/Chinook_%28draughts_player%29 Chinook]. [[Jonathan Schaeffer|Schaeffer]] et al. (1992) <ref>[[Jonathan Schaeffer]], [[Joe Culberson]], [[Norman Treloar]], [[Brent Knight]], [[Paul Lu]], and [[Duane Szafron]] ('''1992'''). ''A World Championship Caliber Checkers Program''. Artificial Intelligence, Vol. 53, Nos. 2-3, pp. 273-289. ISSN 0004-3702</ref> described their approach in a footnode: Chinook performs forward cuts in positions with a [[Material|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'' <ref>[http://skatgame.net/mburo/log.html LOGISTELLO's Homepage]</ref> and increased the program's playing strength <ref>[[Michael Buro]] ('''1995'''). ''ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm.'' [[ICGA Journal|ICCA Journal]], Vol. 18, No. 2, pp. 71-76, [http://www.cs.ualberta.ca/%7Emburo/ps/probcut.pdf pdf]</ref>. Despite some promising results reported by [[Albert Xin Jiang]] and Michael Buro with [[Crafty]] <ref>[[Albert Xin Jiang]], [[Michael Buro]] ('''2003'''). ''First Experimental Results of ProbCut Applied to Chess''. [[Advances in Computer Games 10]], [http://cs.ubc.ca/%7Ejiang/papers/mpc_main.pdf pdf]</ref>, 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]] <ref>[http://www.talkchess.com/forum/viewtopic.php?p=518426 Probcut] by [[Gary Linscott|Gary]], [[CCC]], May 24, 2013</ref> <ref>[https://github.com/official-stockfish/Stockfish/blob/master/src/search.cpp Stockfish/search.cpp at master · official-stockfish/Stockfish · GitHub], Step 9. ProbCut</ref>.
=The Idea=
ProbCut is based on the idea that the result ''v''' of a shallow search with [[Depth|depth]] ''d''' 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 [https://en.wikipedia.org/wiki/Linear_model linear model]:
v = a*v' + b + e
where e is a [https://en.wikipedia.org/wiki/Normal_distribution normally distributed] [https://en.wikipedia.org/wiki/Standard_error_%28statistics%29 error variable] with [https://en.wikipedia.org/wiki/Mean mean] 0 and [https://en.wikipedia.org/wiki/Standard_deviation standard deviation] σ ([https://en.wikipedia.org/wiki/Sigma sigma]) or [https://en.wikipedia.org/wiki/Variance variance] σ². If the evaluation function is relative stable, the [https://en.wikipedia.org/wiki/Slope slope] a is about 1.0, offset b about 0.0 and a small variance σ². The cutoff condition of depth d
v ≥ β
becomes
(v' + b - β)/σ ≥ -e/σ
since -e/σ is normally distributed with mean 0 and variance 1 (and [https://en.wikipedia.org/wiki/Cumulative_distribution_function distribution function] Φ, [https://en.wikipedia.org/wiki/Phi phi]), the condition holds true with [https://en.wikipedia.org/wiki/Probability probability] of at least ''p'' [https://en.wikipedia.org/wiki/If_and_only_if iff]
(v' + b - β)/σ ≥ Φ<span style="vertical-align: super;">-1</span>(p)
which is equivalent to
v' ≥ (Φ<span style="vertical-align: super;">-1</span>(p) * σ + β - b) / a
Similar for
v ≤ α
the condition becomes
v' ≤ (-Φ<span style="vertical-align: super;">-1</span>(p) * σ + α - b) / a
=Pseudo Code=
This observation immediately leads to the implementation of the ProbCut alpha-beta extension for one depth and reduced depth pair using [[Float|floats]]. Before [https://en.wikipedia.org/wiki/Sigma sigma], a and b are estimated by [https://en.wikipedia.org/wiki/Linear_regression linear regression] likely for different [[Game Phases|game phases]], the search depths d and d' < d and cut threshold must be chosen or be determined [https://en.wikipedia.org/wiki/Empirical empirically], by checking the performance of the program with various parameter settings <ref>[[Michael Buro]] ('''1995'''). ''ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm.'' [[ICGA Journal|ICCA Journal]], Vol. 18, No. 2, pp. 71-76, [http://www.cs.ualberta.ca/%7Emburo/ps/probcut.pdf pdf]</ref> .
<pre>
int alphaBetaProbCut(int α, int β, int depth) {
const float T(1.5);
const int DP(4);
const int 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 */
...
}
</pre>
<span id="MPC"></span>
=Multi–ProbCut=
Multi–ProbCut (MPC) enhances ProbCut by
* Allowing different regression parameters and cut thresholds for different stages of the game
* Using more than one depth pair
* Using [[Internal Iterative Deepening|internal iterative deepening]] for shallow searches
<pre>
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 */
...
}
</pre>
=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 <ref>[[Albert Xin Jiang]] ('''2003'''). ''Implementation of Multi-ProbCut and Chess''. CPSC 449 Thesis, [http://www.cs.ubc.ca/%7Ejiang/papers/thesis.pdf pdf], 2.5 ProbeCut in Chess, pp. 6</ref> :
There has been no report of success for ProbCut or MPC in chess thus far. There are at least two reasons for this:
# <code>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.</code>
# <code>Chess searches tend to make more mistakes than Othello searches</code> <ref>[[Andreas Junghanns]], [[Jonathan Schaeffer]], [[Mark Brockington]], [[Yngvi Björnsson]], [[Tony Marsland]] ('''1997'''). ''Diminishing Returns for Additional Search in Chess.'' [[Advances in Computer Chess 8]]</ref><code>. 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</code>.
In his research, Albert Xin Jiang further determined following parameters by [https://en.wikipedia.org/wiki/Linear_regression 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:
[[FILE:CraftyLinearReg.JPG|none|border|text-bottom]]
v' versus v for depth pair (4,8) <ref>Image from [[Albert Xin Jiang]] ('''2003'''). ''Implementation of Multi-ProbCut in Chess''. CPSC 449 Thesis, [http://www.cs.ubc.ca/%7Ejiang/papers/thesis.pdf pdf]</ref>
Linear regression results. The evaluation function’s scale is 100 = one pawn. r is the [https://en.wikipedia.org/wiki/Correlation_and_dependence regression correlation coefficient], a measure of how good the data fits the linear model:
{| class="wikitable"
|-
! Pairs
! Stage
! a
! b
! σ
! r
|-
| (3,5)
| [[Middlegame]]
| 0.998
| style="text-align:right;" | -7.000
| 55.80
| 0.90
|-
| (3,5)
| [[Endgame]]
| 1.026
| style="text-align:right;" | -4.100
| 51.80
| 0.94
|-
| (4,8)
| Middlegame
| 1.020
| style="text-align:right;" | 2.360
| 82.00
| 0.82
|-
| (4,8)
| Endgame
| 1.110
| style="text-align:right;" | 1.750
| 75.00
| 0.90
|}
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 [[Match Statistics|matches]] with three Crafty versions and two time controls versus [[Dieter Bürssner|Dieter Bürssner's]] program [[Yace]] <ref>Page 30 in [[Albert Xin Jiang]], [[Michael Buro]] ('''2003'''). ''First Experimental Results of ProbCut Applied to Chess''. [[Advances in Computer Games 10]], [http://cs.ubc.ca/%7Ejiang/papers/mpc_main.pdf pdf]</ref> :
{| class="wikitable"
|-
! rowspan="2" | Pairing
! colspan="2" | Crafty %
|-
! 2min + <br/>10sec/move
! 8min + <br/>20sec/move
|-
! Crafty - Yace
| style="text-align:right;" | 42.0
| style="text-align:right;" | 50.8
|-
! MPC Crafty(1.2, 1.0) - Yace
| style="text-align:right;" | 53.1
| style="text-align:right;" | 56.3
|-
! MPC Crafty(1.0, 1.0) - Yace
| style="text-align:right;" | 57.0
| style="text-align:right;" | 55.5
|}
However, [[Robert Hyatt]] first stated results were inconclusive <ref>[https://www.stmintz.com/ccc/index.php?id=303565 Re: Multi-ProbCut and Crafty : does it work ?] by [[Robert Hyatt]], [[CCC]], June 28, 2003</ref> , and later that MPC was somewhat worse in every test he tried <ref>[https://www.stmintz.com/ccc/index.php?id=378374 Re: ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm] by [[Robert Hyatt]], [[CCC]], July 21, 2004</ref> , also confirmed by [[Robert Allgeuer]], who performed Crafty MPC tests with following conclusion in [[CCC]] <ref>[https://www.stmintz.com/ccc/index.php?id=322133 Crafty MPC tests (long post)] by [[Robert Allgeuer]], [[CCC]], October 18, 2003</ref> :
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=
* [[Enhanced Forward Pruning]]
* [[Futility Pruning]]
* [[Late Move Reductions]]
* [[Match Statistics]]
* [[Multi-Cut]]
* [[Null Move Pruning]]
=Publications=
<ref>[http://skatgame.net/mburo/publications.html Michael Buro's Publication List]</ref> <ref>[http://www.cs.ubc.ca/%7Ejiang/ Albert Xin Jiang - publications]</ref>
* [[Michael Buro]] ('''1994'''). ''Techniken für die Bewertung von Spielsituationen anhand von Beispielen.'' Ph.D. Thesis. [[University of Paderborn]], Paderborn, Germany. (German), [http://www.cs.ualberta.ca/%7Emburo/ps/mics_dis.pdf pdf]
* [[Michael Buro]] ('''1995'''). ''ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm.'' [[ICGA Journal|ICCA Journal]], Vol. 18, No. 2, pp. 71-76, [http://www.cs.ualberta.ca/%7Emburo/ps/probcut.pdf 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. [http://skatgame.net/mburo/ps/improve.pdf pdf]
* [[Michael Buro]] ('''2000'''). ''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. [[Maastricht University|Universiteit Maastricht]], Maastricht, The Netherlands. ISBN 90-621-6416-1.
* [[Kazutomo Shibahara]], [[Nobuo Inui]], [[Yoshiyuki Kotani]] ('''2002'''). ''Effect of ProbCut in Shogi - by changing parameters according to position category''. [[Conferences#GPW|7th Game Programming Workshop]]
* [[Michael Buro]] ('''2002'''). ''Multi-ProbCut Search''. slides as [http://skatgame.net/mburo/ps/mpc.pdf pdf]
* [[Albert Xin Jiang]] ('''2003'''). ''Implementation of Multi-ProbCut in Chess''. CPSC 449 Thesis, [http://www.cs.ubc.ca/%7Ejiang/papers/thesis.pdf pdf]
* [[Albert Xin Jiang]], [[Michael Buro]] ('''2003'''). ''First Experimental Results of ProbCut Applied to Chess''. [[Advances in Computer Games 10]], [http://cs.ubc.ca/%7Ejiang/papers/mpc_main.pdf pdf]
* [[Maarten Schadd]], [[Mark Winands]], [[Jos Uiterwijk]] ('''2009'''). ''ChanceProbCut: Forward Pruning in Chance Nodes''. in IEEE Symposium on Computational Intelligence and Games (CIG 2009), [http://www.personeel.unimaas.nl/Maarten-Schadd/Papers/2009StrategoCIG.pdf pdf]
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=66467 whats probcut?] by vitor, [[CCC]], August 29, 1999
* [https://www.stmintz.com/ccc/index.php?id=178124 muliti probcut] by [[Martin Fierz]], [[CCC]], July 04, 2001
* [https://www.stmintz.com/ccc/index.php?id=303536 Multi-ProbCut and Crafty : does it work ?] by [[Frédéric Louguet]], [[CCC]], June 28, 2003
* [https://www.stmintz.com/ccc/index.php?id=322133 Crafty MPC tests (long post)] by [[Robert Allgeuer]], [[CCC]], October 18, 2003
* [https://www.stmintz.com/ccc/index.php?id=378283 ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm] by [[Albert Silver]], [[CCC]], July 21, 2004
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=274486&t=28459 Re: Possible search improvment] by [[Ryan Benitez]], [[CCC]], June 17, 2009 » [[History Leaf Pruning]]
* [http://www.talkchess.com/forum/viewtopic.php?t=38407 Bad Pruning] by [[Onno Garms]], [[CCC]], March 13, 2011
* [http://www.talkchess.com/forum/viewtopic.php?p=518426 Probcut] by [[Gary Linscott|Gary]], [[CCC]], May 24, 2013 » [[Stockfish]]
=External Links=
* [http://radagast.se/othello/howto.html Writing an Othello program] by [[Gunnar Andersson]]
* [http://fuego.sourceforge.net/fuego-doc-1.1/smartgame-doc/SgProbCut_8h.html#_details SmartGame Library: SgProbCut.h File Reference], [http://fuego.sourceforge.net/fuego-doc-1.1/ Fuego Documentation] <ref>[http://www.grappa.univ-lille3.fr/icga/program.php?id=535 Fuego], [[Go]] playing program by [[Markus Enzenberger]], [[Martin Müller]], [[Broderick Arneson]], [[Richard Segal]], [[Gerald Tesauro]] and [[Arpad Rimmel]]</ref>
=References=
<references />
'''[[Pruning|Up one Level]]'''
