Writing a chess program in 99 steps

Move generation for sliding pieces

Personally I found bitboard move generation for sliding pieces to be one of the most difficult parts to understand in chess programming (together with alpha-beta search).  The main difference between sliding and non-sliding pieces is that the attack bitboards for sliding pieces not only depend on the from-square (as with non-sliding pieces),  but they also depend on the occupancy ('state') of the files, ranks and diagonals. Non-sliding attack bitboards can be stored in one-dimensional lookup tables (arrays), but sliding attack bitboards  need to be stored in two-dimensional lookup tables, the second dimension relates to the occupancy, or state, of the rank, file, or diagonal.

Sliding pieces will attack a rank, file or diagonal, up to and including the first piece that they encounter (irrespective of the color of that piece). So in terms of move generation, a sliding piece will also attack pieces of the same color.  This is no problem, because equal-color attacks will be 'AND'-ed away by the targetBitmap = ~whitePieces bitboard (same as with non-sliding pieces), and this effectively removes all equal-color captures. The concept might need some time to sink in, but it is totally consistent with how we generated the white knight moves: the knight attack bitboards have no check to see what the contents of an attacked field is, there might be a black piece on the attacked field, or a white piece, or it may be empty.

To clarify the idea a bit further, let's take a look at a chess position with the relevant bitboards for move generation, and look how the moves for the white rook on f1 are generated:

Relevant move generation bitboards for the rook on f1 (compare with the knight move generation):

targetBitmap = ~whitePieces	ROOKMOVES = RANK_ATTACKS[f1][rankstate] | FILE_ATTACKS[f1][filestate]	rook moves: ROOKMOVES & targetBitmap
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 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 . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . 1 1 . 1 .	. . . . . . . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . 1 . . .

Notice how the rook attacks stop when they encounter a piece (any piece), and also how file and rank attacks are combined (using a bitwise OR).
In the example above, the first rank occupancy state could be represented as, going from a1 to h1: 10010110
For this state, a rook attack (from f1) along the 1^st rank will look like: 00011010.  The 6^th file occupancy state can be represented as (from f1 to f8): 10000011, and the rook attack (from f1) along the 6^th file will look like: 01111110.

6 bits only

At this point it is important to understand that the rook attack on the first rank does not depend on the contents of fields a1 or h1 (the first and last bits). Whether these fields are attacked only depends on b1 and g1 respectively, not on the contents of a1 and h1 themselves.

If there is NO piece on b1, then a1's attack status will just be 'inherited' from b1, irrespective if there is a piece on a1 or not. If there IS a piece on b1, then a1 will NOT be attacked, irrespective if there is a piece on a1 or not.
In any case, the presence of a piece on a1 does not matter for generating the rank attacks. Same goes for h1 (the attack depends on g1, not on h1). And this reasoning is equally valid for ranks, files and diagonals.

It means that, for sliding move generation purposes, we can omit the 2 outer bits and only need the 6 inner bits to define the occupancy state of a file, rank or diagonal. As a consequence, the sliding rank attack bitboards are declared as: BitMap RANK_ATTACKS[64][64], using 32KB of memory. The first index is the from field, the second index is the rank occupancy state (6 bits, 0..63).  There are ways to minimize the memory use for diagonal attack bitmaps, because most diagonals have less than 8 fields. But for the sake of speed and simplicity I'll not get into this, it will prevent additional coding to check for the length of the diagonal, at the cost of a little more memory use. 

Calculation of a 6-bit occupancy state index

Calculation of the table lookup index (from the occupancy state) is basically a two-step process:
First, we extract the occupancy bitboard of a single file/rank or diagonal.  This is done by taking occupiedSquares, and masking it with an appropriate masking bitboard that leaves us with only the appropriate bits of one file, rank, or diagonal (the 2 outer bits are not set in the masking bitboards). The example below demonstrates this step to get the file occupancy of field e4:

