Faster than Fancy magic: Hypercube Slider lookup [TEASER]

[dangi12012]

Update: constexpr didnt make kogge stone faster.
Its so slow because of the dependency chain. Modern processors like it when you can reorder the instructions without changing the results. Simple as that. A normal loop is as bad as this kogge stone algo.

Thats why we have the more advanced algorithms that can calculate this without a hard dependency chain and without any branches!

ok the implementation is fine, thanks for trying!
i thought kogge stone was slow because it was long, i still have a lot to learn about low level programming

btw my point was that queen_attacks is rarely used in a chess engine that uses kogge stone because it's expensive, try to run it again with only rook or bishops attacks

Do you know a repo where fancy hash is implemented? I think the code I used is just plain magic.

[Mergi]

Update: constexpr didnt make kogge stone faster.
Its so slow because of the dependency chain. Modern processors like it when you can reorder the instructions without changing the results. Simple as that. A normal loop is as bad as this kogge stone algo.

Thats why we have the more advanced algorithms that can calculate this without a hard dependency chain and without any branches!

ok the implementation is fine, thanks for trying!
i thought kogge stone was slow because it was long, i still have a lot to learn about low level programming

btw my point was that queen_attacks is rarely used in a chess engine that uses kogge stone because it's expensive, try to run it again with only rook or bishops attacks

Do you know a repo where fancy hash is implemented? I think the code I used is just plain magic.

This is fancy magic using the best magic numbers found so far (taken from the wiki). It's a bit unwieldy because i just ripped it out of my engine and tried to squash it into one file, but hopefully it will work for you

[tcusr]

Update: constexpr didnt make kogge stone faster.
Its so slow because of the dependency chain. Modern processors like it when you can reorder the instructions without changing the results. Simple as that. A normal loop is as bad as this kogge stone algo.

Thats why we have the more advanced algorithms that can calculate this without a hard dependency chain and without any branches!

ok the implementation is fine, thanks for trying!
i thought kogge stone was slow because it was long, i still have a lot to learn about low level programming

btw my point was that queen_attacks is rarely used in a chess engine that uses kogge stone because it's expensive, try to run it again with only rook or bishops attacks

Do you know a repo where fancy hash is implemented? I think the code I used is just plain magic.

This is fancy magic using the best magic numbers found so far (taken from the wiki). It's a bit unwieldy because i just ripped it out of my engine and tried to squash it into one file, but hopefully it will work for you

why do you fill the tables at compile time?
i don't see any advantage

[dangi12012]

why do you fill the tables at compile time?
i don't see any advantage

Thanks I will implement Mergi!
tcusr its best to have it at compiletime. When a compiler can infer what the value is it will instantly inline the value. So attacks[23] is a constant. Now if you have a case where you test certain squares like [62] it will make the code faster.

So in summary you lose nothing in most cases - but there are cases where you can win A LOT of performance.

[dangi12012]

This is fancy magic using the best magic numbers found so far (taken from the wiki). It's a bit unwieldy because i just ripped it out of my engine and tried to squash it into one file, but hopefully it will work for you

Does not compile: Neither in clang nor in msvc.
error: call to consteval function 'Chess_Lookup::Fancy::InitTable<88064, const std::array<unsigned char, 64>, const std::array<unsigned long, 64>, unsigned long (Chess_Lookup::Fancy::Square, unsigned long)>' is not a constant expression
constexpr auto r_table = InitTable<88064>(r_magic_shift, r_magic_num, GenRookMoves);

Also too much use of auto keyword

Upate: When removing constexpr and inling manually it throws too. I need working code!

So 88064 is the current record for variable shift fancy magic?

[Mergi]

This is fancy magic using the best magic numbers found so far (taken from the wiki). It's a bit unwieldy because i just ripped it out of my engine and tried to squash it into one file, but hopefully it will work for you

Does not compile: Neither in clang nor in msvc.
error: call to consteval function 'Chess_Lookup::Fancy::InitTable<88064, const std::array<unsigned char, 64>, const std::array<unsigned long, 64>, unsigned long (Chess_Lookup::Fancy::Square, unsigned long)>' is not a constant expression
constexpr auto r_table = InitTable<88064>(r_magic_shift, r_magic_num, GenRookMoves);

Also too much use of auto keyword

Upate: When removing constexpr and inling manually it throws too. I need working code!

So 88064 is the current record for variable shift fancy magic?

Hmm, i'm not sure clang has enough consteval/constexpr/auto support yet. It does compile with GCC 11 though. I'll post a non compile time code in a moment, that should work with clang as well.

[Mergi]

No fancy autos or constexpr anymore! Just call Init() and then GetRookAttacks / GetBishopAttacks

[Mergi]

So 88064 is the current record for variable shift fancy magic?

No idea, i'm using the publicly available magic numbers from https://www.chessprogramming.org/Best_Magics_so_far

Unless there were some new added in the past few months or i missed some when i was originally making the generator, 88064 for rooks and 4800 for bishops should be the smallest for fancy magics.

[dangi12012]

No fancy autos or constexpr anymore! Just call Init() and then GetRookAttacks / GetBishopAttacks

Strange this seems to be 30% slower than this implementation:


Will try different compilers...

[dangi12012]

So 88064 is the current record for variable shift fancy magic?

No idea, i'm using the publicly available magic numbers from https://www.chessprogramming.org/Best_Magics_so_far

Unless there were some new added in the past few months or i missed some when i was originally making the generator, 88064 for rooks and 4800 for bishops should be the smallest for fancy magics.

Ah the performance is slow because:

Code: Select all

((occ & m.inner_mask) * m.magic_num) >> m.shift

That is plain magic with variable shift

Can anyone here on this forum point me to the sourcecode of a fancy magic with fixed shift implementation?
It would look like that:

Code: Select all

((occ | m.inner_mask) * m.magic_num) >> (64-12)