HOME
Latest news
DOWNLOADS
Downloads for all Rival flavours
CHANGE LOG
Recent changes to the engine and the GUI
MAGICS
A random piece on magic bitboards
ABOUT
About the authors and history of Rival chess
CONTACT
Give us some feedback

Magic Bitboards

This article is now being maintained on my programming blog.

This page relates to programming issues involved with creating bitboard chess engines. If you are lucky enough that the previous sentence made no sense then you may not want to read any further!

During development at the end of 2010, I was originally using rotated bitboards in the Rival engine but quickly switched to magic bitboards after realising how damn awesome they were.

Rival for Java uses bitboards coded from 63 (square a8) to 0 (h1).

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…

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 PiecesThe bitboard containing bits set to show the location of every piece on the chessboard.
Rook Mask for C3Occupancy 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.
OccupancyHas bits set for any piece, enemy or friendly, that sits along the attack rays of a rook on C3
Magic Number for Rook on C3If 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 reasonable-sized array. This number is generated by brute force trial an 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 ResultThis 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 C3The number of shifts needed to turn the magic result into an array index.
Array IndexThe 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.
~bitboardFriendlyThe inverted bitboard of friendly pieces.
Move DestinationsA 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…

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.)

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. 63-maxBits).
It is possible that these shift values can be larger than 63-maxBits 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.

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…

Now we have enough information to generate the magic numbers…

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.