Changes

[[FILE:GUGG Magic Garden.jpg|border|right|thumb| [[Arts#:Category:Paul Klee|Paul Klee]] - Magic Garden, 1926

'''Magic bitboardsBitboards''',<br/>

The magic bitboard approach was motivated by [[Gerd Isenberg|Gerd Isenberg's]] multi-direction hashing technique [[Kindergarten Bitboards|kindergarten bitboards]] and probably by Gerd's and [[Tony van Roon-Werten|Tony van Roon-Werten's]] early trials to map line-wise [[Occupancy|occupancies]] by [[De Bruijn sequenceSequence|De Bruijn]]- or random number multiplication <ref>[https://www.stmintz.com/ccc/index.php?id=489834 rotated bitboards obsolete?] by [[Gerd Isenberg]], [[CCC]], February 26, 2006</ref> . [[Lasse Hansen]] had the idea to hash the up to twelve relevant occupied bits of '''both directions''' of a rook- or bishop movement simultaneously <ref>[http://www.open-aurec.com/wbforum/viewtopic.php?t=5015 Fast(er) bitboard move generator] by [[Lasse Hansen]], [[Computer Chess Forums|Winboard Forum]], June 14, [[Timeline#2006|2006]], Initial idea</ref> .

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>:

The development has not finished. [[Lasse Hansen]] came up with another stunning idea <ref>[[Lasse Hansen|Lasse Hansen's]] [http://www.open-aurec.com/wbforum/viewtopic.php?topic_view=threads&p=185506&t=5441 postmask trick], [[Computer Chess Forums|Winboard Forum]], May 09, 2008</ref> , to use a final [[General Setwise Operations#Intersection|intersection]] by attacks [[On an empty Board|attacks on an empty board]], to share tables by two (rooks) or even four (bishops) squares. Bishop sharing is simple to understand, since there are light and dark colored bishops with disjoint attacks-sets, able to share the pre-calculated union of two square-attacks.

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]]?

* [[Maurizio Monge]] ('''20112010'''). ''[http://scholar.google.com/citations?view_op=view_citation&hl=en&user=gpgb4LgAAAAJ&citation_for_view=gpgb4LgAAAAJ:UeHWp8X0CEIC On perfect hashing of numbers with sparse digit representation via multiplication by a constant]''. [httphttps://wwwarxiv.sciencedirectorg/abs/1003.3196 arXiv:1003.3196]* [[Niklas Fiekas]] ('''2020''').com''[https:/science/articlebackscattering.de/piichess/S0166218X11000837 Discrete Applied Mathematics, Volhashtable-packing/ The Hashtable Packing Problem]''. 159, No. 11](Draft)

* [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]]

* [http://web.archive.org/web/20160304114223/http://www.rivalchess.com/magic-bitboards/ Rival Chess Engine - Magic Bitboards] ([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine]) by [[Russell Newman]] and [[Chris Moreton]] » [[Rival]]* [http://web.archive.org/web/20160314001240/http://www.afewmorelines.com/understanding-magic-bitboards-in-chess-programming/ Understanding magic bitboards in chess programming] ([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine]) by [[Chris Moreton]] in his programming blog, August 07, 2013

: line-up: [[Videos#NguyenLe:Category:Nguyên Lê|Nguyên Lê]], [https://de.wikipedia.org/wiki/Claudio_Puntin Claudio Puntin], [https://de.wikipedia.org/wiki/Steffen_Schorn Steffen Schorn], [https://de.wikipedia.org/wiki/Kristjan_Randalu Kristjan Randalu], [http://www.bodekjanke.de/english/home.php Bodek Janke]

* [[Videos#YounSunNah:Category:Youn Sun Nah|Youn Sun Nah]] - [http://www.allaboutjazz.com/lento-youn-sun-nah-act-music-review-by-ian-patterson.php Momento Magico] (2013), [https://en.wikipedia.org/wiki/YouTube YouTube] Video: [[Videos#YounSunNah:Category:Youn Sun Nah|Youn Sun Nah]], [[Videos#UlfWakenius:Category:Ulf Wakenius|Ulf Wakenius]], [[Videos#LarsDanielsson:Category:Lars Danielsson|Lars Danielsson]], [[Videos#VincentPeirani:Category:Vincent Peirani|Vincent Peirani]]