Magic Numbers ?

[Chessnut1071]

I'm almost finished converting my bitboard program to magic bitboards; however, I have an issue. I copied Pradyumna Kanna's rook & bishop magic numbers along with his shift tables and masks. The problem I'm having is they are not unique and multiple move boards point to the same index code. Is anybody else using these magic number, besides Shallow Blue, and having similar issues? It appears the rook and bishop mask are without issue. Also, is there a good alternative source for the magic numbers without issues?

[Chessnut1071]

data listed below for rook:

UInt64[] rookMagics = new UInt64[64]
{
0x0080001020400080, 0x0040001000200040, 0x0080081000200080, 0x0080040800100080,
0x0080020400080080, 0x0080010200040080, 0x0080008001000200, 0x0080002040800100,
0x0000800020400080, 0x0000400020005000, 0x0000801000200080, 0x0000800800100080,
0x0000800400080080, 0x0000800200040080, 0x0000800100020080, 0x0000800040800100,
0x0000208000400080, 0x0000404000201000, 0x0000808010002000, 0x0000808008001000,
0x0000808004000800, 0x0000808002000400, 0x0000010100020004, 0x0000020000408104,
0x0000208080004000, 0x0000200040005000, 0x0000100080200080, 0x0000080080100080,
0x0000040080080080, 0x0000020080040080, 0x0000010080800200, 0x0000800080004100,
0x0000204000800080, 0x0000200040401000, 0x0000100080802000, 0x0000080080801000,
0x0000040080800800, 0x0000020080800400, 0x0000020001010004, 0x0000800040800100,
0x0000204000808000, 0x0000200040008080, 0x0000100020008080, 0x0000080010008080,
0x0000040008008080, 0x0000020004008080, 0x0000010002008080, 0x0000004081020004,
0x0000204000800080, 0x0000200040008080, 0x0000100020008080, 0x0000080010008080,
0x0000040008008080, 0x0000020004008080, 0x0000800100020080, 0x0000800041000080,
0x00FFFCDDFCED714A, 0x007FFCDDFCED714A, 0x003FFFCDFFD88096, 0x0000040810002101,
0x0001000204080011, 0x0001000204000801, 0x0001000082000401, 0x0001FFFAABFAD1A2
};

UInt64[] rookMask = new UInt64[64]
{
0x000101010101017E, 0x000202020202027C, 0x000404040404047A, 0x0008080808080876,
0x001010101010106E, 0x002020202020205E, 0x004040404040403E, 0x008080808080807E,
0x0001010101017E00, 0x0002020202027C00, 0x0004040404047A00, 0x0008080808087600,
0x0010101010106E00, 0x0020202020205E00, 0x0040404040403E00, 0x0080808080807E00,
0x00010101017E0100, 0x00020202027C0200, 0x00040404047A0400, 0x0008080808760800,
0x00101010106E1000, 0x00202020205E2000, 0x00404040403E4000, 0x00808080807E8000,
0x000101017E010100, 0x000202027C020200, 0x000404047A040400, 0x0008080876080800,
0x001010106E101000, 0x002020205E202000, 0x004040403E404000, 0x008080807E808000,
0x0001017E01010100, 0x0002027C02020200, 0x0004047A04040400, 0x0008087608080800,
0x0010106E10101000, 0x0020205E20202000, 0x0040403E40404000, 0x0080807E80808000,
0x00017E0101010100, 0x00027C0202020200, 0x00047A0404040400, 0x0008760808080800,
0x00106E1010101000, 0x00205E2020202000, 0x00403E4040404000, 0x00807E8080808000,
0x007E010101010100, 0x007C020202020200, 0x007A040404040400, 0x0076080808080800,
0x006E101010101000, 0x005E202020202000, 0x003E404040404000, 0x007E808080808000,
0x7E01010101010100, 0x7C02020202020200, 0x7A04040404040400, 0x7608080808080800,
0x6E10101010101000, 0x5E20202020202000, 0x3E40404040404000, 0x7E80808080808000
};

