Comparison of all known Sliding lookup algorithms

[dangi12012]

This is a git repo for many known chess sliding piece lookup algorithms. All of them perform better than the naive 4x loop algorithm we all at least once wrote.
https://github.com/Gigantua/Chess_Movegen
I made sure to include every idea in the wiki at least once. So there is not 10x the same algorithm with the same idea - but we have a C++20 constepxr version of unique algorithms.

Huge thanks to Harald for sending me the sourcecode to his engine - Elephant_1_07. which also contained an assortment of lookup algorithms. Some algorithms were over 20 years old! Some are younger.
I took these and some in the discussions we had in these threads to create a C++20 assortment of known lookup algorithms.
forum3/viewtopic.php?f=7&t=77133#p890486
http://www.talkchess.com/forum3/viewtop ... 67#p914867
Some are really really nice pieces of code!

All of these lookups are constexpr so that the whole initialisation for all 13 algorithms happens at compiletime. Each algorithm lives in its own namespace and if you want to pick one for your engine just copy and include the .hpp file

All you need is namespace::Rook(sq, occ) to get the attacked squares.

It prints the table size - MLU/s for different tests and the dependency on special operations.
I will also add Multithreading tests in the future (L2 cache pressure)

Here is the result for a Ryzen 9 5950X:

Code: Select all

AMD Ryzen 9 5950X 16-Core Processor
Megalooks Simulated Game/s:
Exploading:     150.89MOps      6 kB    Optimal perf: imul64
Reference:      68.93MOps       8 kB    Optimal perf: none
KoggeStone:     111.98MOps      0 kB    Optimal perf: none
RotatedBoard:   92.37MOps       14 kB   Optimal perf: none
QBB Algo:       171.72MOps      0 kB    Optimal perf: countr_zero, countl_zero
BobMike:        211.32MOps      8 kB    Optimal perf: countr_zero, countl_zero
SlideArithm:    256.04MOps      2 kB    Optimal perf: bzhi_u64, blsmsk_u64
XorRookSub:     297.78MOps      2 kB    Optimal perf: bswap
Hash Variable:  399.36MOps      729 kB  Optimal perf: imul64
Hash Plain:     529.61MOps      2306 kB Optimal perf: imul64
Hash Fancy:     597.36MOps      694 kB  Optimal perf: imul64
Pext  :         925.24MOps      843 kB  Optimal perf: pext_u64
HyperCube:      310.30MOps      841 kB  Optimal perf: none

Please post your results (Especially old intel + Ryzen 1/2) and if you want to add an algo please pm me - or create a PR - or contact me under daniel.infuehr@live.de

Happy new year!

[dangi12012]

Oh and if someone known the approximate date when the more obscure ones were invented that would also be nice information!

[gaard]

This is a git repo for many known chess sliding piece lookup algorithms. All of them perform better than the naive 4x loop algorithm we all at least once wrote.
https://github.com/Gigantua/Chess_Movegen
I made sure to include every idea in the wiki at least once. So there is not 10x the same algorithm with the same idea - but we have a C++20 constepxr version of unique algorithms.

Huge thanks to Harald for sending me the sourcecode to his engine - Elephant_1_07. which also contained an assortment of lookup algorithms. Some algorithms were over 20 years old! Some are younger.
I took these and some in the discussions we had in these threads to create a C++20 assortment of known lookup algorithms.
forum3/viewtopic.php?f=7&t=77133#p890486
http://www.talkchess.com/forum3/viewtop ... 67#p914867
Some are really really nice pieces of code!

All of these lookups are constexpr so that the whole initialisation for all 13 algorithms happens at compiletime. Each algorithm lives in its own namespace and if you want to pick one for your engine just copy and include the .hpp file

All you need is namespace::Rook(sq, occ) to get the attacked squares.

It prints the table size - MLU/s for different tests and the dependency on special operations.
I will also add Multithreading tests in the future (L2 cache pressure)

Here is the result for a Ryzen 9 5950X:

Code: Select all

