Properties of magic numbers

[gxchess1]

Questions about magic numbers:

1) Does a magic factor which works with black magic bitboards, always work with white magic bitboards and vice versa? Reasoning: After the masking, the difference between black magic bitboards and white magic bitboards is ~relevant_occupancy] , so black magic bitboards are essentially (occ + ~relevant_occupancy ) * factor and white magic bitboards are essentially occ * factor, since multiplication is distributive over addition, the difference after multiplying with the factor should always be ~relevant_occupancy * factor (modolu 2^64 ofc).

2) If 1 is true, does a magic factor which works with black magic bitboards and also work with shift W, work for white magic bitboards with shift W?

3) Consider white magic bitboards (with shift w) aka '(m * o) >> w'. Can I correctly say that the minimum magic factor 'm' is '(1 << w) / maximum_occupancy '? That is because (1 << w) is the minimum index, and it seems to me that the minimum is the result of the division.

Thanks I will probably have more questions in the future so I will ask in this thread.

[Mike Sherwin]

Questions about magic numbers:

1) Does a magic factor which works with black magic bitboards, always work with white magic bitboards and vice versa? Reasoning: After the masking, the difference between black magic bitboards and white magic bitboards is ~relevant_occupancy] , so black magic bitboards are essentially (occ + ~relevant_occupancy ) * factor and white magic bitboards are essentially occ * factor, since multiplication is distributive over addition, the difference after multiplying with the factor should always be ~relevant_occupancy * factor (modolu 2^64 ofc).

2) If 1 is true, does a magic factor which works with black magic bitboards and also work with shift W, work for white magic bitboards with shift W?

3) Consider white magic bitboards (with shift w) aka '(m * o) >> w'. Can I correctly say that the minimum magic factor 'm' is '(1 << w) / maximum_occupancy '? That is because (1 << w) is the minimum index, and it seems to me that the minimum is the result of the division.

Thanks I will probably have more questions in the future so I will ask in this thread.

There will probably be incompatible collisions. My guess is that there are relatively few out of billions that work for a certain square so changing anything probably results in a different set of solutions. That is just my best guess though.

Luckily, for me at least, my newest generator is very competitive with black magic. The rook by itself is testing 27% faster than Black Magic Rooks. The bishop not so much. But more testing is needed. Maybe KiSSY Rooks and Black Magic Bishops are the way to go.

The following quote is not from a real engine, only a test platform. There are a few names for my method but I now call it KiSSY, lol.

by martinn » Tue May 02, 2023 10:44 am

Mike Sherwin wrote: ↑Sun Apr 30, 2023 5:25 pm
martinn wrote: ↑Sun Apr 30, 2023 4:55 pm
I have also tried to do some profiling. I have never done that before but I think that KGSSB::rook runs aproximately 3-4x times faster than function KGSSB::bishop. So I was thinking that it could be interesting to combine KGSSB::rook with for example Black magic Bishop and queen could be KGSSB::rook | BlackMagic::bishop. It might be interesting to see if it would be faster or not.
That would be surprising. However, if the KGSSB::rook & Black Magic Bishop is the fastest combo then that should be the standard use.

I downloaded your code and will study it. Thanks
Well today I played with Daniel's Chess Movegen. I compared KGSSB Rook with BlackMagic Rook. These are the results:
KGSSB Rook 1004.713782 16544 [129kb] imul64 no https://www.talkchess.com/forum3/viewto ... 4&start=30
Black Magic Rook 789.071881 88891 [694kb] imul64 no Onno Garms and Volker Annuss https://www.chessprogramming.org/Magic_ ... hift_Fancy

For bishop I got these results:
KGSSB Bishop 792.945953 16544 [129kb] imul64 no https://www.talkchess.com/forum3/viewto ... 4&start=30
Black Magic Bishop 1087.234239 88891 [694kb] imul64 no Onno Garms and Volker Annuss https://www.chessprogramming.org/Magic_ ... hift_Fancy

The results simply almost switched. Maybe that is the reason why BlackMagic and KGSSB results for Queen are so similar. Then I merged KGSSB::Rook with BlackMagic::Bishop and these are new results for the Queen:

