Games - Bitboard

	Games - Bitboard

A bitboard is a data structure commonly used in computer systems that play boardgames.

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.

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.

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"

Description for all games or applications

A bitboard 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.

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.

[ Visit the complete Wikipedia entry for Bitboard ]

Searches on eBay

bitboard