25,161
edits
Changes
Created page with "'''Home * Board Representation * Bitboards * Sliding Piece Attacks * SISSY Bitboards''' File:Paul Klee, Hauptweg und Nebenwege, 1929, Öl auf Lein..."
'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * [[Sliding Piece Attacks]] * SISSY Bitboards'''
[[File:Paul Klee, Hauptweg und Nebenwege, 1929, Öl auf Leinwand, 83,7 x 67,5 cm, Museum Ludwig 1976.jpg|border|right|thumb|[[:Category:Paul Klee|Paul Klee]] - Hauptweg und Nebenwege, 1929 <ref>[[:Category:Paul Klee|Paul Klee]] - [https://commons.wikimedia.org/wiki/File:Paul_Klee,_Hauptweg_und_Nebenwege,_1929,_%C3%96l_auf_Leinwand,_83,7_x_67,5_cm,_Museum_Ludwig_1976.jpg Hauptweg und Nebenwege], 1929, [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [https://en.wikipedia.org/wiki/Museum_Ludwig Museum Ludwig]</ref>]]
'''SISSY Bitboards''' (Split Index Super Set Yielding),<br/>
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.
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.
{{MappingHint}}
=Queen Attacks=
The general SISSY attack getter requires a 3-dimensional 1MByte lookup table, with pre-initialized attack bitboards indexed by 6-bit square, 8-bit rank occupancy and 3-bit rank index.
<pre>
U64 qss[64][256][8];
U64 queenAttacks(U64 occ, enumSquare sq) {
return
qss[sq][ occ & 255][0] &
qss[sq][(occ >> 8) & 255][1] &
qss[sq][(occ >> 16) & 255][2] &
qss[sq][(occ >> 24) & 255][3] &
qss[sq][(occ >> 32) & 255][4] &
qss[sq][(occ >> 40) & 255][5] &
qss[sq][(occ >> 48) & 255][6] &
qss[sq][(occ >> 56) & 255][7] ;
}
</pre>
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):
[[FILE:Queen's_Star.jpg|border|right|thumb|267px|link=http://www.carinajorgensen.com/Chess/queensstar.php| [[:Category:Carina Jørgensen|Carina Jørgensen]], Queen's Star <ref>[http://www.carinajorgensen.com/Chess/queensstar.php Queen's Star] 2009 by [[:Category:Carina Jørgensen|Carina Jørgensen]]</ref> ]]
<fentt border="a1" style="font-size:24pt">
...[.]...{k}/{q}..[.]..{p}./.{p}.[.].[p].p/..[n..].../[...](Q)[.N]{..}/P.[P..].../.{P}.[K].[.]P./{.}..{.}..[.].</fentt>
7k/q5p1/1p3p1p/2n5/3Q1N2/P1P5/1P1K2P1/8 w - -
occ = 0x8041A20428054A00
<pre>
[d4][0x80][7] [d4][0x41][6] [d4][0xA2][5] [d4][0x04][4]
. . . 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 .
[d4][0x28][3] [d4][0x05][2] [d4][0x4a][1] [d4][0x00][0]
. . . 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 .
</pre>
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 [[First Rank Attacks#TheOuterSquares|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 [[First Rank Attacks#AttacksOnAllRanks|general rank lookup]].
=Union Bitboard=
Rather then using shift/and instructions to get the ran-wise occupancies, and similar to [[Sherwin Bitboards]], one may use a [[C#Union|union]] of a bitboard and a struct or array of eight [[Byte|bytes]] (Portability concerning [[Endianness|endianness]] is an issue), to appear the code looking simpler.
<pre>
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[64][256][8]; // 1M
U64 queenAttacks(U64 occ, enumSquare sq) {
bbu o; o.b64 = occ;
return
qss[sq][o.b08.r1][0] &
qss[sq][o.b08.r2][1] &
qss[sq][o.b08.r3][2] &
qss[sq][o.b08.r4][3] &
qss[sq][o.b08.r5][4] &
qss[sq][o.b08.r6][5] &
qss[sq][o.b08.r7][6] &
qss[sq][o.b08.r8][7];
};
</pre>
Targeting [[X86-64]], the generated [[Assembly|assembly]] is likely similar to the above shift/and255 code <ref>[https://godbolt.org/ Compiler Explorer] with x86-64 clang (experimental - Wlifetime), -O3</ref>.
<pre>
queenAttacks(unsigned long, int)
mov rcx, rdi
shr rcx, 50
and ecx, -64
movsxd rdx, esi
movzx esi, dil
shl rsi, 6
shl rdx, 14
mov rax, rdi
shr rax, 2
and eax, 16320
mov rax, qword ptr [rdx + rax + qss+8]
and rax, qword ptr [rdx + rsi + qss]
mov rsi, rdi
shr rsi, 10
and esi, 16320
and rax, qword ptr [rdx + rsi + qss+16]
mov rsi, rdi
shr rsi, 18
and esi, 16320
and rax, qword ptr [rdx + rsi + qss+24]
mov rsi, rdi
shr rsi, 26
and esi, 16320
and rax, qword ptr [rdx + rsi + qss+32]
mov rsi, rdi
shr rsi, 34
and esi, 16320
and rax, qword ptr [rdx + rsi + qss+40]
shr rdi, 42
and edi, 16320
and rax, qword ptr [rdx + rdi + qss+48]
and rax, qword ptr [rdx + rcx + qss+56]
ret
</pre>
=Bishop Attacks=
Taking advantage of the [[First Rank Attacks#TheOuterSquares|inner six bits]] optimization for SISSY bishop attacks, but still much memory and computation compared to other techniques:
<pre>
U64 bss[64][64][6]; // 192 K
U64 bishopAttacks(U64 occ, enumSquare sq) {
return
rss[sq][(occ >> 9) & 63][0] & // 2nd rank
rss[sq][(occ >> 17) & 63][1] &
rss[sq][(occ >> 25) & 63][2] &
rss[sq][(occ >> 33) & 63][3] &
rss[sq][(occ >> 41) & 63][4] &
rss[sq][(occ >> 49) & 63][5] ; // 7th rank
}
</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.
=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,
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>
U64 rss[64][2][6]; // 6K
U64 fileAttacks(U64 occ, enumSquare sq) {
occ >>= (sq & 7); // shift occupancy to A file
return
rss[sq][(occ >> 8) & 1][0] & // 2nd rank
rss[sq][(occ >> 16) & 1][1] &
rss[sq][(occ >> 24) & 1][2] &
rss[sq][(occ >> 32) & 1][3] &
rss[sq][(occ >> 40) & 1][4] &
rss[sq][(occ >> 48) & 1][5] ; // 7th rank
}
</pre>
=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=73083 Split Index Super Set Yielding (SISSY) Bitboards] by [[Michael Sherwin]], [[CCC]], February 13, 2020
=References=
<references />
'''[[Sliding Piece Attacks|Up one Level]]'''
[[Category:Paul Klee]]
[[Category:Carina Jørgensen]]
[[File:Paul Klee, Hauptweg und Nebenwege, 1929, Öl auf Leinwand, 83,7 x 67,5 cm, Museum Ludwig 1976.jpg|border|right|thumb|[[:Category:Paul Klee|Paul Klee]] - Hauptweg und Nebenwege, 1929 <ref>[[:Category:Paul Klee|Paul Klee]] - [https://commons.wikimedia.org/wiki/File:Paul_Klee,_Hauptweg_und_Nebenwege,_1929,_%C3%96l_auf_Leinwand,_83,7_x_67,5_cm,_Museum_Ludwig_1976.jpg Hauptweg und Nebenwege], 1929, [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [https://en.wikipedia.org/wiki/Museum_Ludwig Museum Ludwig]</ref>]]
'''SISSY Bitboards''' (Split Index Super Set Yielding),<br/>
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.
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.
{{MappingHint}}
=Queen Attacks=
The general SISSY attack getter requires a 3-dimensional 1MByte lookup table, with pre-initialized attack bitboards indexed by 6-bit square, 8-bit rank occupancy and 3-bit rank index.
<pre>
U64 qss[64][256][8];
U64 queenAttacks(U64 occ, enumSquare sq) {
return
qss[sq][ occ & 255][0] &
qss[sq][(occ >> 8) & 255][1] &
qss[sq][(occ >> 16) & 255][2] &
qss[sq][(occ >> 24) & 255][3] &
qss[sq][(occ >> 32) & 255][4] &
qss[sq][(occ >> 40) & 255][5] &
qss[sq][(occ >> 48) & 255][6] &
qss[sq][(occ >> 56) & 255][7] ;
}
</pre>
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):
[[FILE:Queen's_Star.jpg|border|right|thumb|267px|link=http://www.carinajorgensen.com/Chess/queensstar.php| [[:Category:Carina Jørgensen|Carina Jørgensen]], Queen's Star <ref>[http://www.carinajorgensen.com/Chess/queensstar.php Queen's Star] 2009 by [[:Category:Carina Jørgensen|Carina Jørgensen]]</ref> ]]
<fentt border="a1" style="font-size:24pt">
...[.]...{k}/{q}..[.]..{p}./.{p}.[.].[p].p/..[n..].../[...](Q)[.N]{..}/P.[P..].../.{P}.[K].[.]P./{.}..{.}..[.].</fentt>
7k/q5p1/1p3p1p/2n5/3Q1N2/P1P5/1P1K2P1/8 w - -
occ = 0x8041A20428054A00
<pre>
[d4][0x80][7] [d4][0x41][6] [d4][0xA2][5] [d4][0x04][4]
. . . 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 .
[d4][0x28][3] [d4][0x05][2] [d4][0x4a][1] [d4][0x00][0]
. . . 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 .
</pre>
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 [[First Rank Attacks#TheOuterSquares|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 [[First Rank Attacks#AttacksOnAllRanks|general rank lookup]].
=Union Bitboard=
Rather then using shift/and instructions to get the ran-wise occupancies, and similar to [[Sherwin Bitboards]], one may use a [[C#Union|union]] of a bitboard and a struct or array of eight [[Byte|bytes]] (Portability concerning [[Endianness|endianness]] is an issue), to appear the code looking simpler.
<pre>
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[64][256][8]; // 1M
U64 queenAttacks(U64 occ, enumSquare sq) {
bbu o; o.b64 = occ;
return
qss[sq][o.b08.r1][0] &
qss[sq][o.b08.r2][1] &
qss[sq][o.b08.r3][2] &
qss[sq][o.b08.r4][3] &
qss[sq][o.b08.r5][4] &
qss[sq][o.b08.r6][5] &
qss[sq][o.b08.r7][6] &
qss[sq][o.b08.r8][7];
};
</pre>
Targeting [[X86-64]], the generated [[Assembly|assembly]] is likely similar to the above shift/and255 code <ref>[https://godbolt.org/ Compiler Explorer] with x86-64 clang (experimental - Wlifetime), -O3</ref>.
<pre>
queenAttacks(unsigned long, int)
mov rcx, rdi
shr rcx, 50
and ecx, -64
movsxd rdx, esi
movzx esi, dil
shl rsi, 6
shl rdx, 14
mov rax, rdi
shr rax, 2
and eax, 16320
mov rax, qword ptr [rdx + rax + qss+8]
and rax, qword ptr [rdx + rsi + qss]
mov rsi, rdi
shr rsi, 10
and esi, 16320
and rax, qword ptr [rdx + rsi + qss+16]
mov rsi, rdi
shr rsi, 18
and esi, 16320
and rax, qword ptr [rdx + rsi + qss+24]
mov rsi, rdi
shr rsi, 26
and esi, 16320
and rax, qword ptr [rdx + rsi + qss+32]
mov rsi, rdi
shr rsi, 34
and esi, 16320
and rax, qword ptr [rdx + rsi + qss+40]
shr rdi, 42
and edi, 16320
and rax, qword ptr [rdx + rdi + qss+48]
and rax, qword ptr [rdx + rcx + qss+56]
ret
</pre>
=Bishop Attacks=
Taking advantage of the [[First Rank Attacks#TheOuterSquares|inner six bits]] optimization for SISSY bishop attacks, but still much memory and computation compared to other techniques:
<pre>
U64 bss[64][64][6]; // 192 K
U64 bishopAttacks(U64 occ, enumSquare sq) {
return
rss[sq][(occ >> 9) & 63][0] & // 2nd rank
rss[sq][(occ >> 17) & 63][1] &
rss[sq][(occ >> 25) & 63][2] &
rss[sq][(occ >> 33) & 63][3] &
rss[sq][(occ >> 41) & 63][4] &
rss[sq][(occ >> 49) & 63][5] ; // 7th rank
}
</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.
=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,
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>
U64 rss[64][2][6]; // 6K
U64 fileAttacks(U64 occ, enumSquare sq) {
occ >>= (sq & 7); // shift occupancy to A file
return
rss[sq][(occ >> 8) & 1][0] & // 2nd rank
rss[sq][(occ >> 16) & 1][1] &
rss[sq][(occ >> 24) & 1][2] &
rss[sq][(occ >> 32) & 1][3] &
rss[sq][(occ >> 40) & 1][4] &
rss[sq][(occ >> 48) & 1][5] ; // 7th rank
}
</pre>
=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=73083 Split Index Super Set Yielding (SISSY) Bitboards] by [[Michael Sherwin]], [[CCC]], February 13, 2020
=References=
<references />
'''[[Sliding Piece Attacks|Up one Level]]'''
[[Category:Paul Klee]]
[[Category:Carina Jørgensen]]
