Best node search
 | This article may be too technical for most readers to understand. (October 2016) |
Best Node Search (BNS) 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.[1]
Performance
MTD-f guesses the minimax by calling zero-window alpha-beta prunings. BNS calls search that tells whether the minimax in the subtree is smaller or bigger than the guess. It changes the guessed value until alpha and beta is close enough or only one subtree allows minimax value bigger than guessed value.
Pseudocode
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
Generalization
Tree searching with Murphy Sampling[2] is an extension of Best Node Search to non-deterministic setting.