Comparison of all known Sliding lookup algorithms

[Mergi]

Oops, forgot to post the single threaded results.

Code: Select all

Million Lookups/s Random Squares, Random Occupation/s:
Name                               Performance [MQueens/s]       Tablesize           Dependencies             Template  Author                                       Reference
Binary Neural Network              35.962782                     5852    [45kb]      pdep_u64, AVX2           no        Daniel Inführ (dangi12012)                   http://www.talkchess.com/forum3/viewtopic.php?f=7&t=79332
Exploding Bitboards                61.285682                     768     [6kb]       imul64                   no        Harald Lüßen                                  http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=4523&start=80
Reference (Switch Lookup)          45.776734                     0       [0kb]       none                     yes       Daniel Inführ (dangi12012)                   http://www.talkchess.com/forum3/viewtopic.php?f=7&t=78235&p=907362&hilit=espresso#p907362
AVX Branchless Shift               198.559123                    0       [0kb]       AVX2                     no        Daniel Inführ (dangi12012)                   http://www.talkchess.com/forum3/viewtopic.php?f=7&t=79005&start=60
Pext Emulated                      70.406628                     107904  [843kb]     none                     no        Zach Wegner                                  https://randombit.net/bitbashing/posts/haswell_bit_permutations.html
Dumb7 Fill                         76.379072                     0       [0kb]       none                     no        Gunnar Andersson                             https://www.chessprogramming.org/Dumb7Fill
Kogge-Stone                        121.197186                    0       [0kb]       none                     no        Peter M. Kogge, Harold S. Stone              https://www.chessprogramming.org/Kogge-Stone_Algorithm
Rotated Bitboards                  39.130035                     1848    [14kb]      none                     no        Robert Hyatt                                 https://www.chessprogramming.org/Rotated_Bitboards
QBBEngine                          181.375461                    0       [0kb]       countr_zero, countl_zero yes       Fabio Gobbato                                https://www.chessprogramming.org/QBBEngine
Classical Bob-Mike                 264.465141                    1024    [8kb]       countr_zero, countl_zero yes       Robert Hyatt and Michael Sherwin             https://www.chessprogramming.org/Classical_Approach
Leorik                             257.820557                    128     [1kb]       countl_zero              no        Thomas Jahn (lithander)                      https://github.com/lithander/MinimalChessEngine
Leorik Inline                      96.737293                     0       [0kb]       countl_zero              no        Thomas Jahn (lithander)                      https://github.com/lithander/MinimalChessEngine
Obstruction Difference             291.149068                    768     [6kb]       countl_zero              no        Michael Hoffmann                             http://www.talkchess.com/forum3/viewtopic.php?t=29087
Obstruction Difference Inline      91.151886                     0       [0kb]       countl_zero              yes       Michael Hoffmann                             http://www.talkchess.com/forum3/viewtopic.php?t=29087
Slide Arithmetic                   274.539860                    256     [2kb]       bzhi_u64, blsmsk_u64     no        Jakob Progsch and Daniel Inführ              http://www.talkchess.com/forum3/viewtopic.php?f=7&t=78693&p=914767&hilit=SlideArithm#p914767
Slide Arithmetic Inline            94.212820                     0       [0kb]       bzhi_u64, blsmsk_u64     no        Jakob Progsch and Daniel Inführ              http://www.talkchess.com/forum3/viewtopic.php?f=7&t=78693&p=914767&hilit=SlideArithm#p914767
SBAMG o^(o-3cbn)                   262.902487                    576     [4kb]       countl_zero, bswap       yes       Syed Fahad                                   http://www.talkchess.com/forum3/viewtopic.php?t=59845
SBAMG Inline                       90.577180                     0       [0kb]       countl_zero, bswap       yes       Syed Fahad and Daniel Inführ                 http://www.talkchess.com/forum3/viewtopic.php?t=59845
Hyperbola Quintessence o^(o-2r)    307.683629                    256     [2kb]       bswap                    no        Ryan Mack                                    https://www.chessprogramming.org/Hyperbola_Quintessence
Hyperbola Quintessence Inline      87.670208                     0       [0kb]       bswap                    yes       Ryan Mack                                    https://www.chessprogramming.org/Hyperbola_Quintessence
Kindergarten                       555.769115                    16640   [130kb]     imul64                   no        Urban Koistinen                              https://www.chessprogramming.org/Kindergarten_Bitboards
SISSY Bitboards                    370.042586                    180416  [1409kb]    none                     no        Michael Sherwin                              http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73083
Fancy Magic BB - Variable shift    559.388402                    93376   [729kb]     imul64                   yes       Pradu Kannan                                 https://www.chessprogramming.org/Magic_Bitboards#Fancy
Plain Magic BB                     612.864016                    295168  [2306kb]    imul64                   no        Lasse Hansen                                 https://www.chessprogramming.org/Magic_Bitboards#Plain
Black Magic BB - Fixed shift       764.010034                    88891   [694kb]     imul64                   no        Onno Garms and Volker Annuss                 https://www.chessprogramming.org/Magic_Bitboards#Fixed_shift_Fancy
Pext constexpr                     1163.049905                   107904  [843kb]     pext_u64                 yes       Zach Wegner                                  https://www.chessprogramming.org/BMI2#PEXTBitboards
HyperCube                          55.202769                     107680  [841kb]     none                     yes       Daniel Inführ (dangi12012)                   http://www.talkchess.com/forum3/viewtopic.php?f=7&t=79004&p=916723&hilit=hypercube#p916723

