25,161
edits
Changes
no edit summary
'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * [[Sliding Piece Attacks]] * Magic Bitboards'''
[[FILE:GUGG Magic Garden.jpg|border|right|thumb| [[Arts#:Category:Paul Klee|Paul Klee]] - Magic Garden, 1926
<ref>[https://commons.wikimedia.org/wiki/File:GUGG_Magic_Garden.jpg Paul Klee - Magic Garden, 1926], [https://en.wikipedia.org/wiki/Solomon_R._Guggenheim_Museum Solomon R. Guggenheim Museum]</ref> ]]
=History=
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> .
[[Pradu Kannan|Pradu Kannan's]] improvements to Lasse Hansen's initial approach was to introduce a [[Java]]-like, two-dimensional [[Array|array]] with individual size for each square and all it's relevant occupancies <ref>[[Pradu Kannan]] ('''2007'''). ''Magic Move-Bitboard Generation in Computer Chess'', as [http://www.pradu.us/old/Nov27_2008/Buzz/research/magic/Bitboards.pdf pdf]</ref> . Big savings in table-size - since many squares on either orthogonal or diagonal lines require less bits than others, especially considering the [[First Rank Attacks#TheOuterSquares|inner six bits]]. While center squares are more dense for rooks, it is the opposite for bishops <ref>[http://www.open-aurec.com/wbforum/viewtopic.php?t=5441 List of magics for bitboard move generation] by [[Pradu Kannan]], [[Computer Chess Forums|Winboard Forum]], August 23, [[Timeline#2006|2006]]</ref> .
<span id="IncorporatingOffset"></span>
==Incorporating Offset==
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>.
==Initalization==
* [http://www.talkchess.com/forum/viewtopic.php?t=55712 question about magic keys generation time] by [[Fermin Serrano]], [[CCC]], March 19, 2015 » [[Looking for Magics]]
* [http://www.talkchess.com/forum/viewtopic.php?t=57722 Fancy magic bitboards question] by Eric VanderHelm, [[CCC]], September 22, 2015
'''2016'''
* [http://www.talkchess.com/forum/viewtopic.php?t=60007 M42 - A C++ library for Bitboard attack mask generation] by [[Syed Fahad]], [[CCC]], April 30, 2016 <ref>[https://sites.google.com/site/sydfhd/projects/m42 M42] by [[Syed Fahad]]</ref>
* [http://www.talkchess.com/forum/viewtopic.php?t=60065 understanding fixed shift fancy magic bitboard generation] by [[Kalyankumar Ramaseshan]], [[CCC]], May 05, 2016
: [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
* [http://www.talkchess.com/forum/viewtopic.php?t=62561 Why should magic bitboards be sparse?] by Alessandro Power, [[CCC]], December 21, 2016
'''2017'''
* [http://www.talkchess.com/forum/viewtopic.php?t=64578 Looking for dense magics] by Lucas Braesch, [[CCC]], July 11, 2017
* [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://www.talkchess.com/forum/viewtopic.php?t=65187 Disproving the existence of some magics] by [[Niklas Fiekas]], [[CCC]], September 16, 2017 » [[Looking for Magics]]
'''2018'''
* [http://www.talkchess.com/forum/viewtopic.php?t=66538 magic number comprising offset] by [[Eugene Kotlov]], [[CCC]], February 07, 2018
* [http://www.talkchess.com/forum/viewtopic.php?t=67051 No bishop magics with fixed shift 8] by [[Niklas Fiekas]], [[CCC]], April 09, 2018 » [[Looking for Magics]]
'''2019'''
* [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
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70341 On the establishment of domains wherein magic numbers can and cannot exist] by [[Bruce Newman]], [[CCC]], March 28, 2019
=External Links=
* [https://en.wikipedia.org/wiki/Magic_hypercube Magic hypercube from Wikipedia]
* Five Senses - Magic Constant, [http://www.kalevatravel.ee/index.aw/tallinn2011_culture_capital_europe Christmas Jazz Festival], [https://en.wikipedia.org/wiki/Tallinn Tallinn], December 10, 2011, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: 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]
: {{#evu:https://www.youtube.com/watch?v=oUDnf2fSIRQ|alignment=left|valignment=top}}
* [[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]]
: {{#evu:https://www.youtube.com/watch?v=bOvB6gUpsuk|alignment=left|valignment=top}}
'''[[Sliding Piece Attacks|Up one Level]]'''
[[Category:Paul Klee]]
[[Category:Lars Danielsson]]
[[Category:Nguyên Lê]]
[[Category:Youn Sun Nah]]
[[Category:Vincent Peirani]]
[[Category:Ulf Wakenius]]
