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

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 nextGuess is
return α + × / subtreeCount
function bns is
subtreeCount := number of children of node
do
test := nextGuess
betterCount := 0
for each child of node do
bestVal := −alphabeta
if bestVal ≥ test then
betterCount := betterCount + 1
bestNode := child
'
'
while not
return bestNode
The default nextGuess function above may be replaced with one which uses statistical information for improved performance.

Generalization

with Murphy Sampling is an extension of Best Node Search to non-deterministic setting.