occupiedSquares	FILEMASK[e4]	occupiedSquares & DIAGA1H8MASK[e4]
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 . 1 . . 1	. . . . . . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . . . . .	. . . . . . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . . . . . . . . . . . . . . . . . . . . .

Or, for the 'a1-h8-diagonal' of field e4:

Second, this 64-bit bitboard (with maximum 6 bits set, all on a single file, rank or diagonal) is transformed to a 6-bit (0..63) lookup index.
This transformation is done differently for files, ranks, a1-h8 diagonals and a8-h1 diagonals:

Rank occupancy

For ranks, the occupancy index is simply calculated as follows:

6bitstate = (occupiedSquares & RANKMASK[from]) >> RANKSHIFT[from]

The example below demonstrates how the 6-bit rank occupancy index (in red below) for field d3 is calculated (RANKSHIFT[d3] = 17):

occupiedSquares	RANKMASK[d3]	occupiedSquares & RANKMASK[d3]	occupiedSquares & RANKMASK[d3] >> 17
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 . 1 . . 1	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 1 1 1 1 . . . . . . . . . . . . . . . . .	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 . 1 . 1 1 . . . . . . . . . . . . . . . . .	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 . 1 . 1 1 . .

File occupancy - magic multipliers

For files, the lookup index calculation is as follows:

6bitstate = (occupiedSquares & FILEMASK[from]) * FILEMAGIC[from] >> 57

Compared to ranks, there is one step added: a 64-bit multiplication with FILEMAGIC[from]. These 'magic' multipliers are chosen such that they transform a single file to the last rank, and at the same time retain the bit order, so we only have to shift the result to end up with the 6-bit occupancy state of that file.  Let's take the 3rd file as an example (bit locations are identified by A-F, they can either be 0 or 1, all dots are 0):

3rd file:		magic number for 3rd file: 0x2010080402010080		3rd file * magic number for 3rd file:	3rd file * magic number >> 57:
. . . . . . . . . . A . . . . . . . B . . . . . . . C . . . . . . . D . . . . . . . E . . . . . . . F . . . . . . . . . . . . .	x	. . . . . 1 . . . . . . 1 . . . . . . 1 . . . . . . 1 . . . . . . 1 . . . . . . 1 . . . . . . . . . . . . . . . . . . . . . . 1	=	. A B C D E F . . A B C D E . . . A B C D . . . . A B C . . . . . A B . . . . . . A . . . . . . . . . . . . . . . . . . . . . .	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A B C D E F . .

There is a magic multiplier for every file:

file:   magic:
a-file: 0x8040201008040200
b-file: 0x4020100804020100
c-file: 0x2010080402010080
d-file: 0x1008040201008040
e-file: 0x0804020100804020
f-file: 0x0402010080402010
g-file: 0x0201008040201008
h-file: 0x0100804020100804

How did I get to these magic numbers? Well, basically by trial and error. If you know a magic number for one file, or diagonal (for instance from wikispaces), then it's not hard to work out the magic numbers for the other files or diagonals. Keep in mind that two files only differ by a shift (left or right), if you apply the opposite shift to the magic number, you'll end up with the same multiplication result. 

A8H1 diagonal occupancy - magic multipliers

For a8h1 diagonals ('a8h1' is indicating the direction), calculating the lookup index (or: diagonal occupancy) is very similar to what we did for files:

6bitstate = (occupiedSquares & DIAGA8H1MASK[from]) * DIAGA8H1MAGIC[from] >> 57

Let's define the diagonal numbering: diaga8h1 = file + rank - 1
There are 15 diagonals, numbered from 1 to 15, diagonal 8 being the longest diagonal (from a8 to h1), and let's take diaga8h1 = 9 as an example:

