No bishop magics with fixed shift 8

[Fulvio]

I see, given a 64-bit magic number and a bitboard with only one square, we can divide it in 3 parts considering how it affects the index:
the first (64 - n_hashbits - square - 1) bits are ignored, due to the right shift;
the last (square) bits are ignored, due to the left shift;
the bits in the middle must not all be 0, otherwise the index will be 0 too.

For the square B2, n_hashbits = 5 and square = 9, so
the first 0-49 (64 - 5 - 9 - 1) bits are ignored;
the last 55-63 bits are ignored;
the bits 50-54 must not be 0

For the square D2, n_hashbits = 5 and square = 11, so
the first 0-47 (64 - 5 -11 - 1) bits are ignored;
the last 53-64 bits are ignored;
the bits 48-52 must not be 0

For the square E3, square = 20, so the bits 39-43 must not be 0
For the square F4, square = 29, so the bits 30-34 must not be 0
For the square G5, square = 38, so the bits 21-25 must not be 0

Combining the above you get that the minimum valid magic number is:
2^50 + 2^39 + 2^30 + 2^21
or in c++ notation
(1ull << 50) + (1ull << 39) + (1ull << 30) + (1ull << 21)

However the above maps D2 to index 4, and all the other squares to index 1.
So we should increase the magic number to:
(1ull << 50) + (2ull << 39) + (3ull << 30) + (5ull << 21)

and now the minimum magic number is 0x40100c0a00000
https://ideone.com/CygT3J

It can be probably further increased: for example a bitboard with B2 and E3 maps to 3.
And you calculated that F4 should map to 8 and G5 to 16:
(1ull << 50) + (2ull << 39) + (8ull << 30) + (16ull << 21)
but you should demonstrate why they are the minimum valid values.

[bnewman]

However the above maps D2 to index 4, and all the other squares to index 1.
So we should increase the magic number to:
(1ull << 50) + (2ull << 39) + (3ull << 30) + (5ull << 21)

and now the minimum magic number is 0x40100c0a00000
https://ideone.com/CygT3J

If you try this as a magic number for the C1 square you will see that it does not work.
The reason is that the resulting hash for the F5 square being solely occupied collides with the hash for the B2 and E3 squares occupied. (3 = 1 + 2)
Additionally, the hash for the G6 square being solely occupied collides with the hash for the B2 and D2 squares occupied (5 = 1 + 4).

The magic number needs to be increased to :
(1ull << 50) | (4ull << 48 ) | (2ull << 39 ) | (8ull << 30) | (16ull << 21) =
(1ull << 50) + (2ull << 39 ) + (8ull << 30) + (16ull << 21)

Of course other choices than powers of two can be chosen for the hashes for individually occupied relevant squares.
We would also be happy with a magic number that hashes any relevant occupancy including the D2 square, but NOT the B2 square to the same code because the attack ray from C2 in each of these cases should stop at D2. (Similarly for relevant occupancies that include the E3 square and neither D2 nor B2, etc.) But, I do not think that these would be minimum magic numbers.

[Fulvio]

and now the minimum magic number is 0x40100c0a00000

If you try this as a magic number for the C1 square you will see that it does not work.

Yes, it is not the minimum valid magic number, but it is a guaranteed lower bound; i.e. any smaller number cannot be a valid magic number.
It also provides an algorithm to construct all the numbers that can be a valid magic:
https://ideone.com/mZmDVt

However, I'm still not sure if the math is really correct.

[bnewman]

My argument that 0x 0004 0102 0200 0000 is the minimum magic number for the C1 square with a shift of 5 is this:
From the MSB of the magic number (bounded by the lowest relevant square) to the LSB (bounded by the highest relevant square), we have selected the smallest possible numbers for hash values which avoid collisions with previously chosen hash values. Having made each section of this magic number as small as possible from the MSB down, how can there be any smaller magic number?

I think with a good discussion on this, we may be able to come up with a more robust theory of magic numbers, their generation, and properties. I have some loose ideas that might link this with linear algebra, vector spaces, and transformations, but its still just a germ of an idea. I wish I had more time to think about this.

[Fulvio]

we have selected the smallest possible numbers for hash values which avoid collisions with previously chosen hash values.

That's the problem. We know that collisions can be valid.
Picking powers of 2 generates big gaps, so it is necessary to demonstrate that all those gaps are filled with invalid collisions.

I think with a good discussion on this, we may be able to come up with a more robust theory of magic numbers, their generation, and properties.

Another interesting observation from the above formulas is that the top 9 bits of the magic numbers are always ignored, because any bitboard mask is at least 9. This allows to store the shift value directly into the top byte of magic number.
For example the Stockfish's Magic:

