Computer Chess Club Archives


Search

Terms

Messages

Subject: Pseudo C code for double nullmove + PVS

Author: Vincent Diepeveen

Date: 07:09:10 08/06/00

Go up one level in this thread


Implementing fail soft PVS with negamax and double
nullmove is a matter of a few minutes,
implementation with all details shouldn't take much longer as a few hours,
toying with it about a year or 5 before you decide you do it a certain
way and that's it.

Note that the initial alfa and beta in most programs is not
-infinite,infinite. In DIEP it is, but that has everyone to figure
out himself whether it saves nodes. It sure does in my draughtsprogram.
Millions of nodes. Evaluation and move ordering not that well in draughts
prog. You can take real big risks, for example you can search
with a certain nullwindow value, if that fails low you research with
-infinite,infinite. If it fails high, then skip to next ply.

Tricks like that. Many tricks to try. I only got PVS to work great.
Usually you skip plies only quick if you already search very deep.

I prefer searching efficient in positions where scores go down.

/* depth: depth left like if iteration = 9 ply then 9,8,7...0 or less
   if reduction depth.
   realply: starting with 0,1,....n for storage in tables
*/
int pvs(depth,realply,side,alfa,beta) {
   int cutoff,score,paralfa,parbeta,best,.. ;

   if( cutoff=GetHash(...) )
     return(cutoff); /* score==0 should be repetition score, you can't
       return that from hashtable */

   if( depth <= 0 )
     return(qsearch(-beta,-alfa,side);

    /* double nullmove */
   if( !incheck
    && (realply <= 1  // first 2 ply you always can nullmove,
        || movelist[realply-1]
        || movelist[realply-2] ) {
     /* so we do NOT nullmove if the previous 2 moves were nullmoves
        or if we are in check
      */
     R = 2; /* in DIEP i'm using R=3, but i do checks in qsearch */
     movelist[realply] = 0; /* 0 means we do nullmove this real move */
     score = -pvs(depth-1-R,realply+1,side^1,-beta,-beta+1);
     /* we nullmove with a nullwindow of  [beta-1,beta], as we are
        only interested in getting a cutoff
      */
     if( score >= beta ) {
       StoreHash(..);
       return(score);
     }
   }

   /* now search the moves */
   paralfa = alfa;
   parbeta = beta;
   best = -infinite;
  for( all moves ) {
    DoMove(side,move); /* don't integrate that datastructure
                       into your search actually i don't even do that
                        for nullmove. I do a DoMove(nullmove) there */
    score = -pvs(depth-1,realply+1,side^1,-parbeta,-paralfa);
    if( score > best ) {
      if( score >= beta ) {
        StoreHash(..);
        return(score);
      }
      best = score;
      if( score > alfa )
        paralfa = score;
      parbeta = paralfa + 1; /* set window after first move to alfa,alfa+1 */
    }
  }
  StoreHash(..);
  return(best);
}

On August 05, 2000 at 12:29:21, Tim Foden wrote:

>On August 05, 2000 at 11:37:01, Larry Griffiths wrote:
>
>>Which Algorithm is considered the best now-adays.
>>
>>NegaScout? MTD? PVS? Others?  I am looking to implement one of the best search
>>type algorithms in my program.  I would like to get it into the 2000 rated range
>>as this has been my lifetime goal.  Then, maybe install winboard or something so
>>it can compete against other programs to get a rating.
>>I dont like MTD as it seems to be complex.
>
>It is generally possible, and I would say advisable, to implement the search in
>small steps.  Get one version working before moving on to the more complex
>version.
>
>Thus the searches you mention above, plus plain A-B search, can be ranked in
>order of implementaion:
>1) Alpha-Beta
>2) PV-search
>3) NegaScout
>4) MTD(f)
>
>To get from 1) to 2), you need to implement null-window search for non-PV lines.
>
>To get from 2) to 3), you implement the safe forward pruning near the leaves, or
>use razoring if you have extensions.
>
>You might want to switch 2) and 3) around.
>
>To get from the 3) to 4) you add the MTD(f) driver on top of the whole thing.
>
>The thing to remember about MTD(f) (if my memory serves me well) is that I think
>it requires a fail-soft version of the underlying search.  Fail soft is:  when
>you detect a cut-off (value >= beta) you return (value).  Fail hard is you
>return (beta).
>
>At some point it would be advisable to implement the Null move heuristic.
>
>All of this is from some hazy memory, so please forgive me if I turn out to be
>talking nonsense. :o)
>
>BTW, I don't necessarily think you need the "best" search algorithm.  Just a
>good one.  I really don't think MTD(f) is a requirement to get a program that is
>2000 (or even 2500) rated.



This page took 0.19 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.