Re: No bishop magics with fixed shift 8
Posted: Mon Mar 25, 2019 5:42 pm
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.
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.