[Mike Sherwin]

Downloaded Visual Studio just for this since CLion was reporting infinite errors for me. Run on the new intel Alder lake - i5 12600.

Code: Select all

Summary:
Name                               Performance [MQueens/s]       Threads
Pext constexpr                     6554.064203                   12
Black Magic BB - Fixed shift       4738.681462                   12
Plain Magic BB                     3886.230599                   12
Fancy Magic BB - Variable shift    2239.493467                   11
SISSY Bitboards                    2227.502228                   12
Kindergarten                       2049.931199                   20
Obstruction Difference Inline      1841.383247                   5
Hyperbola Quintessence o^(o-2r)    1650.040220                   12
Obstruction Difference             1602.430353                   12
Classical Bob-Mike                 1579.920960                   18
Slide Arithmetic                   1476.564158                   12
Rotated Bitboards                  1455.383403                   12
HyperCube                          1419.521976                   12
Leorik                             1412.433535                   12
SBAMG Inline                       1397.168405                   12
SBAMG o^(o-3cbn)                   1391.312413                   12
Hyperbola Quintessence Inline      1241.529150                   12
Slide Arithmetic Inline            1235.689811                   12
Leorik Inline                      1225.377569                   12
AVX Branchless Shift               1136.519693                   12
QBBEngine                          1053.545113                   20
Exploding Bitboards                988.461768                    12
Reference (Switch Lookup)          766.453603                    12
Kogge-Stone                        700.052358                    12
Pext Emulated                      692.727658                    12
Dumb7 Fill                         440.855452                    16
Binary Neural Network              232.960289                    12

Did you feed SISSY with some power supplements or something?

[dangi12012]

Oops, forgot to post the single threaded results.

Mergi please include the CPU name - what did you use to run these tests?

I forgot to say thanks for all the work. So thanks! And I'm looking forward to see what you can do. And you are very welcome to add your name.

Thank you that means a lot to me!

If you want repeated tests for some algos you can just repeat the name you want to run in main.cpp on line 688.

Optimisation results look promising 5% increase for now. 1/2 ideas implemented. 2/2 is coming on the weekend when I find the time.



Greetings from Vienna!

[Mergi]

Mergi please include the CPU name - what did you use to run these tests?

i5 12600 (non k) with enabled AVX support.

[Desperado]

Downloaded Visual Studio just for this since CLion was reporting infinite errors for me. Run on the new intel Alder lake - i5 12600.

Code: Select all

Summary:
Name                               Performance [MQueens/s]       Threads
Pext constexpr                     6554.064203                   12
Black Magic BB - Fixed shift       4738.681462                   12
Plain Magic BB                     3886.230599                   12
Fancy Magic BB - Variable shift    2239.493467                   11
SISSY Bitboards                    2227.502228                   12
Kindergarten                       2049.931199                   20
Obstruction Difference Inline      1841.383247                   5
Hyperbola Quintessence o^(o-2r)    1650.040220                   12
Obstruction Difference             1602.430353                   12
Classical Bob-Mike                 1579.920960                   18
Slide Arithmetic                   1476.564158                   12
Rotated Bitboards                  1455.383403                   12
HyperCube                          1419.521976                   12
Leorik                             1412.433535                   12
SBAMG Inline                       1397.168405                   12
SBAMG o^(o-3cbn)                   1391.312413                   12
Hyperbola Quintessence Inline      1241.529150                   12
Slide Arithmetic Inline            1235.689811                   12
Leorik Inline                      1225.377569                   12
AVX Branchless Shift               1136.519693                   12
QBBEngine                          1053.545113                   20
Exploding Bitboards                988.461768                    12
Reference (Switch Lookup)          766.453603                    12
Kogge-Stone                        700.052358                    12
Pext Emulated                      692.727658                    12
Dumb7 Fill                         440.855452                    16
Binary Neural Network              232.960289                    12

