Difference between revisions of "Bitboards"
GerdIsenberg (talk | contribs) m |
GerdIsenberg (talk | contribs) m (omit leading table) |
||
Line 1: | Line 1: | ||
'''[[Main Page|Home]] * [[Board Representation]] * Bitboards''' | '''[[Main Page|Home]] * [[Board Representation]] * Bitboards''' | ||
− | + | ||
− | + | '''Bitboards''',[[File:BoardsMeeting.jpg|border|right|thumb|[[Arts#Bak|Samuel Bak]] - Boards Meeting <ref> [[Arts#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], [https://en.wikipedia.org/wiki/University_of_Minnesota University of Minnesota]</ref>]] | |
− | [[File:BoardsMeeting.jpg|border|thumb|[[Arts#Bak|Samuel Bak]] - Boards Meeting <ref> [[Arts#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], [https://en.wikipedia.org/wiki/University_of_Minnesota University of Minnesota]</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.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.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= | =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. |
Revision as of 07:47, 23 March 2018
Home * Board Representation * Bitboards
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].
Contents
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.
- Pawn Pattern and Properties
- Knight Pattern
- King Pattern
- Sliding Piece Attacks including rotated and magic bitboards
- Square Attacked By
- X-ray Attacks
- Checks and Pinned Pieces
- Design Principles
Move Generation Issues
Bitboard aspects on move generation and static exchange evaluation (SEE).
- Bitboard Serialization
- Pieces versus Directions
- DirGolem
- SEE - The Swap Algorithm
- Attack and Defend Maps
Miscellaneous
- Backtracking - Eight Queens puzzle with Bitboards
- De Bruijn Sequence Generator
- Quad-Bitboards
- Traversing Subsets of a Set
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 ...
- 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.
- David Slate, Larry Atkin (1977). CHESS 4.5 - The Northwestern University Chess Program. Chess Skill in Man and Machine, reprinted (1988) in Computer Chess Compendium » Chess
1980 ...
- Zdenek Zdráhal, Ivan Bratko, Alen Shapiro (1981). Recognition of Complex Patterns Using Cellular Arrays. The Computer Journal, Vol. 24, No. 3, pp. 263-270
- Stuart Cracraft (1984). Bitmap move generation in Chess. ICCA Journal, Vol. 7, No. 3
- Burton Wendroff (1985). Attack Detection and Move Generation on the X-MP/48. ICCA Journal, Vol. 8, No. 2
- Arch D. Robison, Brian J. Hafner, Steven Skiena (1989). Eight Pieces Cannot Cover a Chess Board. The Computer Journal, Vol. 32, No. 6, pdf
1990 ...
- Ernst A. Heinz (1997). How DarkThought Plays Chess. ICCA Journal, Vol. 20, No. 3 » DarkThought
- Robert Hyatt (1999). Rotated Bitmaps, a New Twist on an Old Idea. ICCA Journal, Vol. 22, No. 4 » Rotated Bitboards [14]
2000 ...
- David Rasmussen (2004). Parallel Chess Searching and Bitboards. Master's thesis, ps » Parallel Search
- Borko Bošković, Sašo Greiner, Janez Brest, Viljem Žumer (2005). The Representation of Chess Game. Proceedings of the 27th International Conference on Information Technology Interfaces
- Pablo San Segundo, Ramón Galán (2005). Bitboards: A New Approach. AIA 2005
- Pablo San Segundo, Ramón Galán, Fernando Matía, Diego Rodríguez-Losada, Agustín Jiménez (2006). Efficient Search Using Bitboard Models. ICTAI 2006, pdf
- Fridel Fainshtein (2006). An Orthodox k-Move Problem-Composer for Chess Directmates. M.Sc. thesis, Bar-Ilan University, pdf, Appendix D - 64-bit Representation, pp. 105
- Fridel Fainshtein, Yaakov HaCohen-Kerner (2006). A Chess Composer of Two-Move Mate Problems. ICGA Journal, Vol. 29, No. 1, pdf, Appendix E: 64-bit representation, pp. 22
- Reijer Grimbergen (2007). Using Bitboards for Move Generation in Shogi. ICGA Journal, Vol. 30, No. 1, pdf » Move Generation, Shogi
- James Glenn, David Binkley (2008) An Investigation of Hierarchical Bit Vectors. New Topics in Theoretical Computer Science, pdf
- Shi-Jim Yen, Jung-Kuei Yang (2009). The Bitboard Design and Bitwise Computing in Connect Six. 14th Game Programming Workshop
- Fritz Reul (2009). New Architectures in Computer Chess. Ph.D. Thesis, pdf
2010 ...
- Stefano Carlini (2010). Arimaa, a New Challenge for Artificial Intelligence. M.Sc. thesis, University of Modena and Reggio Emilia, pdf » Chapter 4, Bitboards in Arimaa
- Shi-Jim Yen, Jung-Kuei Yang, Kuo-Yuan Kao, Tai-Ning Yang (2012). Bitboard Knowledge Base System and Elegant Search Architectures for Connect6. Knowledge-Based Systems, Vol. 34 » Connect6
- Cameron Browne, Stephen Tavener (2013). Life in the Fast Lane. AI Factory » Conway's Game of Life within a Bitboard
- Cameron Browne (2014). Bitboard Methods for Games. ICGA Journal, Vol. 37, No. 2
Forum Posts
1994
- bitboard move generation by Robert Hyatt, rgc, October 25, 1994
- bitboard move generator by Joël Rivat, rgc, November 13, 1994
- bitboard position evaluations by Robert Hyatt, rgc, November 17, 1994 » Evaluation
1995 ...
- Chess programming using bitboards by Joël Rivat, rgcc, August 18, 1995
- Bit Board Bonkers?? by Dave, rec.games.chess.computer, July 28, 1997
- Efficient Bitboard Implementation on 32-bit Architecture by Roberto Waldteufel, CCC, October 25, 1998
- Bitboard question by Werner Inmann, CCC, December 02, 1998
- Bitboards by Frank Phillips, CCC, December 05, 1998
- bitboards in java? by vitor, CCC, April 06, 1999 » Java
- BitBoards by Frank Phillips, CCC, May 29, 1999
- Bitboard user's information request by Robert Hyatt, CCC, October 05, 1999 » Rotated Bitboards [15]
2000 ...
- To bitboard or not to bitboard? by Tord Romstad, CCC, August 30, 2003
- How important are Bitboards? by Martin Schreiber, CCC, February 29, 2004
- questions for bitboard experts by Tord Romstad, Winboard Forum, November 06, 2004 » In Between, Piece-Lists
2005 ...
- Bitboard question by Tord Romstad, Winboard Forum, March 14, 2006
- Speedup with bitboards on 64-bit CPUs by Tord Romstad, CCC, April 27, 2007
- Speedup by bitboards by Onno Garms, Winboard Forum, July 13, 2007
- BitBoard representations of the board by Uri Blass, CCC, October 14, 2007
- Bitboards / move generation on larger boards by Gregory Strong, CCC, January 09, 2009
- Bitboard techniques in Xiangqi by Harm Geert Muller, CCC, February 12, 2009 » Chinese Chess
- Bitboards using 2 DOUBLE's ? by Carey, CCC, June 02, 2009 » Double
2010 ...
- Bitboard implementation, how much time? by Ed Schröder, CCC, January 22, 2012
- 64 bits for 64 squares ? by Thomas Petzke, mACE Chess, April 28, 2013 » Population Count
- Bitboard Tricks for Large Chess Variants by Ed Trice, CCC, November 01, 2014
2015 ...
- Bitboard database code samples by Steven Edwards, CCC, May 25, 2015 » Symbolic
- M42 - A C++ library for Bitboard attack mask generation by Syed Fahad, CCC, April 30, 2016 [16]
- Checkers Bitboard representation by Pranav Deshpande, CCC, July 02, 2017 » Checkers
- Bitboards and Java by Fred Hamilton, CCC, November 14, 2017 » Java
Viewer & Calculator
- Bibob
- Bitboard Calculator by Giuseppe Cannella
- Free Chess Bitboard Viewer - Computer Chess Programming by Steve Maughan
- New free tool : Bitboards Helper by Julien Marcel
External Links
- Bitboards from Wikipedia
- Bit-Array from Wikipedia
- Bitboard-History from Wikipedia
- Chess board representations by Robert Hyatt
- Bitboards (aka bitmaps) by Tom Likens
- An Introduction to BITBOARDS by Franck Zibi
- Bitwise Optimization in Java: Bitfields, Bitboards, and Beyond by Glen Pepicelli, 2005, O'Reilly's OnJava.com » Java, Bit-Twiddling
- Chess and Bitboards by Peter Keller
- Bit functions for Delphi by Andreas Herrmann » Delphi
- Position Representation - Computer Architecture and Languages Laboratory, University of Maribor
- Newest 'bitboard' Questions - Stack Overflow
References
- ↑ 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
- ↑ Reijer Grimbergen (2007). Using Bitboards for Move Generation in Shogi. ICGA Journal, Vol. 30, No. 1, pdf
- ↑ Checker Bitboards Tutorial by Jonathan Kreuzer
- ↑ Checkers Bitboard representation by Pranav Deshpande, CCC, July 02, 2017
- ↑ Lazar A. Lyusternik, Aleksandr A. Abramov, Victor I. Shestakov, Mikhail R. Shura-Bura (1952). Programming for High-Speed Electronic Computers. (Программирование для электронных счетных машин)
- ↑ 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
- ↑ Early Reference on Bit-Boards by Tony Warnock, rec.games.chess, October 29, 1994
- ↑ 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.
- ↑ Robert Hyatt (1999). Rotated Bitmaps, a New Twist on an Old Idea. ICCA Journal, Vol. 22, No. 4
- ↑ Fast(er) bitboard move generator by Lasse Hansen, Winboard Forum, June 14, 2006
- ↑ List of magics for bitboard move generation by Pradu Kannan, Winboard Forum, August 23, 2006
- ↑ Efficient Bitboard Implementation on 32-bit Architecture by Roberto Waldteufel, CCC, October 25, 1998
- ↑ Speedup by bitboards by Onno Garms, Winboard Forum, July 13, 2007
- ↑ Bitboard user's information request by Robert Hyatt, CCC, October 05, 1999
- ↑ Robert Hyatt (1999). Rotated Bitmaps, a New Twist on an Old Idea. ICCA Journal, Vol. 22, No. 4
- ↑ M42 by Syed Fahad