Understanding Magic Bitboards

[Jaco van Niekerk]

Hi all.

Sorry, if these questions seem trivial or if they have already been asked (I searched, but could not get the answers). I am experimenting with Magic Bitboards in Vicki 2.0. I can simply use the existing set of magics, but that misses the point for me. I would like a good understanding on how and why it works. For now, I will be content if I can generate my own set of magics. I have more or less an understanding of the basic ideas.

For a bitscan application the magic is always a proper De Bruijn number (i.e. a number part of the De Bruijn sequence). Since only one bit is set in the occupancy bitboard (before multiplying with the magic and shifting), perfect hashing is achieved. For chess, this is not the case since multiple bits could be set. To generate the magic, a brute-force, trial-and-error approach must be used.

My questions as follows:

(1) Since multiple bits are potentially set, a magic number for rook/bishop lookups is not necessarily a De-Bruijn number. It needs to be sparsely populated though (i.e. only a few bits is set). Is this correct?

(2) From what I've read, a rook on A1, requires a database of size 1024 (10 bits) to hash without collisions using the currently best known magic of 0x1234567890123456. Given an ample amount of time, would it be possible to find a magic for say, a 9-bit database? Since a rook on A1 has 12 possible blockers or none at all (giving 14), the absolute minimum would be 49, i.e. pick 1 from 7 horizontally, or not at all and 1 from 7 vertically, or not at all. This gives a total of 49. Am I talking nonsense here? Of course, finding a magic number that hashes all those boards (2^7^2=16384, i think) to 42 would be a pipe dream. However, is there a proof of some sorts to give the absolute minimum database size required? I don't think there is, or whether it is even possible.

Thank you.

[Jaco van Niekerk]

This resource http://www.rivalchess.com/magic-bitboards/ provides some clarity. The random number does not have a de Bruijn number... It also gives a nice walkthrough on how to calculate it. Furthermore, the database can get smaller, but the number of magic numbers that can result in a perfect hash reduces dramatically and are therefore orders of magnitude harder to find. (Searching for the next prime number comes to mind...)

[Gerd Isenberg]

My questions as follows:

(1) Since multiple bits are potentially set, a magic number for rook/bishop lookups is not necessarily a De-Bruijn number. It needs to be sparsely populated though (i.e. only a few bits is set). Is this correct?

At least there are some minimum number of bits required, to shift all relevant occupied bits left to the upper N. But there are magics with something like 64-N set bits, see "best magics so far"
https://chessprogramming.wikispaces.com ... ics+so+far

(2) From what I've read, a rook on A1, requires a database of size 1024 (10 bits) to hash without collisions using the currently best known magic of 0x1234567890123456. Given an ample amount of time, would it be possible to find a magic for say, a 9-bit database? Since a rook on A1 has 12 possible blockers or none at all (giving 14), the absolute minimum would be 49, i.e. pick 1 from 7 horizontally, or not at all and 1 from 7 vertically, or not at all. This gives a total of 49. Am I talking nonsense here? Of course, finding a magic number that hashes all those boards (2^7^2=16384, i think) to 42 would be a pipe dream. However, is there a proof of some sorts to give the absolute minimum database size required? I don't think there is, or whether it is even possible.

Yes, the rook on square 0 has a ratio of cardinality of all relevant occupancies versus cardinality of distinct attack-sets of 4096/49. So far I am not aware of a 10-bit or even 11-bit range for that rook. Seems still to require 12 bits.

[Jaco van Niekerk]

Yes, correction... The minimum size is 12 bits. There is a magic number for an 11-bit database for a rook on h8. Thanks for the input. I got a brute force searcher running. It searches for magic numbers for all pieces, for all squares, for various database sizes. Sadly, nothing found so far (apart from the existing, maximum sizes).

How should the random numbers be generated? So far I am doing the following (Java) to get a sparsely populated value:

Random random = new Random();
long random = random.nextLong() & random.nextLong();

Any other ideas?

I was wondering whether this has been converted to a Boinc project? (i.e. mass parallel community project).

[Harald Lüßen]

In this forum post Tord Romstad used even more sparsely populated random numbers:
http://www.talkchess.com/forum/viewtopi ... 34&t=19699