AMD Ryzen 9 5950X 16-Core Processor
Megalooks Simulated Game/s:
Exploading:     150.89MOps      6 kB    Optimal perf: imul64
Reference:      68.93MOps       8 kB    Optimal perf: none
KoggeStone:     111.98MOps      0 kB    Optimal perf: none
RotatedBoard:   92.37MOps       14 kB   Optimal perf: none
QBB Algo:       171.72MOps      0 kB    Optimal perf: countr_zero, countl_zero
BobMike:        211.32MOps      8 kB    Optimal perf: countr_zero, countl_zero
SlideArithm:    256.04MOps      2 kB    Optimal perf: bzhi_u64, blsmsk_u64
XorRookSub:     297.78MOps      2 kB    Optimal perf: bswap
Hash Variable:  399.36MOps      729 kB  Optimal perf: imul64
Hash Plain:     529.61MOps      2306 kB Optimal perf: imul64
Hash Fancy:     597.36MOps      694 kB  Optimal perf: imul64
Pext  :         925.24MOps      843 kB  Optimal perf: pext_u64
HyperCube:      310.30MOps      841 kB  Optimal perf: none

Please post your results (Especially old intel + Ryzen 1/2) and if you want to add an algo please pm me - or create a PR - or contact me under daniel.infuehr@live.de

Happy new year!

So PEXT is still the way to go for max throughput? If I wanted max throughput per lines of code, which would you recommend?

[tcusr]

SlideArithm or XorRookSub or QBB have the best speed/LOC ratio

[dangi12012]

I am interested in some results!

Especially some old intel and 1st gen amd ryzen. I think with an old 32 bit cpu this would be interesting to see. Even if immintrin.h is not available for compilation on /arch:IA32. Eveything should work on a 32 bit cpu. Maybe except SlideArithm algo.

[Mike Sherwin]

This is a git repo for many known chess sliding piece lookup algorithms. All of them perform better than the naive 4x loop algorithm we all at least once wrote.
https://github.com/Gigantua/Chess_Movegen
I made sure to include every idea in the wiki at least once. So there is not 10x the same algorithm with the same idea - but we have a C++20 constepxr version of unique algorithms.

Huge thanks to Harald for sending me the sourcecode to his engine - Elephant_1_07. which also contained an assortment of lookup algorithms. Some algorithms were over 20 years old! Some are younger.
I took these and some in the discussions we had in these threads to create a C++20 assortment of known lookup algorithms.
forum3/viewtopic.php?f=7&t=77133#p890486
http://www.talkchess.com/forum3/viewtop ... 67#p914867
Some are really really nice pieces of code!

All of these lookups are constexpr so that the whole initialisation for all 13 algorithms happens at compiletime. Each algorithm lives in its own namespace and if you want to pick one for your engine just copy and include the .hpp file

All you need is namespace::Rook(sq, occ) to get the attacked squares.

It prints the table size - MLU/s for different tests and the dependency on special operations.
I will also add Multithreading tests in the future (L2 cache pressure)

Here is the result for a Ryzen 9 5950X:

Code: Select all

AMD Ryzen 9 5950X 16-Core Processor
Megalooks Simulated Game/s:
Exploading:     150.89MOps      6 kB    Optimal perf: imul64
Reference:      68.93MOps       8 kB    Optimal perf: none
KoggeStone:     111.98MOps      0 kB    Optimal perf: none
RotatedBoard:   92.37MOps       14 kB   Optimal perf: none
QBB Algo:       171.72MOps      0 kB    Optimal perf: countr_zero, countl_zero
BobMike:        211.32MOps      8 kB    Optimal perf: countr_zero, countl_zero
SlideArithm:    256.04MOps      2 kB    Optimal perf: bzhi_u64, blsmsk_u64
XorRookSub:     297.78MOps      2 kB    Optimal perf: bswap
Hash Variable:  399.36MOps      729 kB  Optimal perf: imul64
Hash Plain:     529.61MOps      2306 kB Optimal perf: imul64
Hash Fancy:     597.36MOps      694 kB  Optimal perf: imul64
Pext  :         925.24MOps      843 kB  Optimal perf: pext_u64
HyperCube:      310.30MOps      841 kB  Optimal perf: none

