25,161
edits
Changes
no edit summary
<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> ]]
'''Magic bitboardsBitboards''',<br/>
a multiply-right-shift [[Hash Table#PerfectHashing|perfect hashing]] algorithm to index an attack bitboard database - which leaves both line-attacks of bishop or rook in one run. Thanks to the fast 64-bit [[General Setwise Operations#Multiplication|multiplication]] and fast and huge [https://en.wikipedia.org/wiki/Cache caches] of recent processors, Magic Bitboards has become a [https://en.wikipedia.org/wiki/De_facto_standard de facto standard] of modern bitboard engines, as used for instance in [[Crafty]], [[Arasan]], [[Stockfish]] and [[Houdini]]. While [[Robert Hyatt]] reported no immediate speed gain over [[Rotated Bitboards]] in Crafty <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=140141&t=16002 Re: BitBoard Tests Magic v Non-Rotated 32 Bits v 64 Bits] by [[Robert Hyatt]], [[CCC]], August 25, 2007</ref> , [[Jon Dart]] mentioned a 20-25% speedup <ref>[http://www.arasanchess.org/blogs/aug08.html Arasan Blog - Aug 26, 2008] by [[Jon Dart]]</ref> in Arasan over rotated.
<span id="PostMask"></span>
==Sharing Attacks==
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.
The trick is to share even equal colored bishops and rooks where both attack-sets are not disjoint - but all members of the intersection are always set, since they are direct neighbors of both sliders. This is how rooks and bishops may share union-attack-sets by two resp. four squares:
* [http://www.talkchess.com/forum/viewtopic.php?t=64790 Black magic bitboards] by [[Volker Annuss]], [[CCC]], August 03, 2017 » [[#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]]
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=65448 Magic BitBoards Magic numbers] by [[Tamás Kuzmics]], [[CCC]], October 14, 2017
'''2018'''
* [http://www.talkchess.com/forum/viewtopic.php?t=66538 magic number comprising offset] by [[Eugene Kotlov]], [[CCC]], February 07, 2018
==2020 ...==
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73071 Hashtable packing (e.g. to optimize magic bitboards) is strongly NP-complete] by [[Niklas Fiekas]], [[CCC]], February 13, 2020 <ref>[https://en.wikipedia.org/wiki/Strong_NP-completeness Strong NP-completeness from Wikipedia]</ref>
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73593 Looking for Magics, with ternary field types] by [[Fabian von der Warth]], [[CCC]], April 07, 2020 » [https://en.wikipedia.org/wiki/Hive_(game) Hive]
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73625 magic bitboard perft] by [[Richard Delorme]], [[CCC]], April 11, 2020 » [[Perft]]
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77648 What is the point of magic hashing over simply using masked occupancy as index ?] by Gautier Blandin, [[CCC]], July 06, 2021 » [[Hashing Dictionaries]]
=External Links=
* [http://www.pradu.us/old/Nov27_2008/Buzz/ Buzz - A Winboard Chess Playing Program by Pradu Kannan] - Source of [[Pradu Kannan|Pradu Kannan's]] [[Magic Bitboards|magic]] Move Generator
* [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
* [http://www.chessprogramming.net/generating-magic-multipliers/ Chess Programming | Generating Magic Multipliers] by [[Steve Maughan]] » [[Looking for Magics]]
* [http://stackoverflow.com/questions/16925204/sliding-move-generation-using-magic-bitboard chess - Sliding move generation using magic bitboard] - [https://en.wikipedia.org/wiki/Stack_Overflow Stack Overflow], June 4, 2013
* [https://sites.google.com/site/sydfhd/projects/m42 M42] by [[Syed Fahad]] <ref>[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://github.com/goutham/magic-bits GitHub - goutham/magic-bits: Magic-bitboards for Chess] by [[Goutham Bhat]]
* [https://rhysre.net/fast-chess-move-generation-with-magic-bitboards.html Fast Chess Move Generation With Magic Bitboards] by [[Rhys Rustad-Elliott]], January 15, 2019
=Other Magic Stuff=