uint64 random_uint64_fewbits() {
return random_uint64() & random_uint64() & random_uint64();
}

Harald

[Jaco van Niekerk]

Thank you for the replies, it really helped... I have written a little program that will search for magic numbers for both pieces, for each square, for all database-sizes. It keeps on searching indefinitely.

I have it running for a few hours and found my own set of magic numbers for the normal database sizes (i.e. bit_count(attack_board), for example 12 bits for a rook on a1).

I have also, found the following magic numbers for smaller database sizes (square, magic, size, bit_count(attack_board)):

6(g1) 1297218022431264916 4 (max: 5)
14(g2) 109327276132532097 4 (max: 5)
55(h7) 6503098094720516110 4 (max: 5)
57(b8) -8573582672198804990 4 (max: 5)

Sorry, the program prints it out in decimal and I am too lazy to convert them now. Sadly, a 11-bit rook on a1 would be more exciting. Just a few billion years to go to find them all!

EDIT:

Does anyone know how up to date this list is: http://chessprogramming.wikispaces.com/Best+Magics+so+far

[Gerd Isenberg]

Thank you for the replies, it really helped... I have written a little program that will search for magic numbers for both pieces, for each square, for all database-sizes. It keeps on searching indefinitely.

I have it running for a few hours and found my own set of magic numbers for the normal database sizes (i.e. bit_count(attack_board), for example 12 bits for a rook on a1).

I have also, found the following magic numbers for smaller database sizes (square, magic, size, bit_count(attack_board)):

6(g1) 1297218022431264916 4 (max: 5)
14(g2) 109327276132532097 4 (max: 5)
55(h7) 6503098094720516110 4 (max: 5)
57(b8) -8573582672198804990 4 (max: 5)

Sorry, the program prints it out in decimal and I am too lazy to convert them now. Sadly, a 11-bit rook on a1 would be more exciting. Just a few billion years to go to find them all!

Seems those "easy" bishop squares are already covered in the Best Magics table with 4 bits used

EDIT:

Does anyone know how up to date this list is: http://chessprogramming.wikispaces.com/Best+Magics+so+far

There is an edit button. If you are not member in cpw yet, simply register.

[Jaco van Niekerk]

Hi again everyone

My computer has been running non-stop for 2 days now and I have only found better magics for each of the 6 corner squares for bishops, i.e (capital Bs). Essentially, all the bishop squares we currently have... so no new contribution..

BBbbbbBB
BBbbbbBB
BBbbbbBB
bbbbbbbb
bbbbbbbb
BBbbbbBB
BBbbbbBB
BBbbbbBB

I have not found anything for rooks... what is your experience with rooks? ...from your experience, how many random numbers do I need to check to, statistically, find my first rook.

I have checked 800,000,000 numbers so far

I have considered a technique where I calculate a range of possible magic numbers and then search between these, but I do know how feasible this is... essentially using the following (please excude my use of unfamiliar terminology):

• Since we shift-right to get the index value, the available values pre-shift is anything between abc000 to abc1111 (for a 4-bit database), where abc some selected index value.
• Therefore, abc000 <= magic-number * variation(i) <= abc1111, for all blocker-variations, variation(i), for a particular result-board as stored in the database.
• We can therefore define a range, abc000/variation(i) to abc1111/variation(i), for all i.
• After obtaining all these magic number ranges, the magic number for this square, piece, db-size and index, has to fall in between a range where an overlap occurs between ALL these ranges. If such overlap does not exists, no magic exists for this square, piece, db-size and index.
• We have therefore reduced the search by searching for a magic number, for a (1) particular piece, (2) particular square, (3) particular database size, AND (4) a particular index value (we may need to assign index values in the same value).

I think the above, may possible be less complex than randomly selecting loooooongs to determine magics. I still have to implement it and there are still some detail to sort out... not sure if I am missing something... The above is probably utter nonsense...

[Grant Osborne]