Did you feed SISSY with some power supplements or something?

Why are here different thread numbers reported (again) ? (18,16,5,20,12) And what does that mean in relation to the performance?

[Mike Sherwin]

Downloaded Visual Studio just for this since CLion was reporting infinite errors for me. Run on the new intel Alder lake - i5 12600.

Code: Select all

Summary:
Name                               Performance [MQueens/s]       Threads
Pext constexpr                     6554.064203                   12
Black Magic BB - Fixed shift       4738.681462                   12
Plain Magic BB                     3886.230599                   12
Fancy Magic BB - Variable shift    2239.493467                   11
SISSY Bitboards                    2227.502228                   12
Kindergarten                       2049.931199                   20
Obstruction Difference Inline      1841.383247                   5
Hyperbola Quintessence o^(o-2r)    1650.040220                   12
Obstruction Difference             1602.430353                   12
Classical Bob-Mike                 1579.920960                   18
Slide Arithmetic                   1476.564158                   12
Rotated Bitboards                  1455.383403                   12
HyperCube                          1419.521976                   12
Leorik                             1412.433535                   12
SBAMG Inline                       1397.168405                   12
SBAMG o^(o-3cbn)                   1391.312413                   12
Hyperbola Quintessence Inline      1241.529150                   12
Slide Arithmetic Inline            1235.689811                   12
Leorik Inline                      1225.377569                   12
AVX Branchless Shift               1136.519693                   12
QBBEngine                          1053.545113                   20
Exploding Bitboards                988.461768                    12
Reference (Switch Lookup)          766.453603                    12
Kogge-Stone                        700.052358                    12
Pext Emulated                      692.727658                    12
Dumb7 Fill                         440.855452                    16
Binary Neural Network              232.960289                    12

Did you feed SISSY with some power supplements or something?

Why are here different thread numbers reported (again) ? (18,16,5,20,12) And what does that mean in relation to the performance?

That is a good question. I suppose that you wanted to quote Mergi?

[Desperado]

Downloaded Visual Studio just for this since CLion was reporting infinite errors for me. Run on the new intel Alder lake - i5 12600.

Code: Select all

Summary:
Name                               Performance [MQueens/s]       Threads
Pext constexpr                     6554.064203                   12
Black Magic BB - Fixed shift       4738.681462                   12
Plain Magic BB                     3886.230599                   12
Fancy Magic BB - Variable shift    2239.493467                   11
SISSY Bitboards                    2227.502228                   12
Kindergarten                       2049.931199                   20
Obstruction Difference Inline      1841.383247                   5
Hyperbola Quintessence o^(o-2r)    1650.040220                   12
Obstruction Difference             1602.430353                   12
Classical Bob-Mike                 1579.920960                   18
Slide Arithmetic                   1476.564158                   12
Rotated Bitboards                  1455.383403                   12
HyperCube                          1419.521976                   12
Leorik                             1412.433535                   12
SBAMG Inline                       1397.168405                   12
SBAMG o^(o-3cbn)                   1391.312413                   12
Hyperbola Quintessence Inline      1241.529150                   12
Slide Arithmetic Inline            1235.689811                   12
Leorik Inline                      1225.377569                   12
AVX Branchless Shift               1136.519693                   12
QBBEngine                          1053.545113                   20
Exploding Bitboards                988.461768                    12
Reference (Switch Lookup)          766.453603                    12
Kogge-Stone                        700.052358                    12
Pext Emulated                      692.727658                    12
Dumb7 Fill                         440.855452                    16
Binary Neural Network              232.960289                    12

Did you feed SISSY with some power supplements or something?

Why are here different thread numbers reported (again) ? (18,16,5,20,12) And what does that mean in relation to the performance?

That is a good question. I suppose that you wanted to quote Mergi?

Yes, you are right, i wanted to quote Mergi.

However, the measurements are already through the whole thread as in this case, no matter who (including me) measured.

[dangi12012]

The most important thing was for me personally to have
Modern Intel, Modernd AMD, Old hardware (raspberry pi). These metrics are here now. If you have a modern x64 cpu - use pext.
Oh and I have the data from my phone too - thanks to termux no root or anything is needed.

Snapdragon 888:

Code: Select all

