Difference between revisions of "Bitboards"

From Chessprogramming wiki
Jump to: navigation, search
(Created page with "'''Home * Board Representation * Bitboards''' {| class="wiki_table" |- style="vertical-align:top;float:bottom;" File:NY Met klee variations.JPG|border|thum...")
 
(28 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
'''[[Main Page|Home]] * [[Board Representation]] * Bitboards'''
 
'''[[Main Page|Home]] * [[Board Representation]] * Bitboards'''
{| class="wiki_table"
+
 
|- style="vertical-align:top;float:bottom;"
+
[[File:BoardsMeeting.jpg|border|right|thumb|[[:Category:Samuel Bak|Samuel Bak]] - Boards Meeting <ref> [[:Category:Samuel Bak|Samuel Bak]] - Boards Meeting, Oil on Canvas, 39 x 32". [http://chgs.elevator.umn.edu/asset/viewAsset/57f3b6787d58ae5f74bf8ba9#57f3b6d77d58ae5574bf8bcf Chess in the Art of Samuel Bak], [http://chgs.elevator.umn.edu/ Center for Holocaust & Genocide Studies], [[University of Minnesota]]</ref>]]  
[[File:NY Met klee variations.JPG|border|thumb|222px|Paul Klee, "Variations" au Met de New York, 1927  <ref>[[Arts#Klee|Paul Klee]], "Variations" au Met de New York, 1927, [https://commons.wikimedia.org/wiki/File:NY_Met_klee_variations.JPG] [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [https://en.wikipedia.org/wiki/Metropolitan_Museum_of_Art  Metropolitan Museum of Art]</ref>]]  
+
 
| '''Bitboards''',
+
'''Bitboards''',<br/>
also called bitsets or bitmaps, 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> .
+
also called bitsets or bitmaps, 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.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=  
 
=The Board of Sets=  
 
To [[Board Representation|represent the board]] we typically need one bitboard for each [[Pieces#PieceTypeCoding|piece-type]] and [[Color|color]] - likely encapsulated inside a class or structure, or as an [[Array|array]] of bitboards as part of a position object. A one-bit inside a bitboard implies the existence of a piece of this piece-type on a certain square - one to one associated by the bit-position.
 
To [[Board Representation|represent the board]] we typically need one bitboard for each [[Pieces#PieceTypeCoding|piece-type]] and [[Color|color]] - likely encapsulated inside a class or structure, or as an [[Array|array]] of bitboards as part of a position object. A one-bit inside a bitboard implies the existence of a piece of this piece-type on a certain square - one to one associated by the bit-position.
Line 55: Line 55:
  
 
=<span id="BitboardHistory"></span>Bitboard-History=  
 
=<span id="BitboardHistory"></span>Bitboard-History=  
The general approach of [[Mikhail R. Shura-Bura#Bitsets|bitsets]] was proposed by [[Mikhail R. Shura-Bura]] in 1952 <ref>[https://en.wikipedia.org/wiki/Lazar_Lyusternik Lazar A. Lyusternik]], [[http://www.mathnet.ru/php/person.phtml?personid=30351&option_lang=eng Aleksandr A. Abramov], [https://en.wikipedia.org/wiki/Victor_ShestakovVictor I. Shestakov], [[Mikhail R. Shura-Bura]] ('''1952'''). ''Programming for High-Speed Electronic Computers''. (Программирование для электронных счетных машин)</ref> <ref>[[Mathematician#Ershov|Andrey Ershov]], [[Mikhail R. Shura-Bura]] ('''1980'''). ''[http://ershov.iis.nsk.su/archive/eaindex.asp?lang=2&gid=910 The Early Development of Programming in the USSR]''. in [http://en.wikipedia.org/wiki/Nicholas_C._Metropolis|Nicholas C. Metropolis]] (ed.) ''[[http://dl.acm.org/citation.cfm?id=578384 A History of Computing in the Twentieth Century]''. [https://en.wikipedia.org/wiki/Academic_Press Academic Press], [http://ershov.iis.nsk.su/archive/eaimage.asp?did=28792&fileid=173670 preprint pp. 43]</ref>. The bitboard method for holding a board game appears to have been invented also in 1952 by [[Christopher Strachey]] using White, Black and King bitboards in his checkers program for the [[Ferranti Mark 1]], and in the mid 1950's by [[Arthur Samuel]] in his checkers program as well. In computer chess, bitboards were first described by [[Georgy Adelson-Velsky]] et al. in 1967 <ref>[http://groups.google.com/group/rec.games.chess/browse_frm/thread/0e3a93f45ff07d31# Early Reference on Bit-Boards] by [[Tony Warnock]] from [[Computer Chess Forums|rec.games.chess]], October 29, 1994</ref>, reprinted 1970 <ref>[[Georgy Adelson-Velsky]], [[Vladimir Arlazarov]], [[Alexander Bitman]], [[Alexander Zhivotovsky]], [[Anatoly Uskov]] ('''1970'''). ''[http://iopscience.iop.org/0036-0279/25/2/R07 Programming a Computer to Play Chess]''. [http://iopscience.iop.org/0036-0279/25/2 Russian Mathematical Surveys, Vol. 25], pp. 221-262.</ref> . Bitboards were used in [[Kaissa]] and in [[Chess (Program)|Chess]]. The invention and publication of [[Rotated Bitboards]] by [[Robert Hyatt]] <ref>[[Robert Hyatt]] ('''1999'''). ''[http://www.craftychess.com/hyatt/bitmaps.html Rotated Bitmaps, a New Twist on an Old Idea]''. [[ICGA Journal#22_4|ICCA Journal, Vol. 22, No. 4]]</ref> and [[Peter Gillgasch]] with [[Ernst A. Heinz]] in the 90s was another milestone in the history of bitboards. [[Steffan Westcott|Steffan Westcott's]] innovations, too expensive on 32-bit [[x86]] processors, should be revisited with [[x86-64]] and [[SIMD and SWAR Techniques|SIMD instructions]] in mind. With the advent of fast 64-bit multiplication along with faster [[Memory|memory]], [[Magic Bitboards]] as proposed by [[Lasse Hansen]] <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]]</ref> and refined by [[Pradu Kannan]] <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> have surpassed Rotated.
+
The general approach of [[Mikhail R. Shura-Bura#Bitsets|bitsets]] was proposed by [[Mikhail R. Shura-Bura]] in 1952 <ref>[https://en.wikipedia.org/wiki/Lazar_Lyusternik Lazar A. Lyusternik], [http://www.mathnet.ru/php/person.phtml?personid=30351&option_lang=eng Aleksandr A. Abramov], [https://en.wikipedia.org/wiki/Victor_Shestakov Victor I. Shestakov], [[Mikhail R. Shura-Bura]] ('''1952'''). ''Programming for High-Speed Electronic Computers''. (Программирование для электронных счетных машин)</ref> <ref>[[Mathematician#Ershov|Andrey Ershov]], [[Mikhail R. Shura-Bura]] ('''1980'''). ''[http://ershov.iis.nsk.su/archive/eaindex.asp?lang=2&gid=910 The Early Development of Programming in the USSR]''. in [http://en.wikipedia.org/wiki/Nicholas_C._Metropolis Nicholas C. Metropolis] (ed.) ''[http://dl.acm.org/citation.cfm?id=578384 A History of Computing in the Twentieth Century]''. [https://en.wikipedia.org/wiki/Academic_Press Academic Press], [http://ershov.iis.nsk.su/archive/eaimage.asp?did=28792&fileid=173670 preprint pp. 43]</ref>. The bitboard method for holding a board game appears to have been invented also in 1952 by [[Christopher Strachey]] using White, Black and King bitboards in his checkers program for the [[Ferranti Mark 1]], and in the mid 1950's by [[Arthur Samuel]] in his checkers program as well. In computer chess, bitboards were first described by [[Georgy Adelson-Velsky]] et al. in 1967 <ref>[http://groups.google.com/group/rec.games.chess/browse_frm/thread/0e3a93f45ff07d31# Early Reference on Bit-Boards] by [[Tony Warnock]], [[Computer Chess Forums|rec.games.chess]], October 29, 1994</ref>, reprinted 1970 <ref>[[Georgy Adelson-Velsky]], [[Vladimir Arlazarov]], [[Alexander Bitman]], [[Alexander Zhivotovsky]], [[Anatoly Uskov]] ('''1970'''). ''[http://iopscience.iop.org/0036-0279/25/2/R07 Programming a Computer to Play Chess]''. [http://iopscience.iop.org/0036-0279/25/2 Russian Mathematical Surveys, Vol. 25], pp. 221-262.</ref> . Bitboards were used in [[Kaissa]] and in [[Chess (Program)|Chess]]. The invention and publication of [[Rotated Bitboards]] by [[Robert Hyatt]] <ref>[[Robert Hyatt]] ('''1999'''). ''[http://www.craftychess.com/hyatt/bitmaps.html Rotated Bitmaps, a New Twist on an Old Idea]''. [[ICGA Journal#22_4|ICCA Journal, Vol. 22, No. 4]]</ref> and [[Peter Gillgasch]] with [[Ernst A. Heinz]] in the 90s was another milestone in the history of bitboards. [[Steffan Westcott|Steffan Westcott's]] innovations, too expensive on 32-bit [[x86]] processors, should be revisited with [[x86-64]] and [[SIMD and SWAR Techniques|SIMD instructions]] in mind. With the advent of fast 64-bit multiplication along with faster [[Memory|memory]], [[Magic Bitboards]] as proposed by [[Lasse Hansen]] <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]]</ref> and refined by [[Pradu Kannan]] <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> have surpassed Rotated.
  
 
=Analysis=  
 
=Analysis=  
Line 61: Line 61:
 
* Bitboards can have a high information density.
 
* Bitboards can have a high information density.
 
* Single populated or even empty Bitboards have a low information density.
 
* Single populated or even empty Bitboards have a low information density.
* 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]].
+
* <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 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> .
 
* 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> .
Line 88: Line 88:
 
* [[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.pdf pdf] » [[Move Generation]], [[Shogi]]
 
* [[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.pdf pdf] » [[Move Generation]], [[Shogi]]
 
* [[James Glenn]], [http://www.cs.loyola.edu/~binkley/ David Binkley] ('''2008''') ''An Investigation of Hierarchical Bit Vectors''. [https://www.novapublishers.com/catalog/product_info.php?products_id=6555 New Topics in Theoretical Computer Science], [http://www.cs.loyola.edu/~binkley/papers/tcsrt08-hbit-vectors.pdf pdf]
 
* [[James Glenn]], [http://www.cs.loyola.edu/~binkley/ David Binkley] ('''2008''') ''An Investigation of Hierarchical Bit Vectors''. [https://www.novapublishers.com/catalog/product_info.php?products_id=6555 New Topics in Theoretical Computer Science], [http://www.cs.loyola.edu/~binkley/papers/tcsrt08-hbit-vectors.pdf pdf]
* [[Shi-Jim Yen]], [[Jung-Kuei Yang]] ('''2009'''). ''The Bitboard Design and Bitwise Computing in Connect Six''. [[Conferences#GPW|14th Game Programming Workshop]]
+
* [[Shi-Jim Yen]], [[Jung-Kuei Yang]] ('''2009'''). ''The Bitboard Design and Bitwise Computing in Connect Six''. [[Conferences#GPW|14th Game Programming Workshop]] » [[Connect6]]
 
* [[Fritz Reul]] ('''2009'''). ''New Architectures in Computer Chess''. Ph.D. Thesis, [https://pure.uvt.nl/ws/files/1098572/Proefschrift_Fritz_Reul_170609.pdf pdf]
 
* [[Fritz Reul]] ('''2009'''). ''New Architectures in Computer Chess''. Ph.D. Thesis, [https://pure.uvt.nl/ws/files/1098572/Proefschrift_Fritz_Reul_170609.pdf pdf]
 
==2010 ...==  
 
==2010 ...==  
Line 94: Line 94:
 
* [[Shi-Jim Yen]], [[Jung-Kuei Yang]], [[Kuo-Yuan Kao]], [[Tai-Ning Yang]] ('''2012'''). ''[http://www.sciencedirect.com/science/article/pii/S0950705112001293 Bitboard Knowledge Base System and Elegant Search Architectures for Connect6]''. [https://www.journals.elsevier.com/knowledge-based-systems/ Knowledge-Based Systems], Vol. 34 » [[Connect6]]
 
* [[Shi-Jim Yen]], [[Jung-Kuei Yang]], [[Kuo-Yuan Kao]], [[Tai-Ning Yang]] ('''2012'''). ''[http://www.sciencedirect.com/science/article/pii/S0950705112001293 Bitboard Knowledge Base System and Elegant Search Architectures for Connect6]''. [https://www.journals.elsevier.com/knowledge-based-systems/ Knowledge-Based Systems], Vol. 34 » [[Connect6]]
 
* [[Cameron Browne]], [[Stephen Tavener]] ('''2013'''). ''[http://www.aifactory.co.uk/newsletter/2012_02_fast_lane.htm Life in the Fast Lane]''. [[AI Factory]] »  [http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life Conway's Game of Life] within a [[Bitboards|Bitboard]]
 
* [[Cameron Browne]], [[Stephen Tavener]] ('''2013'''). ''[http://www.aifactory.co.uk/newsletter/2012_02_fast_lane.htm Life in the Fast Lane]''. [[AI Factory]] »  [http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life Conway's Game of Life] within a [[Bitboards|Bitboard]]
 +
* [[Jung-Kuei Yang]], [https://dblp.uni-trier.de/pers/hd/t/Tseng:Ping=Jung Ping-Jung Tseng] ('''2013'''). ''[https://ieeexplore.ieee.org/document/6783902 Bitboard Connection Code Design for Connect6]''. [[TAAI 2013]] » [[Connect6]]
 
* [[Cameron Browne]] ('''2014'''). ''Bitboard Methods for Games''. [[ICGA Journal#37_2|ICGA Journal, Vol. 37, No. 2]]
 
* [[Cameron Browne]] ('''2014'''). ''Bitboard Methods for Games''. [[ICGA Journal#37_2|ICGA Journal, Vol. 37, No. 2]]
 +
* [[Yen-Chi Chen]], [[Shun-Shii Lin]] ('''2019'''). ''A fast nonogram solver that won the TAAI 2017 and ICGA 2018 tournaments''. [[ICGA Journal#41_1|ICGA Journal, Vol. 41, No. 1]] » [[Nonogram]]
  
 
=Forum Posts=  
 
=Forum Posts=  
Line 116: Line 118:
 
==2005 ...==  
 
==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=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.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.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/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=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]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=26527 Bitboard techniques in Xiangqi] by [[Harm Geert Muller]], [[CCC]], February 12, 2009 » [[Chinese Chess]]
Line 128: Line 133:
 
==2015 ...==
 
==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=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=60007 M42 - A C++ library for Bitboard attack mask generation] by [[Syed Fahad]], [[CCC]], April 30, 2016  
 
* [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=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/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
  
 
=Viewer & Calculator=  
 
=Viewer & Calculator=  
 
* [[Bibob]]
 
* [[Bibob]]
* [http://cinnamonchess.altervista.org/bitboard_calculator/Calc.html Bitboard Calculator] by [[Giuseppe Cannella]]
+
* [https://gekomad.github.io/Cinnamon/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.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]]
 
* [http://www.chess2u.com/t2159-new-free-tool-bitboards-helper New free tool : Bitboards Helper] by [[Julien Marcel]]
Line 150: Line 161:
 
* [http://labraj.uni-mb.si/en/Position_Representation Position Representation - Computer Architecture and Languages Laboratory], [[University of Maribor]]
 
* [http://labraj.uni-mb.si/en/Position_Representation Position Representation - Computer Architecture and Languages Laboratory], [[University of Maribor]]
 
* [http://stackoverflow.com/questions/tagged/bitboard Newest 'bitboard' Questions] - [http://en.wikipedia.org/wiki/Stack_Overflow Stack Overflow]
 
* [http://stackoverflow.com/questions/tagged/bitboard Newest 'bitboard' Questions] - [http://en.wikipedia.org/wiki/Stack_Overflow Stack Overflow]
 +
* [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]
 +
: {{#evu:https://www.youtube.com/watch?v=srfRiWZcCg4|alignment=left|valignment=top}}
  
 
=References=  
 
=References=  
 
<references />
 
<references />
 
 
'''[[Board Representation|Up one level]]'''
 
'''[[Board Representation|Up one level]]'''
 +
[[Category:Samuel Bak]]
 +
[[Category:Flottmann]]
 +
[[Category:Industrial Heritage Trail]]
 +
[[Category:Music]]

Revision as of 19:46, 25 February 2021

Home * Board Representation * Bitboards

Samuel Bak - Boards Meeting [1]

Bitboards,
also called bitsets or bitmaps, are among other things used to represent the board inside a chess program in a piece centric manner. Bitboards, are in essence, finite sets of up to 64 elements - all the squares of a chessboard, one bit per square. Other board games with greater board sizes may be use set-wise representations as well [2], but classical chess has the advantage that one 64-bit word or register covers the whole board. Even more bitboard friendly is Checkers with 32-bit bitboards and less piece-types than chess [3] [4].

The Board of Sets

To represent the board we typically need one bitboard for each piece-type and color - likely encapsulated inside a class or structure, or as an array of bitboards as part of a position object. A one-bit inside a bitboard implies the existence of a piece of this piece-type on a certain square - one to one associated by the bit-position.

Bitboard Basics

Of course bitboards are not only about the existence of pieces - it is a general purpose, set-wise data-structure fitting in one 64-bit register. For example, a bitboard can represent things like attack- and defend sets, move-target sets and so on.

General Bitboard Techniques

The fundamental bitboard basics.

Pattern and Attacks

This is basically about chess, how to calculate attack-sets and various pattern for evaluation and move generation purposes.

Move Generation Issues

Bitboard aspects on move generation and static exchange evaluation (SEE).

Miscellaneous

Defining Bitboards

To be aware of their scalar 64-bit origin, we use so far a type defined unsigned integer U64 in our C or C++ source snippets, the scalar 64-bit long in Java. Feel free to define a distinct type or wrap U64 into classes for better abstraction and type-safety during compile time. The macro C64 will append a suffix to 64-bit constants as required by some compilers:

typedef unsigned __int64 U64;    // for the old microsoft compilers 
typedef unsigned long long  U64; // supported by MSC 13.00+ and C99 
#define C64(constantU64) constantU64##ULL

Bitboard-History

The general approach of bitsets was proposed by Mikhail R. Shura-Bura in 1952 [5] [6]. The bitboard method for holding a board game appears to have been invented also in 1952 by Christopher Strachey using White, Black and King bitboards in his checkers program for the Ferranti Mark 1, and in the mid 1950's by Arthur Samuel in his checkers program as well. In computer chess, bitboards were first described by Georgy Adelson-Velsky et al. in 1967 [7], reprinted 1970 [8] . Bitboards were used in Kaissa and in Chess. The invention and publication of Rotated Bitboards by Robert Hyatt [9] and Peter Gillgasch with Ernst A. Heinz in the 90s was another milestone in the history of bitboards. Steffan Westcott's innovations, too expensive on 32-bit x86 processors, should be revisited with x86-64 and SIMD instructions in mind. With the advent of fast 64-bit multiplication along with faster memory, Magic Bitboards as proposed by Lasse Hansen [10] and refined by Pradu Kannan [11] have surpassed Rotated.

Analysis

The use of bitboards has spawned numerous discussions about their costs and benefits. The major points to consider are:

  • Bitboards can have a high information density.
  • Single populated or even empty Bitboards have a low information density.
  • Bitboards are weak in answering questions like what piece if any resides on square x. One reason to keep a redundant mailbox board representation with some additional update costs during make/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.
  • Bitboards are rather handicapped on 32 bit processors, as each bitwise computation must be split into two or more instructions [12] . As most modern processors are now 64 bit, this point is somewhat diminished [13] .
  • Bitboards often rely on bit-twiddling and various optimization tricks and special instructions for certain hardware architectures, such as bitscan and population count. Optimal code requires machine dependent header-files in C/C++. Portable code is likely not optimal for all processors.
  • Some operations on bitboards are less general, f.i. shifts. This requires additional code overhead.

Publications

1970 ...

1980 ...

1990 ...

2000 ...

2010 ...

Forum Posts

1994

1995 ...

2000 ...

2005 ...

Re: Yet another new bitboard move generation method by Harm Geert Muller, Winboard Forum, October 01, 2006 [16]

2010 ...

2015 ...

2020 ...

Viewer & Calculator

External Links

Kerstin Fabry, Christian Ribbe, Elmar Dissinger, Martin Siehoff, Carlotta Ribbe, Ludger Bollinger

References

  1. Samuel Bak - Boards Meeting, Oil on Canvas, 39 x 32". Chess in the Art of Samuel Bak, Center for Holocaust & Genocide Studies, University of Minnesota
  2. Reijer Grimbergen (2007). Using Bitboards for Move Generation in Shogi. ICGA Journal, Vol. 30, No. 1, pdf
  3. Checker Bitboards Tutorial by Jonathan Kreuzer
  4. Checkers Bitboard representation by Pranav Deshpande, CCC, July 02, 2017
  5. Lazar A. Lyusternik, Aleksandr A. Abramov, Victor I. Shestakov, Mikhail R. Shura-Bura (1952). Programming for High-Speed Electronic Computers. (Программирование для электронных счетных машин)
  6. Andrey Ershov, Mikhail R. Shura-Bura (1980). The Early Development of Programming in the USSR. in Nicholas C. Metropolis (ed.) A History of Computing in the Twentieth Century. Academic Press, preprint pp. 43
  7. Early Reference on Bit-Boards by Tony Warnock, rec.games.chess, October 29, 1994
  8. Georgy Adelson-Velsky, Vladimir Arlazarov, Alexander Bitman, Alexander Zhivotovsky, Anatoly Uskov (1970). Programming a Computer to Play Chess. Russian Mathematical Surveys, Vol. 25, pp. 221-262.
  9. Robert Hyatt (1999). Rotated Bitmaps, a New Twist on an Old Idea. ICCA Journal, Vol. 22, No. 4
  10. Fast(er) bitboard move generator by Lasse Hansen, Winboard Forum, June 14, 2006
  11. List of magics for bitboard move generation by Pradu Kannan, Winboard Forum, August 23, 2006
  12. Efficient Bitboard Implementation on 32-bit Architecture by Roberto Waldteufel, CCC, October 25, 1998
  13. Speedup by bitboards by Onno Garms, Winboard Forum, July 13, 2007
  14. Bitboard user's information request by Robert Hyatt, CCC, October 05, 1999
  15. Robert Hyatt (1999). Rotated Bitmaps, a New Twist on an Old Idea. ICCA Journal, Vol. 22, No. 4
  16. Re: multi-dimensional piece/square tables by Tony P., CCC, January 28, 2020
  17. GitHub - sinandredemption/M42: C++ Library for Bitboard Attack Mask Generation
  18. Flottmann-Hallen in Herne, North Rhine-Westphalia, Germany, part of The Industrial Heritage Trail of the Ruhr area

Up one level