The mailbox method simplifies the code implementation of move generation.
To understand why mailbox is used consider 2 knights on a board - one on e4 and the other on a1.
The knight on e4 has moves in all 8 directions but the knight on a1 does not have it because of its proximity to edge of the board.
Without mailbox this would be very cumbersome to code as the number of directions in which a piece can move not only depends on the piece but also on its location on the board (also we have to solve for which are those directions)
Mailbox method is elegant solution to that problem.
What is done is that a padding is added to the usual 8x8 chessboard as edges. The padding should be atleast 2 layers thick on all sides to accommodate knight moves.
Hence rather than having an 8x8 board we should now have a 12x12 board.
However because of the left to right wrap-around we need only 1 file thick padding on each vertical side and hence we use a board with 12 rows and 10 columns - 12x10.
Below is the mailbox array used in code (refer file data.c)
We can see padding is represented by "-1"
int mailbox[120] = {
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, 0, 1, 2, 3, 4, 5, 6, 7, -1,
-1, 8, 9, 10, 11, 12, 13, 14, 15, -1,
-1, 16, 17, 18, 19, 20, 21, 22, 23, -1,
-1, 24, 25, 26, 27, 28, 29, 30, 31, -1,
-1, 32, 33, 34, 35, 36, 37, 38, 39, -1,
-1, 40, 41, 42, 43, 44, 45, 46, 47, -1,
-1, 48, 49, 50, 51, 52, 53, 54, 55, -1,
-1, 56, 57, 58, 59, 60, 61, 62, 63, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1
};
The direction vectors need to adjusted as per the new 12x10 mailbox array.
e.g. previously to go 1 square up the file we subtract 8 in 8x8 board. Now we subtract 10 in our 12x10 board.
Thus, we have to adjust all directions according to our new mailbox board.
Below is the mailbox adjusted offset lookup array for direction vector for each piece:
int offset[6][8] = {
{ 0, 0, 0, 0, 0, 0, 0, 0 },
{ -21, -19, -12, -8, 8, 12, 19, 21 },
{ -11, -9, 9, 11, 0, 0, 0, 0 },
{ -10, -1, 1, 10, 0, 0, 0, 0 },
{ -11, -10, -9, -1, 1, 9, 10, 11 },
{ -11, -10, -9, -1, 1, 9, 10, 11 }
};
In another array we give indexes of all 8x8 board squares as available in our mailbox.
int mailbox64[64] = {
21, 22, 23, 24, 25, 26, 27, 28,
31, 32, 33, 34, 35, 36, 37, 38,
41, 42, 43, 44, 45, 46, 47, 48,
51, 52, 53, 54, 55, 56, 57, 58,
61, 62, 63, 64, 65, 66, 67, 68,
71, 72, 73, 74, 75, 76, 77, 78,
81, 82, 83, 84, 85, 86, 87, 88,
91, 92, 93, 94, 95, 96, 97, 98
};
This gives the mailbox index of 8x8 square index. e.g. square index of A8 is 0 in 8x8. However in mailbox (due to padding) its square index is 21.
Now, these 3 arrays are used for move generation of all pieces except pawns.
The idea is that - rather than adding direction delta to the 8x8 index, we add the mailbox adjusted delta to the mailbox index. As a result the mailbox array would give the desired result.
e.g. if we want to go from a8 to a7 then
a8's 8x8 index = 0 and mailbox index = 21
a7's 8x8 index = 8 and mailbox index = 31.
Now, rather than adding 8 (direction delta) to a8's 8x8 index directly, add 10 (mailbox offsetted direction delta) to a8's mailbox index.
The advantage gained here is that, because of mailbox square encoding, a value of "-1" would be returned for illegal access requests and a correct square index would be returned if the access request is legal.
e.g. if a rook is on a8 and he wants to move left (west).
He cannot because there is edge on left.
As a result if we add west's mailbox offsetted direction delta to a8's mailbox index, mailbox array will return "-1" for that illegal access request.
In simple terms (if the above is not understood) mailbox method does this:
It takes 3 inputs:
1. Current square index
2. Piece_type
3. Direction_index
and returns the square_index of consecutive square in the same direction for that piece.
If ever edge of the board is reached it returns -1.
E.g. Consider a rook on a8 (square index of A8 = 0).
It cannot move Up or Left because of board edge. It can move only Right or Down.
Its consecutive square in right direction is B8.
Its consecutive square in down direction is A7.
Let there be direction_index of each direction.
Then output for each direction will be following:
mailbox ( index_of_current_square(A8), piece(rook), direction_index(Left)) ==> -1
mailbox ( index_of_current_square(A8), piece(rook), direction_index(Up)) ==> -1
mailbox ( index_of_current_square(A8), piece(rook), direction_index(Down)) ==> square_index_of(A7) = 8
mailbox ( index_of_current_square(A8), piece(rook), direction_index(Right)) ==> square_index_of(B8) = 1
(Thus, mailbox method is nothing but a very clever form of square encoding. Rather than encoding the 64 squares from 0 to 63, they are encoded as 120 squares from 0 to 119.
In this set of 120 squares, there exists the valid 64 chess squares + 56 illegal squares encoded to -1. Once, we understand this point that even the 64 chess-board squares can be encoded differently as per the convenience of algorithm, we can better understand the board representation of other complex open source chess programs which use a 0x88 board that gives extra mathematical advantage of unique square relations)