TalkChess.com

I'm writing a move generator using bitboard magic move generation. My question is this: How can I use a value for "bits" that is less than the population count of the mask used to create the occupation bitmap for the square?

For example, if I'm calculating an occupation bitmap for a rook on a1, I code something like: The mask for a1 is all bits representing b1-g1 and a2-a7. So, the population count of this mask is 12. That means that there are 4,096 possible occupation bitmaps for a rook on a1.

I have computed magic numbers for rooks which lets me calculate the index into my rook_attacks table using something like: That made me happy. But then I read that some folks have found magic numbers that allow them to use a "bits" value of less than 12 in this case.

On this web page (http://chessprogramming.wikispaces.com/ ... ics+so+far), Grant Osborne has posted a magic number of 0xEBFFFFB9FF9FC526 for rooks on a1 and indicates that you can use 11 bits instead of 12.

(By the way, thanks Grant! I'm sure I'll get this figured out.)

So does that mean that the rook_attacks table only has 2,048 entries?!

I wrote some test code: When I tested this statement against my 4,096 possible occupation bitmaps, I found that this statement produced the same value for "index" for more than one occupation bitmap.

I expected that to happen, but I assumed that the collisions would only occur for occupation bitmaps that have the exact same attack bitmap.

That wasn't the case. So... I can't use it to index my rook_attacks table as I'd like.

What am I missing? I'd really like to understand this concept, because my rook_attacks table is very large.

Thanks in advance for your help and patience, since I'm betting my terminology is not quite up to snuff.

Charlie Brune
St. Louis, Missouri

The collisions are as you assumed. Different occupancies can result in the same attack set many times, and these are used for "positive" collisions. I don't understand the math behind the collisions, and I doubt anyone else does. The magics were found by just pumping a bunch of random numbers and testing them out. So it's basically a coincidence that there are any positive collisions at all.

As for the magics on the wiki, I believe there is an issue with the square mapping. The discussion on that page mentions some issues. Feel free to join the wiki and correct it.

Zach Wegner wrote:The collisions are as you assumed. Different occupancies can result in the same attack set many times, and these are used for "positive" collisions. I don't understand the math behind the collisions, and I doubt anyone else does. The magics were found by just pumping a bunch of random numbers and testing them out. So it's basically a coincidence that there are any positive collisions at all.

As for the magics on the wiki, I believe there is an issue with the square mapping. The discussion on that page mentions some issues. Feel free to join the wiki and correct it.

I was about to ask Grant whether he already considered his a8==0 mapping, when he posted the numbers short before the winboard forum was locked. Seems I wrongly put the numbers to the flipped squares. Sorry, I didn't try out and counted to someone else to eventually correct the mappings.

To Charly:
it heavily is about positive or constructive collisions. For the corner rooks it is about to map 4096 occupancies to 49 distinct attack sets. How to find those dense magics is about trial and error so far, wasting some hours (or days) of cpu-time. One may try some N-bit magics as a first guess, where each individual bit of the scattered relevant occupancy is shifted left to one of the N upper bits.

Gerd

Zach Wegner wrote:
The magics were found by just pumping a bunch of random numbers and testing them out.

Not exactly!
First I realized that the random numbers needed to be very dense, then by analyzing the results I printed whilst searching I was easily able to identify which bits of the magic number needed to be set (or unset).

Grant

Thanks for your replies!

I'm now running a program that will look for more optimal magics. (i.e., a reduced number of bits).

I'll let you know how it goes.

Charlie Brune

If you are looking for more optimal magics, you shouldn't just rely on random numbers. As grant said, splitting the search into smaller parts, helps.
So for example, if you are trying to find magics for rooks, you could start with the row and then adding the columns. Then you can always check, how many index numbers are used and only continue with the most promising combinations. You will also find out, that there are certain patterns in the Magic numbers, as certain rook_masks only effect certain parts of the Magic.

PS: yesterday I tried to find a solution for Rook on b2 with this approach. Unfortunately I missed the 9 bits by a small margin, maybe I will try a little bit more this evening.
But my results for this were:
For the row on its own (0x7C00): 17 index numbers used
For 0x2000000007C00: 2*17 index numbers used
For 0x2020000007C00: 4*17 index numbers used
For 0x2020200007C00: 8*17 index numbers used
For 0x2020202007C00: 280 index numbers used
And for 0x2020202027C00 I wasn't able to find any more magics with less than 2^9 index numbers used. When I did this tests I always did the next step, excluding all magics-patterns with non optimal index numbers counts -maybe that was the mistake.

If you are looking for more optimal magics, you shouldn't just rely on random numbers. As grant said, splitting the search into smaller parts, helps.
So for example, if you are trying to find magics for rooks, you could start with the row and then adding the columns. Then you can always check, how many index numbers are used and only continue with the most promising combinations. You will also find out, that there are certain patterns in the Magic numbers, as certain rook_masks only effect certain parts of the Magic.

PS: yesterday I tried to find a solution for Rook on b2 with this approach. Unfortunately I missed the 9 bits by a small margin, maybe I will try a little bit more this evening.
But my results for this were:
For the row on its own (0x7C00): 17 index numbers used
For 0x2000000007C00: 2*17 index numbers used
For 0x2020000007C00: 4*17 index numbers used
For 0x2020200007C00: 8*17 index numbers used
For 0x2020202007C00: 280 index numbers used
And for 0x2020202027C00 I wasn't able to find any more magics with less than 2^9 index numbers used. When I did this tests I always did the next step, excluding all magics-patterns with non optimal index numbers counts -maybe that was the mistake.

I'll take a look at B2 9-bits.

Grant

Magic number found!

B2 9-bit = 48FFFE99FECFAA00

Hmm. This is the same as A2 10-bit. Double checking... Yep it works.

Grant

grant wrote:Magic number found!

B2 9-bit = 48FFFE99FECFAA00

Hmm. This is the same as A2 10-bit. Double checking... Yep it works.

Grant

I just tried it, but got:
0x48FFFE99FECFAA00*0x0400=0x1 23 FF FA 67 FB 3E A8 00 00
0x48FFFE99FECFAA00*0x0800=0x2 47 FF F4 CF F6 7D 50 00 00

These two should get different indexes, but thats not provided.

Edmund

I don't see any errors in my code. I have now checked and double checked again, and it works.
B2 is square 49 for me, so maybe B7 for you. Could you check again?

I have also found more 9-bit magic numbers for rooks so it would be nice to get this verified.

Grant