25,161
edits
Changes
no edit summary
'''Bitboards''',<br/>
also called bitsets or bitmaps, or better '''Square Sets''', are among other things used to represent the [[Chessboard|board]] inside a chess program in a '''piece centric''' manner. Bitboards, are in essence, [https://en.wikipedia.org/wiki/Finite_set finite sets] of up to [https://en.wikipedia.org/wiki/64_%28number%29 64] [https://en.wikipedia.org/wiki/Element_%28mathematics%29 elements] - all the [[Squares|squares]] of a [[Chessboard|chessboard]], one [[Bit|bit]] per square. Other board [[Games|games]] with greater board sizes may be use set-wise representations as well <ref>[[Reijer Grimbergen]] ('''2007'''). ''Using Bitboards for Move Generation in Shogi''. [[ICGA Journal#30_1|ICGA Journal, Vol. 30, No. 1]], [http://www2.teu.ac.jp/gamelab/RESEARCH/ICGAJournal2007.pdfICGAJournal2007.pdf pdf]</ref>, but classical chess has the advantage that one [[Quad Word|64-bit word]] or register covers the whole board. Even more bitboard friendly is [[Checkers]] with 32-bit bitboards and less [[Pieces#PieceTypeCoding|piece-types]] than chess <ref>[http://www.3dkingdoms.com/checkers/bitboards.htm Checker Bitboards Tutorial] by [[Jonathan Kreuzer]]</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=64487 Checkers Bitboard representation] by Pranav Deshpande, [[CCC]], July 02, 2017</ref>.
=The Board of Sets=
* Bitboards can have a high information density.
* Single populated or even empty Bitboards have a low information density.
* <span id="getPiece"></span>Bitboards are weak in answering questions like what piece if any resides on square x. One reason to keep a redundant [[Mailbox|mailbox]] board representation with some additional [[Incremental Updates|update]] costs during [[Make Move|make]]/[[Unmake Move|unmake]].
* Bitboards can operate on all squares in parallel using bitwise instructions. This is one of the main arguments used by proponents of bitboards, because it allows for a flexibility in [[Evaluation|evaluation]].
* Bitboards are rather handicapped on 32 bit processors, as each bitwise computation must be split into two or more instructions <ref>[http://www.stmintz.com/ccc/index.php?id=30562 Efficient Bitboard Implementation on 32-bit Architecture] by [[Roberto Waldteufel]], [[CCC]], October 25, 1998</ref> . As most modern processors are now 64 bit, this point is somewhat diminished <ref>[http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6651 Speedup by bitboards] by [[Onno Garms]], [[Computer Chess Forums|Winboard Forum]], July 13, 2007</ref> .
==2005 ...==
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=4521 Bitboard question] by [[Tord Romstad]], [[Computer Chess Forums|Winboard Forum]], March 14, 2006
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=5623 Yet another new bitboard move generation method] by [[Zach Wegner]], [[Computer Chess Forums|Winboard Forum]], September 22, 2006 » [[Titboards]]
: [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=5623&start=6 Re: Yet another new bitboard move generation method] by [[Harm Geert Muller]], [[Computer Chess Forums|Winboard Forum]], October 01, 2006 <ref>[http://www.talkchess.com/forum3/viewtopic.php?f=7&t=52861&start=8 Re: multi-dimensional piece/square tables] by Tony P., [[CCC]], January 28, 2020</ref>
* [http://www.talkchess.com/forum/viewtopic.php?t=13426 Speedup with bitboards on 64-bit CPUs] by [[Tord Romstad]], [[CCC]], April 27, 2007
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6651 Speedup by bitboards] by [[Onno Garms]], [[Computer Chess Forums|Winboard Forum]], July 13, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=17138 BitBoard representations of the board] by [[Uri Blass]], [[CCC]], October 14, 2007
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=19837 compact bitboard move generator] by [[Robert Hyatt]], [[CCC]], February 25, 2008 » [[Bitboard Serialization]], [[Move Generation]]
* [http://www.talkchess.com/forum/viewtopic.php?t=25917 Bitboards / move generation on larger boards] by [[Gregory Strong]], [[CCC]], January 09, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=26527 Bitboard techniques in Xiangqi] by [[Harm Geert Muller]], [[CCC]], February 12, 2009 » [[Chinese Chess]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=56476 Bitboard database code samples] by [[Steven Edwards]], [[CCC]], May 25, 2015 » [[Symbolic]]
* [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=64487 Checkers Bitboard representation] by Pranav Deshpande, [[CCC]], July 02, 2017 » [[Checkers]]
* [http://www.talkchess.com/forum/viewtopic.php?t=65724 Bitboards and Java] by [[Fred Hamilton]], [[CCC]], November 14, 2017 » [[Java]]
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=72461&start=3 Re: Pawn move generation in bitboards] by [[Álvaro Begué]], [[CCC]], December 05, 2019 » [[Cpp|C++]], [[Pawn Pattern and Properties]]
==2020 ...==
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73830 M42 - C++ Library for Bitboard Attack Mask Generation] by [[Syed Fahad]], [[CCC]], May 04, 2020 <ref>[https://github.com/sinandredemption/M42 GitHub - sinandredemption/M42: C++ Library for Bitboard Attack Mask Generation]</ref>
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=76083 Bitboard board representation] by [[Elias Nilsson]], [[CCC]], December 17, 2020
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=76548 Thought bitboards was faster :-)] by [[Daniel Anulliero]], [[CCC]], February 10, 2021
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=76690 Are Bitboards More Intoxicating Than They Are Good?] by [[Michael Sherwin|Mike Sherwin]], [[CCC]], February 24, 2021
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77299 Best bitboard design?] by [[Martin Bryant]], [[CCC]], May 13, 2021
* [https://www.talkchess.com/forum3/viewtopic.php?t=78160 The cost of check & discovered check in bitboards] by Bill Beame, [[CCC]], September 13, 2021
* [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=78680 Bitboards ?: C# vs C++] by Bill Beame, [[CCC]], November 17, 2021 » [[C sharp|C#]], [[Cpp|C++]]
* [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=79365 Move generation for bitboards] by [[Elias Nilsson]], [[CCC]], February 16, 2022
=Viewer & Calculator=
* [[Bibob]]
* [httphttps://cinnamonchessgekomad.altervistagithub.orgio/bitboard_calculatorCinnamon/Calc.html BitboardCalculator Bitboard Calculator] by [[Giuseppe Cannella]]
* [http://www.chessprogramming.net/computerchess/free-chess-bitboard-viewer/ Free Chess Bitboard Viewer - Computer Chess Programming] by [[Steve Maughan]]
* [http://www.chess2u.com/t2159-new-free-tool-bitboards-helper New free tool : Bitboards Helper] by [[Julien Marcel]]
=External Links=
==Descriptions==* [httphttps://en.wikipedia.org/wiki/Bitboard Bitboards from Wikipedia]* [httphttps://en.wikipedia.org/wiki/Bit_array Bit-Array from Wikipedia]* [httphttps://en.wikipedia.org/wiki/Bitboard#History Bitboard-History from Wikipedia]* [httphttps://www.craftychess.com/hyatt/boardrep.html Chess board representations] by [[Robert Hyatt]]* [https://web.archive.org/web/20081007034904/http://webpages.charter.net/tlikens/bitmaps/bit_intro.html Bitboards (aka bitmaps)] by [[Tom Likens]]([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine], 2008)
* [http://www.fzibi.com/cchess/bitboards.htm An Introduction to BITBOARDS] by [[Franck Zibi]]
* [https://web.archive.org/web/20050205014648/http://www.onjava.com/pub/a/onjava/2005/02/02/bitsets.html Bitwise Optimization in Java: Bitfields, Bitboards, and Beyond] by [[Glen Pepicelli]], ([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine], 2005), [http://en.wikipedia.org/wiki/O%27Reilly_Media O'Reilly's] [https://web.archive.org/web/20050203015229/http://onjava.com/ OnJava.com] » [[Java]], [[Bit-Twiddling]]* [httphttps://pages.cs.wisc.edu/~psilord/blog/data/chess-pages/index.html Chess and Bitboards] by [httphttps://pages.cs.wisc.edu/~psilord/ Peter Keller]* [httphttps://sanherlabraj.de/indexferi.htm?lang=eng&url=bitfuncs Bit functions for Delphi] by [[Andreas Herrmann]] » [[Delphi]]* [http://labraj.uni-mbum.si/en/Position_Representation Position Representation - Computer Architecture and Languages Laboratory], [[University of Maribor]]* [httphttps://stackoverflow.com/questions/tagged/bitboard Newest 'bitboard' Questions] - [http://en.wikipedia.org/wiki/Stack_Overflow Stack Overflow]==Libraries==* [https://github.com/sinandredemption/M42 GitHub - sinandredemption/M42: C++ Library for Bitboard Attack Mask Generation] by [[Syed Fahad]]* [https://github.com/kz04px/libchess GitHub - kz04px/libchess: C++ chess library]==Misc==
* [https://www.halloherne.de/artikel/1-september-setunion-in-den-flottmann-hallen-38570.htm?k=tick Setunion] - [https://inherne.net/weltspitze-des-vibraphon-jazz/ Malletmania], [[:Category:Flottmann|Flottmann-Hallen]] <ref>[[:Category:Flottmann|Flottmann-Hallen]] in [https://en.wikipedia.org/wiki/Herne,_North_Rhine-Westphalia Herne], [https://en.wikipedia.org/wiki/North_Rhine-Westphalia North Rhine-Westphalia], [https://en.wikipedia.org/wiki/Germany Germany], part of [[:Category:Industrial Heritage Trail|The Industrial Heritage Trail]] of the [https://en.wikipedia.org/wiki/Ruhr Ruhr area]</ref>, March 10, 2019, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: [http://www.saxophonquartett-quattro-venti.de/#about Kerstin Fabry], [https://www.lokalkompass.de/tag/christian-ribbe Christian Ribbe], [https://www.folkwang-uni.de/home/theater/studiengaenge/physical-theatre/lehrende/detail-lehrende/personen-detail/elmar-dissinger/ Elmar Dissinger], [https://de.wikipedia.org/wiki/Pee_Wee_Bluesgang Martin Siehoff], [https://www.halloherne.de/artikel/carlotta-ribbe-und-setunion-31511.htm Carlotta Ribbe], [http://guitartist-quartett.com/quartett_ludger.htm Ludger Bollinger]
