Thread: NegaScout

  1. #1
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446

    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...
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

  2. #2
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    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.

  3. #3
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446
    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;
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

  4. #4
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446
    I found my answer...it turns out that NegaScout is also known as Principal Variation Search:

    http://www.seanet.com/~brucemo/topics/pvs.htm
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

Popular pages Recent additions subscribe to a feed