Please post your results (Especially old intel + Ryzen 1/2) and if you want to add an algo please pm me - or create a PR - or contact me under daniel.infuehr@live.de

Happy new year!

I made sure to include every idea in the wiki at least once. So there is not 10x the same algorithm with the same idea - but we have a C++20 constepxr version of unique algorithms.

SISSY (Split Index Super Set Yielding) Bitboards are on the CPW.

Code: Select all

// Bishop
void InitializeBSS() {
  u08 sq, sqr, k, l;
  s08 x, dx, y, dy;
  u64 b, bb, i, j, ii, jj;

  for (sq = 0; sq < 64; sq++) {
    y = sq >> 3;
    x = sq & 7;
    for (i = 0; i < 128; i++) {
      for (k = 8, l = 0; k <= 48; k += 8, l++) {
        bb = 0;
        b = ((u64)i << k) & bob[sq];
        for (dx = +1, dy = +1; x + dx < +8 && y + dy < +8; dx++, dy++) {
          sqr = (((y + dy) << 3) + x + dx);
          bb |= one << sqr;
          if ((one << sqr) & b) break;
        }
        for (dx = -1, dy = +1; x + dx > -1 && y + dy < +8; dx--, dy++) {
          sqr = (((y + dy) << 3) + x + dx);
          bb |= one << sqr;
          if ((one << sqr) & b) break;
        }
        for (dx = +1, dy = -1; x + dx < +8 && y + dy > -1; dx++, dy--) {
          sqr = (((y + dy) << 3) + x + dx);
          bb |= one << sqr;
          if ((one << sqr) & b) break;
        }
        for (dx = -1, dy = -1; x + dx > -1 && y + dy > -1; dx--, dy--) {
          sqr = (((y + dy) << 3) + x + dx);
          bb |= one << sqr;
          if ((one << sqr) & b) break;
        }
        bss[sq][i][l] = bb;
      }
    }
  }

  for (sq = 0; sq <= 63; sq++) {
    for (ii = 0; ii <= 127; ii++) {
      for (jj = 0; jj <= 127; jj++) {
        i = ((ii << 8) & bob[sq]) >> 8;
        j = ((jj << 32) & bob[sq]) >> 32;
        bss[sq][i | j][0] = bss[sq][i][0] & bss[sq][j][3];
        i = ((ii << 16) & bob[sq]) >> 16;
        j = ((jj << 40) & bob[sq]) >> 40;
        bss[sq][i | j][1] = bss[sq][i][1] & bss[sq][j][4];
        i = ((ii << 24) & bob[sq]) >> 24;
        j = ((jj << 48) & bob[sq]) >> 48;
        bss[sq][i | j][2] = bss[sq][i][2] & bss[sq][j][5];
      }
    }
  }
}

    case WB:
    case BB:
      blocks.bb = aPieces & b7e[fs];
      blocks.bb = ((blocks.l32 >> 8) | blocks.h32);
      bb1 = bss[fs][blocks.r1][0]
        & bss[fs][blocks.r2][1]
        & bss[fs][blocks.r3][2]
        & notme;
      break;

