New board representation

I learnt with my first approach with a chess engine the way how you store the chess board is an important (if not the most important) decision when you start programming. The way you store the content of the board determines how efficient can you generate moves or evaluate the current situation of the board. When finding a move the engine generates hundreds of thousands of moves and evaluates millions of positions so you want to do that very efficiently.

In my first approach I used a 12x12 board with two rings of invalid squares around the actual board. The advantage of this approach is that you know instantly for any given square whether it is empty or what type of piece it holds. I also stored the positions of both kings. So if you want to know whether one side is in check you don't have to loop over all the squares just to find out where the kings are.

But even with this information at hand generating moves is very slow. You have an outer loop that loops over all squares, if it hits a piece of the side to move it jumps to piece specific code for generating the moves for that piece. For sliding pieces like bishop, rook or queen this involves inner loops that travel along the lines until they hit a piece or invalid square (the edge of the board). 

If you research a bit how other engines represent the board you find a method called BitBoards for storing the board information. This is actually a very clever way to do that but you should be comfortable with Boolean algebra (bitwise AND, OR, NOT and XOR).

The main idea is that you store for every piece type a 64 bit Integer in which a 1 bit on a certain position in that integer stands for a piece of that type on that square. So you will need in total 12 of that Int64 for all types of pieces (6 for white and 6 for black).   It makes also sense to have some helper BitBoards like OccupiedSquares, EmptySquares, WhitePieces and BlackPieces. It is possible to generate them any time by bitwise OR of the piece BitBoards but as they are required very often it is faster to maintain them when executing moves.

To give a glimpse what BitBoards can do here the method for generating standard white pawn moves.

The pawn positions on the board are in a BitBoard called w_Pawns. In the bitboard bit 0 stands for square A1,  bit 1 for B1 and bit 63 for square H8. To generate the moves we do the following

// we generate the target squares by shifting all pawns 8 bits left and remove those

// who hit another piece or reach the 8th rank (those are special as they promote 

// and handled differently)

// BB_RANKS is a array of BitBoard constants, that have bits set that specify

// a certain rank e.g. BB_RANKS[8]  is set to  $FF00000000000000

// TMove.Create accepts start square, target square, moved piece and captured
// piece as arguments

targetSq_bb := (w_Pawns shl 8) AND EmptySquares AND NOT(BB_RANKS[8]);    

for each bit=1 in targetSq_bb do 

  targetSq := bitPosition;

  move := TMove.Create(targetSq-8, targetSq, W_Pawn, NONE);

next

We have now generated all simple pawn moves in one go. Very efficient. How to efficiently determine the position of a 1 bit in a bitboard is explained in a later post.

Although BitBoards are sufficient to know what piece is located on what square, it requires some effort to answer the question what piece stands on a certain square. I have to loop through all the piece BitBoards until I find the one with the 1 bit for that square set. So I decided to have in addition to BitBoards a traditional array where I maintain the content of each square.

So for whatever information I need, I either look at the BitBoards or the square array. Of course there is an overhead in move execution as both data structures must be maintained, but I decided it is worth it.