Overview
This post relates to programming issues involved with creating bitboard chess engines. It was originally rewritten to coincide with the release of the Android version of Rival Chess in 2011 and published on rivalchess.com.
For further reference, the back catalog of Rival Chess code going back to 1992 is available on my GitHub account.
Up until 2010, Rival was using pretty straightforward movegeneration techniques. I had always intended to dive into bitboards at some point but never had the time. The chance came, however, with the development of a new Java engine for an Android version of Rival.
I started that phase of development using rotated bitboards but quickly switched to magic bitboards after dedicating a few days to their full understanding.
I think generating chess moves using magic bitboards is one of the most awesome things you can do with computer code and this post is my attempt to explain the process in as simple a manner as possible, something I wish I had been able to read before I started.
I think it’s quite possible to understand how to use magic bitboards without a background in the wider concept of standard and rotated bitboards, which are not covered in any detail in this post.
Rival and bitboards
Throughout the code, Rival uses bitboards to represent chess board states. Board states are represented by 64bit integers, with bit 63 representing square A8 and bit 0 representing square H1. For example, you can imagine a bitboard where every set bit represents a square occupied by an enemy piece. When you have various states represented like this, there are many manipulations and calculations you can perform to get valuable information, and get it quickly (admittedly, the code is Java so speed isn’t the main focus here).
What are magic bitboards?
Magic bitboards allow us to calculate the possible destination squares for sliding pieces with a simple calculation, rather than needing to loop through each square to determine if it is occupied, and then, if it is, to go back and set off in another direction, gathering possible moves as we go.
Given infinite memory, we could hold a huge lookup table in memory. We could index into this table using the piece type, the destination square, and a 64bit integer representing the position of all the enemy pieces on the board. Unfortunately, the 64bit number part of that necessitates an impossibly large array.
With magic bitboards, we can indeed use that tablebasedlookup idea, but instead of using a 64bit number to represent the state of the board, we can use a much, much smaller number.
The trick is to determine the position of all the blockers on the board (friendly and enemy pieces on the horizontal or diagonals in question) and represent this as a 64bit number. Then we multiply this by a magic number that is specific to the type of piece and the source square, perform a little shift on the result, and then we have a nice, small number that we can use as an index into the memory table that we return us another bitboard representing the available destination squares for our piece. This will include moves that take our own pieces, so we perform another bitwise operation on the result to remove those destination squares and we’re done.
The magic of the magic number (and the related, magic number of shifts performed at the end) is that it is produces the correct index for all the various blocker configurations either by
1) Returning the same index for different blocker configurations that require the result
2) Returning a different index that points to the same result
Here is an example of how to use a magic calculation to generate a bitboard with bits set for each destination square available for the moves for a rook on square C3…
1
2
3
4
5
 bbBlockers = bbAllPieces & occupancyMaskRook[C3]
databaseIndex = (int)((bbBlockers * magicNumberRook[C3]) >>> rookMagicShifts[C3])
bbMoveSquares = magicMovesRook[C3][databaseIndex] & ~bbFriendlyPieces 
As an example, let’s say we want to use this forumula to find the moves of the white rook on C3 on the following board…
We would use…
All Pieces 

Rook Mask for C3 

Occupancy 

Magic Number for Rook on C3 

Magic Result 

Required Shifts for Rook on C3 

Array Index 
10010001
00000111
10000000
00010000
10110110
00000111
01100000
00001100

& 
00000000
00100000
00100000
00100000
00100000
01011110
00100000
00000000

= 
00000000
00000000
00000000
00000000
00100000
00000110
00100000
00000000

* 
01101000
00100000
10000000
10000000
00000100
00000000
00100010
00000000

= 
00010011
10010000
00011100
11000000
11010000
01000000
00000000
00000000

>>> 
54

= 
00000000
00000000
00000000
00000000
00000000
00000000
00000000
01001110

= 
78

And then we use the index “78″ to find the moves…
magicMovesRook[C3][78] 

~bitboardFriendly 

