This is where we actually start.
Board representation is to be decided keeping 3 main algorithms in mind.
1. Move Generation (Generates a list of all possible moves)
2. Move make (Changes the current chess position to a new one because of the move that is made)
3. Move unmake / takeback (Changes the current position back to the previous one - which existed before the move was made)
The execution of the above algorithms should be as efficient as possible.
We have already discussed how colour and piece are encoded as indexes in lookup arrays.
Now we will come up with representation of complete chess position.
A complete chess position has got many parameters.
1. The placement of various pieces on the board - This is the hard visible aspect. Easy to see but difficult to implement in code.
2. Soft aspects - side to move, castling rights, 50 move tracker for draw rule, en-passant flag - these are difficult to account for (not visible and retained in the brains while playing) but easy to implement in code.
1. Piece placement:
Piece placement basically answers what piece on what square.
We need to encode piece as well as square first before we move ahead.
Square encoding depends on how the chess engine perceives the board.
If it is a 2 dimensional 8 x 8 array then a square is encoded with 2 parameters.
However, if the board is a 1 dimensional array of 64 elements, then a square gets encoded with 1 parameter only.
The advantage of this is many. Few listed:
1. A 1 dimensional array is faster than a 2 dimensional array, is faster than a 3 dimensional array etc.
2. Nested loops are slower than single loop. For 8 x 8 array there would be 2 nested loops. The outer loop to be traversed 8 times and the inner loop to be traversed 8 times - each time the outer loop is traversed.
3. Chess pieces need to move on board (i.e. their squares change) in particular directions. More the parameters used to define the square - more updates required to the originating square to reach the destination square.
Hence, its better to have 1 dimensional array of 64 elements to represent board.
In TSCP, (refer file data.c) 2 arrays of int data type of 64 elements are used -
int color[64]; /* LIGHT, DARK, or EMPTY */
int piece[64]; /* PAWN, KNIGHT, BISHOP, ROOK, QUEEN, KING, or EMPTY */
One holds the piece type and other holds the colour of the piece.
Both arrays are needed to get the complete information on piece placement. With the piece array we can only know that the square is occupied by which type of piece, for the colour of the piece we refer to the 'color' array.
For programming, the piece array holds all the piece encodings and color array holds all the color encodings.
Refer file defs.h to understand how the indexing is done.
#define A1 56
#define B1 57
#define C1 58
#define D1 59
#define E1 60
#define F1 61
#define G1 62
#define H1 63
#define A8 0
#define B8 1
#define C8 2
#define D8 3
#define E8 4
#define F8 5
#define G8 6
#define H8 7
The A8 square is indexed 0.
It is the first square. Then all other squares belonging to the same rank have the index incremented by 1.
The index of B8 square is 1,
the index of C8 square is 2 ..and it is continued.
All squares of the same rank lie within particular multiples of 8.
The 8th rank lies between 0 - 7.
The 7th rank lies between 8 - 15.
The 6th rank lies between 16 - 23.
......
The 1st rank lies between 56 - 63.
Thus, to get the rank. we just need to divide the square index by 8.
Integer division would only retain the full number part and fractional part will be discarded.
The 8th rank will be 0
The 7th rank will be 1
The 6th rank will be 2
The 5th rank will be 3
......
The 1st rank will be 7
Integer division by 8 is same as bit right shift by 3 places.
Thus TSCP defines a macro to extract the rank from the square
#define ROW(x) ( x >> 3 )
Also, the file is the remainder when the square index is divided by 8.
Integer remainder when divided by 8 is same as the last 3 bits of the number (Just like when you take any decimal number and the remainder when divided by 10 is the last digit in the unit's place)
Thus TSCP defines a macro to extract the file from the square
#define COL(x) ( x & 7 )
This only takes the last 3 bits (7 = 0111) and masks all other bits to 0.
2. Soft parameters: Soft parameters are: castling permissions, en passant flag ,fifty move tracker, side_to_move and full move tracker.
a. Castling Permissions:
Castling permissions are held as castle flag.The variable name is castle - refer data.c
'castle' flag:
It is a bitfield:
if 1 is set, white can castle kingside
if 2 is set, white can castle queenside
if 4 is set, black can castle kingside
if 8 is set, black can castle queenside
if it is 0 all castling rights are lost in the position
'ep' flag:(en-passant)
The 'ep' flag acts as a flag as well as it gives the e.p. square value. Whenever a pawn double move occurs the e.p. flag value is set to a value which is equal to the potential e.p. square else its value would be -1. e.g. if the move is e4, the e3 square is set as en-passant square. Else (for any other move which is not a pawn double move) the en-passant square is -1.
Other soft parameters being maintained are:
side - the colour of side to move (light or dark)
xside - the side not to move (light or dark) - this is used for faster processing. Rather than calculating the not moving side every time, we just do it once and store it in a variable and use it.
3. Move: For move encoding refer defs.h.
The struct move_bytes is already explained here.
Then the author brilliantly unions it with an int having same size in terms of byte (4 bytes).
typedef union {
move_bytes b;
int u;
} move;
The advantage of this union is in comparing 2 different moves for equality. If I have to check whether move1 is equal to move2, then, without the union I will have to check all the 4 different char variables separately. But, with the union, I just check if int u of move1 is equal to int u of move2.
Thus, it should have been better if it would have been named something like a 'composite', as it is a composite of all 4 char variables.
In the code, I have provided FEN to TSCP board representation convertor.
Try it out with various FEN positions.