maybe a bit premature, but as I already anounced, I post now.

I am currently implementing fixed shift values for magic bitboards. That is, instead of looking up the shift in a table, always shift by 52 for rooks and 55 for bishops. This safes the time to look up the shift value.

Obviously this works with the normal magic multipliers, but that would needlessly blow up the attack table so the program would most likely run slower in a real world environment. The trick is to find multipliers for that the magic product always has the appropriate number of highest bits zero. If one found such multipliers for every square, the table size would not increase at all. I believe that for most squares such multipliers do exist.

First I gave up to get good collisions. E.g. I only want the multiplier to yield the same number of relevant bits in the product as there are squares in the mask. Finding multipliers with good collisions is hard, but in the end the best known multipliers according to my knowledge only safe about 10% of table size for rooks, while there are no known reductions for bishops at all.

Then I set out to compute rook multipliers for all squares a1, b1, ... This takes a little more time then expected, but the results look very promissing. I arrived at d2 now and have found the desired multipliers for 9 out of 12 squares. (OK, a1 and h1 are trivial, so 7 out of 10.) In the remaining cases (f1, a2, and c2) I still found multipliers that produce relatively small indices. That's why I believe that a fixed shift is possible without blowing up the table too much.

Multipliers so far:

- Code: Select all
`0x0080102040008000, 0x0020000800100020, 0x0040100008004004, 0x0040080004004002,`

0x0040040002004001, 0x0040008200010040, 0x0040004000800100, 0x0080002040800100,

0x0000400010200040, 0x0000100400080010, 0x0000400440080010, 0x0000200400020020

Table sizes so far:

- Code: Select all
`0x1000, 0x0800, 0x0800, 0x0800,`

0x0800, 0x0a00, 0x0800, 0x1000,

0x0a00, 0x0400, 0x0600, 0x0400

I will continue to compute multipliers and also do bishop multipliers.

Note that above only works with true 64 bit multiplication. I will try to apply Grant's 32 bit trick later, but that looks difficult, esp. for

- bishops that attack e4, f4, or g4 and

- rooks that attack g4 or h4.