A Qsearch idea

[Alessandro Damiani]

I eventually tried the following modification to the code block that handles alpha updates, with no other changes to my original search posted above and it appears to have resolved the issues, although my tests have not been exhaustive.

Code: Select all

if( eval > alpha ) { 
    alpha = eval; 
    PV[ply][ply] = m;
    if( ply < maxDepth ) {
        System.arraycopy( PV[ply+1], ply+1, PV[ply], ply+1, maxDepth-ply );
        Arrays.fill( PV[ply+1], ply+1, maxDepth+1, 0 );
    }
}

What I proposed works without filling the array with zeros.

[Fguy64]

I eventually tried the following modification to the code block that handles alpha updates, with no other changes to my original search posted above and it appears to have resolved the issues, although my tests have not been exhaustive.

Code: Select all

if( eval > alpha ) { 
    alpha = eval; 
    PV[ply][ply] = m;
    if( ply < maxDepth ) {
        System.arraycopy( PV[ply+1], ply+1, PV[ply], ply+1, maxDepth-ply );
        Arrays.fill( PV[ply+1], ply+1, maxDepth+1, 0 );
    }
}

What I proposed works without filling the array with zeros.

Well, I tried it again and after a couple of tests it does indeed seem you are correct. I must have made a mistake the first time. Your solution is cleaner and more efficient. Thanks much

[hgm]

This is how I do it in Fairy-Max, with a linear array pv (one int per move), a 'stack pointer' sp that points to the first unused position of this array.

Code: Select all

int pv[10000],*sp=pv; // triangular array
int margin;

