Implementing SEE

[hgm]

if you really want tohave alaugh, here is Joker's:

Code: Select all

int SEE(int color, int move)
{
    int a, b, e, w, piece, his, mine, block, from, to, x, y, h, v, ipiece=0;
    static int seq;

    block =  (seq += 0x100) ^ 0x80000000;  /* fresh codes for used/blocked */
/*printf("SEE\n");*/
    /* start doing the given capture, and set up window */
    to   = move & 0x77;
    from = move>>8 & 0x77;
/*printf("to = %02x\n", to);*/
    if(!(move&0x8000)) 
    {   /* offensive SEE: start with given capture */
        a = -1;                   /* if losing, don't care how bad */
        ipiece = board[from];
        e = b = move>>16 & 0xFF;  /* from MMV pre-sort */
        used[ipiece-WHITE] = seq; /* mark as used      */
        w = qval[ipiece-WHITE];   /* what he is gonna capture next */
    } else
    {   /* defensive SEE: let him start, and see how bad it is */
        a = -100; e = b = ipiece = 0;
        w = qval[board[to]-WHITE];
    }

    /* generate first recapture of opponent, preppare his LVA list         */
    his = First[COLOR-color];  /* Pieces-only attacker list, in LVA order  */
    /* Prepend relevant Pawns to list. Other pieces are already sorted.    */
    from = to - color + 47;                          /* first pawn square  */
    piece = board[from];                                                   
    if((piece & (PAWNS|COLOR)) == ((PAWNS|COLOR)^color))      /* his pawn  */
        his = piece;          /* prepend to list (next-field already set)  */

    from += 2;                                      /* second pawn square  */
    piece = board[from];     
    if((piece & (PAWNS|COLOR)) != ((PAWNS|COLOR)^color))  /* not his pawn  */
    {    piece = his; his = next[his-WHITE]; }      /* take next piece     */
/*printf("from = %02x, piece = %02x\n", from, piece);*/
    /* 'piece' now holds first piece, 'mine' the second (+ rest of list)   */
retry:  do {
SDB1
            if((x=pos[piece-WHITE])>=0 &&        /* was already captured */
                used[piece-WHITE]!=seq &&        /* captured in this SEE */
                (code[piece-WHITE] & (h=capt_code[to-x]) ))
            {   /* pseudo-hit: aligned for capture */
/*printf("pseudo hit\n");*/
                if(h & C_CONTACT) break; /* contact attack, always hit   */
                v = delta_vec[to-x];
                y=to;
                while((h=board[y-=v])==DUMMY                 /* scan ray */
                       || used[h-WHITE]==seq)
                       ;     /* ignore used pieces */
                if(x==y) break;          /* ray is clear, distant hit    */
                /* ray is blocked. mark blocker so we can retry later    */
                used[h-WHITE] = block + piece;
            }
            if(!(piece = his)) return b;         /* out of moves         */
            his = next[his-WHITE];               /* remaining list       */
        } while(1);
    LVA = piece; if(w>9) return(-100);
    /* for first capture, we require legality. So test for pin on King   */
    y = x = pos[BLACK-color]; /* opponent's King */
    if(capt_code[pos[piece-WHITE]-x] & C_QUEEN)
    {
/*printf("aligned with King at %02x h= %02x & %02x\n", x, h, C_QUEEN);*/
        v = delta_vec[pos[piece-WHITE]-x];
        while(board[x+=v] == DUMMY || board[x] == piece
                                   || board[x] == ipiece);
/*printf("ray ends at %02x, code=%02x & %02x\n", x, h, code[board[x]-WHITE]);*/
        if(!(board[x] & COLOR^color) &&
           capt_code[y-x] & code[board[x]-WHITE])/* piece was pinned     */
        {   LVA = 0;                             /* try next             */
            if(!(piece = his)) return b;         /* out of moves         */
            his = next[his-WHITE];               /* remaining list       */
            goto retry;
        }
    }
        if((used[piece-WHITE] & ~0xFF) == block)   /* blocked something! */
        {
            h = used[piece-WHITE] & 0xFF;          /* unblocked piece    */
            if((h&COLOR) != color)          /* rewind LVA list for X-ray */
                 his  = h;
            else if(mine==0 || kind[mine-WHITE] > kind[h-WHITE])
                 mine = h; /* for opponent make sure rewind is backwards */
        }
SDB2("he") 
    used[piece-WHITE] = seq; /* mark as used */
    e -= w;
    w = qval[piece-WHITE];
    if(e+w<=a) return a; /* victim not valuable enough to get even, futile */
    if(a<e) a=e;         /* in any case we have score e: if we stop now.   */

    /* look if continuing with capture is better: our first LVA recapture  */
    mine = First[color];       /* pieces-only attacker list, in LVA order  */
    /* Prepend relevant Pawns to list. Other pieces are already sorted.    */
    from = to + color - 49;                          /* first pawn square  */
    piece = board[from];                                                   
    if((piece & (PAWNS|COLOR)) == (PAWNS|color))               /* my pawn  */
        mine = piece;         /* prepend to list (next-field already set)  */

    from += 2;                                      /* second pawn square  */
    piece = board[from];     
    if((piece & (PAWNS|COLOR)) != (PAWNS|color))           /* not my pawn  */
    {    piece = mine; mine = next[mine-WHITE]; }           /* next piece  */

    /* 'piece' now holds first piece, 'mine' the second piece              */

    do {/* Now Pawns are added to both lists, loop for remaining captures  */
/*printf("hoofdloop\n");*/

        /* validate capture with 'piece', or find other one from my list   */
        do {
SDB1 
            if((x=pos[piece-WHITE])>=0 &&        /* was already captured */
                used[piece-WHITE]!=seq &&        /* captured in this SEE */
                (code[piece-WHITE] & (h=capt_code[to-x]) ))
            {   /* pseudo-hit: aligned for capture */
                if(h & C_CONTACT) break; /* contact attack, always hit   */
                v = delta_vec[to-x];
                y = to;
                while((h=board[y-=v])==DUMMY                 /* scan ray */
                       || used[h-WHITE]==seq);     /* ignore used pieces */
                if(x==y) break;          /* ray is clear, distant hit    */
                /* ray is blocked. mark blocker so we can retry later    */
                used[h-WHITE] = block + piece;
            }
            if(!(piece = mine)) return a;        /* out of moves         */
            mine = next[mine-WHITE];             /* remaining list       */
        } while(1);
        if(w>9) return(b);

        if((used[piece-WHITE] & ~0xFF) == block)   /* blocked something! */
        {
            h = used[piece-WHITE] & 0xFF;          /* unblocked piece    */
            if((h&COLOR) == color)          /* rewind LVA list for X-ray */
                 mine = h;                  
            else if(his==0 || kind[his-WHITE] > kind[h-WHITE])
                 his  = h; /* for opponent make sure rewind is backwards */
        }
SDB2("I ")
        used[piece-WHITE] = seq;

        e += w;
        w = qval[piece-WHITE];
        if(e-w>=b) return b;
        if(e<b) b=e;

        /* next recapture of opponent from LVA list */
        do {
            if(!(piece = his)) return b;         /* out of moves         */
            his = next[his-WHITE];               /* remaining list       */
SDB1 
            if((x=pos[piece-WHITE])<0) continue; /* was already captured */
            if(used[piece-WHITE]==seq) continue; /* captured in this SEE */
            if(code[piece-WHITE] & (h=capt_code[to-x]))
            {   /* pseudo-hit: aligned for capture */
                if(h & C_CONTACT) break; /* contact attack, always hit   */
                v = delta_vec[to-x];
                y = to;
                while((h=board[y-=v])==DUMMY                 /* scan ray */
                       || used[h-WHITE]==seq);     /* ignore used pieces */
                if(x==y) break;          /* ray is clear, distant hit    */
                /* ray is blocked. mark blocker so we can retry later    */
                used[h-WHITE] = block + piece;
            }
        } while(1);
        if(w>9) return(a);

        if((used[piece-WHITE] & ~0xFF) == block)   /* blocked something! */
        {
            h = used[piece-WHITE] & 0xFF;          /* unblocked piece    */
/*printf("unblock %x\n", h);*/
            if((h&COLOR) != color)          /* rewind LVA list for X-ray */
                 his  = h;                  
            else if(mine==0 || kind[mine-WHITE] > kind[h-WHITE])
                 mine = h; /* for opponent make sure rewind is backwards */
        }
SDB2("he")
        used[piece-WHITE] = seq;

        e -= w;
        w = qval[piece-WHITE];
        if(e+w<=a) return a;
        if(a<e) a=e;

        /* unhook next recapture of us from LVA list (to conform to  */
        /* situation after prepending Pawns, so we can loop)         */
        if(!(piece = mine)) return a;        /* out of moves         */
        mine = next[mine-WHITE];             /* remaining list       */

    } while(1);

}

