25,161
edits
Changes
Created page with "'''Home * Board Representation * Bitboards * Sliding Piece Attacks * Kindergarten Bitboards''' FILE:Group_of_Masks.jpg|border|right|thumb|232px|li..."
'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * [[Sliding Piece Attacks]] * Kindergarten Bitboards'''
[[FILE:Group_of_Masks.jpg|border|right|thumb|232px|link=http://www.imj.org.il/imagine/collections/item.asp?itemNum=194576| [[Arts#Klee|Paul Klee]] - Group of Masks, 1939 <ref>[http://www.imj.org.il/imagine/collections/viewDataE5.asp?case=Modern%20Art IMAGINE - The Israel Museum's searchable collections database]</ref> ]]
'''Kindergarten''' bitboards <ref>[http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=5958 Magic Bitboards Explained!] by [[Michael Sherwin]] and reply by [[Gerd Isenberg]] to call it Kindergarten Bitboards, [[Computer Chess Forums|Winboard Forum]], December 4, [[Timeline#2006|2006]]</ref> <br/>
was a kind of interactive forum development <ref>[http://www.open-aurec.com/wbforum/viewtopic.php?t=4523 Compact Bitboard Attacks] by [[Tom Likens]], [[Computer Chess Forums|Winboard Forum]], March 14, [[Timeline#2006|2006]]</ref> with a lot of meanders <ref>[https://www.stmintz.com/ccc/index.php?id=489834 rotated bitboards obsolete?] by [[Gerd Isenberg]], [[CCC]], February 26, [[Timeline#2006|2006]]</ref> . There were two issues involved - first to calculate the [[Occupancy of any Line|occupancy of any line]] from the [[Occupancy|occupied bitboard]] <ref>[https://www.stmintz.com/ccc/index.php?id=491079 Re: Some thoughts on Dann Corbit's rotated alternative] by [[Steffan Westcott]], [[CCC]], March 03, 2006</ref> - and second, compact and dense lookup tables. As a quintessence [[Gerd Isenberg]] came up with this nomination. It relies on fast 64-bit multiplication, but is otherwise quite resource friendly and a compromise between calculation and table-size.
=Ranks and Diagonals=
[[Ranks]] and [[Diagonals|diagonals]] - that is their appropriate [[On an empty Board#LineAttacks|line-mask]] by square-index - are first intersected by the occupancy of the whole board. Doesn't matter whether the slider itself is cleared or not - it is redundant anyway, considered by the pre-calculated lookup-table.
Since there is only up to one bit per file, the [[General Setwise Operations#Multiplication|north-fill multiplication]] by the A-file maps the diagonal to the 8th rank. Or - since we only need the [[First Rank Attacks#TheOuterSquares|inner six bits]], we combine the required shift left one by multiplying with the B-file. Shifting right the product by 58 (64-6) leaves the six-bit occupancy-index in the 0..63 range. For instance the diagonal-attacks of a bishop on d4. 'A'-'H' represent the masked occupied bits along this diagonal, which are either zero or one.
{{MappingHint}}
We need 'B'-'G' as six bit number:
<pre>
masked line * B-File = B-G upper six occupancy 6 bit
. . . . . . . H . 1 . . . . . . . A[B C . E F G] . . . . . . . .
. . . . . . G . . 1 . . . . . . . A B C . E F G . . . . . . . .
. . . . . F . . . 1 . . . . . . . A B C . E F . . . . . . . . .
. . . . E . . . . 1 . . . . . . . A B C . E . . >> . . . . . . . .
. . . . . . . . * . 1 . . . . . . = . A B C . . . . 58 . . . . . . . .
. . C . . . . . . 1 . . . . . . . A B C . . . . . . . . . . . .
. B . . . . . . . 1 . . . . . . . A B . . . . . . . . . . . . .
A . . . . . . . . 1 . . . . . . . A . . . . . . [B C . E F G]. .
</pre>
The pre-calculated lookup-table contains the [[First Rank Attacks|attacks of the first rank]] - but eight copies in each [[Ranks|rank]] or [[Byte|byte]]. It is indexed by the six bit occupied-state ('B'-'G') and the [[Files|file]] of the slider's [[Squares|square]]. It needs to be intersected with the same line-mask as formerly the occupancy - to map the first rank attack bits to the appropriate line - that's all. Appropriate pre-calculated attack bits are represented by 'a'-'h':
<pre>
8 copies of rank the attack set
attacks & l-mask -> of this line
a b c . e f g h . . . . . . . h
a b c . e f g h . . . . . . g .
a b c . e f g h . . . . . f . .
a b c . e f g h . . . . e . . .
a b c . e f g h . . . . . . . .
a b c . e f g h . . c . . . . .
a b c . e f g h . b . . . . . .
a b c . e f g h a . . . . . . .
</pre>
Since all [[Ranks|ranks]], [[Diagonals|diagonals]] and [[Anti-Diagonals|anti-diagonals]] are properly file-aligned, it works perfectly with some redundant occupied bits for shorter diagonals as well, like here the outer bit 'B':
<pre>
masked line * B-File = B-G upper six occupancy 6 bit
. . . . . . . . . 1 . . . . . . H .[B C . E F G] . . . . . . . .
. . . . . . . H . 1 . . . . . . . . B C . E F G . . . . . . . .
. . . . . . G . . 1 . . . . . . . . B C . E F G . . . . . . . .
. . . . . F . . . 1 . . . . . . . . B C . E F . >> . . . . . . . .
. . . . E . . . * . 1 . . . . . . = . . B C . E . . 58 . . . . . . . .
. . . . . . . . . 1 . . . . . . . . B C . . . . . . . . . . . .
. . C . . . . . . 1 . . . . . . . . B C . . . . . . . . . . . .
. B . . . . . . . 1 . . . . . . . . B . . . . . [B C . E F G]. .
</pre>
Appropriate pre-calculated attack bits are represented by 'b'-'h' here:
<pre>
8 copies of rank the attack set or the attack set
attacks & l-mask -> of this line -> of the shorter diagonal
a b c . e f g h . . . . . . . h . . . . . . . .
a b c . e f g h . . . . . . g . . . . . . . . h
a b c . e f g h . . . . . f . . . . . . . . g .
a b c . e f g h . . . . e . . . . . . . . f . .
a b c . e f g h . . . . . . . . . . . . e . . .
a b c . e f g h . . c . . . . . . . . . . . . .
a b c . e f g h . b . . . . . . . . c . . . . .
a b c . e f g h a . . . . . . . . b . . . . . .
</pre>
Wasn't that simple? That is why it is called '''kindergarten''' bitboards!
The trick is to share one 4KByte table by three line-directions by re-using the mask for a final intersection. Of course one may use the calculated occupied state to index [[Rotated Bitboards|rotated bitboards]] like tables of 32KByte each. But dividing the table size by 3*8 on the cost of that additional 'and' (and keeping the mask inside a register) is tempting. Of course - like always with computation versus memory issues - it depends on the cache- and memory using and footprint inside a particular chess program and the hardware architecture, which solution is preferable. So far L1 [https://en.wikipedia.org/wiki/Cache Cache] is a rare resource, [https://en.wikipedia.org/wiki/Translation_Lookaside_Buffer Translation Lookaside Buffer] als well.
Like other none rotated approaches, namely [[Magic Bitboards|magic bitboards]] or [[Hyperbola Quintessence#ArrayOfStructs|hyperbola quintessence]], the nice thing is that one can [[Hiding the Implementation|hide the implementation details]] behind a stateless interface. In [[C]] /[[Cpp|C++]] one may use [https://en.wikipedia.org/wiki/Header_file header files] with exclusive, conditional compiled inlined routines, as combinations and variations of the mentioned approaches.
The three routines only differ by the line-mask applied. As pointed out by [[Aleks Peshkov]], it is smarter to index by file, occupancy, since fillUpAttacks[sq&7] may be shared by two (bishop) or three (queen) line-attack getters.
<pre>
U64 fillUpAttacks[8][64]; // 4 KByte
U64 diagonalAttacks(U64 occ, enumSquare sq) {
const U64 bFile = C64(0x0202020202020202);
occ = (diagonalMaskEx[sq] & occ) * bFile >> 58;
return diagonalMaskEx[sq] & fillUpAttacks[sq&7][occ];
}
U64 antiDiagAttacks(U64 occ, enumSquare sq) {
const U64 bFile = C64(0x0202020202020202);
occ = (antidiagMaskEx[sq] & occ) * bFile >> 58;
return antidiagMaskEx[sq] & fillUpAttacks[sq&7][occ];
}
U64 rankAttacks(U64 occ, enumSquare sq) {
const U64 bFile = C64(0x0202020202020202);
occ = (rankMaskEx[sq] & occ) * bFile >> 58;
return rankMaskEx[sq] & fillUpAttacks[sq&7][occ];
}
</pre>
One may use similar structs for the line-masks than the [[Hyperbola Quintessence#ArrayOfStructs|hyperbola quintessence]].
<span id="FileAttacks"></span>
=File-Attacks=
[[Files]] need tad more work. Shift the board left (arithmetical right!) to the A-file to mask it. To get the inner six bits, a [[Flipping Mirroring and Rotating#FiletoaRank|flip-multiplication]] by the c2-h7 diagonal is applied with further shift right 58. The lookup-table contains the A-file attacks, which are shifted "back" to the original file.
<pre>
U64 aFileAttacks [8][64]; // 4 KByte
U64 fileAttacks(U64 occ, enumSquare sq) {
const U64 aFile = C64(0x0101010101010101);
const U64 diac2h7 = C64(0x0080402010080400);
occ = aFile & (occ >> (sq&7));
occ = (diac2h7 * occ ) >> 58;
return aFileAttacks[sq>>3][occ] << (sq&7);
}
</pre>
This is how it works:
<pre>
masked A-file * c2-h7 Diagonal = occupancy
H . . . . . . . . . . . . . . . . .[G F E D C B] . . . . . . . .
G . . . . . . . . . . . . . . 1 . . F E D C B A . . . . . . . .
F . . . . . . . . . . . . . 1 . . . E D C B A . . . . . . . . .
E . . . . . . . . . . . . 1 . . . . D C B A . . >> . . . . . . . .
D . . . . . . . * . . . . 1 . . . = . . C B A . . . 58 . . . . . . . .
C . . . . . . . . . . 1 . . . . . . B A . . . . . . . . . . . .
B . . . . . . . . . 1 . . . . . . . A . . . . . . . . . . . . .
A . . . . . . . . . . . . . . . . . . . . . . . [G F E D C B]. .
</pre>
Note that the six inner bit occupancy is reversed - considered in the pre-calculated aFileAttacks [[Array|array]]. This reversed lookup was justified to share first rank-attacks by all directions - with a dense lookup of 512 Byte. But the 4KByte tables outperform the additional multiplications and shift of the dense version - and one may alternatively multiply with the flipped diagonal, the c7-h2 anti-diagonal:
<pre>
masked A-file * c7-h2 AntiDiag = occupancy
H . . . . . . . . . . . . . . . . .[B C D E F G] . . . . . . . .
G . . . . . . . . . 1 . . . . . . . A B C D E F . . . . . . . .
F . . . . . . . . . . 1 . . . . . . . A B C D E . . . . . . . .
E . . . . . . . . . . . 1 . . . . . . . A B C D >> . . . . . . . .
D . . . . . . . * . . . . . 1 . . = . . . . . A B C 58 . . . . . . . .
C . . . . . . . . . . . . . 1 . . . . . . . A B . . . . . . . .
B . . . . . . . . . . . . . . 1 . . . . . . . A . . . . . . . .
A . . . . . . . . . . . . . . . . . . . . . . . [B C D E F G]. .
</pre>
=Shared Rank Lookup=
As often, [[Space-Time Tradeoff|computation versus memory size]]. One may share a 512Byte Lookup of the first rank by all lines with some trailing computation. Multiplying with the A-file (fill north) for ranks and diagonals, and multiplying with the diagonal for the file. Likely the additional multiplication don't pays off.
<pre>
const BYTE firstRankAttacks[8][64];
U64 fileAttacks(U64 occ, enumSquare sq) {
const U64 aFile = C64(0x0101010101010101);
const U64 hFile = C64(0x8080808080808080);
const U64 diaa1h8 = C64(0x8040201008040201);
const U64 diac2h7 = C64(0x0080402010080400);
unsigned int f = sq & 7;
occ = aFile & (occ >> f);
occ = ( diac2h7 * occ ) >> 58;
occ = diaa1h8 * firstRankAttacks[(sq^56)>>3][occ];
return ( hFile & occ ) >> (f^7);
}
U64 diagonalAttacks(U64 occ, enumSquare sq) {
const U64 aFile = C64(0x0101010101010101);
const U64 bFile = C64(0x0202020202020202);
unsigned int f = sq & 7;
occ = diagonalMaskEx[sq] & occ;
occ = (bFile * occ ) >> 58;
occ = aFile * firstRankAttacks[f][occ];
return diagonalMaskEx[sq] & occ;
}
</pre>
=32-bit Versions=
One other variation of the memory versus computation theme was encouraged by 32-bit mode. 64-bit multiplication is quite expensive in 32-bit mode - a call using three imuls. Thus, it is more efficient to use shift-or plus 32-bit multiplication, which might in fact be used in 64-bit mode as well. [[Piotr Cichy]] proposed a multiplication less [[Parallel Prefix Algorithms|parallel prefix shift]] approach similar to [[Occupancy of any Line]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=29296 Kindergarten bitboards without multiplying] by [[Piotr Cichy]], [[CCC]], August 07, 2009</ref> , which is a good alternative for processors with slow multiplication.
An efficient and tricky file-approach was introduced by [[Zach Wegner]] <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>, using a 32KByte, [[Rotated Bitboards|rotated like]] lookup-table:
It is quite strange, yes, but it is an out of order mapping. There are only 5 bits because each bit in the factor maps more than one bit. The trick here is the odd shift 29, so that the multiply does not overflow individual bits. I have since found that 25 and 27 will work with the same magic:
<pre>
occ
. . . . . . . .
a . . . . . . .
b . . . . . . . occ | occ >> 29 * 0x01041041 with the index bracketed
c . . . . . . . ...\ ...\ ...\
d . . . . . . . d . . . . . . . 1 . . . . . . . d a[f c e b d a]
e . . . . . . . e . . a . . . . . . 1 . . . . . e b . a f c e b
f . . . . . . . f . . b . . . . . . . . 1 . . . f c . b . . f c
. . . . . . . . . . . c . . . . 1 . . . . . 1 . . . . c . . . .
</pre>
The interesting thing is that this works for any masked file. In fact if it was shifted to the a-file, you could get away with the 3-bit factor 0x00041040 (but using a shift of 23).
<pre>
U64 arrFileAttacks[64][64]; // [sq][occ64] 32KByte
U64 fileAttacks(U64 occ, enumSquare sq) {
occ &= fileMask[sq];
U32 fold = (U32)occ | (U32)(occ >> 29);
U32 occ64 = fold * 0x01041041 >> 26;
return arrFileAttacks[sq][occ64];
}
</pre>
Ranks and diagonals are trivial, this version favors rotated like memory size for less computation and same operations than file-attacks. One may therefor generalize the routine by a line-direction parameter:
<pre>
U64 arrDiagonalAttacks[64][64]; // [sq][occ64] 32KByte
U64 diagonalAttacks(U64 occ, enumSquare sq) {
occ &= diagonalMaskEx[sq];
U32 fold = (U32)occ | (U32)(occ >> 32);
U32 occ64 = fold * 0x02020202 >> 26;
return arrDiagonalAttacks[sq][occ64];
}
</pre>
A similar approach was proposed by [[Andrew Fan]] in 2009, been active in his [[FireFly|own engine]] for a few years (2006 earliest recorded file time) <ref>[http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=50616&p=192200 32-bit Magic experiments] by [[Andrew Fan]], [[Computer Chess Forums|Winboard Forum]], December 03, 2009</ref>.
<span id="MagicCompression"></span>
=Magic Compression=
So far Kindergarten bitboards performs a [[Hash Table#PerfectHashing|perfect hashing]] of the up to six relevant and scattered occupied bits of any line to a six-bit index - which is a bijective mapping of 64 different occupancies per line to 64 indices for the precalculated attack sets.
If we have a closer look to the attack sets, say of a rook on the a-file, we enumerate far less disjoint sets. A rook on a1 (a8) has seven different attack-sets on that file, depending on the occupancy of a2-a7. On a2 (a7) there is even one attack set less, on a3 (a6) 2 times 5 and on a4 (a5) 3 times 4 attack-sets. Thus, there are {7, 6, 10, 12, 12, 10, 6, 7} disjoint attack-sets per square on line, or 70 in total over all eight squares.
While kindergarten bitboards apply a minimal perfect mapping of scattered bits to a six-bit index, the mapping of the attack-sets is surjective, since each of the 64 occupancies maps only up to 12 distinct sets. Of course that is because occupancies "behind" the first blocker are redundant and map the same attack.
[[Grant Osborne]] came up with the idea, derived from [[Magic Bitboards|magic bitboards]] - to use different "magic" factors per square (rank), where multiplication may produce carries and enough so called constructive collisions to gain only five or even four bit indices and therefor denser tables. Since different squares may have different table sizes (16 or 32 entries), a Java-like [[Array|array]] is used for the attacks, in C implemented as array of pointers to the arbitrary sized attack tables. The variable right shift by either 60 or 59 is encoded inside the otherwise redundant upper six bits of the magic factor, as mentioned in [[Magic Bitboards#IncorporatingtheShift|incorporating the shift]] of magic bitboards.
Grant's proposal, so far with {5,4,4,5,5,4,4,5} bit ranges for the lookups per square for vertical rook attacks, results in a 1.5 KByte array instead the 4KByte of the initial Kindergarten file attack getter <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=198660&t=21329 Re: How to reduce the "bits" used in a magic number] by [[Grant Osborne]], [[CCC]], July 04, 2008</ref> . Whether the effort of the rank-indexed magic-factor plus additional pointer indirection pays off the memory saving is another question, and should be tried inside a concrete chess program with its individual cache- and memory footprint.
<pre>
U64 aFileAttacks[4*32+4*16]; // 1.5KByte
U64 aPtrFileAttacks[8]; // points to appropriate aFileAttacks
U64 fileMagic[8] = {
0xEFFFA39DB01B23A3, // 5-bit
0xF024691A3227FF42, // 4-bit
0xF2808817CAD6FF0C, // 4-bit see below
0xED6EDFBE467977D5, // 5-bit
0xEC87CB0D961EC43A, // 5-bit
0xF2FF594E14D8801C, // 4-bit
0xF2FF5D69D4E3E7D6, // 4-bit
0xEE404B349599FF88 // 5-bit
};
U64 fileAttacks(U64 occ, enumSquare sq) {
unsigned int file = sq & 7;
unsigned int rank = sq >> 3;
occ = 0x0001010101010100 & (occ >> file);
occ = (fileMagic[rank] * occ) >> (fileMagic[rank] >> 58); // four&five bit index
return *(aPtrFileAttacks[rank] + occ) << file;
}
</pre>
The table demonstrates how it works for file-attack of the a3 rook with a four bit range only five relevant occupied bits, since a3 is member of the inner six bits. The empirical determined factor is 0xF2808817CAD6FF0C, six upper bits contain the right shift for the product, for this square shift 60:
{| class="wikitable"
|-
! occupancy (A-File)
! product
! index 0..15
! attack set
|-
| o - outer squares don't care<br/>
x - empty or any piece<br/>
. - empty<br/>
b - Blocker - any piece<br/>
R - Rook<br/>
| style="text-align:right;" | occupancy *
<code>0xF2808817CAD6FF0C</code>
| style="text-align:center;" | upper<br/>
[[Nibble|nibble]]<br/>
in<br/>
product<br/>
| 1 attacked<br/>
. not attacked
|-
| o<br/>
x<br/>
x<br/>
x<br/>
b<br/>
R<br/>
b<br/>
o
| style="text-align:center;" | 1. attack-set
|
| .<br/>
.<br/>
.<br/>
.<br/>
1<br/>
.<br/>
1<br/>
.
|-
| <code>0x0000010101000100</code>
| style="text-align:right;" | <code>0x3A28F9D5E2FF0C00</code>
| style="text-align:center;" | 3
| <code>0x0000000001000100</code>
|-
| <code>0x0001010101000100</code>
| style="text-align:right;" | <code>0x3934F9D5E2FF0C00</code>
| style="text-align:center;" | 3
| <code>0x0000000001000100</code>
|-
| <code>0x0000000101000100</code>
| style="text-align:right;" | <code>0x6329EDD5E2FF0C00</code>
| style="text-align:center;" | 6
| <code>0x0000000001000100</code>
|-
| <code>0x0000010001000100</code>
| style="text-align:right;" | <code>0x6F51FAC9E2FF0C00</code>
| style="text-align:center;" | 6
| <code>0x0000000001000100</code>
|-
| <code>0x0001000101000100</code>
| style="text-align:right;" | <code>0x6235EDD5E2FF0C00</code>
| style="text-align:center;" | 6
| <code>0x0000000001000100</code>
|-
| <code>0x0001010001000100</code>
| style="text-align:right;" | <code>0x6E5DFAC9E2FF0C00</code>
| style="text-align:center;" | 6
| <code>0x0000000001000100</code>
|-
| <code>0x0000000001000100</code>
| style="text-align:right;" | <code>0x9852EEC9E2FF0C00</code>
| style="text-align:center;" | 9
| <code>0x0000000001000100</code>
|-
| <code>0x0001000001000100</code>
| style="text-align:right;" | <code>0x975EEEC9E2FF0C00</code>
| style="text-align:center;" | 9
| <code>0x0000000001000100</code>
|-
| o<br/>
x<br/>
x<br/>
x<br/>
b<br/>
R<br/>
.<br/>
o
| style="text-align:center;" | 2. attack set
|
| .<br/>
.<br/>
.<br/>
.<br/>
1<br/>
.<br/>
1<br/>
1
|-
| <code>0x0000000001000000</code>
| style="text-align:right;" | <code>0x17CAD6FF0C000000</code>
| style="text-align:center;" | 1
| <code>0x0000000001000101</code>
|-
| <code>0x0001000001000000</code>
| style="text-align:right;" | <code>0x16D6D6FF0C000000</code>
| style="text-align:center;" | 1
| <code>0x0000000001000101</code>
|-
| <code>0x0000010101000000</code>
| style="text-align:right;" | <code>0xB9A0E20B0C000000</code>
| style="text-align:center;" | 11
| <code>0x0000000001000101</code>
|-
| <code>0x0001010101000000</code>
| style="text-align:right;" | <code>0xB8ACE20B0C000000</code>
| style="text-align:center;" | 11
| <code>0x0000000001000101</code>
|-
| <code>0x0000000101000000</code>
| style="text-align:right;" | <code>0xE2A1D60B0C000000</code>
| style="text-align:center;" | 14
| <code>0x0000000001000101</code>
|-
| <code>0x0000010001000000</code>
| style="text-align:right;" | <code>0xEEC9E2FF0C000000</code>
| style="text-align:center;" | 14
| <code>0x0000000001000101</code>
|-
| <code>0x0001000101000000</code>
| style="text-align:right;" | <code>0xE1ADD60B0C000000</code>
| style="text-align:center;" | 14
| <code>0x0000000001000101</code>
|-
| <code>0x0001010001000000</code>
| style="text-align:right;" | <code>0xEDD5E2FF0C000000</code>
| style="text-align:center;" | 14
| <code>0x0000000001000101</code>
|-
| o<br/>
x<br/>
x<br/>
b<br/>
.<br/>
R<br/>
b<br/>
o
| style="text-align:center;" | 3. attack set
|
| .<br/>
.<br/>
.<br/>
1<br/>
1<br/>
.<br/>
1<br/>
.
|-
| <code>0x0001010100000100</code>
| style="text-align:right;" | <code>0x216A22D6D6FF0C00</code>
| style="text-align:center;" | 2
| <code>0x0000000101000100</code>
|-
| <code>0x0000010100000100</code>
| style="text-align:right;" | <code>0x225E22D6D6FF0C00</code>
| style="text-align:center;" | 2
| <code>0x0000000101000100</code>
|-
| <code>0x0000000100000100</code>
| style="text-align:right;" | <code>0x4B5F16D6D6FF0C00</code>
| style="text-align:center;" | 4
| <code>0x0000000101000100</code>
|-
| <code>0x0001000100000100</code>
| style="text-align:right;" | <code>0x4A6B16D6D6FF0C00</code>
| style="text-align:center;" | 4
| <code>0x0000000101000100</code>
|-
| o<br/>
x<br/>
x<br/>
b<br/>
.<br/>
R<br/>
.<br/>
o
| style="text-align:center;" | 4. attack set
|
| .<br/>
.<br/>
.<br/>
1<br/>
1<br/>
.<br/>
1<br/>
1
|-
| <code>0x0000010100000000</code>
| style="text-align:right;" | <code>0xA1D60B0C00000000</code>
| style="text-align:center;" | 10
| <code>0x0000000101000101</code>
|-
| <code>0x0001010100000000</code>
| style="text-align:right;" | <code>0xA0E20B0C00000000</code>
| style="text-align:center;" | 10
| <code>0x0000000101000101</code>
|-
| <code>0x0000000100000000</code>
| style="text-align:right;" | <code>0xCAD6FF0C00000000</code>
| style="text-align:center;" | 12
| <code>0x0000000101000101</code>
|-
| <code>0x0001000100000000</code>
| style="text-align:right;" | <code>0xC9E2FF0C00000000</code>
| style="text-align:center;" | 12
| <code>0x0000000101000101</code>
|-
| o<br/>
x<br/>
b<br/>
.<br/>
.<br/>
R<br/>
b<br/>
o
| style="text-align:center;" | 5. attack set
|
| .<br/>
.<br/>
1<br/>
1<br/>
1<br/>
.<br/>
1<br/>
.
|-
| <code>0x0000010000000100</code>
| style="text-align:right;" | <code>0x578723CAD6FF0C00</code>
| style="text-align:center;" | 5
| <code>0x0000010101000100</code>
|-
| <code>0x0001010000000100</code>
| style="text-align:right;" | <code>0x569323CAD6FF0C00</code>
| style="text-align:center;" | 5
| <code>0x0000010101000100</code>
|-
| o<br/>
x<br/>
b<br/>
.<br/>
.<br/>
R<br/>
.<br/>
o
| style="text-align:center;" | 6. attack set
|
| .<br/>
.<br/>
1<br/>
1<br/>
1<br/>
.<br/>
1<br/>
1
|-
| <code>0x0000010000000000</code>
| style="text-align:right;" | <code>0xD6FF0C0000000000</code>
| style="text-align:center;" | 13
| <code>0x0000010101000101</code>
|-
| <code>0x0001010000000000</code>
| style="text-align:right;" | <code>0xD60B0C0000000000</code>
| style="text-align:center;" | 13
| <code>0x0000010101000101</code>
|-
| o<br/>
b<br/>
.<br/>
.<br/>
.<br/>
R<br/>
b<br/>
o
| style="text-align:center;" | 7. attack set
|
| .<br/>
1<br/>
1<br/>
1<br/>
1<br/>
.<br/>
1<br/>
.
|-
| <code>0x0001000000000100</code>
| style="text-align:right;" | <code>0x7F9417CAD6FF0C00</code>
| style="text-align:center;" | 7
| <code>0x0001010101000100</code>
|-
| o<br/>
b<br/>
.<br/>
.<br/>
.<br/><br/>
R<br/>
.<br/>
o
| style="text-align:center;" | 8. attack set
|
| .<br/>
1<br/>
1<br/>
1<br/>
1<br/>
.<br/>
1<br/>
1
|-
| <code>0x0001000000000000</code>
| style="text-align:right;" | <code>0xFF0C000000000000</code>
| style="text-align:center;" | 15
| <code>0x0001010101000101</code>
|-
| o<br/>
.<br/>
.<br/>
.<br/>
.<br/>
R<br/>
b<br/>
o
| style="text-align:center;" | 9. attack set
|
| 1<br/>
1<br/>
1<br/>
1<br/>
1<br/>
.<br/>
1<br/>
.
|-
| <code>0x0000000000000100</code>
| style="text-align:right;" | <code>0x808817CAD6FF0C00</code>
| style="text-align:center;" | 8
| <code>0x0101010101000100</code>
|-
| o<br/>
.<br/>
.<br/>
.<br/>
.<br/>
R<br/>
.<br/>
o
| style="text-align:center;" | 10. attack set,
no blocker
|
| 1<br/>
1<br/>
1<br/>
1<br/>
1<br/>
.<br/>
1<br/>
1
|-
| <code>0x0000000000000000</code>
| style="text-align:right;" | <code>0x0000000000000000</code>
| style="text-align:center;" | 0
| <code>0x0101010101000101</code>
|}
=See also=
* [[Flipping Mirroring and Rotating#RankFileAndDiagonal|Flipping, Mirroring and Rotating of Rank, File and Diagonal]]
* [[Magic Bitboards]]
* [[Occupancy of any Line]]
* [[Rotated Bitboards]]
* [[OliThink#SlidingPieceAttacks|Sliding Piece Attacks in OliThink]]
* [[Winglet#SlidingAttacks|Sliding Piece Attacks in Winglet]]
=Forum Posts=
* [https://groups.google.com/d/msg/rec.games.chess.computer/YvFagyuVogw/2vNJw_qT8IYJ Re: Rotated bitboards] by [[Urban Koistinen]], [[Computer Chess Forums|rgcc]], October 31, 1997 » [[Occupancy of any Line#CollapsedFiles|Collapsed files]], [[Occupancy of any Line#CollapsedRanks|Collapsed ranks]]
* [https://www.stmintz.com/ccc/index.php?id=489834 rotated bitboards obsolete?] by [[Gerd Isenberg]], [[CCC]], February 26, [[Timeline#2006|2006]]
* [https://www.stmintz.com/ccc/index.php?id=491079 Re: Some thoughts on Dann Corbit's rotated alternative] by [[Steffan Westcott]], [[CCC]], March 03, 2006
* [http://www.open-aurec.com/wbforum/viewtopic.php?t=4523 Compact Bitboard Attacks] by [[Tom Likens]], [[Computer Chess Forums|Winboard Forum]], March 14, [[Timeline#2006|2006]]
* [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, [[Timeline#2006|2006]]
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=5958 Magic Bitboards Explained!] by [[Michael Sherwin]], [[Computer Chess Forums|Winboard Forum]], December 04, 2006
* [http://www.talkchess.com/forum/viewtopic.php?t=24724 Kindergarten Bitboard Approach by Gerd Isenberg] by [[Edsel Apostol]], [[CCC]], November 05, 2008 » [[OliThink]]
* [http://www.talkchess.com/forum/viewtopic.php?t=29296 Kindergarten bitboards without multiplying] by [[Piotr Cichy]], [[CCC]], August 07, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=30742 Kindergarten Bitboard help] by [[Gregory Strong]], [[CCC]], November 22, 2009
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=50616&p=192200 32-bit Magic experiments] by [[Andrew Fan]], [[Computer Chess Forums|Winboard Forum]], December 03, 2009 » [[Magic Bitboards]]
* [http://www.talkchess.com/forum/viewtopic.php?t=31348 Kindergarten bitboards and Xiangqi move genaration?] by Han Chengye, [[CCC]], December 30, 2009 » [[Chinese Chess]]
=External Links=
* [https://en.wikipedia.org/wiki/Kindergarten Kindergarten from Wikipedia]
* [[Videos#GeorgeBenson|George Benson]] - [https://en.wikipedia.org/wiki/This_Masquerade This Masquerade], 1976, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=T8eXCdjdSHE|alignment=left|valignment=top}}
* [[Videos#PatMetheny|Pat Metheny]] and friends - [https://en.wikipedia.org/wiki/This_Masquerade This Masquerade], [https://en.wikipedia.org/wiki/Jazz_Baltica Jazz Baltica], July 6, 2003, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: [https://en.wikipedia.org/wiki/Nils_Landgren_%28musician%29 Nils Landgren], [[Videos#LarsDanielsson|Lars Danielsson]], [https://en.wikipedia.org/wiki/Wolfgang_Haffner Wolfgang Haffner], [https://en.wikipedia.org/wiki/Esbj%C3%B6rn_Svensson Esbjörn Svensson], [[Videos#PatMetheny|Pat Metheny]], [[Videos#MichaelBrecker|Michael Brecker]]
: {{#evu:https://www.youtube.com/watch?v=Lzrp7H4j8TE|alignment=left|valignment=top}}
=References=
<references />
'''[[Sliding Piece Attacks|Up one Level]]'''
[[Category:Paul Klee]]
[[FILE:Group_of_Masks.jpg|border|right|thumb|232px|link=http://www.imj.org.il/imagine/collections/item.asp?itemNum=194576| [[Arts#Klee|Paul Klee]] - Group of Masks, 1939 <ref>[http://www.imj.org.il/imagine/collections/viewDataE5.asp?case=Modern%20Art IMAGINE - The Israel Museum's searchable collections database]</ref> ]]
'''Kindergarten''' bitboards <ref>[http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=5958 Magic Bitboards Explained!] by [[Michael Sherwin]] and reply by [[Gerd Isenberg]] to call it Kindergarten Bitboards, [[Computer Chess Forums|Winboard Forum]], December 4, [[Timeline#2006|2006]]</ref> <br/>
was a kind of interactive forum development <ref>[http://www.open-aurec.com/wbforum/viewtopic.php?t=4523 Compact Bitboard Attacks] by [[Tom Likens]], [[Computer Chess Forums|Winboard Forum]], March 14, [[Timeline#2006|2006]]</ref> with a lot of meanders <ref>[https://www.stmintz.com/ccc/index.php?id=489834 rotated bitboards obsolete?] by [[Gerd Isenberg]], [[CCC]], February 26, [[Timeline#2006|2006]]</ref> . There were two issues involved - first to calculate the [[Occupancy of any Line|occupancy of any line]] from the [[Occupancy|occupied bitboard]] <ref>[https://www.stmintz.com/ccc/index.php?id=491079 Re: Some thoughts on Dann Corbit's rotated alternative] by [[Steffan Westcott]], [[CCC]], March 03, 2006</ref> - and second, compact and dense lookup tables. As a quintessence [[Gerd Isenberg]] came up with this nomination. It relies on fast 64-bit multiplication, but is otherwise quite resource friendly and a compromise between calculation and table-size.
=Ranks and Diagonals=
[[Ranks]] and [[Diagonals|diagonals]] - that is their appropriate [[On an empty Board#LineAttacks|line-mask]] by square-index - are first intersected by the occupancy of the whole board. Doesn't matter whether the slider itself is cleared or not - it is redundant anyway, considered by the pre-calculated lookup-table.
Since there is only up to one bit per file, the [[General Setwise Operations#Multiplication|north-fill multiplication]] by the A-file maps the diagonal to the 8th rank. Or - since we only need the [[First Rank Attacks#TheOuterSquares|inner six bits]], we combine the required shift left one by multiplying with the B-file. Shifting right the product by 58 (64-6) leaves the six-bit occupancy-index in the 0..63 range. For instance the diagonal-attacks of a bishop on d4. 'A'-'H' represent the masked occupied bits along this diagonal, which are either zero or one.
{{MappingHint}}
We need 'B'-'G' as six bit number:
<pre>
masked line * B-File = B-G upper six occupancy 6 bit
. . . . . . . H . 1 . . . . . . . A[B C . E F G] . . . . . . . .
. . . . . . G . . 1 . . . . . . . A B C . E F G . . . . . . . .
. . . . . F . . . 1 . . . . . . . A B C . E F . . . . . . . . .
. . . . E . . . . 1 . . . . . . . A B C . E . . >> . . . . . . . .
. . . . . . . . * . 1 . . . . . . = . A B C . . . . 58 . . . . . . . .
. . C . . . . . . 1 . . . . . . . A B C . . . . . . . . . . . .
. B . . . . . . . 1 . . . . . . . A B . . . . . . . . . . . . .
A . . . . . . . . 1 . . . . . . . A . . . . . . [B C . E F G]. .
</pre>
The pre-calculated lookup-table contains the [[First Rank Attacks|attacks of the first rank]] - but eight copies in each [[Ranks|rank]] or [[Byte|byte]]. It is indexed by the six bit occupied-state ('B'-'G') and the [[Files|file]] of the slider's [[Squares|square]]. It needs to be intersected with the same line-mask as formerly the occupancy - to map the first rank attack bits to the appropriate line - that's all. Appropriate pre-calculated attack bits are represented by 'a'-'h':
<pre>
8 copies of rank the attack set
attacks & l-mask -> of this line
a b c . e f g h . . . . . . . h
a b c . e f g h . . . . . . g .
a b c . e f g h . . . . . f . .
a b c . e f g h . . . . e . . .
a b c . e f g h . . . . . . . .
a b c . e f g h . . c . . . . .
a b c . e f g h . b . . . . . .
a b c . e f g h a . . . . . . .
</pre>
Since all [[Ranks|ranks]], [[Diagonals|diagonals]] and [[Anti-Diagonals|anti-diagonals]] are properly file-aligned, it works perfectly with some redundant occupied bits for shorter diagonals as well, like here the outer bit 'B':
<pre>
masked line * B-File = B-G upper six occupancy 6 bit
. . . . . . . . . 1 . . . . . . H .[B C . E F G] . . . . . . . .
. . . . . . . H . 1 . . . . . . . . B C . E F G . . . . . . . .
. . . . . . G . . 1 . . . . . . . . B C . E F G . . . . . . . .
. . . . . F . . . 1 . . . . . . . . B C . E F . >> . . . . . . . .
. . . . E . . . * . 1 . . . . . . = . . B C . E . . 58 . . . . . . . .
. . . . . . . . . 1 . . . . . . . . B C . . . . . . . . . . . .
. . C . . . . . . 1 . . . . . . . . B C . . . . . . . . . . . .
. B . . . . . . . 1 . . . . . . . . B . . . . . [B C . E F G]. .
</pre>
Appropriate pre-calculated attack bits are represented by 'b'-'h' here:
<pre>
8 copies of rank the attack set or the attack set
attacks & l-mask -> of this line -> of the shorter diagonal
a b c . e f g h . . . . . . . h . . . . . . . .
a b c . e f g h . . . . . . g . . . . . . . . h
a b c . e f g h . . . . . f . . . . . . . . g .
a b c . e f g h . . . . e . . . . . . . . f . .
a b c . e f g h . . . . . . . . . . . . e . . .
a b c . e f g h . . c . . . . . . . . . . . . .
a b c . e f g h . b . . . . . . . . c . . . . .
a b c . e f g h a . . . . . . . . b . . . . . .
</pre>
Wasn't that simple? That is why it is called '''kindergarten''' bitboards!
The trick is to share one 4KByte table by three line-directions by re-using the mask for a final intersection. Of course one may use the calculated occupied state to index [[Rotated Bitboards|rotated bitboards]] like tables of 32KByte each. But dividing the table size by 3*8 on the cost of that additional 'and' (and keeping the mask inside a register) is tempting. Of course - like always with computation versus memory issues - it depends on the cache- and memory using and footprint inside a particular chess program and the hardware architecture, which solution is preferable. So far L1 [https://en.wikipedia.org/wiki/Cache Cache] is a rare resource, [https://en.wikipedia.org/wiki/Translation_Lookaside_Buffer Translation Lookaside Buffer] als well.
Like other none rotated approaches, namely [[Magic Bitboards|magic bitboards]] or [[Hyperbola Quintessence#ArrayOfStructs|hyperbola quintessence]], the nice thing is that one can [[Hiding the Implementation|hide the implementation details]] behind a stateless interface. In [[C]] /[[Cpp|C++]] one may use [https://en.wikipedia.org/wiki/Header_file header files] with exclusive, conditional compiled inlined routines, as combinations and variations of the mentioned approaches.
The three routines only differ by the line-mask applied. As pointed out by [[Aleks Peshkov]], it is smarter to index by file, occupancy, since fillUpAttacks[sq&7] may be shared by two (bishop) or three (queen) line-attack getters.
<pre>
U64 fillUpAttacks[8][64]; // 4 KByte
U64 diagonalAttacks(U64 occ, enumSquare sq) {
const U64 bFile = C64(0x0202020202020202);
occ = (diagonalMaskEx[sq] & occ) * bFile >> 58;
return diagonalMaskEx[sq] & fillUpAttacks[sq&7][occ];
}
U64 antiDiagAttacks(U64 occ, enumSquare sq) {
const U64 bFile = C64(0x0202020202020202);
occ = (antidiagMaskEx[sq] & occ) * bFile >> 58;
return antidiagMaskEx[sq] & fillUpAttacks[sq&7][occ];
}
U64 rankAttacks(U64 occ, enumSquare sq) {
const U64 bFile = C64(0x0202020202020202);
occ = (rankMaskEx[sq] & occ) * bFile >> 58;
return rankMaskEx[sq] & fillUpAttacks[sq&7][occ];
}
</pre>
One may use similar structs for the line-masks than the [[Hyperbola Quintessence#ArrayOfStructs|hyperbola quintessence]].
<span id="FileAttacks"></span>
=File-Attacks=
[[Files]] need tad more work. Shift the board left (arithmetical right!) to the A-file to mask it. To get the inner six bits, a [[Flipping Mirroring and Rotating#FiletoaRank|flip-multiplication]] by the c2-h7 diagonal is applied with further shift right 58. The lookup-table contains the A-file attacks, which are shifted "back" to the original file.
<pre>
U64 aFileAttacks [8][64]; // 4 KByte
U64 fileAttacks(U64 occ, enumSquare sq) {
const U64 aFile = C64(0x0101010101010101);
const U64 diac2h7 = C64(0x0080402010080400);
occ = aFile & (occ >> (sq&7));
occ = (diac2h7 * occ ) >> 58;
return aFileAttacks[sq>>3][occ] << (sq&7);
}
</pre>
This is how it works:
<pre>
masked A-file * c2-h7 Diagonal = occupancy
H . . . . . . . . . . . . . . . . .[G F E D C B] . . . . . . . .
G . . . . . . . . . . . . . . 1 . . F E D C B A . . . . . . . .
F . . . . . . . . . . . . . 1 . . . E D C B A . . . . . . . . .
E . . . . . . . . . . . . 1 . . . . D C B A . . >> . . . . . . . .
D . . . . . . . * . . . . 1 . . . = . . C B A . . . 58 . . . . . . . .
C . . . . . . . . . . 1 . . . . . . B A . . . . . . . . . . . .
B . . . . . . . . . 1 . . . . . . . A . . . . . . . . . . . . .
A . . . . . . . . . . . . . . . . . . . . . . . [G F E D C B]. .
</pre>
Note that the six inner bit occupancy is reversed - considered in the pre-calculated aFileAttacks [[Array|array]]. This reversed lookup was justified to share first rank-attacks by all directions - with a dense lookup of 512 Byte. But the 4KByte tables outperform the additional multiplications and shift of the dense version - and one may alternatively multiply with the flipped diagonal, the c7-h2 anti-diagonal:
<pre>
masked A-file * c7-h2 AntiDiag = occupancy
H . . . . . . . . . . . . . . . . .[B C D E F G] . . . . . . . .
G . . . . . . . . . 1 . . . . . . . A B C D E F . . . . . . . .
F . . . . . . . . . . 1 . . . . . . . A B C D E . . . . . . . .
E . . . . . . . . . . . 1 . . . . . . . A B C D >> . . . . . . . .
D . . . . . . . * . . . . . 1 . . = . . . . . A B C 58 . . . . . . . .
C . . . . . . . . . . . . . 1 . . . . . . . A B . . . . . . . .
B . . . . . . . . . . . . . . 1 . . . . . . . A . . . . . . . .
A . . . . . . . . . . . . . . . . . . . . . . . [B C D E F G]. .
</pre>
=Shared Rank Lookup=
As often, [[Space-Time Tradeoff|computation versus memory size]]. One may share a 512Byte Lookup of the first rank by all lines with some trailing computation. Multiplying with the A-file (fill north) for ranks and diagonals, and multiplying with the diagonal for the file. Likely the additional multiplication don't pays off.
<pre>
const BYTE firstRankAttacks[8][64];
U64 fileAttacks(U64 occ, enumSquare sq) {
const U64 aFile = C64(0x0101010101010101);
const U64 hFile = C64(0x8080808080808080);
const U64 diaa1h8 = C64(0x8040201008040201);
const U64 diac2h7 = C64(0x0080402010080400);
unsigned int f = sq & 7;
occ = aFile & (occ >> f);
occ = ( diac2h7 * occ ) >> 58;
occ = diaa1h8 * firstRankAttacks[(sq^56)>>3][occ];
return ( hFile & occ ) >> (f^7);
}
U64 diagonalAttacks(U64 occ, enumSquare sq) {
const U64 aFile = C64(0x0101010101010101);
const U64 bFile = C64(0x0202020202020202);
unsigned int f = sq & 7;
occ = diagonalMaskEx[sq] & occ;
occ = (bFile * occ ) >> 58;
occ = aFile * firstRankAttacks[f][occ];
return diagonalMaskEx[sq] & occ;
}
</pre>
=32-bit Versions=
One other variation of the memory versus computation theme was encouraged by 32-bit mode. 64-bit multiplication is quite expensive in 32-bit mode - a call using three imuls. Thus, it is more efficient to use shift-or plus 32-bit multiplication, which might in fact be used in 64-bit mode as well. [[Piotr Cichy]] proposed a multiplication less [[Parallel Prefix Algorithms|parallel prefix shift]] approach similar to [[Occupancy of any Line]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=29296 Kindergarten bitboards without multiplying] by [[Piotr Cichy]], [[CCC]], August 07, 2009</ref> , which is a good alternative for processors with slow multiplication.
An efficient and tricky file-approach was introduced by [[Zach Wegner]] <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>, using a 32KByte, [[Rotated Bitboards|rotated like]] lookup-table:
It is quite strange, yes, but it is an out of order mapping. There are only 5 bits because each bit in the factor maps more than one bit. The trick here is the odd shift 29, so that the multiply does not overflow individual bits. I have since found that 25 and 27 will work with the same magic:
<pre>
occ
. . . . . . . .
a . . . . . . .
b . . . . . . . occ | occ >> 29 * 0x01041041 with the index bracketed
c . . . . . . . ...\ ...\ ...\
d . . . . . . . d . . . . . . . 1 . . . . . . . d a[f c e b d a]
e . . . . . . . e . . a . . . . . . 1 . . . . . e b . a f c e b
f . . . . . . . f . . b . . . . . . . . 1 . . . f c . b . . f c
. . . . . . . . . . . c . . . . 1 . . . . . 1 . . . . c . . . .
</pre>
The interesting thing is that this works for any masked file. In fact if it was shifted to the a-file, you could get away with the 3-bit factor 0x00041040 (but using a shift of 23).
<pre>
U64 arrFileAttacks[64][64]; // [sq][occ64] 32KByte
U64 fileAttacks(U64 occ, enumSquare sq) {
occ &= fileMask[sq];
U32 fold = (U32)occ | (U32)(occ >> 29);
U32 occ64 = fold * 0x01041041 >> 26;
return arrFileAttacks[sq][occ64];
}
</pre>
Ranks and diagonals are trivial, this version favors rotated like memory size for less computation and same operations than file-attacks. One may therefor generalize the routine by a line-direction parameter:
<pre>
U64 arrDiagonalAttacks[64][64]; // [sq][occ64] 32KByte
U64 diagonalAttacks(U64 occ, enumSquare sq) {
occ &= diagonalMaskEx[sq];
U32 fold = (U32)occ | (U32)(occ >> 32);
U32 occ64 = fold * 0x02020202 >> 26;
return arrDiagonalAttacks[sq][occ64];
}
</pre>
A similar approach was proposed by [[Andrew Fan]] in 2009, been active in his [[FireFly|own engine]] for a few years (2006 earliest recorded file time) <ref>[http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=50616&p=192200 32-bit Magic experiments] by [[Andrew Fan]], [[Computer Chess Forums|Winboard Forum]], December 03, 2009</ref>.
<span id="MagicCompression"></span>
=Magic Compression=
So far Kindergarten bitboards performs a [[Hash Table#PerfectHashing|perfect hashing]] of the up to six relevant and scattered occupied bits of any line to a six-bit index - which is a bijective mapping of 64 different occupancies per line to 64 indices for the precalculated attack sets.
If we have a closer look to the attack sets, say of a rook on the a-file, we enumerate far less disjoint sets. A rook on a1 (a8) has seven different attack-sets on that file, depending on the occupancy of a2-a7. On a2 (a7) there is even one attack set less, on a3 (a6) 2 times 5 and on a4 (a5) 3 times 4 attack-sets. Thus, there are {7, 6, 10, 12, 12, 10, 6, 7} disjoint attack-sets per square on line, or 70 in total over all eight squares.
While kindergarten bitboards apply a minimal perfect mapping of scattered bits to a six-bit index, the mapping of the attack-sets is surjective, since each of the 64 occupancies maps only up to 12 distinct sets. Of course that is because occupancies "behind" the first blocker are redundant and map the same attack.
[[Grant Osborne]] came up with the idea, derived from [[Magic Bitboards|magic bitboards]] - to use different "magic" factors per square (rank), where multiplication may produce carries and enough so called constructive collisions to gain only five or even four bit indices and therefor denser tables. Since different squares may have different table sizes (16 or 32 entries), a Java-like [[Array|array]] is used for the attacks, in C implemented as array of pointers to the arbitrary sized attack tables. The variable right shift by either 60 or 59 is encoded inside the otherwise redundant upper six bits of the magic factor, as mentioned in [[Magic Bitboards#IncorporatingtheShift|incorporating the shift]] of magic bitboards.
Grant's proposal, so far with {5,4,4,5,5,4,4,5} bit ranges for the lookups per square for vertical rook attacks, results in a 1.5 KByte array instead the 4KByte of the initial Kindergarten file attack getter <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=198660&t=21329 Re: How to reduce the "bits" used in a magic number] by [[Grant Osborne]], [[CCC]], July 04, 2008</ref> . Whether the effort of the rank-indexed magic-factor plus additional pointer indirection pays off the memory saving is another question, and should be tried inside a concrete chess program with its individual cache- and memory footprint.
<pre>
U64 aFileAttacks[4*32+4*16]; // 1.5KByte
U64 aPtrFileAttacks[8]; // points to appropriate aFileAttacks
U64 fileMagic[8] = {
0xEFFFA39DB01B23A3, // 5-bit
0xF024691A3227FF42, // 4-bit
0xF2808817CAD6FF0C, // 4-bit see below
0xED6EDFBE467977D5, // 5-bit
0xEC87CB0D961EC43A, // 5-bit
0xF2FF594E14D8801C, // 4-bit
0xF2FF5D69D4E3E7D6, // 4-bit
0xEE404B349599FF88 // 5-bit
};
U64 fileAttacks(U64 occ, enumSquare sq) {
unsigned int file = sq & 7;
unsigned int rank = sq >> 3;
occ = 0x0001010101010100 & (occ >> file);
occ = (fileMagic[rank] * occ) >> (fileMagic[rank] >> 58); // four&five bit index
return *(aPtrFileAttacks[rank] + occ) << file;
}
</pre>
The table demonstrates how it works for file-attack of the a3 rook with a four bit range only five relevant occupied bits, since a3 is member of the inner six bits. The empirical determined factor is 0xF2808817CAD6FF0C, six upper bits contain the right shift for the product, for this square shift 60:
{| class="wikitable"
|-
! occupancy (A-File)
! product
! index 0..15
! attack set
|-
| o - outer squares don't care<br/>
x - empty or any piece<br/>
. - empty<br/>
b - Blocker - any piece<br/>
R - Rook<br/>
| style="text-align:right;" | occupancy *
<code>0xF2808817CAD6FF0C</code>
| style="text-align:center;" | upper<br/>
[[Nibble|nibble]]<br/>
in<br/>
product<br/>
| 1 attacked<br/>
. not attacked
|-
| o<br/>
x<br/>
x<br/>
x<br/>
b<br/>
R<br/>
b<br/>
o
| style="text-align:center;" | 1. attack-set
|
| .<br/>
.<br/>
.<br/>
.<br/>
1<br/>
.<br/>
1<br/>
.
|-
| <code>0x0000010101000100</code>
| style="text-align:right;" | <code>0x3A28F9D5E2FF0C00</code>
| style="text-align:center;" | 3
| <code>0x0000000001000100</code>
|-
| <code>0x0001010101000100</code>
| style="text-align:right;" | <code>0x3934F9D5E2FF0C00</code>
| style="text-align:center;" | 3
| <code>0x0000000001000100</code>
|-
| <code>0x0000000101000100</code>
| style="text-align:right;" | <code>0x6329EDD5E2FF0C00</code>
| style="text-align:center;" | 6
| <code>0x0000000001000100</code>
|-
| <code>0x0000010001000100</code>
| style="text-align:right;" | <code>0x6F51FAC9E2FF0C00</code>
| style="text-align:center;" | 6
| <code>0x0000000001000100</code>
|-
| <code>0x0001000101000100</code>
| style="text-align:right;" | <code>0x6235EDD5E2FF0C00</code>
| style="text-align:center;" | 6
| <code>0x0000000001000100</code>
|-
| <code>0x0001010001000100</code>
| style="text-align:right;" | <code>0x6E5DFAC9E2FF0C00</code>
| style="text-align:center;" | 6
| <code>0x0000000001000100</code>
|-
| <code>0x0000000001000100</code>
| style="text-align:right;" | <code>0x9852EEC9E2FF0C00</code>
| style="text-align:center;" | 9
| <code>0x0000000001000100</code>
|-
| <code>0x0001000001000100</code>
| style="text-align:right;" | <code>0x975EEEC9E2FF0C00</code>
| style="text-align:center;" | 9
| <code>0x0000000001000100</code>
|-
| o<br/>
x<br/>
x<br/>
x<br/>
b<br/>
R<br/>
.<br/>
o
| style="text-align:center;" | 2. attack set
|
| .<br/>
.<br/>
.<br/>
.<br/>
1<br/>
.<br/>
1<br/>
1
|-
| <code>0x0000000001000000</code>
| style="text-align:right;" | <code>0x17CAD6FF0C000000</code>
| style="text-align:center;" | 1
| <code>0x0000000001000101</code>
|-
| <code>0x0001000001000000</code>
| style="text-align:right;" | <code>0x16D6D6FF0C000000</code>
| style="text-align:center;" | 1
| <code>0x0000000001000101</code>
|-
| <code>0x0000010101000000</code>
| style="text-align:right;" | <code>0xB9A0E20B0C000000</code>
| style="text-align:center;" | 11
| <code>0x0000000001000101</code>
|-
| <code>0x0001010101000000</code>
| style="text-align:right;" | <code>0xB8ACE20B0C000000</code>
| style="text-align:center;" | 11
| <code>0x0000000001000101</code>
|-
| <code>0x0000000101000000</code>
| style="text-align:right;" | <code>0xE2A1D60B0C000000</code>
| style="text-align:center;" | 14
| <code>0x0000000001000101</code>
|-
| <code>0x0000010001000000</code>
| style="text-align:right;" | <code>0xEEC9E2FF0C000000</code>
| style="text-align:center;" | 14
| <code>0x0000000001000101</code>
|-
| <code>0x0001000101000000</code>
| style="text-align:right;" | <code>0xE1ADD60B0C000000</code>
| style="text-align:center;" | 14
| <code>0x0000000001000101</code>
|-
| <code>0x0001010001000000</code>
| style="text-align:right;" | <code>0xEDD5E2FF0C000000</code>
| style="text-align:center;" | 14
| <code>0x0000000001000101</code>
|-
| o<br/>
x<br/>
x<br/>
b<br/>
.<br/>
R<br/>
b<br/>
o
| style="text-align:center;" | 3. attack set
|
| .<br/>
.<br/>
.<br/>
1<br/>
1<br/>
.<br/>
1<br/>
.
|-
| <code>0x0001010100000100</code>
| style="text-align:right;" | <code>0x216A22D6D6FF0C00</code>
| style="text-align:center;" | 2
| <code>0x0000000101000100</code>
|-
| <code>0x0000010100000100</code>
| style="text-align:right;" | <code>0x225E22D6D6FF0C00</code>
| style="text-align:center;" | 2
| <code>0x0000000101000100</code>
|-
| <code>0x0000000100000100</code>
| style="text-align:right;" | <code>0x4B5F16D6D6FF0C00</code>
| style="text-align:center;" | 4
| <code>0x0000000101000100</code>
|-
| <code>0x0001000100000100</code>
| style="text-align:right;" | <code>0x4A6B16D6D6FF0C00</code>
| style="text-align:center;" | 4
| <code>0x0000000101000100</code>
|-
| o<br/>
x<br/>
x<br/>
b<br/>
.<br/>
R<br/>
.<br/>
o
| style="text-align:center;" | 4. attack set
|
| .<br/>
.<br/>
.<br/>
1<br/>
1<br/>
.<br/>
1<br/>
1
|-
| <code>0x0000010100000000</code>
| style="text-align:right;" | <code>0xA1D60B0C00000000</code>
| style="text-align:center;" | 10
| <code>0x0000000101000101</code>
|-
| <code>0x0001010100000000</code>
| style="text-align:right;" | <code>0xA0E20B0C00000000</code>
| style="text-align:center;" | 10
| <code>0x0000000101000101</code>
|-
| <code>0x0000000100000000</code>
| style="text-align:right;" | <code>0xCAD6FF0C00000000</code>
| style="text-align:center;" | 12
| <code>0x0000000101000101</code>
|-
| <code>0x0001000100000000</code>
| style="text-align:right;" | <code>0xC9E2FF0C00000000</code>
| style="text-align:center;" | 12
| <code>0x0000000101000101</code>
|-
| o<br/>
x<br/>
b<br/>
.<br/>
.<br/>
R<br/>
b<br/>
o
| style="text-align:center;" | 5. attack set
|
| .<br/>
.<br/>
1<br/>
1<br/>
1<br/>
.<br/>
1<br/>
.
|-
| <code>0x0000010000000100</code>
| style="text-align:right;" | <code>0x578723CAD6FF0C00</code>
| style="text-align:center;" | 5
| <code>0x0000010101000100</code>
|-
| <code>0x0001010000000100</code>
| style="text-align:right;" | <code>0x569323CAD6FF0C00</code>
| style="text-align:center;" | 5
| <code>0x0000010101000100</code>
|-
| o<br/>
x<br/>
b<br/>
.<br/>
.<br/>
R<br/>
.<br/>
o
| style="text-align:center;" | 6. attack set
|
| .<br/>
.<br/>
1<br/>
1<br/>
1<br/>
.<br/>
1<br/>
1
|-
| <code>0x0000010000000000</code>
| style="text-align:right;" | <code>0xD6FF0C0000000000</code>
| style="text-align:center;" | 13
| <code>0x0000010101000101</code>
|-
| <code>0x0001010000000000</code>
| style="text-align:right;" | <code>0xD60B0C0000000000</code>
| style="text-align:center;" | 13
| <code>0x0000010101000101</code>
|-
| o<br/>
b<br/>
.<br/>
.<br/>
.<br/>
R<br/>
b<br/>
o
| style="text-align:center;" | 7. attack set
|
| .<br/>
1<br/>
1<br/>
1<br/>
1<br/>
.<br/>
1<br/>
.
|-
| <code>0x0001000000000100</code>
| style="text-align:right;" | <code>0x7F9417CAD6FF0C00</code>
| style="text-align:center;" | 7
| <code>0x0001010101000100</code>
|-
| o<br/>
b<br/>
.<br/>
.<br/>
.<br/><br/>
R<br/>
.<br/>
o
| style="text-align:center;" | 8. attack set
|
| .<br/>
1<br/>
1<br/>
1<br/>
1<br/>
.<br/>
1<br/>
1
|-
| <code>0x0001000000000000</code>
| style="text-align:right;" | <code>0xFF0C000000000000</code>
| style="text-align:center;" | 15
| <code>0x0001010101000101</code>
|-
| o<br/>
.<br/>
.<br/>
.<br/>
.<br/>
R<br/>
b<br/>
o
| style="text-align:center;" | 9. attack set
|
| 1<br/>
1<br/>
1<br/>
1<br/>
1<br/>
.<br/>
1<br/>
.
|-
| <code>0x0000000000000100</code>
| style="text-align:right;" | <code>0x808817CAD6FF0C00</code>
| style="text-align:center;" | 8
| <code>0x0101010101000100</code>
|-
| o<br/>
.<br/>
.<br/>
.<br/>
.<br/>
R<br/>
.<br/>
o
| style="text-align:center;" | 10. attack set,
no blocker
|
| 1<br/>
1<br/>
1<br/>
1<br/>
1<br/>
.<br/>
1<br/>
1
|-
| <code>0x0000000000000000</code>
| style="text-align:right;" | <code>0x0000000000000000</code>
| style="text-align:center;" | 0
| <code>0x0101010101000101</code>
|}
=See also=
* [[Flipping Mirroring and Rotating#RankFileAndDiagonal|Flipping, Mirroring and Rotating of Rank, File and Diagonal]]
* [[Magic Bitboards]]
* [[Occupancy of any Line]]
* [[Rotated Bitboards]]
* [[OliThink#SlidingPieceAttacks|Sliding Piece Attacks in OliThink]]
* [[Winglet#SlidingAttacks|Sliding Piece Attacks in Winglet]]
=Forum Posts=
* [https://groups.google.com/d/msg/rec.games.chess.computer/YvFagyuVogw/2vNJw_qT8IYJ Re: Rotated bitboards] by [[Urban Koistinen]], [[Computer Chess Forums|rgcc]], October 31, 1997 » [[Occupancy of any Line#CollapsedFiles|Collapsed files]], [[Occupancy of any Line#CollapsedRanks|Collapsed ranks]]
* [https://www.stmintz.com/ccc/index.php?id=489834 rotated bitboards obsolete?] by [[Gerd Isenberg]], [[CCC]], February 26, [[Timeline#2006|2006]]
* [https://www.stmintz.com/ccc/index.php?id=491079 Re: Some thoughts on Dann Corbit's rotated alternative] by [[Steffan Westcott]], [[CCC]], March 03, 2006
* [http://www.open-aurec.com/wbforum/viewtopic.php?t=4523 Compact Bitboard Attacks] by [[Tom Likens]], [[Computer Chess Forums|Winboard Forum]], March 14, [[Timeline#2006|2006]]
* [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, [[Timeline#2006|2006]]
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=5958 Magic Bitboards Explained!] by [[Michael Sherwin]], [[Computer Chess Forums|Winboard Forum]], December 04, 2006
* [http://www.talkchess.com/forum/viewtopic.php?t=24724 Kindergarten Bitboard Approach by Gerd Isenberg] by [[Edsel Apostol]], [[CCC]], November 05, 2008 » [[OliThink]]
* [http://www.talkchess.com/forum/viewtopic.php?t=29296 Kindergarten bitboards without multiplying] by [[Piotr Cichy]], [[CCC]], August 07, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=30742 Kindergarten Bitboard help] by [[Gregory Strong]], [[CCC]], November 22, 2009
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=50616&p=192200 32-bit Magic experiments] by [[Andrew Fan]], [[Computer Chess Forums|Winboard Forum]], December 03, 2009 » [[Magic Bitboards]]
* [http://www.talkchess.com/forum/viewtopic.php?t=31348 Kindergarten bitboards and Xiangqi move genaration?] by Han Chengye, [[CCC]], December 30, 2009 » [[Chinese Chess]]
=External Links=
* [https://en.wikipedia.org/wiki/Kindergarten Kindergarten from Wikipedia]
* [[Videos#GeorgeBenson|George Benson]] - [https://en.wikipedia.org/wiki/This_Masquerade This Masquerade], 1976, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=T8eXCdjdSHE|alignment=left|valignment=top}}
* [[Videos#PatMetheny|Pat Metheny]] and friends - [https://en.wikipedia.org/wiki/This_Masquerade This Masquerade], [https://en.wikipedia.org/wiki/Jazz_Baltica Jazz Baltica], July 6, 2003, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: [https://en.wikipedia.org/wiki/Nils_Landgren_%28musician%29 Nils Landgren], [[Videos#LarsDanielsson|Lars Danielsson]], [https://en.wikipedia.org/wiki/Wolfgang_Haffner Wolfgang Haffner], [https://en.wikipedia.org/wiki/Esbj%C3%B6rn_Svensson Esbjörn Svensson], [[Videos#PatMetheny|Pat Metheny]], [[Videos#MichaelBrecker|Michael Brecker]]
: {{#evu:https://www.youtube.com/watch?v=Lzrp7H4j8TE|alignment=left|valignment=top}}
=References=
<references />
'''[[Sliding Piece Attacks|Up one Level]]'''
[[Category:Paul Klee]]