Million Lookups/s Random Squares, Random Occupation/s:
Name                               Performance [MQueens/s]       Tablesize           Dependencies             Template  Author                                       Reference
Binary Neural Network              0.964475                      5852    [45kb]      pdep_u64, AVX2           no        Daniel Inf�hr (dangi12012)                   http://www.talkchess.com/forum3/viewtopic.php?f=7&t=79332
Exploding Bitboards                58.367696                     768     [6kb]       imul64                   no        Harald L��en                                    http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=4523&start=80
Reference (Switch Lookup)          66.870471                     0       [0kb]       none                     yes       Daniel Inf�hr (dangi12012)                   http://www.talkchess.com/forum3/viewtopic.php?f=7&t=78235&p=907362&hilit=espresso#p907362
AVX Branchless Shift               21.521543                     0       [0kb]       AVX2                     no        Daniel Inf�hr (dangi12012)                   http://www.talkchess.com/forum3/viewtopic.php?f=7&t=79005&start=60
Pext Emulated                      41.477350                     107904  [843kb]     none                     no        Zach Wegner                                  https://randombit.net/bitbashing/posts/haswell_bit_permutations.html
Dumb7 Fill                         66.891244                     0       [0kb]       none                     no        Gunnar Andersson                             https://www.chessprogramming.org/Dumb7Fill     
Kogge-Stone                        142.388079                    0       [0kb]       none                     no        Peter M. Kogge, Harold S. Stone              https://www.chessprogramming.org/Kogge-Stone_Algorithm
Rotated Bitboards                  20.767520                     1848    [14kb]      none                     no        Robert Hyatt                                 https://www.chessprogramming.org/Rotated_Bitboards
QBBEngine                          138.407971                    0       [0kb]       countr_zero, countl_zero yes       Fabio Gobbato                                https://www.chessprogramming.org/QBBEngine     
Classical Bob-Mike                 167.568268                    1024    [8kb]       countr_zero, countl_zero yes       Robert Hyatt and Michael Sherwin             https://www.chessprogramming.org/Classical_Approach
Leorik                             181.636576                    128     [1kb]       countl_zero              no        Thomas Jahn (lithander)                      https://github.com/lithander/MinimalChessEngine
Leorik Inline                      91.578294                     0       [0kb]       countl_zero              no        Thomas Jahn (lithander)                      https://github.com/lithander/MinimalChessEngine
Obstruction Difference             173.547555                    768     [6kb]       countl_zero              no        Michael Hoffmann                             http://www.talkchess.com/forum3/viewtopic.php?t=29087
Obstruction Difference Inline      91.102446                     0       [0kb]       countl_zero              yes       Michael Hoffmann                             http://www.talkchess.com/forum3/viewtopic.php?t=29087
Slide Arithmetic                   202.909424                    256     [2kb]       bzhi_u64, blsmsk_u64     no        Jakob Progsch and Daniel Inf�hr              http://www.talkchess.com/forum3/viewtopic.php?f=7&t=78693&p=914767&hilit=SlideArithm#p914767
Slide Arithmetic Inline            92.927057                     0       [0kb]       bzhi_u64, blsmsk_u64     no        Jakob Progsch and Daniel Inf�hr              http://www.talkchess.com/forum3/viewtopic.php?f=7&t=78693&p=914767&hilit=SlideArithm#p914767
SBAMG o^(o-3cbn)                   193.827305                    576     [4kb]       countl_zero, bswap       yes       Syed Fahad                                   http://www.talkchess.com/forum3/viewtopic.php?t=59845
SBAMG Inline                       117.650002                    0       [0kb]       countl_zero, bswap       yes       Syed Fahad and Daniel Inf�hr                 http://www.talkchess.com/forum3/viewtopic.php?t=59845
Hyperbola Quintessence o^(o-2r)    275.414915                    256     [2kb]       bswap                    no        Ryan Mack                                    https://www.chessprogramming.org/Hyperbola_Quintessence
Hyperbola Quintessence Inline      169.233447                    0       [0kb]       bswap                    yes       Ryan Mack                                    https://www.chessprogramming.org/Hyperbola_Quintessence
Kindergarten                       315.629848                    16640   [130kb]     imul64                   no        Urban Koistinen                              https://www.chessprogramming.org/Kindergarten_Bitboards
SISSY Bitboards                    150.427387                    180416  [1409kb]    none                     no        Michael Sherwin                              http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73083
Fancy Magic BB - Variable shift    380.584881                    93376   [729kb]     imul64                   yes       Pradu Kannan                                 https://www.chessprogramming.org/Magic_Bitboards#Fancy
Plain Magic BB                     207.034129                    295168  [2306kb]    imul64                   no        Lasse Hansen                                 https://www.chessprogramming.org/Magic_Bitboards#Plain
Black Magic BB - Fixed shift       333.949340                    88891   [694kb]     imul64                   no        Onno Garms and Volker Annuss                 https://www.chessprogramming.org/Magic_Bitboards#Fixed_shift_Fancy
Pext constexpr                     40.178011                     107904  [843kb]     pext_u64                 yes       Zach Wegner                                  https://www.chessprogramming.org/BMI2#PEXTBitboards
HyperCube                          30.703956                     107680  [841kb]     none                     yes       Daniel Inf�hr (dangi12012)                   http://www.talkchess.com/forum3/viewtopic.php?f=7&t=79004&p=916723&hilit=hypercube#p916723

