Mizar chess engine

 board[index_square]

 board[to]=board[from]
 board[from]=EMPTY

• Array of 144 elements (12 x 12) or array of 120 elements (12 x 12)

• “0×88″ (which is means hexidecimal 88, array of 16 x 8 = 128 elements)

• Array of 16 x 12 or 16 x 16 elements

• Bitboards (integers of 64 bits)

Which data structure to choose between these? The perfect board representation doesn’t exist! I suggest to start with “0×88″ or “12 x 12″ (they are more simple to implement) and later, if you need, you can try bitboards. Now i’ll explain how different data structures work. First of all a little explanation: we call horizontal lines “Ranks” (1st rank,2nd rank… 8th rank) and vertical lines “Columns” (column A, column B… column H); talking about indexs of array you can imagine an 8 x 8 chess board in this way:

8: 56,57,58,59,60,61,62,63
7: 48,49,50,51,52,53,54,55,
6: 40,41,42,43,44,45,46,47,
5: 32,33,34,35,36,37,38,39,
4: 24,25,26,27,28,29,30,31,
3: 16,17,18,19,20,21,22,23,
2: q8, 9,10,11,12,13,14,15,
1: q0, 1, 2, 3, 4, 5, 6, 7,

q qA qB qC qD qE qF qG qH

the formula to calculate a square is:

index = rank * 8 + column

where rank 1, rank 2,…, rank 8 and column A, column B,…, column H are 0,1,2…7; the index of square “e4″ is : 3 * 8 + 4=28 (the red number) .

Now you can understand why it is difficult to know if a piece is outside board: if you have a rook on a3 (index:16 blu number) and you want to know if it can move a square on the right, you simply add 1 to index (16+1=17 -> b3), if board[17] is empty you can move your rook; if you want to know if you can move a square on the left you simply add -1 (16+(-1)=15) but 15 is h2 and even if board[15] is empty this move is impossible! The board representations that i’m going to describe are designed to haven’t this drawback.

Array 12 x 12 or 10 x 12

One solution is to extended the 8 x 8 array by encircling it with two layers of “bogus squares” containing sentinel values marking the squares as illegal. You can imagine your board in this way:

-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,A8,B8,C8,D8,E8,F8,G8,H8,-1,-1,
-1,-1,A7,B7,C7,D7,E7,F7,G7,H7,-1,-1,
-1,-1,A6,B6,C6,D6,E6,F6,G6,H6,-1,-1,
-1,-1,A5,B5,C5,D5,E5,F5,G5,H5,-1,-1,
-1,-1,A4,B4,C4,D4,E4,F4,G4,H4,-1,-1,
-1,-1,A3,B3,C3,D3,E3,F3,G3,H3,-1,-1,
-1,-1,A2,B2,C2,D2,E2,F2,G2,H2,-1,-1,
-1,-1,A1,B1,C1,D1,E1,F1,G1,H1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,

This trick accelerated move generation: for example, a bishop would generate moves by sliding one square at a time until it reached an illegal square, then stop. No need for complicated a priori computations to make sure that a move would not take a piece out of the memory area associated with the board. A move is on board only:

if ( board[target] =! -1 )

The second layer of fake squares is required by knight moves: for example, a knight on a corner square might try to jump out of bounds by two columns, so a single protection layer would be no protection at all. We will see later how to generate moves, but now you can understand these simple routines in pseudo code:

//Knights
delta[]={-25,-23,-14,-10,10,14,23,25};
for (i=0 to 7) {
qto=from+delta[i];
qif (board[to] != -1) {
qqif (board[to] == EMPTY) Generate_move();
qqelse if (board[to] == ENEMY) Generate_capture();
q}
}

//Rooks
delta[]={-12,-1,1,12};
for (i=0 to 3) {
qto=from + delta[i];
qwhile(board[to] != -1) {
qqif (board[to] == EMPTY) Generate_move();
qqelse if (board[to] == ENEMY) Generate_capture();
qqto = to + delta[i];
q}
}