[Don]

Hi

I've been away from chess programming for a while, but I'm still stuck on SEE.
Every time I try to resolve something I seem to open a new can of worms.

I suggest you start with a recursive version, don't worry about speed, get it debugged, then build a fast iterative version. Call BOTH versions while getting the iterative version debugged to make sure they are returning the same answer.

The recursive version is easier to understand and will get you started.

I planned on using an iterative static exchange evaluation following the psuedo code:

Code: Select all

int staticexchangeevaluationw ( const int from , const int to ) 
{
    int iteration ;
    int valuelist[ 3 2 ] ;
    int next ;
    int valueattacker ;

    // iteration for White
    iteration=0;
    valuelist[iteration] = boardvalue ( to ) ;
    next = from ;
    generateattackers ( next , to ) ;
    if ( blackattackers( ) == 0 ) return boardvalue ( t o ) ;

    valueattacker = boardvalue ( from ) ;

    // forward−iterationloop : ( 1 ) fill the valuelist
    while ( true ) 
    {
        // iteration for Black
        iteration ++;
        valuelist[ iteration ]= valueattacker −valuelist [iteration− 1 ] ;
        next = nextblackattacker ( ) ;
        updatexrayattackers ( next , t o ) ;

        if ( whiteattackers( ) == 0 ) break ;

        valueattacker = board value ( next ) ;

        //iteration for White
       iteration ++;
       valuelist [iteration ]= valueattacker −valuelist [iteration − 1 ] ;
       next = nextwhiteattacker ( ) ;
       updatexrayattackers( next , t o ) ;

       if ( blackattackers( ) == 0 ) break ;

       valueattacker = board value ( next ) ;
    }

    // reverse −iteration loop : ( 2 ) evaluate the valuelist
    while ( true ) 
    {
        if( iteration == 0 ) return valuelistt [ 0 ] ;

        if ( valuelist [iteration ] > − valuelist [ iiteration −1])
        {
            valuelist [iteration −1] = −valuelist [iteration ] ;
        }

        iteration −−;
    }
}