[dangi12012]

Next idea: Generating random codes and finding cheap algos - if this is even possible remains an open question.

We have 2^14 different inputs where the result has to correspond to the correct bits. There are many possibilities to find solutions because the inputs are known - and the output is known so a Dictionary (Hashing) or PEXT (also hashing) are the obvious approaches. There are even possibilities to go to binary synthesis algos like karnaugh veitch maps or advances (Espresso Logistic) minimizer. All these have been done.

Now take the core algo of hyperbola quintessence:


I count 7 instructions here - and a handfull of constants here.
Now having a abstract syntax tree is really simple if we exclude loops conditions (which we want - we want to find the simplest possible branchless algorithm).

So going down that route would yield this:

Code: Select all

struct Instruction 
{
	virtual uint64_t eval() const = NULL;
};

struct BinaryInstruction : Instruction
{
	Instruction* left;
	Instruction* right;

	BinaryInstruction(Instruction& Left, Instruction& Right) : left(&Left), right(&Right)
	{
		
	}
	
	virtual uint64_t eval() const = NULL;
};

struct ConstInstruction : Instruction {
	uint64_t value;
	ConstInstruction(uint64_t constant) : value(constant)
	{

	}

	virtual uint64_t eval() const override {
		return value;
	}
};

struct OrInstruction : BinaryInstruction
{
	OrInstruction(Instruction& Left, Instruction& Right) : BinaryInstruction(Left, Right)
	{

	}

	virtual uint64_t eval() const override {
		return left->eval() | right->eval();
	}
};

struct XorInstruction : BinaryInstruction
{
	XorInstruction(Instruction& Left, Instruction& Right) : BinaryInstruction(Left, Right)
	{

	}

	virtual uint64_t eval() const override {
		return left->eval() ^ right->eval();
	}
};

struct ShiftLeftInstruction : BinaryInstruction
{
	ShiftLeftInstruction(Instruction& Left, Instruction& Right) : BinaryInstruction(Left, Right)
	{

	}

	virtual uint64_t eval() const override {
		return left->eval() << right->eval();
	}
};

Then some simple code like this already works:

Code: Select all

ConstInstruction a(1);
ConstInstruction b(3);
ShiftLeftInstruction c(a, b);

std::cout << c.eval();

If you want C++ code from that all that needs to be done is also have a virtual print function and call that once on root (like eval()) then the tree can print itself into a C++ code string.

Since its a tree with constant tokens and other stuff randomly finding the correct solution would be 1/N! - so its important to limit the possible inputs for the algo to really simple instructions and a handfull of constants. Probably around 14 ast tokens max. (14! = ~10^11)

For the beginning I will limit it to single squares so it might be possible to have 64 different very small algorithms that are also performing correct lookups. That might even be competitive against PEXT since for some movegenerators the current square is a known constant (like in a 64 loop)

Will keep you posted if searching with 14 AST tokens and limiting those to simple instructions yields some previously not found slider piece lookups.
If it does not find solution quickly there will have to be a form of tree search that approximates and finds better and better solutions - kind of like chess: but not finding good moves in a gametree - but finding good instructions in a tree of code. There you have it. Not solving chess - but solving treeseach that finds the optimal treesearch sourcecode for chess.

Since I want to have an algorithm in N instructions or less I think exhaustive search with the discovery cost of N! should yield some algos. (Hopefully)

[Mike Sherwin]

Classic Bob_Mike optimized a bit, no stop bit or ray with stop tables needed.

Code: Select all

         sq = std::countr_zero(ray[fs].rayNN & occ);
         rayNN = sq == 64 ? 0 : ray[sq].rayNN
  
	 sq = std::countl_zero(ray[fs].raySS & occ);
	 raySS = sq == 64 ? 0 : ray[63 - sq].raySS;