Chess Board Representation
When anyone writes a chess program, one of the first things to decide is how you’re going to represent the layout of the chess board. Chess Programming Wiki has a good section on the various approaches to Board Representation. When considering the different structures you need to consider the ease and speed of several factors:
- Generating Moves
- Making Moves
- Undoing Moves
- Evaluating the Position
I find rookies chess programmers tend to focus too much on Move Generation but in reality all four factors are important.
As I outlined in the Design Philosophy section, I am keen to create a Magic Bitboard engine. Bitboards are not new. They use a 64 bit number to represent the locations of each type of chess piece. In the binary format an occupied square is “1” and an unoccupied square in a “0”. Generating king, knight and pawn moves is trivial. The “magic” comes in when generating moves for sliding pieces (which was always the awkward part of bitboard programming). Sliding piece move generation is now a “multiplication, a shift and a table look-up”. The result is extremely efficient manipulation of chess boards. Not only is the good for move generation, it comes in handy when evaluating a chess position, where attack tables can be quickly generated on the fly.
So let’s create a bitboard board structure:
//===========================================================//
// Chess Board Structure
//===========================================================//
typedef struct t_board
{
t_bitboard piece[2][6];
t_chess_color to_move;
t_hash hash;
t_hash pawn_hash;
uchar castling;
uchar ep_square;
uchar king_square[2];
uchar ply;
uchar in_check;
t_chess_square check_attacker;
uchar fifty_move_count;
int static_value;
};
The “piece” variable has two dimensions, one for the color (i.e. black or white) and the other for the 6 types of chess pieces. The structure also contains all of the board “state” information (e.g. castling rights etc.). I may add to the structure with variable such as the kings’ location. This may be helpful when detecting check. But at this stage I’d like to keep the structure as small as possible and only add more terms when absolutely necessary.
I can then declare the board as:
// ----------------------------------------------------------//
// Chess Board
// ----------------------------------------------------------//
struct t_board position[1];
I’m planning to pass this “position” variable to most of the board manipulation routines. This will make it easier to implement a multi-core engine at a later stage.