Code: Select all

/// Magic holds all magic bitboards relevant data for a single square
struct Magic {
  Bitboard  mask;
  Bitboard  magic;
  Bitboard* attacks;
  unsigned  shift;

  // Compute the attack's index using the 'magic bitboards' approach
  unsigned index(Bitboard occupied) const {
        return unsigned(((occupied & mask) * magic) >> shift);
  }
};

can be written as:

Code: Select all

struct Magic {
  Bitboard  mask;
  Bitboard  magic;
  Bitboard* attacks;

  unsigned index(Bitboard occupied) const {
        const auto shift = magic >> 56;
        return unsigned(((occupied & mask) * magic) >> shift);
  }
};

Saving 8 * 64 = 512 bytes

[bnewman]

That's the problem. We know that collisions can be valid.
Picking powers of 2 generates big gaps, so it is necessary to demonstrate that all those gaps are filled with invalid collisions.

I see your point. Let me consider this a bit more.

Another interesting observation from the above formulas is that the top 9 bits of the magic numbers are always ignored, because any bitboard mask is at least 9. This allows to store the shift value directly into the top byte of magic number.

Yes, the MSB "playground" was also determined another way by Niklas Fiekas in http://www.talkchess.com/forum3/viewtopic.php?t=65187 and storing the shift there was introduced by Grant Osborne in http://www.talkchess.com/forum3/viewtop ... 57&t=21329.

[Fulvio]

Some futher considerations, I hope the math is correct.

For a bishop in C1, let's define:
bitboard_D2 = 1 << 11;
bitboard_E3 = 1 << 20;
bitboard_D2_E3 = bitboard_D2 + bitboard_E3;

If we search for a 4 bits hash, we know that:
idx_bitboard_D2 > 0 && idx_bitboard_D2 < 16
idx_bitboard_E3 > 0 && idx_bitboard_E3 < 16
magic = (idx_bitboard_D2 << 49) + (idx_bitboard_E3 << 40) + unknown;
unknown < (1 << 49)

We also know that we need to have at least 16 valid collisions, so we want:
idx_bitboard_D2_E3 = idx_bitboad_D2

We start with:
idx_bitboard_D2_E3 = (magic * bitboard_D2_E3) >> 60
and we can expand:
(magic * bitboard_D2_E3)
= magic * (1 << 11) + magic * (1 << 20)
= magic * (1 << 11) + (idx_bitboard_D2 << 69) + (idx_bitboard_E3 << 60) + (unknow << 20)
= (idx_bitboard_D2 << 60) + (idx_bitboard_E3 << 51) + (unknow << 11) + (idx_bitboard_E3 << 60) + (unknow << 20)
= ((idx_bitboard_D2 + idx_bitboard_E3) << 60) + (idx_bitboard_E3 << 51) + (unknow << 11) + (unknow << 20)

let x = ((idx_bitboard_E3 << 51) + (unknow << 11) + (unknow << 20)) >> 60
then
idx_bitboard_D2 = ((idx_bitboard_D2 + idx_bitboard_E3) << 60 >> 60) + x

Since all the number are positive, we have demonstrated that an overflow is necessary to achieve the collision.
If we demonstrate that x can be only 0 or 1 we can find all the possible valid indexes with:

Code: Select all

for (int idxD2 = 1; idxD2 < 16; ++idxD2) {
  for (int idxE3 = 1; idxE3 < 16; ++idxE3) {
    if (idxE3 == idxD2) continue;
    auto idx0 = (idxD2 + idxE3) & 0x0F;
    auto idx1 = (idxD2 + idxE3 + 1) & 0x0F;
    if (idx0 == idxD2 || idx1 == idxD2) {
       std::cout << "Valid pair: " << idxD2 << "  " << idxE3 << "\n";
    }
  }
}

and the result is that idx_bitboard_E3 must be 15 and that the bitboard_D2_F4 and bitboard_D2_G5 cannot have the same index as bitboard_D2.

[bnewman]

We also know that we need to have at least 16 valid collisions, so we want:
idx_bitboard_D2_E3 = idx_bitboad_D2

It seems that there are other ways to get the necessary collisions, for instance:
idx_bitboard_D2_G5 = idx_bitboard_D2

I have started a new topic to discuss the partitioning of all possible 64-bit numbers into regions wherein magic numbers can and cannot be found at http://www.talkchess.com/forum3/viewtop ... =7&t=70341.
With the ideas established there, I think I can prove that the magic I identified earlier is the minimum possible magic number for the C1 square Bishop moves with a shift of 5.
Of course, it will be more interesting to apply this to a search for dense magics.