Best node search

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.

Performance

MTD-f guesses the minimax by calling zero-window alpha-beta prunings. BNS calls search that tells whether the minmax 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, α, β)
subtreeCount := number of children of node
do
    test := NextGuess(α, β, subtreeCount)
    betterCount := 0
    foreach child of node
        bestVal := -AlphaBeta(child, -test, -(test - 1))
        if bestVal ≥ test
            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

External links

• fuzzy minimax algorithms