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.^[1]

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

References

1. ↑ http://www.bjmc.lu.lv/fileadmin/user_upload/lu_portal/projekti/bjmc/Contents/770_7.pdf