A Faster Magic Move Bitboard Generator?

[Onno Garms]

Are you still having a problem with your rook multiplier for square number 27 or is it fixed now?

Well, I replaced it with the multiplier that I posted. That works. But if yours is really buggy it's strange that noone before me noticed that.

I believe that this program demonstrates the bug:

Code: Select all

#include <iostream>

typedef unsigned long long U64;

const U64 d2 = 1ULL<<(1*8+3);
const U64 d7 = 1ULL<<(6*8+3);

const U64 magic = 0x0F4A2006C2001602ULL;
//const U64 magic = 0x0021000800001001ULL;
const int shift = 22;


U64 index (U64 occ)
{
   unsigned int lo = (int)(occ) * (int)(magic);
   unsigned int hi = (int)(occ >> 32) * (int)(magic >> 32);
   return (lo ^ hi) >> shift;
}


int main ()
{
  if (index(d2) == index(d2|d7))
    std::cout << "multiplier is broken" << std::endl;
}


Since I discovered that the shift can be incorporated in the multiplier,

Interesting idea. Saves one memory access. But aren't the shifts in cache anyway? Then I would assume that a lookup in a separate table is faster then extracting the shift from the multiplier. Have you done tests?

I found that the better magics are the more dense ones for a smaller table.

Sure. I meant that I prefer multipliers with fewer bits set (as in 0x0021000800001001 compared to 0x0F4A2006C2001602) when the shifts are the same. With "sparse" I refered to "fewer bits set in multiplier" not "more remaining bits after shift".

But the reason for replacing the multiplier was that I believe that the latter multiplier is broken. So I computed a correct one with pencil and paper, and I am unable to find multipliers with many bits set this way.

[Grant Osborne]

I double checked square 27. Works fine. No bugs. And while testing I found a better one 0xB750100C0100220E
I also tried your number 0x0021000800001001 and that works OK too.

Incorporating the shift in the multiplier makes absolutly no difference in the speed as I thought it might, but rather than change them all back I just kept what I found.

Grant

[Onno Garms]

I double checked square 27. Works fine. No bugs.

Why does above program print "multiplier is broken" then?

And while testing I found a better one 0xB750100C0100220E

Also broken. Maps d2 and d2+g4 to same index.

I also tried your number 0x0021000800001001 and that works OK too.

Nice to hear.

Incorporating the shift in the multiplier makes absolutly no difference in the speed as I thought it might, but rather than change them all back I just kept what I found.

Thank you anyway. This motivated a similar idea in mind that should make a little difference in speed. If it works I will post this Wednesday.

[Onno Garms]

And while testing I found a better one 0xB750100C0100220E

Also broken. Maps d2 and d2+g4 to same index.

Sorry. The new one is OK. I forgot to exchange high and low dword when inserting into my engine.
But the original one still seems to be broken to me.

[Grant Osborne]

Onno

Are you able to establish which of the 1024 masked occupations is failing?

Grant

[Onno Garms]

Are you able to establish which of the 1024 masked occupations is failing?

I already did. d2 and d2|d7 map to the same index. Because the attack set is different for them, one of them must fail. Which one depends on the implementation.

[Grant Osborne]

Onno

You say that D2 and D2|D7 map to the same index using the multiplier 0x0F4A2006C2001602

D2 = 0x0000000000000800
D2|D7 = 0x0008000000000800


For D2

Code: Select all

0xC2001602 * 0x00000800 = 0x00B01000
0x0F4A2006 * 0x00000000 = 0

0x00B01000 ^ 0 = 0x00B01000
0x00B01000 >> 22 = 2

For D2|D7

Code: Select all

0xC2001602 * 0x00000800 = 0x00B01000
0x0F4A2006 * 0x00800000 = 0x03000000

0x00B01000 ^ 0x03000000 = 0x03B01000
0x03B01000 >> 22 = 14

I would say they do not map to the same index.

Grant

[Onno Garms]

0x0F4A2006 * 0x00800000 = 0x03000000

No. 0x0F4A2006 * 0x00080000 = 0x00300000

[Grant Osborne]

My apologies. You are correct.
0xF4A2006C2001602 is broken.

Grant

[Onno Garms]

My apologies. You are correct.
0xF4A2006C2001602 is broken.

No problem.

[Grant Osborne]

I have another magic number for this square 0xB022221F00480812 which only requires 1020 elements. Perhaps you could check this for me?

You said you had an idea that might make a little speed difference. Any luck?

Grant

[Onno Garms]

I have another magic number for this square 0xB022221F00480812 which only requires 1020 elements. Perhaps you could check this for me?

Correct as a 10-bit magic. My framework does not tell if 1020 elements are sufficient or if all 1024 are needed. Wouldn't be too hard to implement, but I prefer to work on my idea, see below.

You said you had an idea that might make a little speed difference. Any luck?

Still trying. I expect (positive or negative) results for 64 bit this evening. 32 bit is more difficult.