SEE - The Swap Algorithm

From Chessprogramming wiki

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

Theiterative SEE Swap-Algorithm in Bitboards creates a swap-list of best casematerial gains by traversing asquare attacked/defended by set in least valuable piece order frompawn,knight,bishop,rook,queen untilking, with alternating sides. The swap-list, an unary tree since there are no branches but just a series of captures, isnegamaxed for a final static exchange evaluation^[1]^[2].

Traversal of To-Attacks

Assuming this arbitraryBoard-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 perC++ 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 thecapture 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];}

ConsideringX-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. WithMagic Bitboards one will likely use something similar as the sliding piece subset ofSquare Attacked By. The preliminary pruning of the swap-list fill (if (max (-gain[d-1], gain[d]) < 0) break;) and other improvements were proposed byMichael Hoffmann^[3].

Traces

Two positions with traces of the swap-list during traversal and negamaxing with some arbitrarypiece 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 rxpgain[1]  =  400 ; win for black if white rook e5 is en-prise,  500-100, speculative storeno 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 nxpgain[1] =  225 ; win for black if white knight e5 is en-prise by nxn,  325- 100gain[2] =  100 ; win for white if black knight e5 is en-prise by rxn,  325- 225 -> x-rays includes queen e1gain[3] =  400 ; win for black if white rook   e5 is en-prise by bxr,  500- 100 -> x-rays includes queen h8gain[4] =  -75 ; win for white if black bishop e5 is en-prise by qxb,  325- 400gain[5] = 1075 ; win for black if white queen  e5 is en-prise by qxq, 1000- -75gain[6] =  -75 ; win for white if black queen  e5 is en-prise,        1000-1075 speculative storeno further attacks for white at depth = 6gain[4] = -max(--75,  1075) = -1075gain[3] = -max(-400, -1075) =   400gain[2] = -max(-100,   400) =  -400gain[1] = -max(-225,  -400) =   225gain[0] = -max(-100,   225) =  -225-> SEE(nxe5) == -225