// Rook & Queen
void InitializeQSS() {
  u08 sq, sqr, k, l;
  s08 x, y, dx, dy;
  s32 i;
  u64 b, bb;

  for (sq = 0; sq < 64; sq++) {
    y = sq >> 3;
    x = sq & 7;
    bob[sq] = 0;
    rob[sq] = 0;
    for (i = 0; i < 256; i++) {
      for (k = 0, l = 0; k <= 56; k += 8, l++) {
        bb = 0;
        b = (u64)i << k;
        for (dx = +1, dy = +1; x + dx < +8 && y + dy < +8; dx++, dy++) {
          sqr = (((y + dy) << 3) + x + dx);
          bb |= one << sqr;
          bob[sq] |= one << sqr;
          if ((one << sqr) & b) break;
        }
        for (dx = -1, dy = +1; x + dx > -1 && y + dy < +8; dx--, dy++) {
          sqr = (((y + dy) << 3) + x + dx);
          bb |= one << sqr;
          bob[sq] |= one << sqr;
          if ((one << sqr) & b) break;
        }
        for (dx = +1, dy = -1; x + dx < +8 && y + dy > -1; dx++, dy--) {
          sqr = (((y + dy) << 3) + x + dx);
          bb |= one << sqr;
          bob[sq] |= one << sqr;
          if ((one << sqr) & b) break;
        }
        for (dx = -1, dy = -1; x + dx > -1 && y + dy > -1; dx--, dy--) {
          sqr = (((y + dy) << 3) + x + dx);
          bb |= one << sqr;
          bob[sq] |= one << sqr;
          if ((one << sqr) & b) break;
        }
        for (dx = -1; x + dx > -1; dx--) {
          sqr = (y << 3) + x + dx;
          bb |= one << sqr;
          rob[sq] |= one << sqr;
          if ((one << sqr) & b) break;
        }
        for (dx = +1; x + dx < +8; dx++) {
          sqr = (y << 3) + x + dx;
          bb |= one << sqr;
          rob[sq] |= one << sqr;
          if ((one << sqr) & b) break;
        }
        for (dy = +1; y + dy < +8; dy++) {
          sqr = ((y + dy) << 3) + x;
          bb |= one << sqr;
          rob[sq] |= one << sqr;
          if ((one << sqr) & b) break;
        }
        for (dy = -1; y + dy > -1; dy--) {
          sqr = ((y + dy) << 3) + x;
          bb |= one << sqr;
          rob[sq] |= one << sqr;
          if ((one << sqr) & b) break;
        }
        qss[sq][i][l] = bb;
      }
    }
    b7e[sq] = bob[sq] & 0x007e7e7e7e7e7e00;
  }
}

void InitializeRNK() {
  u08 sq, sqr, i;
  s08 x, y, dx, dy;
  u64 bb, b;

  for (sq = 0; sq < 64; sq++) {
    y = sq >> 3;
    x = sq & 7;
    for (i = 0; i < 128; i++) {
      bb = 0;
      b = (u64)i << (sq & 56);
      for (dx = +1, dy = +1; x + dx < +8 && y + dy < +8; dx++, dy++) {
        sqr = (((y + dy) << 3) + x + dx);
        bb |= one << sqr;
        bob[sq] |= one << sqr;
        if ((one << sqr) & b) break;
      }
      for (dx = -1, dy = +1; x + dx > -1 && y + dy < +8; dx--, dy++) {
        sqr = (((y + dy) << 3) + x + dx);
        bb |= one << sqr;
        bob[sq] |= one << sqr;
        if ((one << sqr) & b) break;
      }
      for (dx = +1, dy = -1; x + dx < +8 && y + dy > -1; dx++, dy--) {
        sqr = (((y + dy) << 3) + x + dx);
        bb |= one << sqr;
        bob[sq] |= one << sqr;
        if ((one << sqr) & b) break;
      }
      for (dx = -1, dy = -1; x + dx > -1 && y + dy > -1; dx--, dy--) {
        sqr = (((y + dy) << 3) + x + dx);
        bb |= one << sqr;
        bob[sq] |= one << sqr;
        if ((one << sqr) & b) break;
      }
      for (dx = -1; x + dx > -1; dx--) {
        sqr = (y << 3) + x + dx;
        bb |= one << sqr;
        rob[sq] |= one << sqr;
        if ((one << sqr) & b) break;
      }
      for (dx = +1; x + dx < +8; dx++) {
        sqr = (y << 3) + x + dx;
        bb |= one << sqr;
        rob[sq] |= one << sqr;
        if ((one << sqr) & b) break;
      }
      for (dy = +1; y + dy < +8; dy++) {
        sqr = ((y + dy) << 3) + x;
        bb |= one << sqr;
        rob[sq] |= one << sqr;
        if ((one << sqr) & b) break;
      }
      for (dy = -1; y + dy > -1; dy--) {
        sqr = ((y + dy) << 3) + x;
        bb |= one << sqr;
        rob[sq] |= one << sqr;
        if ((one << sqr) & b) break;
      }
      qss[sq][i][0] = bb;
    }
  }
}

    case WR:
    case WRC:
    case BR:
    case BRC:
      blocks.bb = aPieces & rob[fs];
      bb1 = qss[fs][(blocks.bb >> (fs & 56)) & 127][0]
        & qss[fs][blocks.r2][1]
        & qss[fs][blocks.r3][2]
        & qss[fs][blocks.r4][3]
        & qss[fs][blocks.r5][4]
        & qss[fs][blocks.r6][5]
        & qss[fs][blocks.r7][6]
        & rob[fs]
        & notme;
      break;

    case WQ:
    case BQ:
      blocks.bb = aPieces & (rob[fs] | bob[fs]);
      bb1 = qss[fs][(blocks.bb >> (fs & 56)) & 127][0]
        & qss[fs][blocks.r2][1]
        & qss[fs][blocks.r3][2]
        & qss[fs][blocks.r4][3]
        & qss[fs][blocks.r5][4]
        & qss[fs][blocks.r6][5]
        & qss[fs][blocks.r7][6]
        & notme;
      break;

