How does the NegaScout algorithm work?

On Alpha-Beta pruning, NegaScout claims that it can accelerate the process by setting [Alpha,Beta] to [Alpha,Alpha-1].

I do not understand the whole process of NegaScout.

How does it work? What is its recovery mechanism when its guessing failed?

NegaScout is a very simple algorithm. To understand we should first review iterative deepening negamax (minimax).

Iterative deepening is a technique to search for depth i, then i+1, then i+2, etc. This is an example of dynamic programming. During each iteration we have our best guess of what the best move would be. Most programs would keep this move in a hashing table.

Imagine we are now at iteration i+1, and we have the best move from the last iteration i. Also assume we have 5 nodes to search from here, what should we do?

If we assume we have done a reasonably good job of scoring during our last iteration, the best move from the last iteration (which we get from the hash table) should also be the best move for that depth in the current iteration.

If our assumption is correct, we can then save time by searching every move other than the best move (the four moves not in the hash table) with a null window. For example:

score := -pvs(child, depth+1, -α-1, -α, -color)

Note that Negascout is also known as Principal-Variation Search hence the pvs. And also note -α-1 and -α. They are the alpha and beta values, respectively, we are passing to the next call / depth. Since the width of the window is only 1 (-α-1 - (-α)), essentially null, this enables cutoffs to be produced very quickly, since the greater the gap between alpha and beta, there's more moves that can fit between them and not get cutoff. So the search will return the following:

• If it fails below α, the move is worse than what we already have, so we can ignore it

• If it fails above β, the move is too good to play, so we can also ignore it

• Otherwise, if it doesn't fail, we need to do a new search properly to get the exact value of that child

Of course, we will still search the best move (the one we get from the hash table) with a proper alpha and beta window. We need to do this because we need to know the exact value of the best node.

Everything I've said is implemented in the following pseudocode which can also be found here. The pseudocode specifies if child is not first child but this is a way to check whether the move is also the best move in the previous iteration since it orders the children based on how good it is. Furthermore, it also displays depth in reverse order, starting at a depth i and ending at 0.

function pvs(node, depth, α, β, color)
    if node is a terminal node or depth = 0
        return color x the heuristic value of node

    for each child of node
        if child is not the first child
            # search with a null window
            score := -pvs(child, depth - 1, -α - 1, -α, -color)

            # if it failed high, do a full re-search
            if α = β
            break

    return α

StackExchange Computer Science Q#1134, answer score: 8