I'm not sure about generating attackers, the problem is more trickier than it seems.
I have had a few ideas but they all seem problematic.

Any advice would be grateful, thanks.

[mcostalba]

Hi Marco,

well it is always the same when i give code chunks to the public. I get unhappy
with my code, because i am looking more intensive on it, and maybe more carefully.

Although it was on my _improve someday_ todo list, i think now is a better time.

The first step I take when I want to optimize something is to measure it. So, in case of SEE I have just done a quick measure of what we are talking about regarding the loop cycles needed to resolve a capture.

Here are the results:

Code: Select all

29% of cases side to move captures and opponent has no defendants
47% of cases opponent defends and side to move cannot recapture
16% opponent defends with one piece and side to move can recapture
8% all the other more complex cases together

So I would say that any optimization should attack especially the first 2 points and an optimization of the last point simply it is not worth.

Regarding promotion I'd guess that you don't have a clear ELO advantage if you include them in the SEE also because (queen) promotions are usually always tried by the search and never pruned.

For what I have written before optimization of point c is an optimization of a rare case, so the effect is small, but the added code complexity could be big.

[mcostalba]

Here's mine if it helps. It's basically the one of StockFish, that I also improved to handle promotions and en passant captures.

I'd think that the en passant case was already handled in the original Stokfish version....