KGSSB Bishop + BlackMagic Bishop 580.753818 16544 [129kb] imul64 no https://www.talkchess.com/forum3/viewto ... 4&start=30
Black Magic BB 501.439549 88891 [694kb] imul64 no Onno Garms and Volker Annuss https://www.chessprogramming.org/Magic_ ... hift_Fancy
Kindergarten Super SISSY Bitboards 495.964912 16544 [129kb] imul64 no Michael Sherwin https://www.talkchess.com/forum3/viewto ... 4&start=30
Pext constexpr 717.957554 107904 [843kb] pext_u64 yes Zach Wegner https://www.chessprogramming.org/BMI2#PEXTBitboards
SISSY Bitboards 178.695824 180416 [1409kb] none no Michael Sherwin http://www.talkchess.com/forum3/viewtop ... =7&t=73083
Fancy Magic BB - Variable shift 362.512575 93376 [729kb] imul64 yes Pradu Kannan https://www.chessprogramming.org/Magic_Bitboards#Fancy

So it looks like that it is aproximately 16% faster than both BlackMagic and KGSSB. So Kindergarten of Black Magic Sissy Bitboards looks promising .

However, the permutations need testing in a real world engine.

[Volker Annuss]

1) and 2) No. it does not work, It's the constant offset ~mask * factor that makes black magics a little different from white magics.

3) You can say that every magic factor m is at least as big as (1 << w) / maximum_occupancy, but (1 << w) / maximum_occupancy is not necessary a magic factor.

[gxchess1]

1) and 2) No. it does not work, It's the constant offset ~mask * factor that makes black magics a little different from white magics.

3) You can say that every magic factor m is at least as big as (1 << w) / maximum_occupancy, but (1 << w) / maximum_occupancy is not necessary a magic factor.

About 3: Makes sense to me, okay and thanks.

About 2: Ok true I verified it now but here are some interesting facts: According to a simulation which I did now, with a completely random generator (avg 32 bits, not sparse) the probability that a magic number works for both white and black magics is: >0.99 for shift>13, >0.9 for 10<shift<13, 0.87 for shift=9, 0.77 for shift=8, 0.57 for shift=7, 0.28 for shift=6, and 0.07 for shift=5.

Anyways, I wonder if anyone knows why for example if you have a magic, why is -magic more likely to be a magic than another random number? How do I analyze the patterns? Anything? Literature about it?

[Volker Annuss]

Anyways, I wonder if anyone knows why for example if you have a magic, why is -magic more likely to be a magic than another random number? How do I analyze the patterns? Anything? Literature about it?

Because (-magic)*something == -(magic*something) == ~(magic*something)+1 so when shifting that right you almost always get all relevant bits inverted. Except for the guaranteed overflow to 0 for white magics with empty occupancy, there almost always is a bijective function from the indexes you get from magic to the indexes you get from -magic.

[dangi12012]

Finally finally finally I found my old hashing program!

This was a research project to find magic numbers that dont need to be looked up anymore but we can "maybe" shift a constant by the square and be done. I have searched and found no single pattern but some constants that highly correlate to each other.

I can finally show the pattern of magics that can be found for instance the rook squares:

Code: Select all

