Changes

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. [[Paderborn 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. [httphttps://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]. ] by [[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''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 53, Nos. 2-3, pp. 273-2896, "If a line leads to a material deficit and there is insufficient positional compensation (the positional assessment of the position does not reach a fixed threshold) then the remaining search depth is cut in half. If the result of this search does not restore the material deficit, or result in sufficient positional compensation, this line is abandoned. Otherwise, the line is researched to the full search depth". ISSN 0004-3702</ref> described their approach in a footnodefootnote: 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#18_2|ICCA Journal]], Vol. 18, No. 2, pp. 71-76]], [httphttps://wwwskatgame.cs.ualberta.canet/%7Emburomburo/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 proved 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>.

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#18_2|ICCA Journal]], Vol. 18, No. 2, pp. 71-76]], [httphttps://www.cs.ualbertaskatgame.canet/%7Emburomburo/ps/probcut.pdf pdf]</ref> .

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ürssnerBürßner|Dieter BürssnerBürßner'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> :

* [[Michael Buro]] ('''1994'''). ''Techniken für die Bewertung von Spielsituationen anhand von Beispielen.'' Ph.D. Thesis. [[Paderborn 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#18_2|ICCA Journal]], Vol. 18, No. 2, pp. 71-76]], [httphttps://wwwskatgame.cs.ualberta.canet/%7Emburomburo/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. [httphttps://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.

* [[Michael Buro]] ('''2002'''). ''Multi-ProbCut Search''. slides as [httphttps://skatgame.net/mburo/ps/mpc.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]