# Representation of a Chess Board with a Bitboard

## Chess Coordinate system

How do we talk about a chess board? We must know where the pieces are and what they are called. r, n, b, q, k, p are the black Rook, Knight, Bishop, Queen, and King, and R, N, B, Q, K, P and the white Rook, Knight, Bishop, Queen, and King, respectively. A row of a chess board is called a "rank" and a column is called a "file". Each square also has a location, and when talking about a square, its location is always used, such as "a white pawn is on a2". The letters are on the X axis of the board and the numbers are on Y axis of the board. Here is a visual description of the initial state of the board and of the idenitification system for each square:
 r n b q k b n r p p p p p p p p P P P P P P P P R N B Q K B N R
 A8 B8 C8 D8 E8 F8 G8 H8 A7 B7 C7 D7 E7 F7 G7 H7 A6 B6 C6 D6 E6 F6 G6 H6 A5 B5 C5 D5 E5 F5 G5 H5 A4 B4 C4 D4 E4 F4 G4 H4 A3 B3 C3 D3 E3 F3 G3 H3 A2 B2 C2 D2 E2 F2 G2 H2 A1 B1 C1 D1 E1 F1 G1 H1

Note that the white side will ALWAYS be on the bottom and the black side will ALWAYS be on top.

## The 64-bit number

Here is an example of what a 64-bit number looks like:
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
The blue digit is the 63rd bit (or Most Significant Bit, abbreviated MSB) and the green digit is the 0th bit (or the Least Significant Bit, abbreviated LSB). When used to represent chess state, this 64-bit number is called a bitboard.

Modern computers like the Opteron or IA64 can natively handle 64-bit numbers and manipulate them in one instruction. 32-bit computers must break up the bit operations in to 2 or more instructions causing a slowdown of performance. However, we will be ignoring such performance issues for clarity's sake.

The operations that can happen with a 64-bit number that concern us at this moment are the logical bitwise operators: NOT, AND, OR, XOR. The boolean logic looks much like this:

 A B NOT A NOT B A AND B A OR B A XOR B 0 0 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 1 0 1 1 1 1 0 0 1 1 0

In practice, this is what an AND could look like:
 1 0 1 0 1 1 1 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 0 1 1
AND
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
=
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

There are also two more bit operations that aren't boolean logic, but instead actions that you can perform with a 64 bit number. The LSHFT and RSHFT operators are left shift and right shift operators respectively. In C, LSHFT would be << and RSHFT would be >>. They mean that you take the 64 bit number and shift it left or right by a specified number of bit places. If bits fall off the edge, they are gone forever and if there aren't enough bits to produce a full 64 bit number, zero are added to always keep the bits at 64. Here's an example.

Suppose we have this 64-bit number:
Number:
 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
If we shift it left (from LSB to MSB) by 4 bits, then this is what we end up with:
Number:
 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0
Consequently, if we shift it right by 4 bits, then this is what we get:
Number:
 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1

Shifting might not appear to be of obvious use at this moment, but it will become very important when determining movements and attacks in parallel of certain pieces.

## FirstBit and LastBit

The function FirstBit gives the index of the first bit that is turned on from the LSB side. So in this example:
Number:
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0

FirstBit(Number) is equal to 4 which is the number of the index (from zero) of the green digit in the Number from the LSB side.

The function LastBit gives the index of the first bit that is turned on from the MSB side. So, continuing the above example:

LastBit(Number) is equal to 45 which is the number of the index (from zero) of the blue digit in the Number from the LSB side.

## C code representation

Simple C89-ish code to define a bitboard can look like this if your compiler and architecture supports the unsigned long long extension at 8 bytes width:

typedef unsigned long long Bitboard;
C99 users could probably get away with:
typedef uint64_t Bitboard;

## Chess Board Mapping

So how do we decide how to map each chess board square to a bit in the 64-bit integer? This mapping could be arbitrary, but it behooves us to pick a mathematically advantageous mapping. In this particular mapping (or winding) we are going to say that position a1 is the least signficant bit (LSB), bit 0, of the 64 bit number and h8 is the most significant bit (MSB), bit 63. The squares will be assigned in a left to right, bottom to top ordering to each bit index in the 64 bit number from LSB to MSB.
 A8 B8 C8 D8 E8 F8 G8 H8 A7 B7 C7 D7 E7 F7 G7 H7 A6 B6 C6 D6 E6 F6 G6 H6 A5 B5 C5 D5 E5 F5 G5 H5 A4 B4 C4 D4 E4 F4 G4 H4 A3 B3 C3 D3 E3 F3 G3 H3 A2 B2 C2 D2 E2 F2 G2 H2 A1 B1 C1 D1 E1 F1 G1 H1
 56 57 58 59 60 61 62 63 48 49 50 51 52 53 54 55 40 41 42 43 44 45 46 47 32 33 34 35 36 37 38 39 24 25 26 27 28 29 30 31 16 17 18 19 20 21 22 23 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7

Our first real example will be a bitboard which represents the WhitePawns. The left board is the initial physical location of the white pawns on a real board, and the right board is the bitboard equivalent.
 P P P P P P P P
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
The bitboard which represents the WhitePawns is this.
WhitePawns:
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
These functions will be useful to us later when we want to iteratively process the results of a bitboard calculation.

At this point once more piece of information must be explained concerning the chess board square identification with respect to the winding. We are explicitly assigning a direct bit index to each position of the board. So:

A1 = 0
B1 = 1
C1 = 2
D1 = 3
E1 = 4
F1 = 5
G1 = 6
H1 = 7
A2 = 8
B2 = 9
.....
G7 = 54
H7 = 55
A8 = 56
B8 = 57
C8 = 58
D8 = 59
E8 = 60
F8 = 61
G8 = 62
H8 = 63

And we are explicitly assigning a bit index to a position on the board:

0 = A1
1 = B1
.....
62 = G8
63 = H8

This becomes important later when we start using the bit index and the chess board identification symbol interchangeably depending upon if we are talking about a position on the chess board or a index into a bitboard--especially in terms of FirstBit and LastBit

## Bitboard Visualization

Often in this document, you will see me formatting a bitboard like the above and doing logical bitwise operations on it with the results also being bitboards formatted to look like chess boards. In effect, if I had two boards, say BOARD_A and BOARD_B, then if I wanted to do this: BOARD_A AND BOARD_B = BOARD_C, then BOARD_A's A1 AND BOARD_B's A1 = BOARD_C's A1 for each position from A1 to H8.

Here is an example of visualizing the bitboards as chess boards while doing bitwise operations on them.

A previous example:
 1 0 1 0 1 1 1 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 0 1 1
AND
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
=
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

The previous example rendered as chess boards:
 0 1 1 1 0 1 0 1 1 0 1 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 0 1 1 0 1 1 1 0 1 1 1 0 0
AND
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
=
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
These two forms, the bitboard AND operation and the chess board AND operation, are equivalent.