A diagram is needed here

A bitboard is a data structure commonly used in computer systems that play board games. Image File history File links Diagram_Needed. ... Image File history File links Diagram_Needed. ... A binary tree, a simple type of branching linked data structure. ... Game AI refers to techniques used in computer and video games to produce the illusion of intelligence in the behavior of non-player characters (NPCs). ... A board game is a game played with counters or pieces that are placed on, removed from, or moved across a board (a premarked surface, usually specific to that game). ...

Definition

A bitboard, often used for boardgames such as chess, checkers and othello, is a type of data structure and bitset, 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. Chess (Sanskrit: Chaturanga) is an abstract strategy board game and mental sport for two players. ... starting position on a 10×10 draughts board Draughts, also known as checkers, is a group of mental sport board games between two players which involve diagonal moves of uniform pieces and mandatory captures by jumping over the enemys pieces. ... Reversi and Othello are names for a strategic boardgame which involves play by two parties on an eight-by-eight square grid with pieces that have two distinct sides. ...

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 1950's, 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 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". 1960 (MCMLX) was a leap year starting on Friday (the link is to a full 1960 calendar). ...

Description for all games or applications

Main article: Bit field

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. A bit field is a common idiom used in computer programming to store a set of Boolean datatype flags compactly. ...

At some point in any hardware and software system, the CPU must do the actual work. The idea behind the bitboard is to put software representations in a very CPU friendly format. In typical programming, a lot of information or memory bandwidth is wasted. For example, a chess program might want to know what number turn it is. The programmer assigned a variable to track the turn number. If she is using a 32-bit computer, she is able to track chess games up to billions of moves long. However, real chess games are almost always less than 200 moves and would only require a few bits to represent their turn numbers. The programmer has "wasted" a number of bits in the 32-bit number. She could easily have gotten by with only 16-bits or even 8-bits. Let's say the programmer wants to save memory. She could take some of those 32-bits and use them to track other information. Can white still castle? She can use the 17th bit to answer this yes or no question.

The programmer is now using one variable as two. This is not what she learned in her Computer Science 101 class. What has she gained? Well actually, nothing at all. She got to save four bytes; however, she had to write code to decode her special double variable into separate ones and back which took a lot more than four bytes. This is why typical languages are designed to "waste" bits in the first place--the cure is worse than the disease.

One thing she did gain is that some operations are faster. If she wants to know if it is turn forty and white has castled, she can answer this in one comparison rather than two.

General technical advantages and disadvantages

Processor use

Pros

The advantage of the bitboard representation is that it takes advantage of the essential logical bitwise 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. In computer programming, a bitwise operation operates on one or two bit patterns or binary numerals at the level of their individual bits. ... CPU can stand for: in computing: Central processing unit in journalism: Commonwealth Press Union in law enforcement: Crime prevention unit in software: Critical patch update, a type of software patch distributed by Oracle Corporation in Macleans College is often known as Ash Lim. ... AND Logic Gate In logic and mathematics, logical conjunction (usual symbol and) is a two-place logical operation that results in a value of true if both of its operands are true, otherwise a value of false. ... OR logic gate. ... NOR Logic Gate The logical NOR or joint denial is a boolean logic operator which produces a result that is the inverse of logical or. ... Exclusive disjunction (usual symbol xor) is a logical operator that results in true if one of the operands (not both) is true. ...

Furthermore, modern CPUs have instruction pipelines 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 pineline(s) because the CPU can't tell what it needs to do in advance. Too much branching makes the pipline 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. An instruction pipeline is a technique used in the design of microprocessors and other digital electronic devices to increase their performance. ...

CPU have a bit width which they are designed toward and can carry out bitwise operation 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 must be larger than the width of the instruction set 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. There is a trade-off.

Memory use

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 anyway). 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 are sometimes hard to read. It must be documented very well.

Many bitboard chess engines are written in fully compiled languages. C is a popular choice. Wikibooks has a book on the topic of C Programming The C programming language (often, just C) is a general-purpose, procedural, imperative computer programming language developed in the early 1970s by Dennis Ritchie for use on the Unix operating system. ...

The theoretically fastest language would be one that is fully compiled and has direct support for useful bitwise instructions on the hardware platform it is implemented on. One possibility is a C compiler that supports assembly language extensions.

Software development