D(k,q,l,e,E,z,n)        /* recursive minimax search, k=moving side, n=depth*/
int k,q,l,e,E,z,n;      /* (q,l)=window, e=current eval. score, E=e.p. sqr.*/
{                       /* e=score, z=prev.dest; J,Z=hashkeys; return score*/
 int j,r,m,v,d,h,i,F,G,P,V,f=J,g=Z,C,s,flag,FF,*ps=sp;                    <--- remember PV start for this ply level in ps
 signed char t,p,u,x,y,X,Y,H,B;
 struct _*a=A+(J+(k+S)*E&U-1);                 /* lookup pos. in hash table*/
 *sp++=0;                                                                <--- add termination code 0 (invalid as move)
 q-=q<e;l-=l<=e;                               /* adj. window: delay bonus */
 d=a->D;m=a->V;X=a->F;Y=a->Y;                  /* resume at stored depth   */
 if(a->K-Z|z&S  |                              /* miss: other pos. or empty*/
  !(m<=q|X&8&&m>=l|X&S))                       /*   or window incompatible */
  d=Y=0;                                       /* start iter. from scratch */
 X=a->X;                                       /* start at best-move hint  */
 W(d++<n||d<3||              /*** min depth = 2   iterative deepening loop */
   z&S&&K==I&&(GetTickCount()-Ticks<tlim&d<=MaxDepth|| /* root: deepen upto time   */
   (K=X,L=Y&~S,Score=m,d=3)))                  /* time's up: go do best    */
 {x=B=X;                                       /* start scan at prev. best */
  h=Y&S;                                       /* request try noncastl. 1st*/
  P=d>2&&l+I?D(16-k,-l,1-l,-e,2*S,2*S,d-3):I;  /* search null move         */
  m=-P<l|R<5?d-2?-I:e:-P;   /*** prune if > beta  unconsidered:static eval */
  SHAMAX( if(pl[k]<=1&pl[16-k]>1)m=I-1; )      /* bare king loses          */
  N++;                                         /* node count (for timing)  */
  do{u=b[x];                                   /* scan board looking for   */
   if(u&&(u&16)==k)                            /*  own piece (inefficient!)*/
   {r=p=u&15;                                  /* p = piece type (set r>0) */
    j=od[p];                                   /* first step vector f.piece*/
    W(r=o[++j])                                /* loop over directions o[] */
    {A:                                        /* resume normal after best */
     flag=h?3:of[j];                           /* move modes (for fairies) */
     y=x;F=FF=G=S;                             /* (x,y)=move, (F,G)=castl.R*/
     do{                                       /* y traverses ray, or:     */
      H=y=h?Y^h:y+r;                           /* sneak in prev. best move */
      if(flag&1<<8)H=y=(y&15)>13?y+BW:(y&15)>=BW?y-BW:y; /* cylinder board */
      if(y&S|(y&15)>=BW)break;                 /* board edge hit           */
#ifdef MULTIPATH
      if(flag&1<<9)                            /* if multipath move        */
      {t=flag>>12;                             /* get dir. stepped twice   */
       if(b[x+t]){if(b[y-2*t]|b[y-t])break;}else 
       if(b[x+2*t]&&b[y-t])break;              /* test if empty path exists*/
      }
#endif
      m=E<16|(E^112)<16&&flag&1&y-E<2&E-y<2?I:m;      /* bad castling  */
      if(p<3&y==E)H=z&127;                     /* shift capt.sqr. H if e.p.*/
      t=b[H];
      if(flag&1+!t)                            /* mode (capt/nonc) allowed?*/
      {if(t&&(t&16)==k)break;                  /* capture own              */
       i=w[t&15]+((t&192)>>sh);                /* value of capt. piece t   */
       if(i<0)m=I,d=98;                        /* K capture                */
       if(m>=l&d>1)goto C;                     /* abort on fail high       */
       v=d-1?e:i-p;                            /*** MVV/LVA scoring if d=1**/
       if(d-!t>1)                              /*** all captures if d=2  ***/
       {v=centr[p]?b[x+257]-b[y+257]:0;        /* center positional pts.   */
        b[G]=b[H]=b[x]=0;b[y]=u|32;            /* do move, set non-virgin  */
        if(!(G&S))b[FF]=k+6,v+=50;             /* castling: put R & score  */
        v-=w[p]>0|R<EG?0:20;                   /*** freeze K in mid-game ***/
        if(p<3)                                /* pawns:                   */
        {v-=9*((x-2&M||b[x-2]-u)+              /* structure, undefended    */
               (x+2&M||b[x+2]-u)               /*        squares plus bias */
              +(w[b[x^16]&15]<0))              /*** cling to magnetic K ***/
              +(R-76>>2);                      /* end-game Pawn-push bonus */
         b[y]+=V=y+r+1&S?647-p:2*(u&y+16&32);  /* upgrade P or convert to Q*/
         if(makruk&V)b[y]|=7,V=640;
         V>>=sh;                               /* for Shatranj promo to F  */
         i+=V;                                 /* promotion / passer bonus */
        } if(z&S && GamePtr<6) v+=(rand()>>10&31)-16;
        J+=J(0);Z+=J(4)+G-S;
        SHAMAX( pl[k]-=!!t; )                  /* count pieces per side    */
        v+=e+i;V=m>q?m:q;                      /*** new eval & alpha    ****/
        if(z&S)V=m-margin>q?m-margin:q;        /* multiPV                  */
        C=d-1-(d>5&p>2&!t&!h);                 /* nw depth, reduce non-cpt.*/
        C=R<EG|P-I|d<3||t&&p-3?C:d;            /* extend 1 ply if in-check */
        do
         s=C>2|v>V?-D(16-k,-l,-V,-v,/*** futility, recursive eval. of reply */
                                     F,y&255,C):v;
        W(s>q&++C<d); v=s;                     /* no fail:re-srch unreduced*/
        if(v>V&v<l){int *p=sp;                              <----- if score v between alpha (V) and beta (l)
         sp=ps+1;                                                  put returned PV after the current move
         W(*sp++=*p++);                                      copy the returned PV
         *ps=256*x+y;                                           put current move in front of it (x = from, y = to square)
        }
        if(z&S&&K-I)                           /* move pending: check legal*/
        {if(v+I&&x==K&y==L)                    /*   if move found          */
         {Q=-e-i;O=F;LL=L;prom=0;
          if(b[y]-u&15)prom=b[y]-=PromPiece,   /* under-promotion, correct */
                       J+=PromPiece;           /*  piece & invalidate hash */
          a->D=99;a->V=0;                      /* lock game in hash as draw*/
          R-=i/FAC;                            /*** total captd material ***/
          Fifty = t|p<3?0:Fifty+1;
          sp=ps;
                     return l;}                /*   & not in check, signal */
         v=m;                                  /* (prevent fail-lows on    */
        }                                      /*   K-capt. replies)       */
        J=f;Z=g;
        SHAMAX( pl[k]+=!!t; )
        b[G]=k+6;b[FF]=b[y]=0;b[x]=u;b[H]=t;   /* undo move,G can be dummy */
       }                                       /*          if non-castling */
       if(z&S&&Post&v>V&v<l){int *p=ps;char X,Y;
        printf("%2d ",d-2);
        printf("%6d ",v);
        printf("%8d %10d",(GetTickCount()-Ticks)/10,N);
        while(*p){X=*p>>8;Y=*p++;
        printf(" %c%c%c%c",'a'+(X&15),'8'-(X>>4),'a'+(Y&15),'8'-(Y>>4&7));}
        printf("\n");fflush(stdout);
       }       if(v>m)                                 /* new best, update max,best*/
        m=v,X=x,Y=y|S&F;                       /* mark non-double with S   */
       if(h){h=0;goto A;}                      /* redo after doing old best*/
      }
      s=t;
      if(flag&15^4|u&32||                      /* no double or moved before*/
         p>2&&                                 /* no P & no lateral K move,*/
         (b[G=r<0?x&~15:BW-1|x&112]-k-6        /* no virgin R in corner G, */
         ||b[G^1]|b[G^2]|b[FF=r<0?G+3:G-2])    /* no 2 empty sq. next to R */
        )t+=flag&4;                            /* fake capt. for nonsliding*/
      else F=y;                                /* enable e.p.              */
      if(s&&flag&8)t=0,flag^=flag>>4&15;       /* hoppers go to next phase */
      if(!(flag&S))                            /* zig-zag piece?           */
       r^=flag>>12,flag^=flag>>4&15;           /* alternate vector & mode  */
     }W(!t);                                   /* if not capt. continue ray*/
   }}
   if((++x&15)>=BW)x=x+16&112;                 /* next sqr. of board, wrap */
  }W(x-B);           
C:FMAX( m=m+I|P==I?m:(X=Y=0); )                /* if stalemate, draw-score */
  if(a->D<99)                                  /* protect game history     */
   a->K=Z,a->V=m,a->D=d,a->X=X,                /* always store in hash tab */
   a->F=8*(m>q)|S*(m<l),a->Y=Y;                /* move, type (bound/exact),*/
  }                                            /*    encoded in X S,8 bits */
if(z&4*S)K=X,L=Y&~S;
 sp=ps;                                                                          <---- mark current PV as free by setting sp to start, but do not erase it yet
 return m+=m<e;                                /* delayed-loss bonus       */
}

