No bishop magics with fixed shift 8

[niklasf]

Here's an iterim result of my search for magic factors, that may be interesting: There is no magic factor with shift 8 for the bishop square d5. Therefore fixed shift magics will always have to use shift 9.

Using the trick from http://www.talkchess.com/forum/viewtopic.php?t=65187 I had to test only 2^50 candidates instead of all 2^64. This yielded a list of 364854 magics with shift 9: https://raw.githubusercontent.com/nikla ... hop-d5.txt

None of them works for shift 8 and the index range is from 0 to 511 for all of them.

Here's the program I used for this search: https://github.com/niklasf/magics/blob/ ... c/magics.c. It uses one more trick I haven't seen before: Try to order the relevant occupancies so that candidates are refuted as quickly as possible. Any other ideas for speeding this up are most welcome. Moving on to rooks now, after this warmup.

[ZirconiumX]

This line looks ripe for an OpenMP pragma, and the code looks to be thread-safe. You might find that helps.

[niklasf]

Yes, thanks. So far I've split the range into chunks and used GNU parallel, which requires a bit of bookkeeping.

[ZirconiumX]

This line looks ripe for an OpenMP pragma, and the code looks to be thread-safe. You might find that helps.

I think I spoke too soon; `refs` and `magic` are shared, and some bookkeeping that seems irrelevant is done. Still, your method of GNU Parallel works fine.

EDIT: you could add `-flto -fwhole-program` to CFLAGS, for optimisation purposes.

[bnewman]

Here's the program I used for this search: https://github.com/niklasf/magics/blob/ ... c/magics.c.

Unfortunately, this link no longer seems correct.
I was wondering if you also recognized that the minimum bound on a magic number is
2^(64-c-r0),
where r0 is the lowest numbered square of the relevant occupancies and c is the intended shift.
Suppose a magic number, m, exists with the associated right shift, c.
Then, if r0 represents the lowest numbered square in the relevant occupancy mask,
m * 2^r0 >> (64-c) >= 1.
(Otherwise a collision would exist with the hash for the open board.)
Therefore, m * 2^(r0+c-64) >= 1 and thus m >= 2^(64-c-r0).

[niklasf]

Sorry, I moved the file in the repository. It still exists under v1 in https://github.com/niklasf/magics.

Yes, that's a nice observation. Initially I did not think it is important, because due to the "-c" in the exponent the excluded range is quite small (at least compared to the period).

