25,161
edits
Changes
no edit summary
=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 and 3-bit rank index.
<pre>
U64 qss[8][64][256][8];
U64 queenAttacks(U64 occ, enumSquare sq) {
return
qss[0][sq][ occ & 255][0] & qss[1][sq][(occ >> 8) & 255][1] & qss[2][sq][(occ >> 16) & 255][2] & qss[3][sq][(occ >> 24) & 255][3] & qss[4][sq][(occ >> 32) & 255][4] & qss[5][sq][(occ >> 40) & 255][5] & qss[6][sq][(occ >> 48) & 255][6] & qss[7][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):
occ = 0x8041A20428054A00
<pre>
[7][d4][0x80] [76] [d4][0x41] [65] [d4][0xA2] [54] [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 . 1 . . 1 . . 1 .
[3][d4][0x28] [32] [d4][0x05] [21] [d4][0x4a] [10] [d4][0x00][0]
. . . 1 . . . 1 . . . 1 . . . 1 . . . 1 . . . 1 . . . 1 . . . 1
1 . . 1 . . 1 . 1 . . 1 . . 1 . 1 . . 1 . . 1 . 1 . . 1 . . 1 .
union bbu {U64 b64; bb8 b08;};
U64 qss[8][64][256][8]; // 1M
U64 queenAttacks(U64 occ, enumSquare sq) {
bbu o; o.b64 = occ;
return
qss[0][sq][o.b08.r1][0] & qss[1][sq][o.b08.r2][1] & qss[2][sq][o.b08.r3][2] & qss[3][sq][o.b08.r4][3] & qss[4][sq][o.b08.r5][4] & qss[5][sq][o.b08.r6][5] & qss[6][sq][o.b08.r7][6] & qss[7][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 long, int): # @queenAttacks(unsigned long long, int) mov rdx, rdi
mov rcx, rdi
shr rcx, 50 and ecx, -6456 movsxd rdxrsi, esi movzx esiedi, dildl shl rsi, 611 shl rdx, 14 mov rax, rdi shr rax, 2 and movzx eax, 16320dh mov rax, qword ptr [rdx rsi + 8*rax + qss+8131072] and rax, qword ptr [rdx rsi + rsi 8*rdi + qss] mov rsirdi, rdirdx shr rsirdi, 1013 and esiedi, 163202040 and rax, qword ptr [rdx rsi + rsi rdi + qss+16262144] mov rsirdi, rdirdx shr rsirdi, 1821 and esiedi, 163202040 and rax, qword ptr [rdx rsi + rsi rdi + qss+24393216] mov rsirdi, rdirdx shr rsirdi, 2629 and esiedi, 163202040 and rax, qword ptr [rdx rsi + rsi rdi + qss+32524288] mov rsirdi, rdirdx shr rsirdi, 3437 and esiedi, 163202040 and rax, qword ptr [rdx rsi + rsi rdi + qss+40655360] shr rdirdx, 4245 and ediedx, 163202040 and rax, qword ptr [rsi + rdx + rdi + qss+48786432] and rax, qword ptr [rdx rsi + 8*rcx + qss+56917504]
ret
</pre>
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[646][64][664]; // 192 K
U64 bishopAttacks(U64 occ, enumSquare sq) {
return
</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.
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[646][2][664]; // 6K
U64 fileAttacks(U64 occ, enumSquare sq) {
occ >>= (sq & 7); // shift occupancy to A file
return
</pre>
