SISSY Bitboards

Home * Board Representation * Bitboards * Sliding Piece Attacks * SISSY Bitboards

Paul Klee - Hauptweg und Nebenwege, 1929

SISSY Bitboards (Split Index Super Set Yielding),
a new and interesting approach to determine sliding piece attacks devised by Michael Sherwin, introduced and discussed in CCC in February 2020 as an improvement of his Sherwin Bitboards. SISSY bitboards apply the occupancy lookup rank by rank to intersect supersets of the attack bitboards from the same square considering blocking pieces on that particular rank only. While using eight lookups to intersect sounds expensive on the first glance, SISSY Bitboards yields up to eight ray-directions of a queen in one run with cheap instructions and high IPC potential, and thus may be an alternative for magic bitboards on architectures with slow multiplication, in particular for the queen.

Code samples and bitboard diagrams rely on Little endian file and rank mapping.

Queen Attacks

The general SISSY attack getter requires a 3-dimensional 1MByte lookup table, with pre-initialized attack bitboards indexed by 3-bit rank index, 6-bit square, 8-bit rank occupancy.

U64 qss[8][64][256]; 

U64 queenAttacks(U64 occ, enumSquare sq) {  
  return                             
    qss[0][sq][ occ        & 255] &  
    qss[1][sq][(occ >>  8) & 255] &  
    qss[2][sq][(occ >> 16) & 255] &  
    qss[3][sq][(occ >> 24) & 255] &  
    qss[4][sq][(occ >> 32) & 255] &  
    qss[5][sq][(occ >> 40) & 255] &  
    qss[6][sq][(occ >> 48) & 255] &  
    qss[7][sq][(occ >> 56) & 255] ;  
}

The following sample demonstrates how to determine queen attacks. The intersection of the eight split index addressed attack bitboards yields the desired queen attack bitboard (red squares attacked by queen, blue reset due to blocker):

Carina Jørgensen, Queen's Star

	abcdefgh
8 7 6 5 4 3 2 1	                                                                                                        ♚ ♛     ♟   ♟   ♟ ♟   ♞         ♕ ♘   ♙ ♙       ♙ ♔  ♙	8 7 6 5 4 3 2 1
	abcdefgh

7k/q5p1/1p3p1p/2n5/3Q1N2/P1P5/1P1K2P1/8 w - - 
occ = 0x8041A20428054A00

    [7][d4][0x80]     [6][d4][0x41]     [5][d4][0xA2]     [4][d4][0x04]  
   . . . 1 . . . 1*  . . . 1 . . . 0   . . . 1 . . . 0   . . . 1 . . . 1
   1 . . 1 . . 1 .   1 . . 1 . . 1 .*  0 . . 1 . . 0 .   0 . . 1 . . 1 .
   . 1 . 1 . 1 . .   . 1 . 1 . 1 . .   . 1 . 1 . 1 . .*  . 0 . 1 . 1 . .
   . . 1 1 1 . . . & . . 1 1 1 . . . & . . 1 1 1 . . . & . . 1 1 1 . . .* 
   1 1 1 Q 1 1 1 1   1 1 1 Q 1 1 1 1   1 1 1 Q 1 1 1 1   1 1 1 Q 1 1 1 1
   . . 1 1 1 . . .   . . 1 1 1 . . .   . . 1 1 1 . . .   . . 1 1 1 . . .
   . 1 . 1 . 1 . .   . 1 . 1 . 1 . .   . 1 . 1 . 1 . .   . 1 . 1 . 1 . .
   1 . . 1 . . 1 .   1 . . 1 . . 1 .   1 . . 1 . . 1 .   1 . . 1 . . 1 .

    [3][d4][0x28]     [2][d4][0x05]     [1][d4][0x4a]     [0][d4][0x00] 
   . . . 1 . . . 1   . . . 1 . . . 1   . . . 1 . . . 1   . . . 1 . . . 1
   1 . . 1 . . 1 .   1 . . 1 . . 1 .   1 . . 1 . . 1 .   1 . . 1 . . 1 .
   . 1 . 1 . 1 . .   . 1 . 1 . 1 . .   . 1 . 1 . 1 . .   . 1 . 1 . 1 . .
 & . . 1 1 1 . . . & . . 1 1 1 . . . & . . 1 1 1 . . . & . . 1 1 1 . . .
   1 1 1 Q 1 1 0 0*  1 1 1 Q 1 1 1 1   1 1 1 Q 1 1 1 1   1 1 1 Q 1 1 1 1
   . . 1 1 1 . . .   . . 1 1 1 . . .*  . . 1 1 1 . . .   . . 1 1 1 . . .
   . 1 . 1 . 1 . .   . 0 . 1 . 1 . .   . 1 . 1 . 1 . .*  . 1 . 1 . 1 . .
   1 . . 1 . . 1 .   0 . . 1 . . 1 .   0 . . 0 . . 1 .   1 . . 1 . . 1 .*
  
   . . . 1 . . . 0 
   0 . . 1 . . 0 . 
   . 0 . 1 . 1 . . 
 = . . 1 1 1 . . . 
   1 1 1 Q 1 1 0 0 
   . . 1 1 1 . . . 
   . 0 . 1 . 1 . . 
   0 . . 0 . . 1 . 

