Magic Numbers ?

[Henk]

I copied Pradyumna Kanna's rook & bishop magic numbers along with his shift tables and masks. The problem I'm having is ..

Copied??? Be authentic and reinvent the wheel.

[Chessnut1071]

I copied Pradyumna Kanna's rook & bishop magic numbers along with his shift tables and masks. The problem I'm having is ..

Copied??? Be authentic and reinvent the wheel.

it turned out his shift tables were wrong for the bishop.

[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.

Woops. correction: magic bitboards averaging 2,638,533 pseudo moves per second versus 454,545 from standard bitboards. I had some debug statements still active that need to commented out. That's about what I expected. The question I have now is about faster solutions than magic bitboards. Are they really that much faster to make a significant difference. I had a heck of a time getting magic bitboards to work. Some of the alternatives listed here are making my head ache. -- computer chip I7, 2.6 Ghz, 1 core.

[dangi12012]

I copied Pradyumna Kanna's rook & bishop magic numbers along with his shift tables and masks. The problem I'm having is ..

Copied??? Be authentic and reinvent the wheel.

Henk - he had a specific predicate to fullfill:
"The problem I'm having is they are not unique and multiple move boards point to the same index code"

Magic hashing does not need to point only to a solution uint64_t bitmap - but when you have no overlaps you can point to any other structure you want.
But then you would like to be able to generate non overlapping magics. So you could point to a preprepared movelist - and just point there with the list of 16bit 'moves' already sorted and inplace.

The question I have now is about faster solutions than magic bitboards. Are they really that much faster to make a significant difference. I had a heck of a time getting magic bitboards to work. Some of the alternatives listed here are making my head ache. -- computer chip I7, 2.6 Ghz, 1 core.

Yes it makes a huge ~(35%) difference: Just copy and paste and good PEXT solution like this one:
https://github.com/Gigantua/Chess_Moveg ... n/Pext.hpp

This also gives you direct Xray lookup which most algos didnt bother with generating - but are very useful for detecting which pieces are pinned.

[syzygy]

On any modern ARM or Intel processor pext is fastest.

Pext absolutely kills performance on AMD Zen 2 and earlier. Zen 2 is still modern.

And pext on ARM? What are you talking about?

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

That would be terrible for performance. For good performance, the magic/pext code will have to be inlined.

If you don't want to settle for magic because of some lost performance on some architectures, then you need separate binaries for different CPUs or somehow try to build "fat" binaries which combine multiple separate compiles (just like MacOS X can have binaries combining x86 and ARM builds). The latter is not impossible but I don't think there is any compiler support for it.

[dangi12012]

If you don't want to settle for magic because of some lost performance on some architectures, then you need separate binaries for different CPUs or somehow try to build "fat" binaries which combine multiple separate compiles (just like MacOS X can have binaries combining x86 and ARM builds). The latter is not impossible but I don't think there is any compiler support for it.

Its simple:
Benchmark on the architectures you intend to target.

Valid point:
My idea around virtuals is horrible.

The point I am making:
Having the default assumption that magic is *always* one of the fastest and picking it by default is not valid.

Recommendation:
Modern x64 (Zen3+, SandyBride+) -> PEXT
Old x64 -> Fancy Magic
Other architectures: You need to benchmark. Easiest bechmark - https://github.com/Gigantua/Chess_Movegen
Maybe I will do an EMScripten Website - so you only need to surf to a page and instantly know how the performance distribution.

[Chessnut1071]

I copied Pradyumna Kanna's rook & bishop magic numbers along with his shift tables and masks. The problem I'm having is ..

Copied??? Be authentic and reinvent the wheel.

Henk - he had a specific predicate to fullfill:
"The problem I'm having is they are not unique and multiple move boards point to the same index code"

Magic hashing does not need to point only to a solution uint64_t bitmap - but when you have no overlaps you can point to any other structure you want.
But then you would like to be able to generate non overlapping magics. So you could point to a preprepared movelist - and just point there with the list of 16bit 'moves' already sorted and inplace.

The question I have now is about faster solutions than magic bitboards. Are they really that much faster to make a significant difference. I had a heck of a time getting magic bitboards to work. Some of the alternatives listed here are making my head ache. -- computer chip I7, 2.6 Ghz, 1 core.

Yes it makes a huge ~(35%) difference: Just copy and paste and good PEXT solution like this one:
https://github.com/Gigantua/Chess_Moveg ... n/Pext.hpp

This also gives you direct Xray lookup which most algos didnt bother with generating - but are very useful for detecting which pieces are pinned.

"Yes it makes a huge ~(35%) difference: Just copy and paste and good PEXT solution like this one:"

I'm using C# windows OS target 7.0 and can not seem to get "PDEP" - C# version of PEXT - to work. Anybody using C# 7.0 have it working?

[dangi12012]

I'm using C# windows OS target 7.0 and can not seem to get "PDEP" - C# version of PEXT - to work. Anybody using C# 7.0 have it working?

It definitely is not PDEP - but this function here:

https://docs.microsoft.com/en-us/dotnet ... ew=net-6.0
Namespace: System.Runtime.Intrinsics
Available in: .NET Core 3.0, Core 3.1, 5, 6, 7

Code: Select all

Bmi2.X64.ParallelBitExtract(UInt64, UInt64)

When you get it running - it also might interest

You know... Thinking of it. I originally started programming with C# and switched to C++ out of necessity (more performance and better pay) but I quite like the language. So I might even translate my "comparison of all known lookups" to C#.
Could be a fun weekend project.

[Chessnut1071]

I'm using C# windows OS target 7.0 and can not seem to get "PDEP" - C# version of PEXT - to work. Anybody using C# 7.0 have it working?

It definitely is not PDEP - but this function here:

https://docs.microsoft.com/en-us/dotnet ... ew=net-6.0
Namespace: System.Runtime.Intrinsics
Available in: .NET Core 3.0, Core 3.1, 5, 6, 7

Code: Select all

Bmi2.X64.ParallelBitExtract(UInt64, UInt64)

When you get it running - it also might interest

You know... Thinking of it. I originally started programming with C# and switched to C++ out of necessity (more performance and better pay) but I quite like the language. So I might even translate my "comparison of all known lookups" to C#.
Could be a fun weekend project.

thanks, it's working. I'm thinking about trying C++, but, it was a huge leap for me coming from visual basic. When I first joined, my pseudo move generator crept along at a robust 12,230 moves per second in release mode. Now, it's clocking 6,238,303 pseudo moves/sec in release mode. Hopefully, the PEXT will take me to a new level. I dread to think what comes next.

[Chessnut1071]

I'm using C# windows OS target 7.0 and can not seem to get "PDEP" - C# version of PEXT - to work. Anybody using C# 7.0 have it working?

It definitely is not PDEP - but this function here:

https://docs.microsoft.com/en-us/dotnet ... ew=net-6.0
Namespace: System.Runtime.Intrinsics
Available in: .NET Core 3.0, Core 3.1, 5, 6, 7

Code: Select all

Bmi2.X64.ParallelBitExtract(UInt64, UInt64)

When you get it running - it also might interest

You know... Thinking of it. I originally started programming with C# and switched to C++ out of necessity (more performance and better pay) but I quite like the language. So I might even translate my "comparison of all known lookups" to C#.
Could be a fun weekend project.

thanks, it's working. I'm thinking about trying C++, but, it was a huge leap for me coming from visual basic. When I first joined, my pseudo move generator crept along at a robust 12,230 moves per second in release mode. Now, it's clocking 6,238,303 pseudo moves/sec in release mode. Hopefully, the PEXT will take me to a new level. I dread to think what comes next.