25,161
edits
Changes
no edit summary
'''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. [[Paderborn University]], Paderborn, Germany. (German), 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. [https://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 [[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, [http://webdocs.cs.ualberta.ca/~duane/publications/pdf/1992ai.pdf pdf preprint]</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]], [https://skatgame.net/mburo/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]]</ref>, it seemed not that successful in chess programs which already perform [[Null Move Pruning]] and [[Late Move Reductions]], until [[Stockfish]] 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>.