I presume that by 'better magics' you mean less bits?
Of course you can let your computer run for 2 days, 3 days or even a week or more, but personally I couldn't wait that long. I worked on one square at a time and if I didn't find anything within 2 or 3 minutes, I tried something else.
Try manually setting and/or clearing certain bits in the magic number.
e.g. magicNo |= 0x......
magicNo &= 0x......
For squares higher up e.g. A1 to H1 try setting the high bits of the magic number. For example for square 63 (H1) try magicNo |= 0xFFFFF00000000000 and let your program randomize the lower bits.
For the lower squares (A8 to H8) do the opposite. Square A8 set the lower bits of the magic number magicNo |= 0x0000000000000FFF and let your program randomize the higher bits.
Worked pretty well for me.

Grant

[Jaco van Niekerk]

Thanks Grant, trying that now... I've read that a smaller database does not make a very large difference on modern processors. However, I still like the idea of a magic number that maps n numbers to a database containing less than n spots. Thanks for the idea.

EDIT:

I am happy to report that I found more dense (by 1-bit) databases for the rook on square a8, b8 and c8.

a8: 0x6ffffd00560068ce
b8: 0x6ffffd00560068ce
c8: 0x12bfff803200296a

I don't understand the post/pre-mask on the "best-magics-so-far" page, but these are just plain-straight magics for for the rook on the aforementioned squares. What I particularly like about magics bitboards is that normal chess programming can continue, while the computer works in the background searching for more dense databases. It's almost like your computer is also "working" on your chess engine!

Thanks again!

[crystalclear]

(1) Since multiple bits are potentially set, a magic number for rook/bishop lookups is not necessarily a De-Bruijn number. It needs to be sparsely populated though (i.e. only a few bits is set). Is this correct?

Not as far as I am aware. I think sparsely populated numbers are more likely to avoid problems, but I don't see that a large number of ones will not work, it is just much less likely. If you want to create a magic number to effectively coalesce some sparsely distributed bits a,b,c,d,e,... then you might want to shift bit a to bit 63, bit b to bit 62, bit c to bit 61, etc.
So the number of ones required in the magic can be similar to the number of bits of interest {a,b,c,d,e,...}. However, if some of the bits are close, e.g. 1 bit apart, then shifting bit b to bit 62 might also simultaneously shift bit c to bit 61, and one bit less is required in the magic number. For pieces like a rook, there will be a string of consecutive bits and the magics are likely quite small (in terms of number of ones).

Although it might be nice to collect the bits 00000a00000b00000c00000d00e0f000g0000 or something like that together nicely in the form
abcdefg, I didn't create a real example there, just an arbitrary pattern, but see how the e and f bits are two bits apart?
So if I shift the e bit to where I want it, look where the f bit goes ...
****e*f
So when I find a magic number, it might not be possible to order the bits how I want them, and I might have to accept something like this as a result
abcdegf
Note the f and g bits are reversed.

Since the order the bits are packed into an index isn't known when we start looking for magics, some trial and error is involved in finding them.
I can think of about 4 ways then of finding magics. This amounts to 4 different ways of generating the guesses.

1. I have hand crafted some magics, where the packing was awkward.
2. SNOOB. (Same number of one bits)
3. repeated trial with random numbers
4. recursive software trying to pack the pits in different orders.

1. There is an example of this somewhere in the forum.
2. I have not used snoob to find magics, but have heard of it being used. This can find minimal magics, and I believe multiplication with less ones can be quicker
on some hardware - though I don't know for sure.
3, This is what I use. I do a search using a table of magics already found as first guesses, and limit the number of guesses per square and go onto another square if I don't find a magic. Then I start again with a deeper search for the missing ones. That way the program doesn't hang on an obstinate square and I can get an overview of whether what I am looking for is easy, difficult, very challenging, or maybe impossible. For example 14 bit magics for rooks didn't seem possible without a little trick (also described elsewhere on here).
4. This should be posssible, attempting to shift the bits into various orders, eg for a rook there might be 14 bits of interest and so there are 14! (factorial) ways you might try to pack them. Some of the bits are consecutive in the original data (due to the way a rook moves) and these will land together in the index after tha magic multiplication has been applied and they cannot be separated, but that just reduces the number of possibilities. I tried method 4 with no success. My coding skills and patience were not up to the task.

With a large number of bits in a magic, you are likely to start getting problems.
Suppose your product after the magic multiplication starts looking like this
abcdefgXYZ.....
Those bits XYZ are close to producing a carry that will start corrupting the bit g.
There is also a likelyhood that instead of getting a single copy of each bit you want in the index, you will start getting multiple copies, corrupting each other.
That is the reason that small numbers of one bits work best. But it doesn't mean -- as far as I can see -- that a large number will never work.
Some collisions you can get away with, but that's another story.

