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]], 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''. 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#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 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> .

* [[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]