Bitboards complicate debugging and can greatly increase the man hours required to complete a project.

Chess bitboards

A diagram is needed here

Image File history File links Diagram_Needed. ... Image File history File links Diagram_Needed. ...

Standard

The first bit usually represents A1 (the lower left square), and the 64th bit represents H8 (the diagonally opposite square). But there are also implementations with different mappings where H8 is the first bit and A1 is the last bit.

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 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. Crafty is a term used in World Of Warcraft to describe someone who plays the game 24/7 - sometimes longer. ...

Magics

Magic move bitboard generation is a new and fast alternative to rotated move bitboard generators. These are also more versitile than rotated move bitboard generators because the generator can be used independantly 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. A sample implementation of a magic move bitboard generator can be found here.

Chess bitboard myths

• Engines use either standard or rotated bitboards.
  • Engines use either standard alone or they use standard together with rotated.

• The reason chess bitboards work is because there are exactly 64 squares on the chessboard because computers "like" the number 64.
  • They would just the same if there were 49 or 36 squares on a chessboard too.

• You need an unsigned 64-bit datatype to do a chess bitboard.
  • You can use a signed 64-bit too, as long as you understand how Two's complement encoding works.

Twos complement is the most popular method of representing signed integers in computer science. ...

Other bitboards

Many other games besides chess benefit from bitboards.

• In Connect Four, they allow for very efficient testing for 4 consecutive discs, by just two shift+and operations per direction.
• In the Conway's Game of Life, they are a possible alternative to arrays.
• Othello/Reversi (see the Reversi article).

Connect Four (also known as Plot Four) is a two-player board game in which the objective is to be the first to get four of ones own discs in a line. ... Gospers Glider Gun creating gliders. The Game of Life is a cellular automaton devised by the British mathematician John Horton Conway in 1970. ... Reversi and Othello are names for a strategic boardgame which involves play by two parties on an eight-by-eight square grid with pieces that have two distinct sides. ...

See also

• Bit array
• Bit field
• Bit manipulation
• Bit twiddler
• Bitwise operation
• Board representation (chess)
• Boolean algebra
• Instruction set, Instruction pipeline, opcode and Byte-code
• Ghost (chess)

A bit array is an array data structure which compactly stores individual bits (boolean values). ... A bit field is a common idiom used in computer programming to store a set of Boolean datatype flags compactly. ... Bit manipulation is the act of algorithmically manipulating bits or other pieces of data shorter than byte. ... In 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; Reading or writing binary file formats; or Being unnecessarily complex, perhaps due to premature optimization A programmer who writes bit twiddlers, as described above... In computer programming, a bitwise operation operates on one or two bit patterns or binary numerals at the level of their individual bits. ... In computer chess software developers must choose a data structure to represent chess positions. ... In abstract algebra, a Boolean algebra is an algebraic structure (a collection of elements and operations on them obeying defining axioms) that captures essential properties of both set operations and logic operations. ... An instruction set, or instruction set architecture (ISA), describes the aspects of a computer architecture visible to a programmer, including the native datatypes, instructions, registers, addressing modes, memory architecture, interrupt and exception handling, and external I/O (if any). ... An instruction pipeline is a technique used in the design of microprocessors and other digital electronic devices to increase their performance. ... Microprocessors perform operations using binary bits (on/off/1or0). ... Byte-code is a sort of intermediate code that is more abstract than machine code. ...

External links

Checkers

• Checkers Bitboard Tutorial by Jonathan Kreuzer

Chess

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))

Code examples

• [1] The author of the Frenzee engine had posted some source examples.

Implementations

Open source

• Beowulf Unix, Linux, Windows. Rotated bitboards.
• Crafty See the Crafty article. Written in straight C. Rotated bitboards. Strong.
• GNU Chess See the GNU Chess Article.
• KnightCap GPL. ELO of 2300.
• Pepito C. Bitboard, by Carlos del Cacho. Windows and Linux binaries as well as source available.
• Simontacci Rotated bitboards.

Crafty is a term used in World Of Warcraft to describe someone who plays the game 24/7 - sometimes longer. ... GNU Chess is a computer program for playing chess, and is thus a computer chess program. ... KnightCap is an open source computer chess engine. ...

Closed source

• DarkThought Home Page

Othello

• A complete discussion of Othello (Reversi) engines with some source code including an Othello bitboard in C and assembly.