I know, they aren’t fast, but we will see later how to write faster routines: for example you can do only a single color control to know if a square is empty, out of board or occupied by an enemy piece. Better memory usage can be achieved with a 10×12 array, which provides the same functionalities as a 12×12 one by overlapping the leftmost and rightmost edge files (which are marked as off-the board). If you have an index and you want to know which is his rank/column:

Column = index MOD 12;//12 x 12
Column = index MOD 10;//10 x 12
Rank = index / 12;//it is an integer division
Rank = index / 10;//(10 x 12)it is an integer division

Warning: rank e columns values are from 2 to 9!

0×88

The 0×88 method uses an array of size 16×8 = 128, numbered 0 to 127. It is basically 2 boards next to each other. The actual board is on the left, and the board on the right represents illegal moves.

A8,B8,C8,D8,E8,F8,G8,H8,-1,-1,-1,-1,-1,-1,-1,-1,
A7,B7,C7,D7,E7,F7,G7,H7,-1,-1,-1,-1,-1,-1,-1,-1,
A6,B6,C6,D6,E6,F6,G6,H6,-1,-1,-1,-1,-1,-1,-1,-1,
A5,B5,C5,D5,E5,F5,G5,H5,-1,-1,-1,-1,-1,-1,-1,-1,
A4,B4,C4,D4,E4,F4,G4,H4,-1,-1,-1,-1,-1,-1,-1,-1,
A3,B3,C3,D3,E3,F3,G3,H3,-1,-1,-1,-1,-1,-1,-1,-1,
A2,B2,C2,D2,E2,F2,G2,H2,-1,-1,-1,-1,-1,-1,-1,-1,
A1,B1,C1,D1,E1,F1,G1,H1,-1,-1,-1,-1,-1,-1,-1,-1,

When generating moves from the main board, you can check that the destination square is on the main board simply by ANDing the square number with 0×88 (136 in decimal). A non zero result indicates that the square is off the main board and on the illegal-move board.

if ((index & 0×88)!=0)…the move is on illegal board
//& is BITWISE AND

Why? The indexes of the squares are:

112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127
A8, B8, C8, D8, E8, F8, G8, H8, -1, -1, -1, -1, -1, -1, -1, -1,
…
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,
A1,B1,C1,D1,E1,F1,G1,H1,-1,-1,-1,-1,-1,-1,-1,-1,

You want to know if a move is on board and if the index is between 0 and 128. If you have a rook in h1 (index 7) and you want to know if it is possible to move a square on the right, simply add 1 to index: 7+1=8. In binary we have:

8 0000000: 00001000
0×88(136): 10001000
8 & 0×88 : 00001000 illegal move

Every indexes on the left side of the board have that red bit set to 0, instead every indexes on the right side of the board have that red bit set to 1. On the other hand if you have a rook in h8 (index 119) and you want to know if it is possible to move a square aheadt, simply add 16 to index: 119+16=135. In binary we have:

135 00000: 10000111
0×88(136): 10001000
135 & 0×88: 10000000 illegal move

Every indexes bigger than 128 or lower than 0 have that red bit set to 1.

A nice property of 16 x N arrays (16 x 8, 16 x 12, 16 x 16) is that if you subtract two indexes of squares on that board, you get a value that accurately describes the relationship between the two squares. For example, if the result of the subtraction is 1, you know that the second square was to the right of the first square; if your result was 16, you were one square up the file from the first square. This is useful to detect if a square is attacked by another square in a very fast way (we’ll talk about that later).

If you have an index and you want to know which is his rank/column:
Column = index MOD 16;//=index & 15…very fast
Rank = index / 16;//=index & 4…very fast
Warning: rank e columns values are from 0 to 7!

Array 16 x 12 or 16 x 16