[xr_a_y]

Just pick one implementation somewehre ?

- https://github.com/Matthies/RubiChess/b ... d.cpp#L709
- https://github.com/milostatarevic/xipho ... agic.h#L24
- https://github.com/tryingsomestuff/Mini ... k.cpp#L169
- https://github.com/AndyGrant/Ethereal/b ... acks.h#L55
- https://github.com/Luecx/Koivisto/blob/ ... acks.h#L26
- https://github.com/connormcmonigle/seer ... tion.h#L36

but look at the code using the table, not only the table itself.

[dangi12012]

https://raw.githubusercontent.com/Gigan ... _Fancy.hpp
https://raw.githubusercontent.com/Gigan ... _Plain.hpp
https://raw.githubusercontent.com/Gigan ... sh_Var.hpp

However why go for magic if a faster solution exists?
https://raw.githubusercontent.com/Gigan ... n/Pext.hpp

All files are without external dependencies.

[Tearth]

Isn't PEXT actually much slower on some AMD processors? ( It's not a big deal if you're not planning to run an engine on them, but good to know this little trap.

[abulmo2]

Isn't PEXT actually much slower on some AMD processors? ( It's not a big deal if you're not planning to run an engine on them, but good to know this little trap.

Yes, the PEXT CPU instruction is also absent on some older CPU or on ARM CPU (apple M1, rpi, etc.).

[Tearth]

This too, that's why I've completely resigned from using PEXT and I'm doing magic in a traditional way, slower but more solid.

[dangi12012]

This too, that's why I've completely resigned from using PEXT and I'm doing magic in a traditional way, slower but more solid.

It s so strange to target older architectures or pick slower algos - just beacuse.
Is fancy on ARM even under the top 10 algos? It heavily depends on if ram access is fast.
Picking fancy magic per default will almost never be the right choice.

On any modern ARM or Intel processor pext is fastest. On older x64 architectures - probably fancy magic.
32 bit cpus - unclear winner
alternatice arch including arm - unclear. probably even lookup free algos can be fastest.


For perfect performance one can do a quick bench at startup and set a virt function to the fastest impl.

[abulmo2]

For perfect performance one can do a quick bench at startup and set a virt function to the fastest impl.

Well, a virtual function is usually slower than a direct function. Having the right bench is also a hard task. For example, in Dumb, I tried magic numbers instead of hyperbola quintessence. Magic algo was faster in perft but slower in normal search, so a right bench would be to do a normal search on various positions covering opening, midgame and endgame, which is rather slow, and not a quick perft. And if you want to test a dozen algo this can take some time at startup.
Moreover the move generation of sliding pieces is just a tiny part of the performance of a chess engine, even on an engine as simple as Dumb. Having an algo just fast enough is usually fine.

[Chessnut1071]

For perfect performance one can do a quick bench at startup and set a virt function to the fastest impl.

Well, a virtual function is usually slower than a direct function. Having the right bench is also a hard task. For example, in Dumb, I tried magic numbers instead of hyperbola quintessence. Magic algo was faster in perft but slower in normal search, so a right bench would be to do a normal search on various positions covering opening, midgame and endgame, which is rather slow, and not a quick perft. And if you want to test a dozen algo this can take some time at startup.
Moreover the move generation of sliding pieces is just a tiny part of the performance of a chess engine, even on an engine as simple as Dumb. Having an algo just fast enough is usually fine.

Moreover the move generation of sliding pieces is just a tiny part of the performance of a chess engine, even on an engine as simple as Dumb. Having an algo just fast enough is usually fine.

I just finished my magic bitboard program from classic bitboards and the performance gain was disappointing. My classic bitboard program could compute 454,545 pseudo moves per second versus the magic bitboard speed of 515,729. I was under the impression that the speed pickup from precomputed magic bitboards would at least double the nodes/sec. Granted, magic bitboards are faster; however, you are right about sliding pieces being a small part of engine performance.