Multi-Prob Cut: Difference between revisions

Revision as of 18:51, 14 February 2020

Latest revision as of 06:18, 30 March 2020

(3 intermediate revisions by 3 users not shown)

Line 1:

#REDIRECT [[Computer Othello]]

<!-- Please do not remove or change this AfD message until the discussion has been closed. -->

{{Rcat shell|1=

{{Article for deletion/dated|page=Multi-Prob Cut|timestamp=20200214022511|year=2020|month=February|day=14|substed=yes|help=off}}

{{R from merge}}

<!-- Once discussion is closed, please place on talk page: {{Old AfD multi|page=Multi-Prob Cut|date=14 February 2020|result='''keep'''}} -->

}}

<!-- End of AfD message, feel free to edit beyond this point -->

{{Multiple issues|{{context|date=August 2017}}{{technical|date=August 2017}}}}

In [[game theory]], '''Multi-ProbCut''' is a heuristic used in [[alpha–beta pruning]] of the search tree.<ref name="Buro1997">{{cite journal|last1=Buro|first1=Michael|date=1997|title=Experiments with Multi-ProbCut and a New High-Quality Evaluation Function for Othello|url=http://citeseerx.ist.psu.edu/viewdoc/versions?doi=10.1.1.19.1136|journal=Games in AI Research|language=en|volume=34|issue=4|pages=77-96|via=}}</ref> The ProbCut heuristic estimates evaluation scores at deeper levels of the search tree using a [[linear regression]] between deeper and shallower scores. Multi-ProbCut extends this approach to multiple levels of the search tree. The linear regression itself is learned through previous tree searches, making the heuristic a kind of dynamic search control.<ref name="Bulitko2008">{{cite journal |last1=Bulitko |first1=Vadim |last2=Lustrek |first2=Mitja |last3=Schaeffer |first3=Jonathan |last4=Bjornsson |first4=Yngvi |last5=Sigmundarson |first5=Sverrir |title=Dynamic control in real-time heuristic search |journal=Journal of Artificial Intelligence Research |date=1 June 2008 |volume=32 |pages=419-452 |url=https://dl.acm.org/doi/abs/10.5555/1622673.1622683 |language=EN}}</ref> It is particularly useful in games such as [[Othello]] where there is a strong correlation between evaluations scores at deeper and shallower levels.<ref name="Fürnkranz2001">{{cite book |last1=Fürnkranz |first1=Johannes |title=Machines that learn to play games {{!}} Guide books |date=2001 |publisher=Nova Science Publishers, Inc. |___location=Nova Science Publishers, Inc.6080 Jericho Tpke. Suite 207 Commack, NYUnited States |isbn=978-1-59033-021-0 |pages=11-59 |url=https://dl.acm.org/doi/book/10.5555/644391}}</ref><ref name="Heinz2013">{{cite book |last1=Heinz |first1=Ernst A. |title=Scalable Search in Computer Chess: Algorithmic Enhancements and Experiments at High Search Depths |date=2013 |publisher=Springer Science & Business Media |isbn=978-3-322-90178-1 |page=32 |url=https://books.google.com/books?id=KkQBCAAAQBAJ&lr=&source=gbs_navlinks_s |language=en}}</ref>

==References==

{{Reflist}}

[[Category:Game artificial intelligence]]

[[Category:Heuristics]]

[[Category:Search algorithms]]

{{algorithm-stub}}