diaga8h1[9]:		magic number for diaga8h1[9]: 0x0080808080808080		diaga8h1[9] * 0x0080808080808080:	diaga8h1[9] * 0x0080808080808080 >> 57:
. . . . . . . . . . A . . . . . . . . B . . . . . . . . C . . . . . . . . D . . . . . . . . E . . . . . . . . . . . . . . . . .	x	. . . . . . . . . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . 1	=	. A B C D E . . . . B C D E . . . . . C D E . . . . . . D E . . . . . . . E . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A B C D E . . .

Note that this particular diagonal only needs 5 addressing bits. For simplicity, we will just treat it as if it has 6 bits (with the last bit being irrelevant), such that all diagonal attack bitboards will have the same addressing range.

Again, there is a magic multiplier for every a8h1 diagonal (and some diagonals share the same multiplier):

diagonal:             magic:
diaga8h1 =  1, a1:    0x0
diaga8h1 =  2, a2-b1: 0x0
diaga8h1 =  3, a3-c1: 0x0101010101010100
diaga8h1 =  4, a4-d1: 0x0101010101010100
diaga8h1 =  5, a5-e1: 0x0101010101010100
diaga8h1 =  6, a6-f1: 0x0101010101010100
diaga8h1 =  7, a7-g1: 0x0101010101010100
diaga8h1 =  8, a8-h1: 0x0101010101010100
diaga8h1 =  9, b8-h2: 0x0080808080808080
diaga8h1 = 10, c8-h3: 0x0040404040404040
diaga8h1 = 11, d8-h4: 0x0020202020202020
diaga8h1 = 12, e8-h5: 0x0010101010101010
diaga8h1 = 13, f8-h6: 0x0008080808080808
diaga8h1 = 14, g8-h7: 0x0
diaga8h1 = 15, h8:    0x0
 

The first two and last two diagonals don't need magic numbers, because they consist of only 1 or 2 squares, so the attacks along these diagonals don't depend on their occupancy.

A1H8 diagonal occupancy - magic multipliers

a1h8 diagonal occupancy lookup indices are calculated the same way:

6bitstate = (occupiedSquares & DIAGA1H8MASK[from]) * DIAGA1H8MAGIC[from] >> 57

We define a1h8 diagonal numbers as follows: diaga1h8 = file - rank + 8,  so numbered from 1 to 15, and 8 is the longest diagonal. Take diaga1h8 = 9 as an example:

diaga1h8[9]		magic number for diaga8h1[9]: 0x8080808080808000		diaga8h1[9] * 0x0080808080808080:	diaga8h1[9] * 0x0080808080808080 >> 57:
. . . . . . . . . . . . . . . . . . . . . . E . . . . . . D . . . . . . C . . . . . . B . . . . . . A . . . . . . . . . . . . .	x	. . . . . . . . . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . . . . . 1	=	. A B C D E . . . A B C D E . . . A B C D . . . . A B C . . . . . A B . . . . . . A . . . . . . . . . . . . . . . . . . . . . .	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A B C D E . . .

Again, there is a magic multiplier for every a8h1 diagonal (and again, some diagonals have the same multiplier):

diagonal:             magic:
diaga1h8 =  1, a8:    0x0
diaga1h8 =  2, a7-b8: 0x0
diaga1h8 =  3, a6-c8: 0x0101010101010100
diaga1h8 =  4, a5-d8: 0x0101010101010100
diaga1h8 =  5, a4-e8: 0x0101010101010100
diaga1h8 =  6, a3-f8: 0x0101010101010100
diaga1h8 =  7, a2-g8: 0x0101010101010100
diaga1h8 =  8, a1-h8: 0x0101010101010100
diaga1h8 =  9, b1-h7: 0x8080808080808000
diaga1h8 = 10, c1-h6: 0x4040404040400000
diaga1h8 = 11, d1-h5: 0x2020202020000000
diaga1h8 = 12, e1-h4: 0x1010101000000000
diaga1h8 = 13, f1-h3: 0x0808080000000000
diaga1h8 = 14, g1-h2: 0x0
diaga1h8 = 15, h1:    0x0

last update: Thursday 02 June 2011