Computer Chess Club Archives


Search

Terms

Messages

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

Author: Bruce Moreland

Date: 17:12:49 03/21/00

Go up one level in this thread


On March 21, 2000 at 20:06:10, Andrei Fortuna wrote:

>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)

You want == 0 here.  This is almost certainly the cause of your problem, because
you use the wide window only on the second move you try.

bruce

>             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.01 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

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