NegaScout

Can anyone give a plain english description of how NegaScout works. Most links I've found online simply say that Negascout dominates AlphaBeta, but don't really explain conceptually how or why. The algorithm given on Wikipedia seems fairly similar to AlphaBeta, and I'm sure if I stared at it for long enough, it would eventually make some sense, but...

It looks similar to alpha-beta because they are both MiniMax algorithms. NegaScout claims superiority because it explores less nodes in the case where strong moves are searched first. As wikipedia notes though, NegaScout is actually worse than alpha-beta if the search order is randomized.

They are both optimizations of the MiniMax algorithm.

Disclaimer: ive never even heard of NegaScout before, my explanation is simply an interpretation of wikipedia's article.

Yeah, I sort of understood as much, I was basically wondering the inner workings of how the optimization produces a better result.

For example, the following is basically the code given on Wiki (I changed it so that it makes more c++ sense). And I put ifdefs around the place where the code is different. And I'm trying to figure out exactly what that means...besides "this is some hocus pocus that performs better than alphabeta but only in certain circomstances." As an example of the kind of description I'm hoping for, check this link for an AlphaBeta description:

http://www.seanet.com/~brucemo/topics/alphabeta.htm

And, in case you're wondering, I'm going to implement NegaScout, for my ConnectFour game, and I'm running on the assumption that it won't work correctly the first time. And if my implementation is just me copying code, I'll probably never figure out the real problem...

Code:

---

  /* Compute minimax value of position p */
  NegaScout ( GameState& gs, int depth, int alpha, int beta )  {
    if (gs.EndState() || depth == 0) {
        return gs.Evaluate();
    }
    list<moves_t> themoves;
    gs.GenerateMoves(themoves);

    for (list<moves_t>::iterator itr = themoves.begin();
          itr != themoves.end(); itr++) {
        MakeMove(gs);
        int temp = -NegaScout ( gs, depth - 1, -beta, -alpha )

#    if NEGASCOUT
       
        if ( alpha > temp && temp > beta) && not_first_child(*itr))
          alpha = -NegaScout ( gs, depth -1, -beta, -temp );
          UnMakeMove(gs);

        // these lines look very similar to alpha beta code ...
        if (temp > alpha) alpha = temp; // this is done after the next line in AlphaBeta!
        if (alpha >= beta) 
            return alpha; // alpha beta returns beta here!
        beta = alpha + 1; // this is not done in alphabeta!
#  elif ALPHABETA
      UnMakeMove(gs);
      if (temp >= beta) return beta;
      if (temp > alpha) alpha = temp;
#  endif
    }
    return alpha;

---

I found my answer...it turns out that NegaScout is also known as Principal Variation Search:

http://www.seanet.com/~brucemo/topics/pvs.htm