Move Destinations 
00000000
00000000
00000000
00000000
00100000
11011100
00100000
00000000

& 
11111111
11111111
11111111
11111111
01101011
11111100
10011111
11110011

= 
00000000
00000000
00000000
00000000
00100000
11011100
00000000
00000000

All Pieces 
The bitboard containing bits set to show the location of every piece on the chessboard. 
Rook Mask for C3 
Occupancy Mask For Rook on C3. Each “1″ represents a blocker which would bring an end to the slides of the rook. Note that we don’t need to specify the edge squares because they are always blockers. The difference between a friendly blocker and an enemy blocker is sorted out at the end of the calculation. 
Occupancy 
Has bits set for any piece, enemy or friendly, that sits along the attack rays of a rook on C3 
Magic Number for Rook on C3 
If memory were no issue, we could just use the occupancy value as an index into a huge 2^64 size array. But this is not possible, so here is the magic number whose purpose is to allow the generation of an index into a reasonablesized array.
This number is generated by brute force trial and error. We can always find a number that will generate an index between 0 and 2^n (and if you’re really smart you can sometimes get a smaller index), where n is the number of bits set in the occupancy mask. A perfect mapping to unique indexes is probably impossible (I’m not a mathematician but I suspect it’s impossible) but luckily multiple occupancies can share the same index as they will produce the same moves.
Note that the number is fairly sparse (just a few 1s) – you’ll notice when generating magics by brute force that it is much, much quicker to try random sparse numbers than just any old number. 
Magic Result 
This doesn’t mean much, at least not until we shift it a bit… You need “>>>” rather than “>>” when coding in Java as there is no unsigned long type. 
Required Shifts for Rook on C3 
The number of shifts needed to turn the magic result into an array index. 
Array Index 
The index into the rook moves database. 
magicMovesRook[C3][78] 
Using the index “78″ from above.
As mentioned, more than one occupancy pattern would map to this result, but also this result may reside in multiple indexes – all that matters is that the magic number creates an index that can retrieve the correct result. 
~bitboardFriendly 
The inverted bitboard of friendly pieces. 
Move Destinations 
A bitboard with 1s set for each legal destination square for our rook on C3. 
Using the coding of a8=63, h1=0, the following magic numbers will work for generating the sliding moves…
1
2
3
 public static long magicNumberRook[] = {
0xa180022080400230L, 0x40100040022000L, 0x80088020001002L, 0x80080280841000L, 0x4200042010460008L, 0x4800a0003040080L, 0x400110082041008L, 0x8000a041000880L, 0x10138001a080c010L, 0x804008200480L, 0x10011012000c0L, 0x22004128102200L, 0x200081201200cL, 0x202a001048460004L, 0x81000100420004L, 0x4000800380004500L, 0x208002904001L, 0x90004040026008L, 0x208808010002001L, 0x2002020020704940L, 0x8048010008110005L, 0x6820808004002200L, 0xa80040008023011L, 0xb1460000811044L, 0x4204400080008ea0L, 0xb002400180200184L, 0x2020200080100380L, 0x10080080100080L, 0x2204080080800400L, 0xa40080360080L, 0x2040604002810b1L, 0x8c218600004104L, 0x8180004000402000L, 0x488c402000401001L, 0x4018a00080801004L, 0x1230002105001008L, 0x8904800800800400L, 0x42000c42003810L, 0x8408110400b012L, 0x18086182000401L, 0x2240088020c28000L, 0x1001201040c004L, 0xa02008010420020L, 0x10003009010060L, 0x4008008008014L, 0x80020004008080L, 0x282020001008080L, 0x50000181204a0004L, 0x102042111804200L, 0x40002010004001c0L, 0x19220045508200L, 0x20030010060a900L, 0x8018028040080L, 0x88240002008080L, 0x10301802830400L, 0x332a4081140200L, 0x8080010a601241L, 0x1008010400021L, 0x4082001007241L, 0x211009001200509L, 0x8015001002441801L, 0x801000804000603L, 0xc0900220024a401L, 0x1000200608243L
}; 
1
2
3
 public static long magicNumberBishop[] = {
0x2910054208004104L, 0x2100630a7020180L, 0x5822022042000000L, 0x2ca804a100200020L, 0x204042200000900L, 0x2002121024000002L, 0x80404104202000e8L, 0x812a020205010840L, 0x8005181184080048L, 0x1001c20208010101L, 0x1001080204002100L, 0x1810080489021800L, 0x62040420010a00L, 0x5028043004300020L, 0xc0080a4402605002L, 0x8a00a0104220200L, 0x940000410821212L, 0x1808024a280210L, 0x40c0422080a0598L, 0x4228020082004050L, 0x200800400e00100L, 0x20b001230021040L, 0x90a0201900c00L, 0x4940120a0a0108L, 0x20208050a42180L, 0x1004804b280200L, 0x2048020024040010L, 0x102c04004010200L, 0x20408204c002010L, 0x2411100020080c1L, 0x102a008084042100L, 0x941030000a09846L, 0x244100800400200L, 0x4000901010080696L, 0x280404180020L, 0x800042008240100L, 0x220008400088020L, 0x4020182000904c9L, 0x23010400020600L, 0x41040020110302L, 0x412101004020818L, 0x8022080a09404208L, 0x1401210240484800L, 0x22244208010080L, 0x1105040104000210L, 0x2040088800c40081L, 0x8184810252000400L, 0x4004610041002200L, 0x40201a444400810L, 0x4611010802020008L, 0x80000b0401040402L, 0x20004821880a00L, 0x8200002022440100L, 0x9431801010068L, 0x1040c20806108040L, 0x804901403022a40L, 0x2400202602104000L, 0x208520209440204L, 0x40c000022013020L, 0x2000104000420600L, 0x400000260142410L, 0x800633408100500L, 0x2404080a1410L, 0x138200122002900L
}; 
Generating the required arrays and magic numbers
The occupancyMask arrays can be calculated easily enough, but here they are along with the code to calculate them… you’ll notice in the code that we avoid marking edge squares in the mask. This is because an edge square is always a blocker so does not need to be defined as such – a slider will always stop on top of the first blocker it encounters (captures of friendly pieces are filtered out at the end as you can see above.)
1
2
3
 public static final long occupancyMaskRook[] = {
0x101010101017eL, 0x202020202027cL, 0x404040404047aL, 0x8080808080876L, 0x1010101010106eL, 0x2020202020205eL, 0x4040404040403eL, 0x8080808080807eL, 0x1010101017e00L, 0x2020202027c00L, 0x4040404047a00L, 0x8080808087600L, 0x10101010106e00L, 0x20202020205e00L, 0x40404040403e00L, 0x80808080807e00L, 0x10101017e0100L, 0x20202027c0200L, 0x40404047a0400L, 0x8080808760800L, 0x101010106e1000L, 0x202020205e2000L, 0x404040403e4000L, 0x808080807e8000L, 0x101017e010100L, 0x202027c020200L, 0x404047a040400L, 0x8080876080800L, 0x1010106e101000L, 0x2020205e202000L, 0x4040403e404000L, 0x8080807e808000L, 0x1017e01010100L, 0x2027c02020200L, 0x4047a04040400L, 0x8087608080800L, 0x10106e10101000L, 0x20205e20202000L, 0x40403e40404000L, 0x80807e80808000L, 0x17e0101010100L, 0x27c0202020200L, 0x47a0404040400L, 0x8760808080800L, 0x106e1010101000L, 0x205e2020202000L, 0x403e4040404000L, 0x807e8080808000L, 0x7e010101010100L, 0x7c020202020200L, 0x7a040404040400L, 0x76080808080800L, 0x6e101010101000L, 0x5e202020202000L, 0x3e404040404000L, 0x7e808080808000L, 0x7e01010101010100L, 0x7c02020202020200L, 0x7a04040404040400L, 0x7608080808080800L, 0x6e10101010101000L, 0x5e20202020202000L, 0x3e40404040404000L, 0x7e80808080808000L
}; 
1
2
3
 public static final long occupancyMaskBishop[] = {
0x40201008040200L, 0x402010080400L, 0x4020100a00L, 0x40221400L, 0x2442800L, 0x204085000L, 0x20408102000L, 0x2040810204000L, 0x20100804020000L, 0x40201008040000L, 0x4020100a0000L, 0x4022140000L, 0x244280000L, 0x20408500000L, 0x2040810200000L, 0x4081020400000L, 0x10080402000200L, 0x20100804000400L, 0x4020100a000a00L, 0x402214001400L, 0x24428002800L, 0x2040850005000L, 0x4081020002000L, 0x8102040004000L, 0x8040200020400L, 0x10080400040800L, 0x20100a000a1000L, 0x40221400142200L, 0x2442800284400L, 0x4085000500800L, 0x8102000201000L, 0x10204000402000L, 0x4020002040800L, 0x8040004081000L, 0x100a000a102000L, 0x22140014224000L, 0x44280028440200L, 0x8500050080400L, 0x10200020100800L, 0x20400040201000L, 0x2000204081000L, 0x4000408102000L, 0xa000a10204000L, 0x14001422400000L, 0x28002844020000L, 0x50005008040200L, 0x20002010080400L, 0x40004020100800L, 0x20408102000L, 0x40810204000L, 0xa1020400000L, 0x142240000000L, 0x284402000000L, 0x500804020000L, 0x201008040200L, 0x402010080400L, 0x2040810204000L, 0x4081020400000L, 0xa102040000000L, 0x14224000000000L, 0x28440200000000L, 0x50080402000000L, 0x20100804020000L, 0x40201008040200L
}; 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 public void generateOccupancyMasks()
{
int i, bitRef;
long mask;
for (bitRef=0; bitRef<=63; bitRef++)
{
mask = 0;
for (i=bitRef+8; i<=55; i+=8) mask = (1L << i);
for (i=bitRef8; i>=8; i=8) mask = (1L << i);
for (i=bitRef+1; i%8!=7 && i%8!=0 ; i++) mask = (1L << i);
for (i=bitRef1; i%8!=7 && i%8!=0 && i>=0; i) mask = (1L << i);
occupancyMaskRook[bitRef] = mask;
mask = 0;
for (i=bitRef+9; i%8!=7 && i%8!=0 && i<=55; i+=9) mask = (1L << i);
for (i=bitRef9; i%8!=7 && i%8!=0 && i>=8; i=9) mask = (1L << i);
for (i=bitRef+7; i%8!=7 && i%8!=0 && i<=55; i+=7) mask = (1L << i);
for (i=bitRef7; i%8!=7 && i%8!=0 && i>=8; i=7) mask = (1L << i);
occupancyMaskBishop[bitRef] = mask;
}
} 
And the shift arrays are a function of the maximum number of bits that can be set in the occupancy mask for that piece and that square (i.e. 63maxBits
).
It is possible that these shift values can be larger than 63maxBits if a magic number is found that can generate a database index smaller than 2^maxBits – although I’ve not done this here, this is possible because many occupancy variations share the same eventual move destinations bitboard.
1
2
3
4
5
6
 public static int magicNumberShiftsRook[] = {
52,53,53,53,53,53,53,52,53,54,54,54,54,54,54,53,
53,54,54,54,54,54,54,53,53,54,54,54,54,54,54,53,
53,54,54,54,54,54,54,53,53,54,54,54,54,54,54,53,
53,54,54,54,54,54,54,53,52,53,53,53,53,53,53,52
}; 
1
2
3
4
5
6
 public static int magicNumberShiftsBishop[] = {
58,59,59,59,59,59,59,58,59,59,59,59,59,59,59,59,
59,59,57,57,57,57,59,59,59,59,57,55,55,57,59,59,
59,59,57,55,55,57,59,59,59,59,57,57,57,57,59,59,
59,59,59,59,59,59,59,59,58,59,59,59,59,59,59,58
}; 
To generate the magic numbers, we first need to populate a occupancyVariation and atttackSet array. The occupancyVariation array will contain all the occupancy variations for a piece on a given square.
In the case of a rook on C3, as there are 10 bits in the occupancy mask, there (2^10) = 1024 occupancy variations, and many of these variations will be effectively the same as one another as they represent the same available moves.
e.g.
This occupancy variation... 
...is the same as this one... 

