On the establishment of domains wherein magic numbers can and cannot exist

[bnewman]

Consider an arbitrary 64-bit number, M. For each square, S, in a relevant occupancy mask, a separate N-bit whole number and an additional fractional part can be generated from the 64-bit number as follows:
The whole number part will consist of the N bits of M from bit 64-S to bit 64-S-N.
The fractional part will consist of the remaining LSBs of M.
A hash code is generated by adding together the whole and fractional parts of the number associated with each of the occupied relevant occupancy bits, stripping off the remaining fractional part and any overflow bits.
M is a magic number for this relevant occupancy mask if and only if the following condition is valid:

• If a hash code for one set of occupied squares collides with the hash code for another set of occupied squares, then the occupied squares closest to the piece square along each ray in each set must be identical.

As an example, I select the magic found by Gerd Isenberg for the Bishop on G8 with shift of 4: 0x 7E8E4BB2F736 (with his MSBs trimmed off according to the work done by Niklas Fiekas in http://www.talkchess.com/forum3/viewtopic.php?t=65187). In binary, this number is represented thus:
111 1110 1000 1110 0100 1011 1011 0010 1111 0111 0011 0110.
In this case, the numbers associated with each of the relevant squares are:
B3 (17) --- > 1111.110100011100100… which is a bit more than 15 13/16.
C4 (26) --- > 0011.100100101110110… which is a bit more than 3 9/16.
D5 (35) --- > 0101.110110010111101… which is somewhat more than 5 13/16.
E6 (44) --- > 0010.111101110011011… which is about 2 15/16.
F7 (53) --- > 1110.0110110 which is about 14 6/16.
We would expect that occupancies including the F7 square should have the most collisions—each of which returning an attack bitboard containing only the F7 square. The sixteen possible relevant occupancies that contain the F7 square hash to the following numbers: 14,14,1,1,4,4,7,7,1,1,4,4,7,7,10,10.
The eight possible relevant occupancies that contain E6, but not F7 hash to the following:
2,2,6,6,8,8,12,12
The four relevant occupancies that contain D5, but neither E6, nor F7 hash like so:
5,5,9,9
The two relevant occupancies that contain C4, but not D5, E6, or F7 hash thusly:
3,3
And finally, the relevant occupancy in which only the B3 square is involved hashes as:
15

With this information as the background, it seems that one should be able to partition the domain of all 64-bit numbers into sections which can and cannot contain magic numbers for a particular square, sliding attack type, and shift amount. See also some preliminary ideas discussed in http://www.talkchess.com/forum3/viewtopic.php?t=65187
I plan to add to this topic in future posts to demonstrate some ideas in this regard.

[Fulvio]

A bishop on G8 is the easiest case, because all the relevant squares are aligned and well spaced.
We can than decompose magic * bitboard into (magic * 2^square1) + (magic * 2^square2) + ...
without worrying about collision and interference.
With very few lines of code we can quickly find 48 valid** magic:
https://ideone.com/B9S40Q

Code: Select all

#include <iostream>
#include <iomanip>
#include <bitset>

template <typename TCont>
bool valid_index(uint8_t v1, uint8_t v2, TCont& slots) {
    uint8_t index = static_cast<uint8_t>(v1 + v2) >> 4;
    if (index == 0) { // Index 0 is invalid
        return false;
    }
    if (slots[index] == 0) { // An empty slot is valid
        slots[index] = v1;
        return true;
    }
    // A collision is valid only if they share the lowest index
    return (slots[index] == v1);    
}

int main() {
    unsigned long long count = 0;
    unsigned long long valid_count = 0;

    // For every sorted combination of 5 indexes
    const uint8_t step = 0b0000'0010;
    for (uint8_t i1 = 0b0001'0000; i1; i1 += step)
    for (uint8_t i2 = 0b0001'0000 + (i1 & 0xF0); i2; i2 += step)
    for (uint8_t i3 = 0b0001'0000 + (i2 & 0xF0); i3; i3 += step)
    for (uint8_t i4 = 0b0001'0000 + (i3 & 0xF0); i4; i4 += step)
    for (uint8_t i5 = 0b0001'0000 + (i4 & 0xF0); i5; i5 += step) {
        ++count;
        
        uint8_t slots[16] = {};
        if (valid_index(i1, 0, slots) &&
            valid_index(i2, 0, slots) &&
            valid_index(i3, 0, slots) &&
            valid_index(i4, 0, slots) &&
            valid_index(i5, 0, slots) &&
            valid_index(i1, i2, slots) &&
            valid_index(i1, i3, slots) &&
            valid_index(i1, i4, slots) &&
            valid_index(i1, i5, slots) &&
            valid_index(i2, i3, slots) &&
            valid_index(i2, i4, slots) &&
            valid_index(i2, i5, slots) &&
            valid_index(i3, i4, slots) &&
            valid_index(i3, i5, slots) &&
            valid_index(i4, i5, slots) &&
            valid_index(i1, i2 + i3, slots) &&
            valid_index(i1, i2 + i4, slots) &&
            valid_index(i1, i2 + i5, slots) &&
            valid_index(i1, i3 + i4, slots) &&
            valid_index(i3, i3 + i5, slots) &&
            valid_index(i1, i4 + i5, slots) &&
            valid_index(i2, i3 + i4, slots) &&
            valid_index(i2, i3 + i5, slots) &&
            valid_index(i2, i4 + i5, slots) &&
            valid_index(i3, i4 + 15, slots) &&
            valid_index(i1, i2 + i3 + i4, slots) &&
            valid_index(i1, i2 + i3 + i5, slots) &&
            valid_index(i1, i2 + i4 + i5, slots) &&
            valid_index(i1, i3 + i4 + i5, slots) &&
            valid_index(i2, i3 + i4 + i5, slots) &&
            valid_index(i1, i2 + i3 + i4 + i5, slots))
        {
            ++valid_count;
            std::cout << "Valid combination: ";
            std::cout << std::setw(10) << (i1 / 16.0);
            std::cout << std::setw(10) << (i2 / 16.0);
            std::cout << std::setw(10) << (i3 / 16.0);
            std::cout << std::setw(10) << (i4 / 16.0);
            std::cout << std::setw(10) << (i5 / 16.0) << "\n";

            auto magic = 60ull << 56;
            magic |= static_cast<uint64_t>(i1) << (60 - 53 - 4); // F7
            magic |= static_cast<uint64_t>(i2) << (60 - 44 - 4); // E6
            magic |= static_cast<uint64_t>(i3) << (60 - 35 - 4); // D5
            magic |= static_cast<uint64_t>(i4) << (60 - 26 - 4); // C4
            magic |= static_cast<uint64_t>(i5) << (60 - 17 - 4); // B3
            std::cout << "Magic: " << std::hex << magic << std::dec;
            std::cout << "  " << std::bitset<64>(magic) << "\n\n";
        }
    }

    std::cout << valid_count << "/" << count << std::endl;
}

**I have checked only the last one:
https://ideone.com/mezweJ