422
edits
Changes
Created page with "'''Home * Search * Best-first minimax search''' '''Best-first minimax search''', '''(BFMMS)'''<br/> is a Best-First search algorithm based on..."
'''[[Main Page|Home]] * [[Search]] * Best-first minimax search'''
'''Best-first minimax search''', '''(BFMMS)'''<br/>
is a [[Best-First|Best-First search]] algorithm based on [[Best-First]] and a shallow [[Alpha-Beta|alpha-beta]] [[Depth-First|depth-first-search]] proposed by [[Richard Korf]] and [[Max Chickering]] <ref>[[Richard Korf]], [[Max Chickering]] ('''1996'''). ''[https://www.microsoft.com/en-us/research/publication/best-first-minimax-search/ Best-First Minimax Search]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 84, No 1-2</ref>.
BFMMS, [[MCαβ]], the [[Bojun Huang#Rollout|Rollout Paradigm]] and further [[Monte-Carlo_Tree_Search|MCTS]]-minimax hybrids share the same idea, to combine Best-First with Depth-First searches.
<span id="Four Phases"></span>
=Four Phases=
BFMMS can be divided into four strategic phases, repeated as long as there is time left:<span id="Four Phases"></span>
# In the Selection phase the best node is selected from the game tree via node score from the [[Root|root node]] until it selects an unexpanded node
# The Expansion strategy adds the unexpanded child nodes to the tree
# The Playout phase performs a shallow alpha-beta search to get a node score
# The Backpropagation strategy propagates the score through the tree
=See also=
* [[MCαβ]]
* [[Bojun Huang#Rollout|Rollout Paradigm]]
<span id="Publications"></span>
=Publications=
* [[Richard Korf]], [[Max Chickering]] ('''1996'''). ''[https://www.microsoft.com/en-us/research/publication/best-first-minimax-search/ Best-First Minimax Search]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 84, No 1-2
* [[Yaron Shoham]], [[Sivan Toledo]] ('''2001'''). ''[http://www.cs.tau.ac.il/~stoledo/Pubs/rbf-ai.pdf Parallel Randomized Best-First Minimax Search]''
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=41730 MCTS without random playout?] by [[Antonio Torrecillas]], [[CCC]], January 01, 2012 » [[B*]]
* [http://talkchess.com/forum/viewtopic.php?t=44165 Help with Best-First Select-Formula ] by [[Srdja Matovic]], [[CCC]], July 23, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=66280&start=67 Re: Announcing lczero] by [[Daniel Shawul]], [[CCC]], January 21, 2018 » [[Leela Chess Zero]]
* [http://www.talkchess.com/forum/viewtopic.php?t=66414 Alpha-Beta as a rollouts algorithm] by [[Daniel Shawul]], [[CCC]], January 25, 2018 » [[Alpha-Beta]], [[Monte-Carlo Tree Search]], [[Scorpio]]
=External Links=
=References=
<references />
'''Best-first minimax search''', '''(BFMMS)'''<br/>
is a [[Best-First|Best-First search]] algorithm based on [[Best-First]] and a shallow [[Alpha-Beta|alpha-beta]] [[Depth-First|depth-first-search]] proposed by [[Richard Korf]] and [[Max Chickering]] <ref>[[Richard Korf]], [[Max Chickering]] ('''1996'''). ''[https://www.microsoft.com/en-us/research/publication/best-first-minimax-search/ Best-First Minimax Search]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 84, No 1-2</ref>.
BFMMS, [[MCαβ]], the [[Bojun Huang#Rollout|Rollout Paradigm]] and further [[Monte-Carlo_Tree_Search|MCTS]]-minimax hybrids share the same idea, to combine Best-First with Depth-First searches.
<span id="Four Phases"></span>
=Four Phases=
BFMMS can be divided into four strategic phases, repeated as long as there is time left:<span id="Four Phases"></span>
# In the Selection phase the best node is selected from the game tree via node score from the [[Root|root node]] until it selects an unexpanded node
# The Expansion strategy adds the unexpanded child nodes to the tree
# The Playout phase performs a shallow alpha-beta search to get a node score
# The Backpropagation strategy propagates the score through the tree
=See also=
* [[MCαβ]]
* [[Bojun Huang#Rollout|Rollout Paradigm]]
<span id="Publications"></span>
=Publications=
* [[Richard Korf]], [[Max Chickering]] ('''1996'''). ''[https://www.microsoft.com/en-us/research/publication/best-first-minimax-search/ Best-First Minimax Search]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 84, No 1-2
* [[Yaron Shoham]], [[Sivan Toledo]] ('''2001'''). ''[http://www.cs.tau.ac.il/~stoledo/Pubs/rbf-ai.pdf Parallel Randomized Best-First Minimax Search]''
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=41730 MCTS without random playout?] by [[Antonio Torrecillas]], [[CCC]], January 01, 2012 » [[B*]]
* [http://talkchess.com/forum/viewtopic.php?t=44165 Help with Best-First Select-Formula ] by [[Srdja Matovic]], [[CCC]], July 23, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=66280&start=67 Re: Announcing lczero] by [[Daniel Shawul]], [[CCC]], January 21, 2018 » [[Leela Chess Zero]]
* [http://www.talkchess.com/forum/viewtopic.php?t=66414 Alpha-Beta as a rollouts algorithm] by [[Daniel Shawul]], [[CCC]], January 25, 2018 » [[Alpha-Beta]], [[Monte-Carlo Tree Search]], [[Scorpio]]
=External Links=
=References=
<references />
