25,161
edits
Changes
no edit summary
'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * Bitboard Serialization'''
[[FILE:EschersEncounter.jpg|border|right|thumb|276px|link=http://www.mcescher.com/Gallery/back-bmp/LW331.jpg|[[Arts#:Category:M. C. Escher|M. C. Escher]], Encounter, 1944 <ref>[http://www.mcescher.com/Gallery/gallery-back.htm Picture gallery "Back in Holland 1941 - 1954"] from [http://www.mcescher.com/ The Official M.C. Escher Website]</ref> ]]
'''Bitboard Serialization''' refers to the transformation of a bitboard with up to 64 one-bits set into a list of up to 64 bit-indices aka [[Squares|square indices]] of a [[8x8 Board|8x8 board]] - for instance to process [[Target Square|move-target]] sets for [[Move Generation|move generation]]. This is done in two phases, isolating none-empty [https://en.wikipedia.org/wiki/Subset subsets] and then transforming those more versatile subsets into lists, either bit by bit, by applying a [https://en.wikipedia.org/wiki/Bisection bisection] scheme, where finally [[Word|words]] or [[Byte|bytes]] may act as index of a pre-calculated database, or by [[Hash Table#PerfectHashing|perfect hashing]] of square lists by subsets with a limited maximum popularity, for instance move-target sets of a [[King|king]] or [[Knight|knight]] even with [[Hash Table#MinimalPerfectHashing|minimal perfect hashing]].
===Scanning with Reset===
A win of abstraction is to use a combined [[BitScan#BitscanwithReset|bitscan with reset]] found bit routine. This is fine. But probably harder for compilers to generate optimal code in the if-do-while-sense, where reset last bit already sets the zero-flag. If you don't care on such micro-optimizations, this is the preferred control structure<ref>[http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70202 CPW bitscan with reset could someone explain this line?] by [[Mahmoud Uthman]], [[CCC]], March 14, 2019</ref>.
<pre>
while ( x ) {
3:{a1-b1,a1-a2,a1-b2}
</pre>
Kings on edges have 5 potential target squares, thus there are 32 possible move-lists. All other kings have 8 all the 8 neighbors with up to 256 move-lists. Similar move-list enumeration is possible with knights and others. All possible move-target subsets of kings and knights for all 64 from-squares are [[Hash Table#MinimalPerfectHashing|perfectly minimal hashtablehashable]] with a magic factor of four one-bits set. 10016 possible king-move-lists and 5520 knight-move-lists. To reduce memory one may offset the sets to a "normalized" source square per king, knight and sliding piece line, implying some vector arithmetic in the board centric world considering the offset.
The less populated move-target subsets are, the less efficient this hashing technique. This might become a problem since bitboard move-generation is essentially about subsets of moves with certain properties, like most importantly fast winning captures at [[Node Types#CUT|Cut-nodes]].
=Forum Posts=
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=487844 Subject: sliding move generation idea with bitboards] by [[Gerd Isenberg]], [[CCC]], February 19, 2006
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6099 Magic Knight- and King-Move Generation] by [[Gerd Isenberg]], [[Computer Chess Forums|Winboard Forum]], Januar 11, 2007
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=19837 compact bitboard move generator] by [[Robert Hyatt]], [[CCC]], February 25, 2008 » [[Move Generation]]
==2010 ...==
* [http://www.open-chess.org/viewtopic.php?f=5&t=2228 Extracting moves from bitboards] by [[Christian Daley|CDaley11]], [[Computer Chess Forums|OpenChess Forum]], January 18, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47414&start=4 Re: C vs ASM] by [[Rein Halbersma]], [[CCC]], March 05, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=54704 Symmetric move generation using bitboards] by [[Lasse Hansen]], [[CCC]], December 20, 2014 » [[BitScan]]
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70065 An improvement to classic Chess4.5 style bitboards] by [[Michael Sherwin]], [[CCC]], March 01, 2019
=External Links=
* [https://en.wikipedia.org/wiki/Serialization Serialization from Wikipedia]
* [[:Category:The United Jazz + Rock Ensemble|The United Jazz + Rock Ensemble]] - [https://www.allmusic.com/song/steps-of-mc-escher-mt0012121605 Steps of M.C. Escher], [https://www.allmusic.com/album/live-im-schutzenhaus-mw0000062412 Live Im Schutzenhaus] (1978), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: [[:Category:Eberhard Weber|Eberhard Weber]], [[:Category:Jon Hiseman|Jon Hiseman]], [[:Category:Barbara Thompson|Barbara Thompson]], [[:Category:Volker Kriegel|Volker Kriegel]], [[:Category:Wolfgang Dauner|Wolfgang Dauner]],<br/>
: [[:Category:Charlie Mariano|Charlie Mariano]], [[:Category:Albert Mangelsdorff|Albert Mangelsdorff]], [[:Category:Ian Carr|Ian Carr]], [https://en.wikipedia.org/wiki/Ack_van_Rooyen Ack van Rooyen], [https://en.wikipedia.org/wiki/Kenny_Wheeler Kenny Wheeler]
: {{#evu:https://www.youtube.com/watch?v=XKToNeW7r9s|alignment=left|valignment=top}}
=References=
<references />
'''[[Bitboards|Up one Level]]'''
[[Category:M. C. Escher]]
[[Category:The United Jazz + Rock Ensemble]]
[[Category:Ian Carr]]
[[Category:Wolfgang Dauner]]
[[Category:Jon Hiseman]]
[[Category:Volker Kriegel]]
[[Category:Albert Mangelsdorff]]
[[Category:Charlie Mariano]]
[[Category:Barbara Thompson]]
[[Category:Eberhard Weber]]
