Changes

Recently, [[Robert Purves]] coined the names Plain and Fancy Magics <ref>[http://www.talkchess.com/forum/viewtopic.php?t=35858 Plain and fancy magic on modern hardware] by [[Robert Purves]], [[CCC]], August 22, 2010</ref> , and found Hansen's initial Plain Magics with 2 MiB table for rooks and 256 KiB for bishops nearly indistinguishable from Fancy (about 800 KiB and 38 KiB) on his [https://en.wikipedia.org/wiki/Intel_Core_i5 Intel i5] with huge L3 smart cache, see [[Magic Bitboards#Plain|plain]] versus [[Magic Bitboards#Fancy|fancy]] source code. In the same [[CCC]] forum thread, [[Robert Houdart]] proposed a [[Magic Bitboards#ByteLookup|byte lookup]] per square for further table reductions.

But the purpose is to perfectly hash attack-sets rather than consecutive occupied bits. The number of distinct attack-sets is much smaller than the relevant occupancies. Thus, with the help of constructive collisions, some initial guess how to map the bits, and/or [[Trial and Error|trial and error]], using exactly N bits is always possible. If one tries hard enough to maximize constructive collisions - even less. There are some N-1 ones reported at [[Best Magics so far]], which will half the individual table size for some squares in the widespread [[Magic Bitboards#Fancy|Fancy Magic Bitboards]] approach.

But the idea seems like a wishing dream. Can we find ONE of the '''magic group''' of magics? Does it exist in theory? If not, can we use more bits to reach the condition? If yes, can we find a good magic group? A good magic group means that all the hash value <=n, so we can reduce the table size to n, until it reach to 1428/4900. Enough? If all hash values are grouped by square, can we think about using the [[Magic Bitboards#PostMask|Sharing Attacks]] method?

A fancy fixed shift variation was introduced by [[Onno Garms]], looking for magics producing factors with appropriate reduced value ranges. That is, leave 12 bit rook indices for all squares, but with upper bit(s) clear for all possible occupancies for all the squares with less than 12 relevant bits, so that it efficiently becomes a less 12 bit index. Onno believes that it is possible to find magic factors with that property for most of those squares, to come close to the fancy table size with the advantage of a fixed shift <ref>[http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=50043 Magic with fixed shift] by [[Onno Garms]], [[Computer Chess Forums|Winboard Forum]], March 18, 2009</ref> . Even an "overlapping" of square arrays is feasible, if they contain accordant unused slot gaps on both ends. [[Volker Annuss]] came up with a fixed shift solution of only 800 KiB and below <ref>[http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=51162 Fixed shift magics with 800KB lookup table] by [[Volker Annuss]], [[Computer Chess Forums|Winboard Forum]], September, 05, 2010</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=60065&start=14 Re: understanding fixed shift fancy magic bitboard generation] by [[Volker Annuss]], [[CCC]], May 06, 2016</ref>, and more recently even innovated with [[Magic Bitboards#BlackMagics|Black Magic Bitboards]].

[[Volker Annuss|Volker Annuss']] most recent innovation and further improvement of his already dense 700 KiB [[Magic Bitboards#FixedShiftFancy|fixed shift fancy]] reference implementation is called '''Black Magic Bitboards''', introduced in [[CCC]] in August 2017 <ref>[http://www.talkchess.com/forum/viewtopic.php?t=64790 Black magic bitboards] by [[Volker Annuss]], [[CCC]], August 03, 2017</ref>. Instead of [[General Setwise Operations#Intersection|intersection]] with a mask to clear the not relevant occupancy bits, he used the [[General Setwise Operations#Union|union]] with the [[General Setwise Operations#ComplementSet|complement]] of mask to set all not relevant occupancy bits.

This trick, which basically adds a huge constant to the occupancy factor, enables to find '''Black Magics''' yielding in even smaller array sizes per square, determined by maximum and minimum index - the latter no longer zero for the empty occupancy! Unfortunately so far, the individual savings with denser square arrays don't completely advance to the size of the combined overlapping table, since overlapping became harder due to smaller gaps <ref>[http://www.talkchess.com/forum/viewtopic.php?t=64790&start=11 Re: Black magic bitboards] by [[Volker Annuss]], [[CCC]], August 04, 2017</ref> . However, 692 KiB for the complete rook and bishop attack table is the new fixed shift reference. Black Magic Bitboards are now used in Volker's engine [[Arminius]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=64790&start=14 Re: Black magic bitboards] by [[Volker Annuss]], [[CCC]], August 04, 2017</ref> <ref>source code according to the [[Magic Bitboards#FixedShiftFancy|fixed shift fancy]] sample - array size from Volker's posting, also containing black magics and arrayoffsets, see [http://www.talkchess.com/forum/viewtopic.php?t=64790 Black magic bitboards] by [[Volker Annuss]], [[CCC]], August 03, 2017</ref>:

A similar idea as in [[Magic Bitboards#IncorporatingtheShift|Incorporating the Shift]] in the domain [[Magic Bitboards#FixedShiftFancy|fixed shift magics]] was proposed by [[Eugene Kotlov]] concerning the indirection to the stored attack array, using the 16 lower bits of the magic factor as offset <ref>[http://www.talkchess.com/forum/viewtopic.php?t=66538 magic number comprising offset] by [[Eugene Kotlov]], [[CCC]], February 07, 2018</ref>, later even combined with incorporating the shift in the domain of Fancy <ref>[http://www.talkchess.com/forum3/viewtopic.php?f=7&t=69947 Shift and Address included into Magic number] by [[Eugene Kotlov]], [[CCC]], February 18, 2019</ref>.

You may try to find your own magics - to possibly contribute to the record table for most dense fancy or plain tables. So far, there were no magics found for the expensive rook squares a1 and h1 (0, 7) with less than 12 bits, which would allow to half the plain table size. Is there any prove they don't exist - even with [[Magic Bitboards#BlackMagics|Black Magic]]?

* [http://www.talkchess.com/forum/viewtopic.php?t=64790 Black magic bitboards] by [[Volker Annuss]], [[CCC]], August 03, 2017 » [[Magic Bitboards#BlackMagics|Black Magic Bitboards]]