How does the NegaScout algorithm work?
Sorry for the late reply (4 years!)

NegaScout is a very simple algorithm. To understand we should revise iterative deepening.

Iterative deepening is a technique for a chess engine 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 chess engines 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. Now we have 5 nodes to search, we should we do?

If we assume we have done reasonably good job 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 the current iteration.

If our assumption is correct, we should be able to save time by searching every move other than the best move (the four moves not in the hash table) with a null window. A null window is something like:

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

Note -α-1 and -α. They are the alpha and beta values we will give to the next recursion. Since the width of the window is only 1, the search will always fail:


If it fails below α, the move is worse than we already have, so we can ignore it
If it fails above β, the move is too good to play, so we can ignore it 
Otherwise, we need to do a new search properly


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 exactly the value of the node, we can't just ignore it.

Everything I've said is implemented in the following pseudocode. The pseudocode specifies child is not first child but this is a way to check whether the move is also the best move int the previous iteration. Hash table is the most common implementation.

# Negasort is also termed Principal Variation Search - hence - pvs

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 α &lt; score &lt; β
                score := -pvs(child, depth - 1, -β, -score, -color)
        else
            score := -pvs(child, depth - 1, -β, -α, -color)

        α := max(α, score)

        # beta cut-off
        if α &gt;= β
            break

    return α