Bitboard
Encyclopedia
A bitboard is a data structure
commonly used in computer systems that play board game
s.
A bitboard, often used for boardgames such as chess
, checkers and othello
, is a specialization of the bitset data structure, where each bit represents a game position or state, designed for optimization of speed and/or memory or disk use in mass calculations. Bits in the same bitboard relate to each other in the rules of the game often forming a game position when taken together. Other bitboards are commonly used as masks to transform or answer queries about positions. The "game" may be any game-like system where information is tightly packed in a structured form with "rules" affecting how the individual units or pieces relate.
Bitboards are interesting because they allow the computer to answer some questions about game state with one logical operation. For example, if a chess program wants to know if the white player has any pawns in the center of the board (center four squares) it can just compare a bitboard for the player's pawns with one for the center of the board using a logical AND operation. If there are no center pawns then the result will be zero.
Query results can also be represented using bitboards. For example, the query "What are the squares between X and Y?" can be represented as a bitboard. These query results are generally pre-calculated, so that a program can simply retrieve a query result with one memory load.
However, as a result of the massive compression and encoding, bitboard programs are not easy for software developers to either write or debug.
For the more complicated game of chess, it appears the method was independently rediscovered later by the Kaissa
team in the Soviet Union
in the late 1960s, although not publicly documented, and again by the authors of the U.S. Northwestern University program "Chess
" in the early 1970s, and documented in 1977 in "Chess Skill in Man and Machine".
operations available on nearly all CPUs that complete in one cycle and are full pipelined and cached etc. Nearly all CPUs have AND
, OR
, NOR
, and XOR. Many CPUs have additional bit instructions, such as finding the "first" bit, that make bitboard operations even more efficient. If they do not have instructions well known algorithms can perform some "magic" transformations that do these quickly.
Furthermore, modern CPUs have instruction pipeline
s that queue instructions for execution. A processor with multiple execution units can perform more than one instruction per cycle if more than one instruction is available in the pipeline. Branching (the use of conditionals like if) makes it harder for the processor to fill its pipeline(s) because the CPU can't tell what it needs to do in advance. Too much branching makes the pipeline less effective and potentially reduces the number of instructions the processor can execute per cycle. Many bitboard operations require fewer conditionals and therefore increase pipelining and make effective use of multiple execution units on many CPUs.
CPUs have a bit width which they are designed toward and can carry out bitwise operations in one cycle in this width. So, on a 64-bit or more CPU, 64-bit operations can occur in one instruction. There may be support for higher or lower width instructions. Many 32-bit CPUs may have some 64-bit instructions and those may take more than one cycle or otherwise be handicapped compared to their 32-bit instructions.
If the bitboard is larger than the width of the instruction set, then a performance hit will be the result. So a program using 64-bit bitboards would run faster on a real 64-bit processor than on a 32-bit processor.
There are twelve types of pieces, and each type gets its own bitboard. Black pawns get a board, white pawns, etc. Together these twelve boards can represent a position. Some trivial information also needs to be tracked elsewhere; the programmer may use boolean variables for whether each side is in check, can castle, etc.
Constants are likely available, such as WHITE_SQUARES, BLACK_SQUARES, FILE_A, RANK_4 etc. More interesting ones might include CENTER, CORNERS, CASTLE_SQUARES, etc.
Examples of variables would be WHITE_ATTACKING, ATTACKED_BY_PAWN, WHITE_PASSED_PAWN, etc.
These bitboards rotate the bitboard positions by 90 degrees, 45 degrees, and/or 315 degrees. A typical bitboard will have one byte per rank of the chess board. With this bitboard it's easy to determine rook attacks across a rank, using a table indexed by the occupied square and the occupied positions in the rank (because rook attacks stop at the first occupied square). By rotating the bitboard 90 degrees, rook attacks across a file can be examined the same way. Adding bitboards rotated 45 degrees and 315 degrees produces bitboards in which the diagonals are easy to examine. The queen can be examined by combining rook and bishop attacks. Rotated bitboards appear to have been developed separately and (essentially) simultaneously by the developers of the DarkThought and Crafty
programs. The Rotated bitboard is hard to understand if one doesn't have a firm grasp of normal bitboards and why they work. Rotated bitboards should be viewed as a clever but advanced optimization.
link not working please update
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
commonly used in computer systems that play board game
Board game
A board game is a game which involves counters or pieces being moved on a pre-marked surface or "board", according to a set of rules. Games may be based on pure strategy, chance or a mixture of the two, and usually have a goal which a player aims to achieve...
s.
A bitboard, often used for boardgames such as chess
Chess
Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...
, checkers and othello
Reversi
Reversi is a board game involving abstract strategy and played by two players on a board with 8 rows and 8 columns and a set of distinct pieces for each side. Pieces typically are disks with a light and a dark face, each face belonging to one player...
, is a specialization of the bitset data structure, where each bit represents a game position or state, designed for optimization of speed and/or memory or disk use in mass calculations. Bits in the same bitboard relate to each other in the rules of the game often forming a game position when taken together. Other bitboards are commonly used as masks to transform or answer queries about positions. The "game" may be any game-like system where information is tightly packed in a structured form with "rules" affecting how the individual units or pieces relate.
Short description
Bitboards are used in many of the world's best chess playing programs. They help the programs analyze chess positions with few CPU instructions and hold a massive number of positions in memory efficiently.Bitboards are interesting because they allow the computer to answer some questions about game state with one logical operation. For example, if a chess program wants to know if the white player has any pawns in the center of the board (center four squares) it can just compare a bitboard for the player's pawns with one for the center of the board using a logical AND operation. If there are no center pawns then the result will be zero.
Query results can also be represented using bitboards. For example, the query "What are the squares between X and Y?" can be represented as a bitboard. These query results are generally pre-calculated, so that a program can simply retrieve a query result with one memory load.
However, as a result of the massive compression and encoding, bitboard programs are not easy for software developers to either write or debug.
History
The bitboard method for holding a board game appears to have been invented in the mid-1950s, by Arthur Samuel and was used in his checkers program. The method was published in 1959 as "Some Studies in Machine Learning Using the Game of Checkers" in the IBM Journal of Research and Development.For the more complicated game of chess, it appears the method was independently rediscovered later by the Kaissa
Kaissa
Kaissa was a chess program developed in the Soviet Union in the 1960s. It was named so after the chess goddess Caissa. Kaissa became the first world computer chess champion in 1974 in Stockholm.- History :...
team in the Soviet Union
Soviet Union
The Soviet Union , officially the Union of Soviet Socialist Republics , was a constitutionally socialist state that existed in Eurasia between 1922 and 1991....
in the late 1960s, although not publicly documented, and again by the authors of the U.S. Northwestern University program "Chess
Chess (Northwestern University)
Chess was a pioneering chess program from the 1970s, authored by Larry Atkin and David Slate at Northwestern University. Chess ran on Control Data Corporation's line of supercomputers. It dominated the first computer chess tournaments, such as the World Computer Chess Championship and ACM's North...
" in the early 1970s, and documented in 1977 in "Chess Skill in Man and Machine".
Description for all games or applications
A bitboard or bit field is a format that stuffs a whole group of related boolean variables into the same integer, typically representing positions on a board game. Each bit is a position, and when the bit is positive, a property of that position is true. In chess, for example, there would be a bitboard for black knights. There would be 64-bits where each bit represents a chess square. Another bitboard might be a constant representing the center four squares of the board. By comparing the two numbers with a bitwise logical AND instruction, we get a third bitboard which represents the black knights on the center four squares, if any. This format is generally more CPU and memory friendly than others.Pros
The advantage of the bitboard representation is that it takes advantage of the essential logical bitwiseBitwise
Bitwise may refer to:* Bitwise operation, a basic function in computer programming* Bitwise IIT Kharagpur, an algorithm-intensive programming contest by CSE IIT Kharagpur...
operations available on nearly all CPUs that complete in one cycle and are full pipelined and cached etc. Nearly all CPUs have AND
Logical conjunction
In logic and mathematics, a two-place logical operator and, also known as logical conjunction, results in true if both of its operands are true, otherwise the value of false....
, OR
Logical disjunction
In logic and mathematics, a two-place logical connective or, is a logical disjunction, also known as inclusive disjunction or alternation, that results in true whenever one or more of its operands are true. E.g. in this context, "A or B" is true if A is true, or if B is true, or if both A and B are...
, NOR
Logical NOR
In boolean logic, logical nor or joint denial is a truth-functional operator which produces a result that is the negation of logical or. That is, a sentence of the form is true precisely when neither p nor q is true—i.e. when both of p and q are false...
, and XOR. Many CPUs have additional bit instructions, such as finding the "first" bit, that make bitboard operations even more efficient. If they do not have instructions well known algorithms can perform some "magic" transformations that do these quickly.
Furthermore, modern CPUs have instruction pipeline
Instruction pipeline
An instruction pipeline is a technique used in the design of computers and other digital electronic devices to increase their instruction throughput ....
s that queue instructions for execution. A processor with multiple execution units can perform more than one instruction per cycle if more than one instruction is available in the pipeline. Branching (the use of conditionals like if) makes it harder for the processor to fill its pipeline(s) because the CPU can't tell what it needs to do in advance. Too much branching makes the pipeline less effective and potentially reduces the number of instructions the processor can execute per cycle. Many bitboard operations require fewer conditionals and therefore increase pipelining and make effective use of multiple execution units on many CPUs.
CPUs have a bit width which they are designed toward and can carry out bitwise operations in one cycle in this width. So, on a 64-bit or more CPU, 64-bit operations can occur in one instruction. There may be support for higher or lower width instructions. Many 32-bit CPUs may have some 64-bit instructions and those may take more than one cycle or otherwise be handicapped compared to their 32-bit instructions.
If the bitboard is larger than the width of the instruction set, then a performance hit will be the result. So a program using 64-bit bitboards would run faster on a real 64-bit processor than on a 32-bit processor.
Cons
Some queries are going to take longer than they would with perhaps arrays, so bitboards are generally used in conjunction with array boards in chess programs.Pros
Bitboards are extremely compact. Since only a very small amount of memory is required to represent a position or a mask, more positions can find their way into registers, full speed cache, Level 2 cache, etc. In this way, compactness translates into better performance (on most machines). Also on some machines this might mean that more positions can be stored in main memory before going to disk.Cons
For some games writing a suitable bitboard engine requires a fair amount of source code that will be longer than the straight forward implementation. For limited devices (like cell phones) with a limited number of registers or processor instruction cache, this can cause a problem. For full-sized computers it may cause cache misses between level one and level two cache. This is a potential problem—not a major drawback. Most machines will have enough instruction cache so that this isn't an issue.Source code
Bitboard source code is very dense and sometimes hard to read. It must be documented very well.Standard
The first bit usually represents the square a1 (the lower left square), and the 64th bit represents the square h8 (the diagonally opposite square).There are twelve types of pieces, and each type gets its own bitboard. Black pawns get a board, white pawns, etc. Together these twelve boards can represent a position. Some trivial information also needs to be tracked elsewhere; the programmer may use boolean variables for whether each side is in check, can castle, etc.
Constants are likely available, such as WHITE_SQUARES, BLACK_SQUARES, FILE_A, RANK_4 etc. More interesting ones might include CENTER, CORNERS, CASTLE_SQUARES, etc.
Examples of variables would be WHITE_ATTACKING, ATTACKED_BY_PAWN, WHITE_PASSED_PAWN, etc.
Rotated
"Rotated" bitboards are usually used in programs that use bitboards. Rotated bitboards make certain operations more efficient. While engines are simply referred to as "rotated bitboard engines," this is a misnomer as rotated boards are used in addition to normal boards making these hybrid standard/rotated bitboard engines.These bitboards rotate the bitboard positions by 90 degrees, 45 degrees, and/or 315 degrees. A typical bitboard will have one byte per rank of the chess board. With this bitboard it's easy to determine rook attacks across a rank, using a table indexed by the occupied square and the occupied positions in the rank (because rook attacks stop at the first occupied square). By rotating the bitboard 90 degrees, rook attacks across a file can be examined the same way. Adding bitboards rotated 45 degrees and 315 degrees produces bitboards in which the diagonals are easy to examine. The queen can be examined by combining rook and bishop attacks. Rotated bitboards appear to have been developed separately and (essentially) simultaneously by the developers of the DarkThought and Crafty
Crafty
Crafty is a chess program written by UAB professor Dr. Robert Hyatt. It is directly derived from Cray Blitz, winner of the 1983 and 1986 World Computer Chess Championships....
programs. The Rotated bitboard is hard to understand if one doesn't have a firm grasp of normal bitboards and why they work. Rotated bitboards should be viewed as a clever but advanced optimization.
Magics
Magic move bitboard generation is a new and fast alternative to rotated move bitboard generators. These are also more versatile than rotated move bitboard generators because the generator can be used independently from any position. The basic idea is that you can use a multiply, right-shift hashing function to index a move database, which can be as small as 1.5K. A speedup is gained because no rotated bitboards need to be updated, and because the lookups are more cache-friendly.Other bitboards
Many other games besides chess benefit from bitboards.- In Connect FourConnect FourConnect Four is a two-player game in which the players first choose a color and then take turns dropping their colored discs from the top into a seven-column, six-row vertically-suspended grid...
, they allow for very efficient testing for four consecutive discs, by just two shift+and operations per direction. - In the Conway's Game of LifeConway's Game of LifeThe Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970....
, they are a possible alternative to arrays. - Othello/Reversi (see the ReversiReversiReversi is a board game involving abstract strategy and played by two players on a board with 8 rows and 8 columns and a set of distinct pieces for each side. Pieces typically are disks with a light and a dark face, each face belonging to one player...
article).
See also
- Bit array
- Bit fieldBit fieldA bit field is a common idiom used in computer programming to compactly store multiple logical values as a short series of bits where each of the single bits can be addressed separately. A bit field is most commonly used to represent integral types of known, fixed bit-width. A well-known usage of...
- Bit manipulationBit manipulationBit manipulation is the act of algorithmically manipulating bits or other pieces of data shorter than a word. Programming tasks that require bit manipulation include low-level device control, error detection and correction algorithms, data compression, encryption algorithms, and optimization...
- Bit twiddlerBit twiddlerIn computing, bit twiddler may refer to:* A piece of source code that does bit twiddling, which may mean:** Doing bit manipulation;** Interacting with computer hardware, especially when using a bit-banging technique;...
- Bitwise operationBitwise operationA bitwise operation operates on one or more bit patterns or binary numerals at the level of their individual bits. This is used directly at the digital hardware level as well as in microcode, machine code and certain kinds of high level languages...
- Board representation (chess)
- Boolean algebra (logic)
- Instruction setInstruction setAn instruction set, or instruction set architecture , is the part of the computer architecture related to programming, including the native data types, instructions, registers, addressing modes, memory architecture, interrupt and exception handling, and external I/O...
- Instruction pipelineInstruction pipelineAn instruction pipeline is a technique used in the design of computers and other digital electronic devices to increase their instruction throughput ....
- OpcodeOpcodeIn computer science engineering, an opcode is the portion of a machine language instruction that specifies the operation to be performed. Their specification and format are laid out in the instruction set architecture of the processor in question...
- BytecodeBytecodeBytecode, also known as p-code , is a term which has been used to denote various forms of instruction sets designed for efficient execution by a software interpreter as well as being suitable for further compilation into machine code...
Checkers
- Checkers Bitboard Tutorial by Jonathan Kreuzer
Articles
- Programming area of the Beowulf project
- Heinz, Ernst A. How DarkThought plays chess. ICCA Journal, Vol. 20(3), pp. 166-176, Sept. 1997
- Laramee, Francois-Dominic. Chess Programming Part 2: Data Structures.
- Verhelst, Paul. Chess Board Representations
- Hyatt, Robert. Chess program board representations
- Hyatt, Robert. Rotated bitmaps, a new twist on an old idea
- Frayn, Colin. How to implement bitboards in a chess engine (chess programming theory)
- Pepicelli, Glen. Bitfields, Bitboards, and Beyond -(Example of bitboards in the Java Language and a discussion of why this optimization works with the Java Virtual Machine (www.OnJava.com publisher: O'Reilly 2005))
- Magic Move-Bitboard Generation in Computer Chess. Pradyumna Kannan
Code examples
link not working please update
- http://www.cwi.nl/~tromp/c4/Connect4.java A 155 line java Connect-4 program demonstrating the use of bitboards.
Open source
- Beowulf Unix, Linux, Windows. Rotated bitboards.
- CraftyCraftyCrafty is a chess program written by UAB professor Dr. Robert Hyatt. It is directly derived from Cray Blitz, winner of the 1983 and 1986 World Computer Chess Championships....
See the Crafty article. Written in straight C. Rotated bitboards in the old versions, now uses magic bitboards. Strong. - GNU ChessGNU ChessGNU Chess is a computer program which plays a full game of chess against a human or other computer program.GNU Chess is one of the oldest computer chess programs for Unix-based computers and one of the earliest available with full source code....
See the GNU Chess Article. - StockfishStockfish (chess)Stockfish is an open source chess engine, developed by Tord Romstad, Joona Kiiski and Marco Costalba and licensed under the GNU General Public License version 3. The current version 2.1.1 is available as C++ source code, and also has precompiled versions for Microsoft Windows, Mac OS X Snow...
UCI chess engine ranking second in Elo as of 2010 - Gray Matter C++, rotated bitboards.
- KnightCapKnightCapKnightCap is an open source computer chess engine. Its primary author is Andrew Tridgell and it was created circa 1996. Major contributions have also been made by Jon Baxter and probably minor contributions by a few others....
GPL. ELO of 2300. - Pepito C. Bitboard, by Carlos del Cacho. Windows and Linux binaries as well as source available.
- Simontacci Rotated bitboards.
Othello
- A complete discussion of Othello (ReversiReversiReversi is a board game involving abstract strategy and played by two players on a board with 8 rows and 8 columns and a set of distinct pieces for each side. Pieces typically are disks with a light and a dark face, each face belonging to one player...
) engines with some source code including an Othello bitboard in C and assembly.