Generating Magic Keys for Bitboard Move Generation
Posted: 26 Jul 2006, 00:50Hi all,
I would like to post for some work I'm doing on an algorithmically fast magic key generator for magic bitboard move generation so that we can get better magic keys for smaller move databases. It isn't complete but hopefully with your help it can be finished faster.
For those who haven't heard of "magic bitboard move generation" you might like to read this topic posted by Lasse Hansen:
http://wbforum.volker-pittlik.name/viewtopic.php?t=5015
I'll summarize it here:
Say you had this position and you wanted to generate moves for the white rook.
[diag]8/8/8/2kbR1N1/8/8/4K3/4b3 w - - 0 1[/diag]
8/8/8/2kbR1N1/8/8/4K3/4b3 w - - 0 1
You would first need a couple databases
RookMask[64];
Magic[64];
RookDatabase[64][1<<NumBits]; //Contains rook move bitboards
RookMask[E5] will look like this
For bishops BishopMask[E5] it might look like this
First we need to get the occupancy bitboard which we find like this:
OccupancyBB = AllPieces & RookMask[E5];
Then we multiply it by a magic and shift the "NumBits" top bits down to index to our rook move bitboard database.
Index = ( OccupancyBB * Magic[E5] ) >> ( 64 - NumBits );
RookMoveBB = RookDatabase[E5][Index];
What (OccupancyBB*Magic[E5]) does is "shift" bits up in the occupancy bitboard and you take the top n bits as your index (which will depend on your occupancy bitboard).
But generating this Magic is pretty difficult. It will have to take into account that different occupancy bitboards should hash to an index with the same move. It would be ideal to have all the respective occupancs hash to the same index (as this will reduce our Database size by a lot) but it might not be possible.
===================================
Anyways what I'm trying to do is create magic keys be able to create indecies that only take up 8 bits for rooks and 7 bits for bishops (so that we can reduce the database size):
In an effort to do this I've noticed that not all bits will affect the top n bits so that we don't have to try the impossible process of iterating through all possible 64 bit magics and instead just iterate through a just select few magics. In order to simplify the analysis I've broken down the multiplication for an 8bit integer:
We can already see from this simple example that the 6th bit of the multiplier dosen't affect the result at all for how many ever top n bits. This is because the bits of the key gets shifted out of the number. Say we wanted only 2 bits for our index. Then we can see the first expression in the simplification won't even make it up to the top 2 bits -- but it gets a bit more complicated. We have only seen the direct infuence of the shifted bits on the 2 top bits but we haven't seen any the effect of the carry. When the addition process is actually done, we will see that the first expression which we thought wouldn't have an effect, really does because of the second expression which when added to the first will make the bits below the first 2 bits carry up. Likewise there are occations when bits that map directly to the top n bits will carry too far out and really won't have an effect. Currently I'm working on how the carry effects the top n bits, and if anybody can help me out, we can create better magic keys for magic bitboard move generators.
I would like to post for some work I'm doing on an algorithmically fast magic key generator for magic bitboard move generation so that we can get better magic keys for smaller move databases. It isn't complete but hopefully with your help it can be finished faster.
For those who haven't heard of "magic bitboard move generation" you might like to read this topic posted by Lasse Hansen:
http://wbforum.volker-pittlik.name/viewtopic.php?t=5015
I'll summarize it here:
Say you had this position and you wanted to generate moves for the white rook.
[diag]8/8/8/2kbR1N1/8/8/4K3/4b3 w - - 0 1[/diag]
8/8/8/2kbR1N1/8/8/4K3/4b3 w - - 0 1
You would first need a couple databases
RookMask[64];
Magic[64];
RookDatabase[64][1<<NumBits]; //Contains rook move bitboards
RookMask[E5] will look like this
- Code: Select all
00000000
00001000
00001000
01110110
00001000
00001000
00001000
00000000
For bishops BishopMask[E5] it might look like this
- Code: Select all
00000000
00100010
00010100
00000000
00010100
00100010
01000000
00000000
First we need to get the occupancy bitboard which we find like this:
OccupancyBB = AllPieces & RookMask[E5];
Then we multiply it by a magic and shift the "NumBits" top bits down to index to our rook move bitboard database.
Index = ( OccupancyBB * Magic[E5] ) >> ( 64 - NumBits );
RookMoveBB = RookDatabase[E5][Index];
What (OccupancyBB*Magic[E5]) does is "shift" bits up in the occupancy bitboard and you take the top n bits as your index (which will depend on your occupancy bitboard).
But generating this Magic is pretty difficult. It will have to take into account that different occupancy bitboards should hash to an index with the same move. It would be ideal to have all the respective occupancs hash to the same index (as this will reduce our Database size by a lot) but it might not be possible.
===================================
Anyways what I'm trying to do is create magic keys be able to create indecies that only take up 8 bits for rooks and 7 bits for bishops (so that we can reduce the database size):
- Code: Select all
Data from the top part of my keygen program to show 8 bits are needed for rooks and 7 bits are needed for bishops.
Possible rook move bitboards for each square
49 42 70 84 84 70 42 49
42 36 60 72 72 60 36 42
70 60 100 120 120 100 60 70
84 72 120 144 144 120 72 84
84 72 120 144 144 120 72 84
70 60 100 120 120 100 60 70
42 36 60 72 72 60 36 42
49 42 70 84 84 70 42 49
Possible bishop move bitboards for each square
7 6 10 12 12 10 6 7
6 6 10 12 12 10 6 6
10 10 40 48 48 40 10 10
12 12 48 108 108 48 12 12
12 12 48 108 108 48 12 12
10 10 40 48 48 40 10 10
6 6 10 12 12 10 6 6
7 6 10 12 12 10 6 7
In an effort to do this I've noticed that not all bits will affect the top n bits so that we don't have to try the impossible process of iterating through all possible 64 bit magics and instead just iterate through a just select few magics. In order to simplify the analysis I've broken down the multiplication for an 8bit integer:
- Code: Select all
00111000 * 01001011 = 00111000<<0 + 00111000<<1 + 00111000<<3 + 00111000<<6
= 00111000 + 01110000 + 11000000 + 00000000
We can already see from this simple example that the 6th bit of the multiplier dosen't affect the result at all for how many ever top n bits. This is because the bits of the key gets shifted out of the number. Say we wanted only 2 bits for our index. Then we can see the first expression in the simplification won't even make it up to the top 2 bits -- but it gets a bit more complicated. We have only seen the direct infuence of the shifted bits on the 2 top bits but we haven't seen any the effect of the carry. When the addition process is actually done, we will see that the first expression which we thought wouldn't have an effect, really does because of the second expression which when added to the first will make the bits below the first 2 bits carry up. Likewise there are occations when bits that map directly to the top n bits will carry too far out and really won't have an effect. Currently I'm working on how the carry effects the top n bits, and if anybody can help me out, we can create better magic keys for magic bitboard move generators.
. I've heard of De Burijin from some of your posts before but never really knew exactly what it was. I would also like to note these magics can be used with the division operator (if it helps anyone with their magic generation).