Difference between revisions of "SISSY Bitboards"

From Chessprogramming wiki
Jump to: navigation, search
 
(2 intermediate revisions by the same user not shown)
Line 6: Line 6:
 
a new and interesting approach to determine sliding piece attacks devised by [[Michael Sherwin]], introduced and discussed in [[CCC]] in February 2020 <ref>[http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73083 Split Index Super Set Yielding (SISSY) Bitboards] by [[Michael Sherwin]], [[CCC]], February 13, 2020</ref> as an improvement of his [[Sherwin Bitboards]].
 
a new and interesting approach to determine sliding piece attacks devised by [[Michael Sherwin]], introduced and discussed in [[CCC]] in February 2020 <ref>[http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73083 Split Index Super Set Yielding (SISSY) Bitboards] by [[Michael Sherwin]], [[CCC]], February 13, 2020</ref> as an improvement of his [[Sherwin Bitboards]].
 
SISSY bitboards apply the occupancy lookup [[Ranks|rank]] by rank to [[General Setwise Operations#Intersection|intersect]] supersets of the attack bitboards from the same square considering blocking pieces on that particular rank only.
 
SISSY bitboards apply the occupancy lookup [[Ranks|rank]] by rank to [[General Setwise Operations#Intersection|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 [[Direction#RayDirections|ray-directions]] of a queen in one run with cheap instructions and high [https://en.wikipedia.org/wiki/Instructions_per_cycle IPC] potential, and thus may be an alternative for [[Magic Bitboards|magic bitboards]] on architectures with slow multiplication, in particular for the queen.
+
While using eight lookups to intersect sounds expensive on the first glance, SISSY Bitboards yields up to eight [[Direction#RayDirections|ray-directions]] of a queen in one run with cheap instructions and high [https://en.wikipedia.org/wiki/Instructions_per_cycle IPC] potential, and thus may be an alternative for [[Magic Bitboards|magic bitboards]] on architectures with slow 64-bit multiplication, in particular for the queen.
 
{{MappingHint}}
 
{{MappingHint}}
  
Line 138: Line 138:
 
}     
 
}     
 
</pre>
 
</pre>
One may half the table size by combining occupancy indices of two consecutive ranks, since their relevant bits on [[Diagonals|diagonal]] and [[Anti-Diagonals|anti-diagonal]] are always disjoint.
+
There is a more recent attempt to half the number of lookups by [[Martin Sedlak]] but using much larger tables <ref>[http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73083&start=55 Re: Split Index Super Set Yielding (SISSY) Bitboards] by [[Martin Sedlak]], [[CCC]], February 14, 2021</ref>.
  
 
=Rook Attacks=
 
=Rook Attacks=
If combined with the [[First Rank Attacks#AttacksOnAllRanks|rank lookup]] to dense the occupy index range to 2, considering only blockers on the same file,
+
If combined with the [[First Rank Attacks#AttacksOnAllRanks|rank lookup]] for SISSY fileAttacks only, one can 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 Bitboards#File-Attacks|Kindergarten file attacks]] or [[Hyperbola Quintessence]].
 
 
<pre>
 
<pre>
U64 rss[6][2][64];  // 6K
+
U64 rss[6][64][2];  // 6K
  
 
U64 fileAttacks(U64 occ, enumSquare sq) {  
 
U64 fileAttacks(U64 occ, enumSquare sq) {  
 
   occ >>= (sq & 7); // shift occupancy to A file
 
   occ >>= (sq & 7); // shift occupancy to A file
 
   return
 
   return
     rss[0][(occ >>  8) & 1][sq] &  // 2nd rank
+
     rss[0][sq][(occ >>  8) & 1] &  // 2nd rank
     rss[1][(occ >> 16) & 1][sq] &   
+
     rss[1][sq][(occ >> 16) & 1] &   
     rss[2][(occ >> 24) & 1][sq] &   
+
     rss[2][sq][(occ >> 24) & 1] &   
     rss[3][(occ >> 32) & 1][sq] &   
+
     rss[3][sq][(occ >> 32) & 1] &   
     rss[4][(occ >> 40) & 1][sq] &   
+
     rss[4][sq][(occ >> 40) & 1] &   
     rss[5][(occ >> 48) & 1][sq] ;  // 7th rank
+
     rss[5][sq][(occ >> 48) & 1] ;  // 7th rank
}    
+
}  
 
</pre>
 
</pre>
 +
One may try some more index trickery for instance considering 3 ranks each, for an upper and lower half,
 +
<pre>
 +
U64 rss[2][64][8];  // 8K
  
 +
U64 fileAttacks(U64 occ, enumSquare sq) {
 +
  occ >>= (sq & 7); // shift occupancy to A file
 +
  return
 +
    rss[0][sq][((occ>>22)&4) | ((occ>>15)&2) | ((occ>> 8)&1)] &  // rank 4,3,2
 +
    rss[1][sq][((occ>>46)&4) | ((occ>>39)&2) | ((occ>>32)&1)];  // rank 7,6,5
 +
}
 +
</pre>
 +
One step further, to combine the occupancy to one six-bit index is already quite similar to [[Kindergarten Bitboards#FileAttacks|Kindergarten File Attacks]], in particular [[Zach Wegner|Zach Wegner's]] [[Kindergarten Bitboards#32-bit Versions|32-bit Version]] <ref>[http://www.open-aurec.com/wbforum/viewtopic.php?topic_view=threads&p=26851&t=4523 Zach's tricky 32-bit approach] by [[Zach Wegner]], [[Computer Chess Forums|Winboard Forum]], August 22, 2006</ref>
 
=Forum Posts=
 
=Forum Posts=
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73063 New RookAttacks() - possibly] by [[Michael Sherwin]], [[CCC]], February 12, 2020
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73063 New RookAttacks() - possibly] by [[Michael Sherwin]], [[CCC]], February 12, 2020
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73083 Split Index Super Set Yielding (SISSY) Bitboards] by [[Michael Sherwin]], [[CCC]], February 13, 2020
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73083 Split Index Super Set Yielding (SISSY) Bitboards] by [[Michael Sherwin]], [[CCC]], February 13, 2020
 +
: [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73083&start=46 Re: Split Index Super Set Yielding (SISSY) Bitboards] by [[Michael Sherwin]], [[CCC]], February 13, 2021
 +
: [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73083&start=55 Re: Split Index Super Set Yielding (SISSY) Bitboards] by [[Martin Sedlak]], [[CCC]], February 14, 2021
  
 
=References=  
 
=References=  

Latest revision as of 08:57, 14 February 2021

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

Paul Klee - Hauptweg und Nebenwege, 1929 [1]

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 [2] 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 64-bit multiplication, in particular for the queen.

Cpwmappinghint.JPG
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 [3]
 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 [4].

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
}    

There is a more recent attempt to half the number of lookups by Martin Sedlak but using much larger tables [5].

Rook Attacks

If combined with the rank lookup for SISSY fileAttacks only, one can dense the occupy index range to 2, considering only blockers on the same file.

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

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

One may try some more index trickery for instance considering 3 ranks each, for an upper and lower half,

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

U64 fileAttacks(U64 occ, enumSquare sq) { 
  occ >>= (sq & 7); // shift occupancy to A file
  return
    rss[0][sq][((occ>>22)&4) | ((occ>>15)&2) | ((occ>> 8)&1)] &  // rank 4,3,2
    rss[1][sq][((occ>>46)&4) | ((occ>>39)&2) | ((occ>>32)&1)];   // rank 7,6,5
}

One step further, to combine the occupancy to one six-bit index is already quite similar to Kindergarten File Attacks, in particular Zach Wegner's 32-bit Version [6]

Forum Posts

Re: Split Index Super Set Yielding (SISSY) Bitboards by Michael Sherwin, CCC, February 13, 2021
Re: Split Index Super Set Yielding (SISSY) Bitboards by Martin Sedlak, CCC, February 14, 2021

References

Up one Level