0000000000000001000000100000010000001000000100000010000000000000 - 0 p:24550
0000000000000000100000010000001000000100000010000001000000000000 - 1 p:27242
0000000000000000010000001000000100000010000001000000100000000000 - 2 p:29026
0000000000000000001000000100000010000001000000100000010000000000 - 3 p:29958
0000000000000000000100000010000001000000100000010000001000000000 - 4 p:30348
0000000000000000000010000001000000100000010000001000000100000000 - 5 p:30456
0000000000000000000001000000100000010000001000000100000010000000 - 6 p:30492
0000000000000000000000100000010000001000000100000010000001000000 - 7 p:30492
0000000000000000000000010000001000000100000010000001000000000000 - 8 p:8136
0000000000000000000000001000000100000010000001000000100000000000 - 9 p:8136
0000000000000000000000000100000010000001000000100000010000000000 - 10 p:8376
0000000000000000000000000010000001000000100000010000001000000000 - 11 p:8448
0000000000000000000000000001000000100000010000001000000100000000 - 12 p:8484
0000000000000000000000000000100000010000001000000100000010000000 - 13 p:8490
0000000000000000000000000000010000001000000100000010000001000000 - 14 p:8490
0000000000000000000000000000001000000100000010000001000000100000 - 15 p:8490
0000000000000001000000000000001000000100000010000001000000000000 - 16 p:6435
0000000000000000100000000000000100000010000001000000100000000000 - 17 p:7046
0000000000000000010000000000000010000001000000100000010000000000 - 18 p:7394
0000000000000000001000000000000001000000100000010000001000000000 - 19 p:7478
0000000000000000000100000000000000100000010000001000000100000000 - 20 p:7490
0000000000000000000010000000000000010000001000000100000010000000 - 21 p:7490
0000000000000000000001000000000000001000000100000010000001000000 - 22 p:7490
0000000000000000000000100000000000000100000010000001000000100000 - 23 p:7490
0000000000000001000000100000000000000100000010000001000000000000 - 24 p:6045
0000000000000000100000010000000000000010000001000000100000000000 - 25 p:6589
0000000000000000010000001000000000000001000000100000010000000000 - 26 p:6950
0000000000000000001000000100000000000000100000010000001000000000 - 27 p:7028
0000000000000000000100000010000000000000010000001000000100000000 - 28 p:7040
0000000000000000000010000001000000000000001000000100000010000000 - 29 p:7040
0000000000000000000001000000100000000000000100000010000001000000 - 30 p:7040
0000000000000000000000100000010000000000000010000001000000100000 - 31 p:7040
0000000000000000100000001000001000000000000001000000100000000000 - 32 p:6204
0000000000000000010000000100000100000000000000100000010000000000 - 33 p:6724
0000000000000000001000000010000010000000000000010000001000000000 - 34 p:7076
0000000000000000000100000001000001000000000000001000000100000000 - 35 p:7172
0000000000000000000010000000100000100000000000000100000010000000 - 36 p:7184
0000000000000000000001000000010000010000000000000010000001000000 - 37 p:7184
0000000000000000000000100000001000001000000000000001000000100000 - 38 p:7184
0000000000000000000000010000000100000100000000000000100000010000 - 39 p:7184
0000000000000000010000000100000110000000000000000000010000000000 - 40 p:6852
0000000000000000001000000010000011000000000000000000001000000000 - 41 p:7389
0000000000000000000100000001000001100000000000000000000100000000 - 42 p:7754
0000000000000000000010000000100000110000000000000000000010000000 - 43 p:7896
0000000000000000000001000000010000011000000000000000000001000000 - 44 p:7932
0000000000000000000000100000001000001100000000000000000000100000 - 45 p:7932
0000000000000000000000010000000100000110000000000000000000010000 - 46 p:7932
0000000000000000000000001000000010000011000000000000000000001000 - 47 p:7932
0000000000000000001000000010000101000000100000000000000000000000 - 48 p:8233
0000000000000000000100000001000010100000010000000000000000000000 - 49 p:8834
0000000000000000000010000000100001010000001000000000000000000000 - 50 p:9236
0000000000000000000001000000010000101000000100000000000000000000 - 51 p:9422
0000000000000000000000100000001000010100000010000000000000000000 - 52 p:9512
0000000000000000000000010000000100001010000001000000000000000000 - 53 p:9548
0000000000000000000000001000000010000101000000100000000000000000 - 54 p:9548
0000000000000000000000000100000001000010100000010000000000000000 - 55 p:9548
0000000000000000000100000001000100100000010000001000000000000000 - 56 p:31014
0000000000000000000010000000100010010000001000000100000000000000 - 57 p:33520

Better ascii code 1 = █

Code: Select all