The relevant lines are marked with arrows. At the end everything upto the first 0 in pv[] is the PV.

[Gerd Isenberg]

Wow, source code with Emoticons

[hgm]

Indeed, one cannot put source wthout code tags around it, but I did that now. Problem is that I cannot color the relevant lines then...

What I do is make the local variable ps ('PV Start') point to the start of the free space, (sp), where it will start building the PV for this level. Jus before D ('Search()') returns, it copies back sp to ps, so that ps always ends up at the same value as it had on entry. But it will also point to the start of the PV of the next level (after return), which is not erased / overwritten yet.

So immediately after the return of the recursive call to Search() I check if it was a PV ranch (score between alpha and beta), and if it is I copy the PV of the Search() that just returned (starting at sp) to the PV for this level, starting at ps+1 to leave room for one more move in front. This aways moves the copied PV to the left in the PV array. Then I put the currently searched move in front of it, and voila, the new PV of the current level, pointed to by ps, while sp, in the process of the copying, is left pointing to the end of it. (Beyond the terminating 0, where there is room to start building a PV for the next level of the next branch.)

Note that W() is a macro transating to while(), an unfortunate obfuscation used in micro-Max to save characters...

[Fguy64]

Thanks HG, by linear PV array I assume you mean a one dimensional array as opposed to a two dimensional array? I suppose there are some performance advantages with indexing in one dimension as opposed to two? I ended up doing that with my possibleMoves array, and use an array of pointers, with one element for each ply. I can't say there was any significant difference in performance though.

