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
6
$\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 α
| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\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.