[code]000000000000000█000000█000000█000000█000000█000000█0000000000000 - 0 p:24550
0000000000000000█000000█000000█000000█000000█000000█000000000000 - █ p:27242
00000000000000000█000000█000000█000000█000000█000000█00000000000 - 2 p:29026
000000000000000000█000000█000000█000000█000000█000000█0000000000 - 3 p:29958
0000000000000000000█000000█000000█000000█000000█000000█000000000 - 4 p:30348
00000000000000000000█000000█000000█000000█000000█000000█00000000 - 5 p:30456
000000000000000000000█000000█000000█000000█000000█000000█0000000 - 6 p:30492
0000000000000000000000█000000█000000█000000█000000█000000█000000 - 7 p:30492
00000000000000000000000█000000█000000█000000█000000█000000000000 - 8 p:8█36
000000000000000000000000█000000█000000█000000█000000█00000000000 - 9 p:8█36
0000000000000000000000000█000000█000000█000000█000000█0000000000 - █0 p:8376
00000000000000000000000000█000000█000000█000000█000000█000000000 - ██ p:8448
000000000000000000000000000█000000█000000█000000█000000█00000000 - █2 p:8484
0000000000000000000000000000█000000█000000█000000█000000█0000000 - █3 p:8490
00000000000000000000000000000█000000█000000█000000█000000█000000 - █4 p:8490
000000000000000000000000000000█000000█000000█000000█000000█00000 - █5 p:8490
000000000000000█00000000000000█000000█000000█000000█000000000000 - █6 p:6435
0000000000000000█00000000000000█000000█000000█000000█00000000000 - █7 p:7046
00000000000000000█00000000000000█000000█000000█000000█0000000000 - █8 p:7394
000000000000000000█00000000000000█000000█000000█000000█000000000 - █9 p:7478
0000000000000000000█00000000000000█000000█000000█000000█00000000 - 20 p:7490
00000000000000000000█00000000000000█000000█000000█000000█0000000 - 2█ p:7490
000000000000000000000█00000000000000█000000█000000█000000█000000 - 22 p:7490
0000000000000000000000█00000000000000█000000█000000█000000█00000 - 23 p:7490
000000000000000█000000█00000000000000█000000█000000█000000000000 - 24 p:6045
0000000000000000█000000█00000000000000█000000█000000█00000000000 - 25 p:6589
00000000000000000█000000█00000000000000█000000█000000█0000000000 - 26 p:6950
000000000000000000█000000█00000000000000█000000█000000█000000000 - 27 p:7028
0000000000000000000█000000█00000000000000█000000█000000█00000000 - 28 p:7040
00000000000000000000█000000█00000000000000█000000█000000█0000000 - 29 p:7040
000000000000000000000█000000█00000000000000█000000█000000█000000 - 30 p:7040
0000000000000000000000█000000█00000000000000█000000█000000█00000 - 3█ p:7040
0000000000000000█0000000█00000█00000000000000█000000█00000000000 - 32 p:6204
00000000000000000█0000000█00000█00000000000000█000000█0000000000 - 33 p:6724
000000000000000000█0000000█00000█00000000000000█000000█000000000 - 34 p:7076
0000000000000000000█0000000█00000█00000000000000█000000█00000000 - 35 p:7█72
00000000000000000000█0000000█00000█00000000000000█000000█0000000 - 36 p:7█84
000000000000000000000█0000000█00000█00000000000000█000000█000000 - 37 p:7█84
0000000000000000000000█0000000█00000█00000000000000█000000█00000 - 38 p:7█84
00000000000000000000000█0000000█00000█00000000000000█000000█0000 - 39 p:7█84
00000000000000000█0000000█00000██00000000000000000000█0000000000 - 40 p:6852
000000000000000000█0000000█00000██00000000000000000000█000000000 - 4█ p:7389
0000000000000000000█0000000█00000██00000000000000000000█00000000 - 42 p:7754
00000000000000000000█0000000█00000██00000000000000000000█0000000 - 43 p:7896
000000000000000000000█0000000█00000██00000000000000000000█000000 - 44 p:7932
0000000000000000000000█0000000█00000██00000000000000000000█00000 - 45 p:7932
00000000000000000000000█0000000█00000██00000000000000000000█0000 - 46 p:7932
000000000000000000000000█0000000█00000██00000000000000000000█000 - 47 p:7932
000000000000000000█0000000█0000█0█000000█00000000000000000000000 - 48 p:8233
0000000000000000000█0000000█0000█0█000000█0000000000000000000000 - 49 p:8834
00000000000000000000█0000000█0000█0█000000█000000000000000000000 - 50 p:9236
000000000000000000000█0000000█0000█0█000000█00000000000000000000 - 5█ p:9422
0000000000000000000000█0000000█0000█0█000000█0000000000000000000 - 52 p:95█2
00000000000000000000000█0000000█0000█0█000000█000000000000000000 - 53 p:9548
000000000000000000000000█0000000█0000█0█000000█00000000000000000 - 54 p:9548
0000000000000000000000000█0000000█0000█0█000000█0000000000000000 - 55 p:9548
0000000000000000000█0000000█000█00█000000█000000█000000000000000 - 56 p:3█0█4
00000000000000000000█0000000█000█00█000000█000000█00000000000000 - 57 p:33520