[hgm]

The main reason I like it is that it is more compact. In a 2D array you would have to reserve the worst-case length of the PV for every column, plus the fact that it is really tri-angular wastes half that space.

Here I store them head to tail. This is possible because you never have to alter the PV for ply N as long as the PV for ply N+1 and higher exists, except at the moment when you want to replace the PV at ply N by the best move there followed by the PV of ply N+1, immediatey after return of the level N+1 Search.

But at that time you can do a simple copy, as you will only have to squeeze out the previous PV of level N, and remember where the new PV at level N will end. So you can start a new level N+1 PV there. And as you have to copy from left to right to move something to the left, you end up at the end automatically.

Without any holes, the storage of the PV causes minimal cache loading, and that is often much more important for speed than anything else.

[Fguy64]

ok, now that I am finally getting PV from my qSearch, it's raising a few questions.

OK I am thinking that a q move that is searched only becomes part of PV if it results in an alpha update right? Well, what's not clear to me is, in the situation where Q adds nothing to the PV, how can I tell if a capture has been searched and just doesn't cause an alpha update, or if it has been rejected out of hand (i.e. without being searched) by the stand pat condition. I suppose I can stick some code in there to output info about what is being searched, but intuitively I feel I should be able to get an answer by just eyeballing the situation, for simple situations at least.

Is my question even valid? I have an illustrative examples ready to go, but I thought I'd just pose the question first.

[hgm]

I don't think the question is valid. You will never get a stand-pat cutoff at the end of the PV: the window there will be the same as in the root, and if you fail high there you would fail high in the root, and whatever move sequence you get is not a PV. At the end of the PV, QS searches all captures, and if it choses to stand pat, all captures were found to be worse than standing pat. So standing pat is an essential part of the PV, just like any other move.

[Fguy64]

I don't think the question is valid. You will never get a stand-pat cutoff at the end of the PV: the window there will be the same as in the root, and if you fail high there you would fail high in the root, and whatever move sequence you get is not a PV. At the end of the PV, QS searches all captures, and if it choses to stand pat, all captures were found to be worse than standing pat. So standing pat is an essential part of the PV, just like any other move.

ok thanks, I'll et that sink in. Let me present my example. In my test, my evaluate() function is material only.

Take WAC.003
[d]5rk1/1ppb3p/p1pb4/6q1/3P1p1r/2P1R2P/PP1BQ1P1/5RKN w - -

when I do a 6-ply search with Q turned off, I get the following PV

1.e3-g3 g5-g3 2.h1-g3 f4-g3 3.f1-f8 d6-f8

If I do a six ply search with Q turned on, I get the same PV and eval. Note that in the final position there is an obviously bad capture. It is searched but does not show up in PV because... it does not improve alpha?

now if I do a 2-ply and a 4-ply search with Q turned on from the same position I get the following PV both times, with the same eval as in the first case.

1.e3-g3 g5-g3 2.h1-g3 f4-g3

So you can see that in both cases there is a different capture, a materially neutral one, that does not show up in PV for the same reason, alpha is not improved. For the two ply search there are PV moves in Q

in these examples, it is not clear to me what role, if any, the Stand pat condition plays. as it seems I might get the same results without one.