...and can be represented as the follwing attack set (we set a 1 on the first blocker, except edge squares) 
00000000
00100000
00100000
00100000
00000000
01010010
00100000
00000000

00000000
00000000
00000000
00100000
00000000
01010110
00100000
00000000

= 
00000000
00000000
00000000
00100000
00000000
01010000
00100000
00000000

Calculating these occupancy variations and attack sets can be done as follows…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 public void generateOccupancyVariations(boolean isRook)
{
int i, j, bitRef;
long mask;
int variationCount;
int[] setBitsInMask, setBitsInIndex;
int bitCount[] = new int[64];
for (bitRef=0; bitRef<=63; bitRef++)
{
mask = isRook ? occupancyMaskRook[bitRef] : occupancyMaskBishop[bitRef];
setBitsInMask = Bitboards.getSetBits(mask);
bitCount[bitRef] = Bitboards.countSetBits(mask);
variationCount = (int)(1L << bitCount[bitRef]);
for (i=0; i<variationCount; i++)
{
occupancyVariation[bitRef][i] = 0;
// find bits set in index "i" and map them to bits in the 64 bit "occupancyVariation"
setBitsInIndex = Bitboards.getSetBits(i); // an array of integers showing which bits are set
for (j=0; setBitsInIndex[j] != 1; j++)
{
occupancyVariation[bitRef][i] = (1L << setBitsInMask[setBitsInIndex[j]]);
}
if (isRook)
{
for (j=bitRef+8; j<=55 && (occupancyVariation[bitRef][i] & (1L << j)) == 0; j+=8);
if (j>=0 && j<=63) occupancyAttackSet[bitRef][i] = (1L << j);
for (j=bitRef8; j>=8 && (occupancyVariation[bitRef][i] & (1L << j)) == 0; j=8);
if (j>=0 && j<=63) occupancyAttackSet[bitRef][i] = (1L << j);
for (j=bitRef+1; j%8!=7 && j%8!=0 && (occupancyVariation[bitRef][i] & (1L << j)) == 0; j++);
if (j>=0 && j<=63) occupancyAttackSet[bitRef][i] = (1L << j);
for (j=bitRef1; j%8!=7 && j%8!=0 && j>=0 && (occupancyVariation[bitRef][i] & (1L << j)) == 0; j);
if (j>=0 && j<=63) occupancyAttackSet[bitRef][i] = (1L << j);
}
else
{
for (j=bitRef+9; j%8!=7 && j%8!=0 && j<=55 && (occupancyVariation[bitRef][i] & (1L << j)) == 0; j+=9);
if (j>=0 && j<=63) occupancyAttackSet[bitRef][i] = (1L << j);
for (j=bitRef9; j%8!=7 && j%8!=0 && j>=8 && (occupancyVariation[bitRef][i] & (1L << j)) == 0; j=9);
if (j>=0 && j<=63) occupancyAttackSet[bitRef][i] = (1L << j);
for (j=bitRef+7; j%8!=7 && j%8!=0 && j<=55 && (occupancyVariation[bitRef][i] & (1L << j)) == 0; j+=7);
if (j>=0 && j<=63) occupancyAttackSet[bitRef][i] = (1L << j);
for (j=bitRef7; j%8!=7 && j%8!=0 && j>=8 && (occupancyVariation[bitRef][i] & (1L << j)) == 0; j=7);
if (j>=0 && j<=63) occupancyAttackSet[bitRef][i] = (1L << j);
}
}
}
} 
Now we have enough information to generate the magic numbers…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 public void generateMagicNumbers(boolean isRook)
{
int i, j, bitRef, variationCount;
Random r = new Random();
long magicNumber = 0;
int index;
long attackSet;
for (bitRef=0; bitRef<=63; bitRef++)
{
int bitCount = Bitboards.countSetBits(isRook ? occupancyMaskRook[bitRef] : occupancyMaskBishop[bitRef]);
variationCount = (int)(1L << bitCount);
boolean fail;
long usedBy[] = new long[(int)(1L << bitCount)];
int attempts = 0;
do
{
magicNumber = r.nextLong() & r.nextLong() & r.nextLong(); // generate a random number with not many bits set
for (j=0; j<variationCount; j++) usedBy[j] = 0;
attempts ++;
for (i=0, fail=false; i<variationCount && !fail; i++)
{
index = (int)((occupancyVariation[bitRef][i] * magicNumber) >>> (64bitCount));
// fail if this index is used by an attack set that is incorrect for this occupancy variation
fail = usedBy[index] != 0 && usedBy[index] != occupancyAttackSet[bitRef][i];
usedBy[index] = attackSet;
}
}
while (fail);
if (isRook)
{
magicNumberRook[bitRef] = magicNumber;
magicNumberShiftsRook[bitRef] = (64bitCount);
}
else
{
magicNumberBishop[bitRef] = magicNumber;
magicNumberShiftsBishop[bitRef] = (64bitCount);
}
}
} 
Now we just need to populate the magicMovesRook and magicMovesBishop arrays. This is easily done by going through each occupancyMask value and multiplying it by the relevant magic number to determine the index that will be generated at runtime. We then just put the correct move bitboard into this index of the array.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 public void generateMoveDatabase(boolean isRook)
{
long validMoves;
int variations, bitCount;
int bitRef, i, j, magicIndex;
for (bitRef=0; bitRef<=63; bitRef++)
{
bitCount = isRook ? Bitboards.countSetBits(occupancyMaskRook[bitRef]) : Bitboards.countSetBits(occupancyMaskBishop[bitRef]);
variations = (int)(1L << bitCount);
for (i=0; i<variations; i++)
{
validMoves = 0;
if (isRook)
{
magicIndex = (int)((occupancyVariation[bitRef][i] * magicNumberRook[bitRef]) >>> magicNumberShiftsRook[bitRef]);
for (j=bitRef+8; j<=63; j+=8) { validMoves = (1L << j); if ((occupancyVariation[bitRef][i] & (1L << j)) != 0) break; }
for (j=bitRef8; j>=0; j=8) { validMoves = (1L << j); if ((occupancyVariation[bitRef][i] & (1L << j)) != 0) break; }
for (j=bitRef+1; j%8!=0; j++) { validMoves = (1L << j); if ((occupancyVariation[bitRef][i] & (1L << j)) != 0) break; }
for (j=bitRef1; j%8!=7 && j>=0; j) { validMoves = (1L << j); if ((occupancyVariation[bitRef][i] & (1L << j)) != 0) break; }
magicMovesRook[bitRef][magicIndex] = validMoves;
}
else
{
magicIndex = (int)((occupancyVariation[bitRef][i] * magicNumberBishop[bitRef]) >>> magicNumberShiftsBishop[bitRef]);
for (j=bitRef+9; j%8!=0 && j<=63; j+=9) { validMoves = (1L << j); if ((occupancyVariation[bitRef][i] & (1L << j)) != 0) break; }
for (j=bitRef9; j%8!=7 && j>=0; j=9) { validMoves = (1L << j); if ((occupancyVariation[bitRef][i] & (1L << j)) != 0) break; }
for (j=bitRef+7; j%8!=7 && j<=63; j+=7) {
validMoves = (1L << j);
if ((occupancyVariation[bitRef][i] & (1L << j)) != 0)
break;
}
for (j=bitRef7; j%8!=0 && j>=0; j=7) {
validMoves = (1L << j);
if ((occupancyVariation[bitRef][i] & (1L << j)) != 0)
break;
}
magicMovesBishop[bitRef][magicIndex] = validMoves;
}
}
}
} 