# 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?

• The main notion behind NegaScout is clearly explained in the link you provided: by using a null window (where $\alpha$ and $\beta$ are the same, instead of $\beta=\alpha-1$ as you put it), it can be verified whether the left-most child of each depth lies on the principal variation or not. If so, the search is terminated. Otherwise, the algorithms proceeds as an ordinary minimax search algorithm with alpha-beta pruning. Note that NegaScout re-expands all nodes that lie in the left branch of the search algorithm. Besides, it is based on Negamax instead of Minimax. May 1, 2012 at 21:49
• What is this sentence means 'it can be verified whether the left-most child of each depth lies on the principal variation or not.' ? Is there any example? Thank you~
– sam
May 8, 2012 at 15:22
• @CarlosLinaresLópez, if you'd like to expand your comment into an answer, we could clean up this answer Nov 25, 2012 at 16:15

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 α < score < β
score := -pvs(child, depth - 1, -β, -score, -color)
else
# search with a normal window
score := -pvs(child, depth - 1, -β, -α, -color)

α := max(α, score)

# alpha-beta cut-off
if α >= β
break

return α


In order to understand NegaScout, it is necessary, at first, to be very clear on what the parameters $$\alpha$$ and $$\beta$$ mean.

Given a chess position to evaluate. All of the legal moves have their own scores (relative to a given depth). The better the move, the higher its score is. Some moves have the highest score - these are the best moves; they all have the same score.

The NegaScout function must find one of the best moves, and must calculate its score. This is the purpose of the function. Such is the formal description of the task NegaScout solves. The key feature is NegaScout does not have to return the computed values.

Whether NegaScout returns a best move itself, depends on the function's implementation. What makes this algorithm (and also the classical AlphaBeta algorithm) faster than brute force is the return value. If $$depth = 0$$, then NegaScout evaluates the position statically by making a call to a special function and returns the obtained estimation - brute force does the same in this case; static evaluation is a separate task out of NegaScout's scope. Suppose $$depth > 0$$. Then three cases are possible (relatively to the given depth!). Note $$\alpha < \beta$$ (otherwise the return value is undetermined).

Case 1: there are no moves stronger than $$\alpha$$. In this case NegaScout must return any number $$\xi\le\alpha$$ such that the score of any legal move in the current position satisfies the condition $$score \le \xi$$.

Case 2: the score of the best moves belong to the interval $$(\alpha,\beta)$$. In this case NegaScout must return the score of the best moves (remember all best moves have the same score, by definition).

Case 3: there is a move stronger than $$\beta$$. In this case NegaScout must return any number $$\xi \ge \beta$$ such the score of that at least one move satisfies the condition $$score \ge \xi$$.

Pay attention at the empathized word "must": don't try to prove these statements by analyzing an implementation of the method. Instead, assume what is written above as the formal definition of NegaScout; i.e. if a function does not return a value satisfying the conditions given above, then assume such a function not to be an implementation of NegaScout, according to the definition. After this, look at the pseudocode given above by the user HelloWorld and make sure this implementation really satisfies our formal definition of NegaScout.

As soon as you understand this formal definition, NegaScout will become evidence. It is obvious NegaScout coincides the brute force in case $$(\alpha = -\infty) \;\&\, (\beta = +\infty)$$.

And the last remark. The classical AlphaBeta algorithm may return any $$\xi \le \alpha$$ and any $$\xi \ge \beta$$ (without any restrictions) in the cases 1 and 3, respectively: this is the only its difference from NegaScout.