# Magic Bitboards

##
This article is now being maintained on my programming blog.

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 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 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 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…

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