Since queens may appear on file A and H with attacks on that outer files, a reduction of the occupancy index range due to the inner six bits is not possible for queens. We will elaborate on reducing occupancy index range possibilities for bishops and rooks later. However, for queens, one may skip the outer ranks if combined with a general rank lookup.

Union Bitboard

Rather then using shift/and instructions to get the rank-wise occupancies, and similar to Sherwin Bitboards, one may use a union of a bitboard and a struct or array of eight bytes (Portability concerning endianness is an issue), to appear the code looking simpler.

typedef unsigned char U08;
struct bb8 {U08 r1; U08 r2; U08 r3; U08 r4; U08 r5; U08 r6; U08 r7; U08 r8;};
union bbu {U64 b64; bb8 b08;};

U64 qss[8][64][256]; // 1M

U64 queenAttacks(U64 occ, enumSquare sq) {
  bbu o; o.b64 = occ;
  return 
    qss[0][sq][o.b08.r1] &
    qss[1][sq][o.b08.r2] &
    qss[2][sq][o.b08.r3] &
    qss[3][sq][o.b08.r4] &
    qss[4][sq][o.b08.r5] &
    qss[5][sq][o.b08.r6] &
    qss[6][sq][o.b08.r7] &
    qss[7][sq][o.b08.r8];
}

Targeting X86-64, the generated assembly is likely similar to the above shift/and255 code .

queenAttacks(unsigned long long, int):                     # @queenAttacks(unsigned long long, int)
        mov     rdx, rdi
        mov     rcx, rdi
        shr     rcx, 56
        movsxd  rsi, esi
        movzx   edi, dl
        shl     rsi, 11
        movzx   eax, dh
        mov     rax, qword ptr [rsi + 8*rax + qss+131072]
        and     rax, qword ptr [rsi + 8*rdi + qss]
        mov     rdi, rdx
        shr     rdi, 13
        and     edi, 2040
        and     rax, qword ptr [rsi + rdi + qss+262144]
        mov     rdi, rdx
        shr     rdi, 21
        and     edi, 2040
        and     rax, qword ptr [rsi + rdi + qss+393216]
        mov     rdi, rdx
        shr     rdi, 29
        and     edi, 2040
        and     rax, qword ptr [rsi + rdi + qss+524288]
        mov     rdi, rdx
        shr     rdi, 37
        and     edi, 2040
        and     rax, qword ptr [rsi + rdi + qss+655360]
        shr     rdx, 45
        and     edx, 2040
        and     rax, qword ptr [rsi + rdx + qss+786432]
        and     rax, qword ptr [rsi + 8*rcx + qss+917504]
        ret

Bishop Attacks

Taking advantage of the inner six bits optimization for SISSY bishop attacks, but still much memory and computation compared to other techniques:

U64 bss[6][64][64]; // 192 K

U64 bishopAttacks(U64 occ, enumSquare sq) {
  return
    bss[0][sq][(occ >>  9) & 63] &  // 2nd rank
    bss[1][sq][(occ >> 17) & 63] &  
    bss[2][sq][(occ >> 25) & 63] &  
    bss[3][sq][(occ >> 33) & 63] &  
    bss[4][sq][(occ >> 41) & 63] &  
    bss[5][sq][(occ >> 49) & 63] ;  // 7th rank
}    

One may half the table size by combining occupancy indices of two consecutive ranks, since their relevant bits on diagonal and anti-diagonal are always disjoint.

Rook Attacks

If combined with the rank lookup to dense the occupy index range to 2, considering only blockers on the same file, SISSY file attack generation looks not that competitive compared to other techniques as well, see for instance Kindergarten file attacks or Hyperbola Quintessence.

U64 rss[6][2][64];  // 6K

U64 fileAttacks(U64 occ, enumSquare sq) { 
  occ >>= (sq & 7); // shift occupancy to A file
  return
    rss[0][(occ >>  8) & 1][sq] &  // 2nd rank
    rss[1][(occ >> 16) & 1][sq] &  
    rss[2][(occ >> 24) & 1][sq] &  
    rss[3][(occ >> 32) & 1][sq] &  
    rss[4][(occ >> 40) & 1][sq] &  
    rss[5][(occ >> 48) & 1][sq] ;  // 7th rank
}      

Forum Posts

• New RookAttacks() - possibly by Michael Sherwin, CCC, February 12, 2020
• Split Index Super Set Yielding (SISSY) Bitboards by Michael Sherwin, CCC, February 13, 2020

References

Up one Level