Changes

Jump to: navigation, search

ProbCut

6 bytes removed, 10:41, 30 May 2018
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 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=
=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. [[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|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]

Navigation menu