Difference between revisions of "Best-First Minimax Search"
GerdIsenberg (talk | contribs) m (GerdIsenberg moved page Best-first minimax search to Best-First Minimax Search: caps consistent with other page titkes) |
GerdIsenberg (talk | contribs) |
||
(One intermediate revision by the same user not shown) | |||
Line 1: | Line 1: | ||
− | '''[[Main Page|Home]] * [[Search]] * Best- | + | '''[[Main Page|Home]] * [[Search]] * Best-First Minimax Search''' |
− | '''Best- | + | '''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>. | 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>. | ||
Line 28: | Line 28: | ||
* [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=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]] | * [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]] | ||
− | |||
− | |||
=References= | =References= | ||
<references /> | <references /> | ||
+ | '''[[Search|Up one level]]''' |
Latest revision as of 21:35, 11 February 2019
Home * Search * Best-First Minimax Search
Best-First Minimax Search, (BFMMS)
is a Best-First search algorithm based on Best-First and a shallow alpha-beta depth-first-search proposed by Richard Korf and Max Chickering [1].
BFMMS, MCαβ, the Rollout Paradigm and further MCTS-minimax hybrids share the same idea, to combine Best-First with Depth-First searches.
Four Phases
BFMMS can be divided into four strategic phases, repeated as long as there is time left:
- In the Selection phase the best node is selected from the game tree via node score from the 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
Publications
- Richard Korf, Max Chickering (1996). Best-First Minimax Search. Artificial Intelligence, Vol. 84, No 1-2
- Yaron Shoham, Sivan Toledo (2001). Parallel Randomized Best-First Minimax Search
Forum Posts
- MCTS without random playout? by Antonio Torrecillas, CCC, January 01, 2012 » B*
- Help with Best-First Select-Formula by Srdja Matovic, CCC, July 23, 2012
- Re: Announcing lczero by Daniel Shawul, CCC, January 21, 2018 » Leela Chess Zero
- Alpha-Beta as a rollouts algorithm by Daniel Shawul, CCC, January 25, 2018 » Alpha-Beta, Monte-Carlo Tree Search, Scorpio
References
- ↑ Richard Korf, Max Chickering (1996). Best-First Minimax Search. Artificial Intelligence, Vol. 84, No 1-2