However it came up again (https://github.com/niklasf/magics/blob/ ... daq.c#L149) when I was working on a divide and conquer approach. I should write an explanation, and update the benchmarks. Essentially it uses lower bound and the period multiple times for subsets of the relevant squares: A factor that has collisions on subsets of the relevant squares cannot be a magic for the full set of squares, but r0 of the subset can be larger.

[bnewman]

Yes, I believe I know what you are talking about. I had the same idea myself.
Here is my explanation:
The search region is divided into multiple sections based upon the (2^c) - 1 possible choices for the hash for when only the lsb of the mask is occupied. For each of these choices, the maximum magic number is limited by the second lsb of the mask. This number is obtained by selecting the largest possible value for the hash for a relevant occupancy on only this square.
For instance, the square F6 (45) has a occupancy mask that includes the squares B2 (9), C3 (18), D4 (27), E5 (36), G5 (38), E7 (52), and G7 (54).
Assuming we are looking for magics that have a right shift of 7, we can determine the minimum possible magic number as:
2^(64-7-9) + 2^(64-7-18+1) = 0x1010000000000.
Additionally, the maximum value a magic number can be, when B2 hashes to 0x01, is limited by the hash for C3 being less than 128. With this in mind, the maximum magic for this range is:
2^(64-7-9) + 2^(64-7-18+7) - 1 = 0x13FFFFFFFFFFF.

The process can be repeated for the B2 occupancy hashing to other values.
Additionally, it may be possible to further partition the search space by looking beyond the least two significant bits in the mask.

[Fulvio]

For instance, the square F6 (45) has a occupancy mask that includes the squares B2 (9), C3 (18), D4 (27), E5 (36), G5 (38), E7 (52), and G7 (54).
Assuming we are looking for magics that have a right shift of 7, we can determine the minimum possible magic number as:
2^(64-7-9) + 2^(64-7-18+1) = 0x1010000000000.
Additionally, the maximum value a magic number can be, when B2 hashes to 0x01, is limited by the hash for C3 being less than 128. With this in mind, the maximum magic for this range is:
2^(64-7-9) + 2^(64-7-18+7) - 1 = 0x13FFFFFFFFFFF.

Interesting.
I understand that since the index is calculated as:
index = magic * bitboard >> n_shiftbits;
if only a square is set in bitboard we can redefine it as:
bitboard = 1 << square;
and we can rework the index formula as:
index = magic << square >> n_shiftbits;
We know that index should be at least 1, so this gives the first part of the two formulas:
2^(64-7-9)

Can you please explain the rest of the formulas with a little bit more details?

[bnewman]

I'll try to clarify (and correct) my post a bit with two examples. I do not yet have code to share for the algorithm, but I'm working on it.
The first example is a fairly simple case, the B2 square. The relevant occupancy mask for this square includes the squares C3 (18), D4 (27), E5 (36), F6 (45), and G7 (54).
If we are attempting to determine the absolute minimum value a magic number can be for B2 (associated with a 5-bit hash code), we might conclude that an occupancy on C3 could minimally hash to 0x01. This requires that magic*2^18 >> (64-5) = 1, or magic << 18 = 1 << (64-5). In other words, counting up from the LSB, bit number 64-5-18 = 41 must be set.
But we can now also examine possible hashes for the D4 occupancy. With 0x00 and 0x01 taken, the next available choice is 0x02. This choice requires that magic << 27 >> (64-5) = 2, which implies that magic << 27 = 2 << (64-5), so bit 33 must be set.
Continuing, we now observe that since the hashes 0x00, 0x01, and 0x02 have been used, we cannot use 0x03 as the hash for the E5 occupancy, since this would collide with the hash for both C3 and D4 being occupied. The next minimum choice is 0x04. This leads to magic << 36 = 4 << (64-5), so bit 25 must be set.
For F6, we see that magic << 45 = 8 << (64-5), so bit 17 should be set.
Finally, for G7, we obtain magic << 54 = 16 << (64-5), so bit 9 is set.
Overall, this leads to the following hexadecimal representation for the minimum possible magic for the B2 square: 0x 0000 0202 0202 0200 (spaces added to improve readability). As it turns out, this “minimum possible” magic is, in fact, a valid magic number for the B2 square (with shift of 5).
In my next example (next post), I will deal with some rather tricky nuances involving relevant occupancy bits that are close together.

[bnewman]

While the result in my previous post is correct, there is an error that I have introduced and wish to correct. It is not true that magic << 18 >> (64-5) = 1 implies that magic << 18 = 1 << (64-5), because there may be lower significant bits in the magic number. Sorry for the confusion.
In this post, I will determine the minimum magic for the C1 square, whose relevant occupancy mask includes the squares B2 (9), D2 (11), E3 (20), F4 (29), and G5 (38).
Again, we start by assigning a hash of 1 to the occupancy of the least significant (lowest) square (B2). This implies that bit (64-5-9) must be set. Now, however, the choices available for the D2 square hash is even more limited than before. The reason for this is that the resulting hash code must contain the bit set for the B2 square. Since the B2 square hash was chosen to be 1, bit 2 of the hash for D2 must always be set (LSB is bit 0). Therefore, the only choices for the D2 hash are 0x04, 0x05, 0x06, 0x07, 0x0C, 0x0D, 0x0E, 0x0F, 0x14, 0x15, 0x16, 0x17, 0x1C, 0x1D, and 0x1E. (0x1F is not available since this would cause the resulting hash for occupancies on both B2 and D2 to be 0, since 0x1F and 0x01 = 0x20 = 0 mod 32). By choosing 4 as the minimum available hash for D2 we are sharing the bit that was set for the B2 hash, bit 50**. (Explanatory note: since squares B2 and D2 are numerically 2 apart [11-9 = 2], any hash code chosen for B2 is left shifted by 2 and OR'ed with the remaining bits available for the D2 hash.)
Fortunately for us, the rest of the consecutive relevant occupancy squares are all separated by at 9 squares, so we can continue with these bits as before. An occupancy on the E3 square can hash to 2 since this number has not yet been used. This implies that bit 40 (=64-5-20+1) should be set.
An occupancy on the F4 square can hash to 8 which implies that bit 33 (=64-5-29+3) should be set.
An occupancy on the G5 square must then hash to 16 which implies that bit 25 (=64-5-38+4) should be set.
This leads to the minimum magic number for the C1 square being 0x 0004 0102 0200 0000.

** I have seen magic numbers for Bishop moves wherein as many as three relevant occupancy squares share the same bit. I have not looked at Rook magics yet, but I can imagine that many of the moves on the same rank could share a single bit.