The first time that i read about 16 x 12 or 16 x 16 array was in an old post of Christophe Theron (the programmer of Chess Tiger) on CCC forum. Basically it is a crossing between 12 x 12 and 0×88: you have the property of 0×88 to have fast attack detection and fast way to calculate ranks and columns and you can use the property of 12 x 12 to have a faster generator of moves (we will see later how).

Bitboards

Bitboards was used maybe for the first time by a Sovietic hardware chess engine: Kaissa. They became famous when they were used by Crafty a strong, freeware chess engine written by Robert Hyatt. What is a bitboard? It is an integer of 64 bit representing a yes-or-no or true-or-false predicate for the whole board: for example, one bitboard might contain the answer to “Is there a white piece here?” for each square of the board. So to represent the state of a chess game you need more than a bitboard, for example: one each for the presence of white pawns, white rooks, black pawns, etc. You can imagine a bitboard in this way:

 White_pawns:
  00000000
  01000000
  00000000
  00000000
  00000000
  00000000
  00000000
  00000000

That is :

0000000001000000000000000000000000000000000000000000000000000000 = 18014398509481984 (decimal)

Warning: there are different bitboard notation. In 12 x 12 or 0×88 we start to count index from A1 instead here (for simplicity) we start at A8, and moving across then down in the sense A8,B8,C8,…,H8,A7,B7,C7,…,G1,H1. For each square, we put a ’1′ if there is a pawn, or a ’0′ otherwise. The bit more on the left is A8, the bit more on the right is H1.

To work with bitboards means to understand bitwise operation, so if don’t understand this please stop, study this until you understand! In short, we have:

• NOT (~): NOT 1000 = 0111

• OR (): 0101 OR 0011 = 0111

• XOR(^): 0101 XOR 0011 = 0110

• AND (&): 0101 AND 0011 = 0001

What we can do with bitboards? A lot of things: first of all you must understand that move generation become a simple table look-up, because we can precalculate a lot of things. You can build a database of bitbords representing the squares attacked by a certain piece on a certain square. For example, suppose you need to verify whether the white queen is checking the black king. With a simple square-array representation, you would need to:

• Find the queen’s position, which requires a linear search of the array.
• Examine the squares to which it is able to move, in all eight directions, until you either find the king or run out of possible moves.

This process is always time-consuming, more so when the queen happens to be located near the end of the array, and even more so when there is no check to be found, which is almost always the case! With a bitboard representation, you would:

• Load the “white queen position” bitboard.
• Use it to index the database of bitboards representing squares attacked by queens.
• Logical-AND that bitboard with the one for “black king position”.

If the result is non-zero, then the white queen is checking the black king! Now you understand how it is very important and time critical to know which is the index of a bit set to 1 Something like that:

typedef unsigned __int64 BITBOARD

BITBOARD Queen_attacks[64][256];

//Queen_attacks[22][occupation_degree] here will be:

  00001000
  00000111
  00000110
  00000111
  00000010
  00000010
  00000000

BITBOARD Black_King; // It’ll be:

 00000001
 00000000
 00000000
 00000000
 00000000
 00000000
 00000000
 00000000

//So black king is checked by white queen only if…

if ((Black-King & Queen_attacks[22][occupation_degree]) != 0) KING_IS_IN_CHECK

We will talk later how to generate moves with bitboards and about “occupation degree”.

Other arguments

1. It is very useful to store kings position in two variables: you’ll use these data a lot of time, so instead to looking for kings every time scanning the chess board, simply you can read a variable.
2. You can generalize this idea to all pieces: instead to scan the board everytime you can memorize the squares where the pieces are in two array called “Pieces List”. You can sort this array to have king position always in ’0′ position: it is very useful because you often need to know where the kings are.
3. To describe a chess position you need to know:
   • Pieces position
   • Castling rights
   • Color to move
   • En passant capture (if available)

So you need other variables to store this information too.