Best node search: Difference between revisions
No edit summary |
Reverting edit(s) by 98.207.210.21 (talk) to rev. 1126507912 by Citation bot: Joke edit (UV 0.1.5) |
||
| (42 intermediate revisions by 16 users not shown) | |||
| Line 1: | Line 1: | ||
{{short description|Alpha-beta game tree search algorithm}} |
|||
{{Multiple issues| |
|||
{{ |
{{Technical|date=October 2016}} |
||
{{technical|date=October 2016}} |
|||
}} |
|||
'''Best node search''' ('''BNS'''), originally known as '''fuzzified game tree search''', is a [[minimax]] [[search algorithm]], developed in 2011. The idea is that the knowledge that one subtree is ''relatively'' better than some (or all) other(s) may be propagated sooner than the absolute value of minimax for that subtree. Then a repetitive search narrows until a particular node is shown to be ''relatively'' best. |
|||
'''Best Node Search''', is a [[minimax]] search algorithm, developed in 2011. Experiments with random trees show it to be the most efficient minimax algorithm. This algorithm does tell which move leads to minmax, but does not tell the evaluation of minimax.<ref>http://www.bjmc.lu.lv/fileadmin/user_upload/lu_portal/projekti/bjmc/Contents/770_7.pdf</ref> |
|||
| ⚫ | First an initial guess at the minimax value must be made, possibly based on statistical information obtained elsewhere. Then BNS calls search that tells whether the minimax of the [[subtree]] is smaller or bigger than the guess. It changes the guessed value until [[alpha]] and [[beta]] are close enough or only one [[subtree]] allows a minimax value greater than the current guess. These results are analogous, respectively, to "prove best" and "disprove rest" heuristic search strategies. |
||
==Performance== |
|||
| ⚫ | |||
The search result is the node (move) whose subtree contains the minimax value, and a bound on that value, but not the minimax value itself.<ref>{{cite journal |last1=Rutko |first1=Dmitrijs |title=Fuzzified Algorithm for Game Tree Search with Statistical and Analytical Evaluation |journal=Scientific Papers, University of Latvia |date=2011 |volume=770 |pages=90–111 |url=https://www.bjmc.lu.lv/fileadmin/user_upload/lu_portal/projekti/bjmc/Contents/770_7.pdf |access-date=5 November 2022 |language=en-us}}</ref> Experiments with [[random tree]]s show it to be the most efficient minimax algorithm.{{citation needed|date=June 2021}} |
|||
==Pseudocode== |
==Pseudocode== |
||
'''function''' nextGuess(α, β, subtreeCount) '''is''' |
|||
'''return''' α + (β − α) × (subtreeCount − 1) / subtreeCount |
|||
| ⚫ | |||
| ⚫ | |||
'''do''' |
|||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
The default '''nextGuess''' function above may be replaced with one which uses statistical information for improved performance. |
|||
==Generalization== |
|||
| ⚫ | |||
[[Monte Carlo tree search|Tree searching]] with Murphy Sampling<ref>{{Cite arXiv |eprint = 1806.00973|last1 = Kaufmann|first1 = Emilie|title = Sequential Test for the Lowest Mean: From Thompson to Murphy Sampling|last2 = Koolen|first2 = Wouter|last3 = Garivier|first3 = Aurelien|class = stat.ML|year = 2018}}</ref> is an extension of Best Node Search to non-deterministic setting. |
|||
| ⚫ | |||
do |
|||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
==External links== |
==External links== |
||
Latest revision as of 22:30, 24 August 2024
 | This article may be too technical for most readers to understand. (October 2016) |
Best node search (BNS), originally known as fuzzified game tree search, is a minimax search algorithm, developed in 2011. The idea is that the knowledge that one subtree is relatively better than some (or all) other(s) may be propagated sooner than the absolute value of minimax for that subtree. Then a repetitive search narrows until a particular node is shown to be relatively best.
First an initial guess at the minimax value must be made, possibly based on statistical information obtained elsewhere. Then BNS calls search that tells whether the minimax of the subtree is smaller or bigger than the guess. It changes the guessed value until alpha and beta are close enough or only one subtree allows a minimax value greater than the current guess. These results are analogous, respectively, to "prove best" and "disprove rest" heuristic search strategies.
The search result is the node (move) whose subtree contains the minimax value, and a bound on that value, but not the minimax value itself.[1] Experiments with random trees show it to be the most efficient minimax algorithm.[citation needed]
Pseudocode
[edit]function nextGuess(α, β, subtreeCount) is
return α + (β − α) × (subtreeCount − 1) / subtreeCount
function bns(node, α, β) is
subtreeCount := number of children of node
do
test := nextGuess(α, β, subtreeCount)
betterCount := 0
for each child of node do
bestVal := −alphabeta(child, −test, −(test − 1))
if bestVal ≥ test then
betterCount := betterCount + 1
bestNode := child
(update number of sub-trees that exceeds separation test value)
(update alpha-beta range)
while not (β − α < 2 or betterCount = 1)
return bestNode
The default nextGuess function above may be replaced with one which uses statistical information for improved performance.
Generalization
[edit]Tree searching with Murphy Sampling[2] is an extension of Best Node Search to non-deterministic setting.
External links
[edit]References
[edit]- ^ Rutko, Dmitrijs (2011). "Fuzzified Algorithm for Game Tree Search with Statistical and Analytical Evaluation" (PDF). Scientific Papers, University of Latvia. 770: 90–111. Retrieved 5 November 2022.
- ^ Kaufmann, Emilie; Koolen, Wouter; Garivier, Aurelien (2018). "Sequential Test for the Lowest Mean: From Thompson to Murphy Sampling". arXiv:1806.00973 [stat.ML].