Finding special magic numbers

[dangi12012]

I have a solution with a 4K table (for knights but same idea) (and also without array of magic multipliers and no pext) so it's probably not what I need yet. This also probably doesn't scale to sliders because a way bigger array size right?

Then you are working on something different.

This solution has a minimum size of 10k for knight/king and somehting around 100k slots for rooks/bishops,
It allows you to hash any valid possible set of valid move bits - to an index into a compiletime movelist.
So the actual "from, to, function pointer or data to permute the board" can be baked leading to much better perfromance.
Also branch prediction can be better - since the baked movelist can for example always contain 8 entries making the processor very happy.
(unrollable loops are more expensive then people think - when you really optimize to the maximum)
doing extra work - but a fixed amount of times may be better then looping the exact amount of times. Mailslot devs will know.

[gxchess1]

You are right, I messed up. The pattern I gave for the Knight on a1 is not correct. A, b, c and d should all have been shifted 8 bits down. That means the left shifts to bring those in view should have been 8 larger (41 instead of 33, 51 instead of 43). So the magic multiplier should have been 0x0008020000002020ull.

Do you know if such numbers would exist for bishops and rooks? If so, what are those?

[hgm]

For leapers it it works because these always have the same, shifted pattern, where some of the moves can be clipped off by the board edge. To get that same property for sliders, you would have to allow 7 moves in each of the four directions. So there would be a magic multiplier that collects a unique signature in the upper 28 bits. But that is too many bits to be useful. For sliders you must make essential use of the fact that not all their moves in opposit directions can be possible at the same time, and only collect those that are. And then omit the edge bits, corresponding to squares that cannot block moves to any other squares. But all that is dependent on the location. So you must use different multipliers for each square.

Of course for a given square you can easily construct a multiplier by hand. E.g. the attacks of a rook could be

Code: Select all

. . . . . . . .
. . . 1 . . . .
. . . 2 . . . .
. 3 4 . 5 6 7 .
. . . 8 . . . .
. . . 9 . . . .
. . . A . . . .
. . . . . . . .

You can left-shift 11 bit to get 1 and 2 in the upper ten bits, shift 34 to get 8 and 9 there, and 23 to get 3-7 there:

Code: Select all

1 . . . . . . . 2 . . . . . 3 4 . 5 6 7 . . . (<< 11)
. 8 . . . . . . . 9 . . . . . . . A . . . (<< 34)
. . 3 4 . 5 6 7 . . . . 8 . . . . . . . 9 (<< 23)
. . . . A . . . . . . . (<< 47)
_______________________________________ +
1 8 3 4 A 5 6 7 2 9 . . 8 . 3 4 ? ? 6 7 

There is enough spacing between the 9 and the lower stuff that there cannot be contamination by carry, and there are no collisions. So the magic multiplier is 0x0000800400800800ull.

[dangi12012]

Now here's an idea:
Try to find magics with as least bits as possible. There are some with only 1 bit set and some with 2 bits for certain squares. Making multiplication replaceable by much faster instructions.

Also find magics that are below 2^32 as imul32 is much cheaper.
Generally for all squares that's not possible but I think I found 5 bit solutions for all squares if memory serves (that is 64bit integers with 5 bit set)

If there exists a shift pattern that extend itself through all squares magics would not have to be looked up at all.