[Sven]

This is a git repo for many known chess sliding piece lookup algorithms. All of them perform better than the naive 4x loop algorithm we all at least once wrote.
https://github.com/Gigantua/Chess_Movegen
I made sure to include every idea in the wiki at least once. So there is not 10x the same algorithm with the same idea - but we have a C++20 constepxr version of unique algorithms.

Huge thanks to Harald for sending me the sourcecode to his engine - Elephant_1_07. which also contained an assortment of lookup algorithms. Some algorithms were over 20 years old! Some are younger.
I took these and some in the discussions we had in these threads to create a C++20 assortment of known lookup algorithms.
forum3/viewtopic.php?f=7&t=77133#p890486
http://www.talkchess.com/forum3/viewtop ... 67#p914867
Some are really really nice pieces of code!

All of these lookups are constexpr so that the whole initialisation for all 13 algorithms happens at compiletime. Each algorithm lives in its own namespace and if you want to pick one for your engine just copy and include the .hpp file

All you need is namespace::Rook(sq, occ) to get the attacked squares.

It prints the table size - MLU/s for different tests and the dependency on special operations.
I will also add Multithreading tests in the future (L2 cache pressure)

Here is the result for a Ryzen 9 5950X:

Code: Select all

AMD Ryzen 9 5950X 16-Core Processor
Megalooks Simulated Game/s:
Exploading:     150.89MOps      6 kB    Optimal perf: imul64
Reference:      68.93MOps       8 kB    Optimal perf: none
KoggeStone:     111.98MOps      0 kB    Optimal perf: none
RotatedBoard:   92.37MOps       14 kB   Optimal perf: none
QBB Algo:       171.72MOps      0 kB    Optimal perf: countr_zero, countl_zero
BobMike:        211.32MOps      8 kB    Optimal perf: countr_zero, countl_zero
SlideArithm:    256.04MOps      2 kB    Optimal perf: bzhi_u64, blsmsk_u64
XorRookSub:     297.78MOps      2 kB    Optimal perf: bswap
Hash Variable:  399.36MOps      729 kB  Optimal perf: imul64
Hash Plain:     529.61MOps      2306 kB Optimal perf: imul64
Hash Fancy:     597.36MOps      694 kB  Optimal perf: imul64
Pext  :         925.24MOps      843 kB  Optimal perf: pext_u64
HyperCube:      310.30MOps      841 kB  Optimal perf: none

Please post your results (Especially old intel + Ryzen 1/2) and if you want to add an algo please pm me - or create a PR - or contact me under daniel.infuehr@live.de

Happy new year!

I miss the following:
- table initialization code (to get an idea of how these hardcoded values were created);
- several algorithms from https://www.chessprogramming.org/Sliding_Piece_Attacks - e.g. Hyperbola Quintessence, Obstruction bitboards, Kindergarten bitboards or (as already mentioned) SISSY bitboards;
- appropriate performance data for using all these algorithms in the context of tree search in a "real" chess engine (i.e., not only for move generation in Perft).

[dangi12012]