(2) From what I've read, a rook on A1, requires a database of size 1024 (10 bits) to hash without collisions using the currently best known magic of 0x1234567890123456. Given an ample amount of time, would it be possible to find a magic for say, a 9-bit database? Since a rook on A1 has 12 possible blockers or none at all (giving 14), the absolute minimum would be 49, i.e. pick 1 from 7 horizontally, or not at all and 1 from 7 vertically, or not at all. This gives a total of 49. Am I talking nonsense here? Of course, finding a magic number that hashes all those boards (2^7^2=16384, i think) to 42 would be a pipe dream. However, is there a proof of some sorts to give the absolute minimum database size required? I don't think there is, or whether it is even possible.

I have not got to grips really with what are the best magics found and what are the optimal ones in some sense. I just found ones that work for my application.
But I have doubts about your calculations. a rook on a1 could be blocked by a piece on b1, c1, d1, e1 or f1, or not at all. That is 6 values. That makes a total of 36 combinations if the application is "what blocks the rook". A rook on a1 can move to b1, c1, d1, e1, f1, g1, h1. That is 7 values. So there might be 49 possiblilties if the application is something like "where might the rook capture". A rook on a1 can capture on b1, c1, d1, e1, f1, g1, h1 or maybe not at all. That is 8 values. So there might be 64 possibilities if the application is something like "what can the rook capture".

If you ignore the exact application when you create magics, then you can use the same magics to create indexes into multiple different tables. You do however possibly lose the chance of some compression. My example is the classic "it is safe to eat oysters when there is an R in the month". There is probably a magic number that multiplies some ASCII month name and gives a single bit saying whether it is safe to eat oysters. However it is generally more useful if you can find a magic that converts a month number into a 4 bit value. Better still would be to covert a month name to an integer 0-11. And the super magic number would map January to 0, feb to 1, march to 2, etc. To me, crunching the months down to 4 bits would be enough and I'd have a 16 entry "safe to eat oysters table". Crunching it down to a single bit using a magic number would mean I'd need new magics next time I needed to use months for something else.

[crystalclear]

3, This is what I use. I do a search using a table of magics already found as first guesses, and limit the number of guesses per square and go onto another square if I don't find a magic. Then I start again with a deeper search for the missing ones. That way the program doesn't hang on an obstinate square and I can get an overview of whether what I am looking for is easy, difficult, very challenging, or maybe impossible. For example 14 bit magics for rooks didn't seem possible without a little trick (also described elsewhere on here).

I neglected to say after looking for magics and finding a few that are stubborn, I often change my guess generator before trying again.

Suppose rand() generates a 64 bit number. We can expect it to have about 32 ones in it.
rand() & rand()
should then have about 16 ones in it.
and
rand() & rand() & rand()
should have about 8 ones, since each consecutive & operation should wipe out about half of the ones.

So we can get approx 4 ones , or 8 ones . With other tricks, you could get maybe approximately 6 ones, though I never bothered.
My line of thought is rand() | rand() should have about 48 ones and that can be halved down.
For other reasons, I now have a function that will give me a random number with a precise quantity of ones.

So I might try 500,000 attempts at magics with about 4 ones and then for the problems that haven't been cracked, try 2 million attempts at 8 ones.
Then go back to 4 ones at yet more attempts, etc.
And then if there is one square unsolved, try doing it by hand, seeing why the jigsaw pieces don't want to fit together.

Code: Select all

uint64_t random_n_ones(int n);


I wrote that function today, not for generating magic numbers, but for a sort of genetic algorithm. A child is to copy half of its bits from its father's 64 bits,
and the other half from it's mother's 64 bits. Which 32 bits come from the father is random, but I wanted exactly 32 bits. I thought it best to write a generic function and to pass the 32 in as a parameter.

[crystalclear]

PS Both Atlanchess and Vicki will hammer Sidonia
I need to write some chess playing software and stop fiddling with the peripheral stuff!
And I don't know how you get your avatars into the list of graphics the site knows about!