I also had a viewer where we can apply one magic to the table and visually see in a bitmap how more and more of the table slot become black and this lead me to conclude that magic can only be improved via above idea and not by density improvements.
So if someone were to find a small code that can produce above list of numbers fancy magic can be improved.

There is also many many patterns that can be found depending on the scoring function:
Above comes from this:

Code: Select all

static int scoreOf(uint64_t sol, uint64_t last_sol)
{
    int match = std::popcount(~(sol ^ last_sol));
    int match_left = std::popcount(~(sol ^ (last_sol << 1)));
    int match_right = 2 * std::popcount(~(sol ^ (last_sol >> 1)));
    return match + match_left + match_right;
}

So we score right shifting solutions. We can find fancy magic results like this also by scoring vertical matches:

Code: Select all

static int scoreOf(uint64_t sol, uint64_t last_sol)
{
    int match = 2*std::popcount(~(sol ^ last_sol));
    int match_left = std::popcount(~(sol ^ (last_sol << 1)));
    int match_right = std::popcount(~(sol ^ (last_sol >> 1)));
    return match + match_left + match_right;
}

Code: Select all

BEST OVERALL:
0000000000000█00000000█0█00000000██00000000000000█00000000000000 -  p:██2865029654██84ull
0000000000000█00000000█000000000███00000000000000█00000000000000 -  p:██28█026882█0944ull
0000000000000█00000000█0000000000███00000000000000█0000000000000 -  p:██28█00809█54560ull
0000000000000█00000000█00000000000███00000000000000█000000000000 -  p:██28099869626368ull
0000000000000█00000000█000000000000██000000000000000█0000█000000 -  p:██28099332753472ull
0000000000000█00000000█000000000000█000000█000000000█0000█000000 -  p:██28099200632896ull
000000000000000000000██000000000000█000000█000000000█0000█000000 -  p:659734030█376ull
0000000000000000000000██00000000000█000000█000000000█0000█000000 -  p:32988054█8048ull
00000000000000000000000██0000000000█000000█000000000█00000000000 -  p:█649537976320ull
000000000000000000000000██000000000█000000█000000000█00000000000 -  p:824904255488ull
0000000000000000000000000█000000█00█000000█000000000█00000000000 -  p:277295925248ull
0000000000000000000000000█000000█000000000██00000000█00000000000 -  p:277028538368ull
0000000000000000000000000█000000█0000000000██0000000█00000000000 -  p:277026965504ull
0000000000000000000000000█000000█0000000000█00000000██0000000000 -  p:277026442240ull
0000000000000000000000000█000000█0000000000█000000000██000000000 -  p:277026440704ull
0000000000000000000000000█000000█0000000000█0000000000██00000000 -  p:277026439936ull
000000000000000█000000000█000000█0000000000█0000000000█000000000 -  p:28█752003█50336ull
000000000000000█0000000000000000██000000000█0000000000█000000000 -  p:28█478█989852█6ull
000000000000000█00000000000000000██00000000█0000000000█000000000 -  p:28█476588372480ull
000000000000000█000000000000000000██0000000█0000000000█000000000 -  p:28█475783066██2ull
000000000000000█000000000000000000█00000000██000000000█000000000 -  p:28█4755█5█54944ull
000000000000000█000000000000000000█000000000██00000000█000000000 -  p:28█4755█43685█2ull
000000000000000█000000000000000000█0000000000██0000000█000000000 -  p:28█4755█3975296ull
0000000000000000█00000000000000000█0000000000█00000000██00000000 -  p:█40738025489█52ull
000000000000000██00000000000000000█0000000000█00000000█000000000 -  p:4222█3002█99552ull
0000000000000000██0000000000000000█0000000000█00000000█000000000 -  p:2███06769666560ull
00000000000000000█000000█000000000█0000000000█00000000█000000000 -  p:709█9037█25█20ull
00000000000000000█000000█0000000000█000000000█00000000█000000000 -  p:709█8768689664ull
00000000000000000█000000█00000000000█00000000█00000000█000000000 -  p:709█863447█936ull
00000000000000000█000000█0000000000000000000██00000000█000000000 -  p:709█8500778496ull
00000000000000000█000000█00000000000000000000██0000000█000000000 -  p:709█8500385280ull
00000000000000000█000000█00000000000000000000█00000000██00000000 -  p:709█8500254464ull
0000000000000000██000000█00000000000000000000█00000000█000000000 -  p:2██655988609536ull
00000000000000000█000000██0000000000000000000█00000000█000000000 -  p:7██93378█6██52ull
00000000000000000█000000█0█000000000000000000█00000000█000000000 -  p:7█055939207680ull
00000000000000000█00000000██00000000000000000█00000000█000000000 -  p:70574902870528ull
00000000000000000█000000000██0000000000000000█00000000█000000000 -  p:7047█823655424ull
00000000000000000█0000000000█000000█000000000█00000000█000000000 -  p:704033726█4█44ull
00000000000000000█0000000000█000000█00000000000000000██000000000 -  p:70403372353024ull
00000000000000000█0000000000█000000█000000000000000000██00000000 -  p:70403372352256ull
000000000000000█0█0000000000█000000█000000000000000000█000000000 -  p:35█878349062656ull
0000000000000000██0000000000█000000█000000000000000000█000000000 -  p:2███40860707328ull
00000000000000000██000000000█000000█000000000000000000█000000000 -  p:█05587744440832ull
00000000000000000█000000000██000000█000000000000000000█000000000 -  p:7047209█828736ull
00000000000000000█0000000000█000000██00000000000000000█000000000 -  p:70403506569728ull
00000000000000000█0000000000█000000█0█0000000000000000█000000000 -  p:70403439460864ull
00000000000000000█0000000000█00000000█00000█0000000000█000000000 -  p:70403█72073984ull
00000000000000000█0000000000█00000000█00000█00000000000█00000000 -  p:70403█72073728ull
000000000000000█0█0000000000█00000000█00000█00000000000000000000 -  p:35█878█48784█28ull
0000000000000000██0000000000█00000000█00000█00000000000000000000 -  p:2███40660428800ull
00000000000000000██000000000█00000000█00000█00000000000000000000 -  p:█05587544█62304ull
00000000000000000█0000000000█0000000██00000█00000000000000000000 -  p:7040330629█200ull
00000000000000000█0000000000█0000000██000000000000█0000000000000 -  p:704033052508█6ull
00000000000000000█00000000000█000000██000000000000█0000000000000 -  p:70386█2538█632ull
00000000000000000█00000000000█000000█0█00000000000█0000000000000 -  p:7038609█827200ull
00000000000000000█00000000000█00000000██0000000000█0000000000000 -  p:70385974386688ull
00000000000000000█00000000000█000000000██00000000██0000000000000 -  p:70385949237248ull
00000000000000000█00000000000█000000000█000000█00██0000000000000 -  p:703859409797█2ull
000000000000000000█0000000000█000000000█000000000███000000000000 -  p:3520█568763904ull
0000000000000000000█000000000█000000000█0000000000███00000000000 -  p:█7609382705█52ull
0000000000000000000000█000000█00000000██00000000000██00000000000 -  p:22█6253462528ull
0000000000000000000000█000000█00000000██00000000000█000000█00000 -  p:22█62534605█2ull
0000000000000000000000█00000000000000███00000000000█000000█00000 -  p:2█99█40700█92ull
00000000000000000000000█00000000000000███0000000000█000000█00000 -  p:█099570352█60ull

Above is definitely not random either.
This elluded me for a year of trying - so if you want to pick up research onto improving fancy magic by finding a magic that correlates to all other squares too via very simple f(sq) function everyone can try.

Find 64 magic solutions for each square. Sort them by trying all 64 solutions and the next best one according to score. Pick the superset of the highest score and arrive at above images.
Best I could find out is that right shifts are much better.

That ellusive "magic = constant >> square" might exist or we can reduce 64 magics to 16 and have intermediate shifts.
cc Mike Sherwin

Greeting!