[Desperado]

Hello Marco,

just a few minutes ago i tried your proposal given in your first post.
Unfortunatelly it will not work with my program flow.

But to be more specific, i just ask you if i really understand what
you had in mind.

original:
======

Code: Select all

...
attadef   = attackers(pos,dst,white) | attackers(pos,dst,black) | fromSet/*pawnPush*/; 
gain[d=0] = vSee[pos->sq[dst]]; 
...

change:
======

Code: Select all

...
attadef = attackers(pos,dst,sidePick);
gain[d=0]=vSee[pos->sq[dst]];

if(attadef==0) return(gain[0]);
attadef |= attackers(pos,dst,pos->ctm) | fromSet;
...

The reason why it does not work is that xray attacks are missing
for the initial move.So, if that was your intention, it is no option for my
code.I need to enter the loop because of the xrays.

easy improvement:
=============

what can be done, and maybe flagged as option is the "easy capture"
possibility. That would mean to order the initilization block a little
bit different like...

Code: Select all

 ...

 aPiece    = pos->sq[unpackSrc(mve)];
 gain[d=0] = vSee[pos->sq[dst]];

 if(vSee[aPiece]</*=*/gain[0]) return(gain[0]); //option;
 
 sidePick  = pos->ctm ^ side;
 fromSet   = onebit(unpackSrc(mve));
 occ       = OCCUPIED;
 attadef   = attackers(pos,dst,white) | attackers(pos,dst,black) | fromSet

 ...

Michael

[mcostalba]

Hello Marco,

just a few minutes ago i tried your proposal given in your first post.
Unfortunatelly it will not work with my program flow.

But to be more specific, i just ask you if i really understand what
you had in mind.

original:
======

Code: Select all

...
attadef   = attackers(pos,dst,white) | attackers(pos,dst,black) | fromSet/*pawnPush*/; 
gain[d=0] = vSee[pos->sq[dst]]; 
...

change:
======

Code: Select all

...
attadef = attackers(pos,dst,sidePick);
gain[d=0]=vSee[pos->sq[dst]];

if(attadef==0) return(gain[0]);
attadef |= attackers(pos,dst,pos->ctm) | fromSet;
...

The reason why it does not work is that xray attacks are missing
for the initial move.So, if that was your intention, it is no option for my
code.I need to enter the loop because of the xrays.

easy improvement:
=============

what can be done, and maybe flagged as option is the "easy capture"
possibility. That would mean to order the initilization block a little
bit different like...

Code: Select all

 ...

 aPiece    = pos->sq[unpackSrc(mve)];
 gain[d=0] = vSee[pos->sq[dst]];

 if(vSee[aPiece]</*=*/gain[0]) return(gain[0]); //option;
 
 sidePick  = pos->ctm ^ side;
 fromSet   = onebit(unpackSrc(mve));
 occ       = OCCUPIED;
 attadef   = attackers(pos,dst,white) | attackers(pos,dst,black) | fromSet

 ...

Michael

You have to remove the original piece from the board before calculating attacks, so something along this lines:

occ ^= fromSet;
attadef = attackers(pos,occ,dst,sidePick)


Regarding what you call "easy capture" it is called "SEE sign" in SF because it does not return the correct SEE value, but just the correct SEE sign: if capture is a gain / equal or if it is a loss. Yes can be handy when you just need to detect if a given move is a bad captures.

I'll be mostly off-line for the week, so sorry if I don't answer you anymore.

[Desperado]

Code: Select all