I miss the following:
- table initialization code (to get an idea of how these hardcoded values were created);
- several algorithms from https://www.chessprogramming.org/Sliding_Piece_Attacks - e.g. Hyperbola Quintessence, Obstruction bitboards, Kindergarten bitboards or (as already mentioned) SISSY bitboards;
- appropriate performance data for using all these algorithms in the context of tree search in a "real" chess engine (i.e., not only for move generation in Perft).

Original Table initialisation will be in another project - since most of the time one method initialized multiple arrays (during runtime) - its not really pleasant or possible to copy code to achieve actual consteval initialisation. (Because consteval cannot initialize multiple arrays - only one at a time and the values are coupled in code!)
Consteval and Constexpr is faster and I am not willing to sacrifice any performance.

Hyperbola Quintessence is in there via "XorRookSub" algo (i am happy if we get another name but Hyperbola Quintessence is the engine name and not the sliding algo lookup name)

"Context of tree search" is not something that is testable. Thats a level of implementation where you really have to test every engine seperately with because the move sorting etc is so different. I made it so that the code is plug and play so just include the header and define the namespace and you are ready to go.

Big thanks to Michael Sherwin - SISSY Boards are implemented:
On Sissy: For a queen it is 8 array lookups into a table which is ~1.8x bigger than fancy hash. So the performance is actually ok for that. The nice thing is no dependency on imul64 and no branches which is a big + for cuda.

Code: Select all

AMD Ryzen 9 5950X 16-Core Processor
Megalooks Random Occupation/s:
Exploading:     149.98MOps      6 kB    Optimal perf: imul64
Reference:      71.15MOps       8 kB    Optimal perf: none
KoggeStone:     112.76MOps      0 kB    Optimal perf: none
RotatedBoard:   91.87MOps       14 kB   Optimal perf: none
QBB Algo:       173.37MOps      0 kB    Optimal perf: countr_zero, countl_zero
BobMike:        213.35MOps      8 kB    Optimal perf: countr_zero, countl_zero
SlideArithm:    250.99MOps      2 kB    Optimal perf: bzhi_u64, blsmsk_u64
SISSY BB:       235.72MOps      1409 kB Optimal perf: none
XorRookSub:     299.28MOps      2 kB    Optimal perf: bswap
Hash Variable:  417.15MOps      729 kB  Optimal perf: imul64
Hash Plain:     540.19MOps      2306 kB Optimal perf: imul64
Hash Fancy:     554.25MOps      694 kB  Optimal perf: imul64
Pext  :         950.37MOps      843 kB  Optimal perf: pext_u64
HyperCube:      313.20MOps      841 kB  Optimal perf: none

What I will be focusing on next is multithreading where the real crux and interesting behaviour will be. Since MMU resources are limited and shared with TT - In my informed opinion the codes with 0kb or <8kb lookup will look much better if there are 32 Threads doing slider queries onto random positions.

After that there will be a cuda translation for most of them.
Anyways who would be so kind to add HyperCube to the wiki? - or is this something that the authors do themselves?

[abulmo2]

I miss the following:
- table initialization code (to get an idea of how these hardcoded values were created);
- several algorithms from https://www.chessprogramming.org/Sliding_Piece_Attacks - e.g. Hyperbola Quintessence, Obstruction bitboards, Kindergarten bitboards or (as already mentioned) SISSY bitboards;
- appropriate performance data for using all these algorithms in the context of tree search in a "real" chess engine (i.e., not only for move generation in Perft).

+1

I'll add that the respect of the traditional names or spellings would be a plus, i.e. magic plain instead of hash plain, mailbox instead of mailslot, exploding instead of exploading, nodes per second instead of megalooks, etc. Daniel Inführ's posts are barely understandable by me because of that.

[abulmo2]

Hyperbola Quintessence is in there via "XorRookSub" algo (i am happy if we get another name but Hyperbola Quintessence is the engine name and not the sliding algo lookup name)

Daniel Inführ's case is worst than I thought ...
Please provide a dictionary to translate your invented name to the conventional one or stick to the conventional one. Hyperbola Quintessence is the name of an algorithm, derived from the Hyperbola project by Ryan Mack, but not an engine name. Hyperbola Quintessence applies to bishop diagonal moves, but not to rook moves on ranks, so calling it ***Rook*** is somewhat misleading.