Computer Chess Club Archives


Search

Terms

Messages

Subject: A Question on simple Alpha-Beta versus PVS/Negascout

Author: Andrei Fortuna

Date: 17:06:10 03/21/00


In my chess program Freyr I've used simple alpha beta from the start, each time
I tried to change it to pvs/negascout it didn't work as expected because it just
generated too many nodes. Does anyone else experienced this behavior ? Is there
a logical explanation for this ?

First I thought I needed better move ordering, so I used SEE for ordering
captures and history scores for non-captures, but the efect was the same.

Then I rewrote the search function, making it as simple as possible, generate
all moves from the start, score captures based on SEE and non captures based on
history scores (making sure that the SEE scores are a few orders of magnitude
higher than history scores so winning captures get first), then sort the move
list and process moves, no hashtable or any other trick. To my disapointment the
simple AB was again generating much more less nodes than my PVS.

Here's an approximation of the simplified code I used :

Search(alpha, beta, depth, ply)
   if (depth <= 0)
      return Quiescence(...)

   [generate all moves]
   [score moves based on SEE and history]
   [sort moves based on score]

   moves_searched = 0;

   for each move m {
      make move(m)

      #if USE_AB
         score = -Search(-beta, -alpha, ...)
      #else // pvs
         if (moves_searched == 1)
             score = -Search(-beta, -alpha, ...)
         else {
             score = -Search(-alpha-1, -alpha, ...)
             if (score > alpha && score < beta)
                 score = -Search(-beta, -alpha, ...)
         }
      #endif

      unmake move(m)

      if (score > alpha){
         if (score >= beta)
             return score;
         alpha = score;
      }

      moves_searched++;
   }

   return alpha






This page took 0.05 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.