8
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Please provide links to your references and formulate a more focused question. $\endgroup$ – Raphael Apr 8 '12 at 16:39
  • 1
    $\begingroup$ 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. $\endgroup$ – Carlos Linares López May 1 '12 at 21:49
  • $\begingroup$ 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~ $\endgroup$ – sam May 8 '12 at 15:22
  • $\begingroup$ @CarlosLinaresLópez, if you'd like to expand your comment into an answer, we could clean up this answer $\endgroup$ – Merbs Nov 25 '12 at 16:15
5
$\begingroup$

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

        α := max(α, score)

        # beta cut-off
        if α >= β
            break

    return α
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.