//* easySEE: not sure that i will use it
 if(vSee[aPiece]<gain[0]) {return(gain[0]);}

Code: Select all

int seeMove(pos_t *pos,mv_t mve)
{
 int gain[32], d ,aPiece,sidePick,dst = unpackDst(mve);
 ui64_t mayXray,fromSet,occ,attadef;
 
 if(moveIsOO(mve)) return(0);
 if(moveIsEP(mve)) return(100);

 aPiece    = pos->sq[unpackSrc(mve)];
 gain[d=0] = vSee[pos->sq[dst]];
 /*easySEE, see above*/
 sidePick  = pos->ctm ^ side;
 fromSet   = onebit(unpackSrc(mve));
 occ       = OCCUPIED;
 attadef   = attackers(pos,dst,white) | attackers(pos,dst,black) | fromSet;

 mayXray   =   occ
	         ^ (pos->bb[wnEnum] | pos->bb[bnEnum]
             |  pos->bb[wkEnum] | pos->bb[bkEnum]);

 do
 {
  d++; gain[d] = vSee[aPiece] - gain[d-1];

  //* improvement: standpat!
  if(-maxN(-gain[d-1],gain[d])>0) break;

  attadef^= fromSet;
  occ    ^= fromSet;

  if(fromSet & mayXray)
  {
   attadef |= attackSlider(pos,occ,dst,white);
   attadef |= attackSlider(pos,occ,dst,black);
  }

  for(aPiece=wpEnum+(sidePick);aPiece<=wkEnum+(sidePick);aPiece+=2)
	 if(fromSet = pos->bb[aPiece] & attadef)
		{fromSet &=- fromSet;sidePick^=side;break;}

 }while(fromSet);

 while(--d) gain[d-1] = -maxN(-gain[d-1],gain[d]); return(gain[0]);
}

ok,think the "standpat" option was what i was looking for with "point c".
Now i am happy and can enjoy the sunday with my familiy

compact + easy i think. Have a nice sunday everyone

Michael

[Desperado]

You have to remove the original piece from the board before calculating attacks, so something along this lines:

occ ^= fromSet;
attadef = attackers(pos,occ,dst,sidePick)


Regarding what you call "easy capture" it is called "SEE sign" in SF because it does not return the correct SEE value, but just the correct SEE sign: if capture is a gain / equal or if it is a loss. Yes can be handy when you just need to detect if a given move is a bad captures.

I'll be mostly off-line for the week, so sorry if I don't answer you anymore.

ok, i am aware of that, but that would require a change of my "attackers()" function
which uses OCCUPIED , not a temporary occupancy (occ) as
parameter like "attackSlider()".

Second point is, that i wonder if it is really profitable _after_ introduced the standpat condition,
which will catch that case too,and is a more general solution.

Many thx anyway.

Michael

[cms271828]

Thanks that might be a good idea.

I see HG's point about the black pawn capture, in that case Qxknight was better than Bxknight.
Perhaps that type of position doesnn't show up too much.
If you played the same engine against itself, one with SEE, one with BLIND, a 1000 times, I would use the one that wins most, surely that would verify which is most efficient.

I tried googling BLIND, it just comes up with blind fold chess, and chess for the blind.
Also I program in java, so this C code is more awkward for me to understand.

I think firstly I need to develop a way of generating the attackers, storing them, and updating them as the capture sequence is played through.

Currently I feel a bit overwhelmed with variations of SEE, I can't really apply them without the mechanisms I described above working first.

[lucasart]

Here's mine if it helps. It's basically the one of StockFish, that I also improved to handle promotions and en passant captures.

I'd think that the en passant case was already handled in the original Stokfish version....

Oh yes, indeed! I actually started with an older version of Glaurung, where the en passant case wasn't handled.

On a connected subject, I'm thinking of modifying it to detect if any checks are involved in the process. If not then the delta pruning could use the SEE directly (more agressive pruning), otherwise normal delta pruning.

What do you think ? Have you ever tried SEE delta pruning ?