Debugging SEE

[Robert Pope]

I'm trying to implement a SEE function using the pseudo-C code from https://www.chessprogramming.org/SEE_-_ ... Algorithm :

Code: Select all

int Board::see ( enumSquare toSq, enumPiece target, enumSquare frSq, enumPiece aPiece)
{
   int gain[32], d = 0;
   U64 mayXray = pawns | bishops | rooks | queen;
   U64 fromSet = 1ULL << frSq;
   U64 occ     = occupiedBB;
   U64 attadef = attacksTo( occ, toSq );
   gain[d]     = value[target];
   do {
      d++; // next depth and side
      gain[d]  = value[aPiece] - gain[d-1]; // speculative store, if defended
      if (max (-gain[d-1], gain[d]) < 0) break; // pruning does not influence the result
      attadef ^= fromSet; // reset bit in set to traverse
      occ     ^= fromSet; // reset bit in temporary occupancy (for x-Rays)
      if ( fromSet & mayXray )
         attadef |= considerXrays(occ, ..);
      fromSet  = getLeastValuablePiece (attadef, d & 1, aPiece);
   } while (fromSet);
   while (--d)
      gain[d-1]= -max (-gain[d-1], gain[d])
   return gain[0];
}

I'm running it on the following test position to get a SEE score for the BxP capture.
[d] rnb1kbnr/ppp2ppp/3p1q2/R3p3/3B4/5N2/PPPPPPPP/1NBQK2R w Kkq - 0 1
Visually, I think the score should be -1. If white plays BxP, then PxB NxP and white has lost a bishop for two pawns. Black could continue QxN but won't because of RxQ.

However, when I walk through this code, it's returning a SEE score of -2. I don't know if I've misinterpreted a variable or what, but can anyone see where I'm going wrong? Here's what I get as I step through the code:

Passed to function: target=PAWN, aPiece=BISHOP
gain[0]=value[target]=value[PAWN]=1
first loop:
d=1, gain[1]=value[aPiece] - gain[0] = value[BISHOP] - 1 = 3-1 = 2
max (-gain[d-1], gain[d]) = max(-gain[0],gain[1]) = max(-1,2) = 2 > 0 so don't break
fromSet=bitboard for pawn on d6, set aPiece=PAWN (is this where I'm going wrong?)

second loop:
d=2, gain[2]=value[aPiece] - gain[1] = value[PAWN] - 2 = 1-2 = -1
max (-gain[d-1], gain[d]) = max(-gain[1],gain[2]) = max(-2,-1) = -1 < 0 so break
But we shouldn't be breaking yet, since white still has the valid recapture NxP.

[jtwright]

At a glance I think this comes from this line:

Code: Select all

      if (max (-gain[d-1], gain[d]) < 0) break; // pruning does not influence the result

The SEE code presented in CPW has an optimization that operates on the assumption that the goal of SEE is to determine if a capture is: winning (> 0), losing (< 0), or neutral (=), so once it has proven winning or losing it can stop early.

This of course results in scores that aren't exact, like in your case. Whether or not this is a problem depends on what you're using SEE for. Try commenting out this line and trying again on the position, and I suspect you'll get -2.

[Robert Pope]

Thank you! I commented out that line and got -2 as expected. Though since I am using it just for Qsearch cutoffs right now, I will probably leave it in.