Home * Board Representation * Bitboards * SEE - The Swap Algorithm

The iterative SEE Swap-Algorithm in Bitboards creates a swap-list of best case material gains by traversing a square attacked/defended by set in least valuable piece order from pawn, knight, bishop, rook, queen until king, with alternating sides. The swap-list, an unary tree since there are no branches but just a series of captures, is negamaxed for a final static exchange evaluation ^[1]^[2].

Traversal of To-Attacks

Assuming this arbitrary Board-Definition with color as least significant piece bit and "even" pieces are the white ones, following routine returns a single populated square set and passes the least valuable piece per C++ reference to the caller. If no more piece is found for the appropriate side, it returns an empty set.

U64 Board::getLeastValuablePiece(U64 attadef, int bySide, int &piece)
{
   for (piece = nWhitePawn + bySide; piece <= nWhiteKing + bySide; piece += 2) {
      U64 subset = attadef & pieceBB[piece];
      if ( subset )
         return subset & -subset; // single bit
   }
   return 0; // empty set
}

SEE a Capture

The first two members of the gain swap-list are likely determined by the capture move we like to prove. Thus, the first element of the swap-list is the value of the target piece, while the second is only written (or used) if the target square is further defended. In this case it is the value of the capturing piece minus the value of captured piece, this is the best-case material gain from the defending point of view. However during traversal, X-ray attacks are considered while capturing with a piece, which may have indirect attacks or defends behind, which unions the set of attackers and defenders.

Pseudo C-Code

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
      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];
}

Considering X-ray attacks leaves some implementation details left, dependent on what sliding attack-getter is handy, ray attacks are sufficient, but requires some effort to determine the ray-direction. With Magic Bitboards one will likely use something similar as the sliding piece subset of Square Attacked By. The preliminary pruning of the swap-list fill (if (max (-gain[d-1], gain[d]) < 0) break;) and other improvements were proposed by Michael Hoffmann ^[3].

Traces

Two positions with traces of the swap-list during traversal and negamaxing with some arbitrary piece values.

Position 1

To demonstrate how SEE works in obvious cases, is Rook takes Pawn a winning capture?

   
   
   
   
   
   
   
   

 
    

    

     
    
   

♚ ♜
♟♟    ♟
♟
    ♟

♙     ♙
♙♙    ♙
  ♔ ♖

1k1r4/1pp4p/p7/4p3/8/P5P1/1PP4P/2K1R3 w - - ; Rxe5?

gain[0]  =  100 ; win for white if black pawn e5 is en-prise by rxp
gain[1]  =  400 ; win for black if white rook e5 is en-prise,  500-100, speculative store
no further attacks for black at depth 1
-> SEE(rxe5) == 100

Position 2

This position covers a more complicated case with X-rays. Is Knight takes pawn a winning capture?

   
   
   
   
   
   
   
   

    
   
    
    

    
  
   

♚ ♜   ♛
♟♟♞   ♟
♟    ♝
    ♟

♙  ♘  ♙
♙♙ ♖ ♗♙
  ♔ ♕

1k1r3q/1ppn3p/p4b2/4p3/8/P2N2P1/1PP1R1BP/2K1Q3 w - - ; Nxe5?

gain[0] =  100 ; win for white if black pawn   e5 is en-prise by nxp
gain[1] =  225 ; win for black if white knight e5 is en-prise by nxn,  325- 100
gain[2] =  100 ; win for white if black knight e5 is en-prise by rxn,  325- 225 -> x-rays includes queen e1
gain[3] =  400 ; win for black if white rook   e5 is en-prise by bxr,  500- 100 -> x-rays includes queen h8
gain[4] =  -75 ; win for white if black bishop e5 is en-prise by qxb,  325- 400
gain[5] = 1075 ; win for black if white queen  e5 is en-prise by qxq, 1000- -75
gain[6] =  -75 ; win for white if black queen  e5 is en-prise,        1000-1075 speculative store
no further attacks for white at depth = 6

gain[4] = -max(--75,  1075) = -1075
gain[3] = -max(-400, -1075) =   400
gain[2] = -max(-100,   400) =  -400
gain[1] = -max(-225,  -400) =   225
gain[0] = -max(-100,   225) =  -225
-> SEE(nxe5) == -225