Comparison of all known Sliding lookup algorithms

Discussion of chess software programming and technical issues.

Moderator: Ras

dangi12012
Posts: 1062
Joined: Tue Apr 28, 2020 10:03 pm
Full name: Daniel Infuehr

Re: Comparison of all known Sliding lookup algorithms

Post by dangi12012 »

Biggest Update Yet: Author references, Kindergarten Board, SBAMG, More Templating

I have added all algos of commentors that sent me PMs and thanks to you all for the nice messages! - With some experience I could squeeze more performance out of some algorithms than their original authors.

This git repo contains one single header for any and all algorithms that you can think of in the best possible and most up to date version:
https://github.com/Gigantua/Chess_Movegen

Now I managed to increase SBAMG by Syed Fahad with the o^(o-3cbn) trick from 280 to 400Mnps! - with some optimsiations. In my opinion this git repo is really great to read and look at all the ideas in a modern C++20 envelope.

No Initialisation - just copy paste any header of your liking and play with it.
If someone is missing an algorithm just respond or PM me.
All algos that support templating have a seperate templated call that improves performance by another 40-70%! (this is possible if the square you query is a constant like in a compiletime unrolled loop!)

If you read this message please run it and posts results! I am Interested in any processor really.
Greetings - Daniel

Code: Select all

AMD Ryzen 9 5950X 16-Core Processor

Megalooks Known Positions/s:
Name                               Performance [MQueens/s]       Tablesize           Dependencies             Template  Author                                       Reference
Exploding Bitboards                151.495605                    768     [6kb]       imul64                   no        Harald Lüßen                                 http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=4523&start=80
Reference (Switch Lookup)          202.809546                    0       [0kb]       none                     yes       Daniel Inführ (dangi12012)                   http://www.talkchess.com/forum3/viewtopic.php?f=7&t=78235&p=907362&hilit=espresso#p907362
Pext Emulated                      97.441194                     107904  [843kb]     none                     no        Zach Wegner                                  https://randombit.net/bitbashing/posts/haswell_bit_permutations.html
Dumb7 Fill                         110.854068                    0       [0kb]       none                     no        Gunnar Andersson                             https://www.chessprogramming.org/Dumb7Fill
Kogge-Stone                        180.547527                    0       [0kb]       none                     no        Peter M. Kogge, Harold S. Stone              https://www.chessprogramming.org/Kogge-Stone_Algorithm
Rotated Bitboards                  60.483067                     1848    [14kb]      none                     no        Robert Hyatt                                 https://www.chessprogramming.org/Rotated_Bitboards
QBBEngine                          226.598966                    0       [0kb]       countr_zero, countl_zero yes       Fabio Gobbato                                https://www.chessprogramming.org/QBBEngine
Classical Bob-Mike                 265.402686                    1024    [8kb]       countr_zero, countl_zero yes       Robert Hyatt and Michael Sherwin             https://www.chessprogramming.org/Classical_Approach
Leorik                             230.667371                    128     [1kb]       countl_zero              no        Thomas Jahn (lithander)                      https://github.com/lithander/MinimalChessEngine
Leorik Inline                      314.600666                    0       [0kb]       countl_zero              no        Thomas Jahn (lithander)                      https://github.com/lithander/MinimalChessEngine
Obstruction Difference             259.557390                    768     [6kb]       countl_zero              no        Michael Hoffmann                             http://www.talkchess.com/forum3/viewtopic.php?t=29087
Obstruction Difference Inline      606.763325                    0       [0kb]       countl_zero              yes       Michael Hoffmann                             http://www.talkchess.com/forum3/viewtopic.php?t=29087
Slide Arithmetic                   262.357123                    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            303.428841                    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)                   283.322362                    576     [4kb]       countl_zero, bswap       yes       Syed Fahad                                   http://www.talkchess.com/forum3/viewtopic.php?t=59845
SBAMG Inline                       416.909593                    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)    319.183210                    256     [2kb]       bswap                    no        Ryan Mack                                    https://www.chessprogramming.org/Hyperbola_Quintessence
Hyperbola Quintessence Inline      386.557931                    0       [0kb]       bswap                    yes       Ryan Mack                                    https://www.chessprogramming.org/Hyperbola_Quintessence
Kindergarten                       406.239070                    16640   [130kb]     imul64                   no        Urban Koistinen                              https://www.chessprogramming.org/Kindergarten_Bitboards
SISSY Bitboards                    260.810387                    180416  [1409kb]    none                     no        Michael Sherwin                              http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73083
Magic BB - Fancy variable shift    292.180875                    93376   [729kb]     imul64                   yes       Pradu Kannan                                 https://www.chessprogramming.org/Magic_Bitboards#Fancy
Magic BB - Plain                   916.191392                    295168  [2306kb]    imul64                   no        Lasse Hansen                                 https://www.chessprogramming.org/Magic_Bitboards#Plain
Black Magic BB - Fixed shift       1300.287079                   88891   [694kb]     imul64                   no        Onno Garms and Volker Annuss                 https://www.chessprogramming.org/Magic_Bitboards#Fixed_shift_Fancy
Pext constexpr                     1643.976368                   107904  [843kb]     pext_u64                 yes       Zach Wegner                                  https://www.chessprogramming.org/BMI2#PEXTBitboards
HyperCube                          329.714714                    107680  [841kb]     none                     yes       Daniel Inführ (dangi12012)                   http://www.talkchess.com/forum3/viewtopic.php?f=7&t=79004&p=916723&hilit=hypercube#p916723
Im somewhat proud of my work since the 0kb versions of most algos didnt exist before and the templated versions also didnt exist before at all. In some cases I could improve the Authors reference to as much as 170% of original performance. This was about 200hrs of work so far.

If you have additional ideas or results please contact me. Now I will focus more on the CUDA side and I am currently creating one more algorithm that should be competitive!
Greetings - Daniel
Worlds-fastest-Bitboard-Chess-Movegenerator
Daniel Inführ - Software Developer
Top
User avatar
j.t.
Posts: 263
Joined: Wed Jun 16, 2021 2:08 am
Location: Berlin
Full name: Jost Triller

Re: Comparison of all known Sliding lookup algorithms

Post by j.t. »

dangi12012 wrote: ↑Sun Jan 30, 2022 1:14 am I am Interested in any processor really.

Code: Select all

Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz

Megalooks Known Positions/s:
Name                               Performance [MQueens/s]       Tablesize           Dependencies             Template  Author                                       Reference
Exploding Bitboards                213.228047                    768     [6kb]       imul64                   no        Harald Lá en	                              http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=4523&start=80
Reference (Switch Lookup)          170.738737                    0       [0kb]       none                     yes       Daniel Infhr (dangi12012)                   http://www.talkchess.com/forum3/viewtopic.php?f=7&t=78235&p=907362&hilit=espresso#p907362
Pext Emulated                      360.779761                    107904  [843kb]     none                     no        Zach Wegner                                  https://randombit.net/bitbashing/posts/haswell_bit_permutations.html
Dumb7 Fill                         160.001029                    0       [0kb]       none                     no        Gunnar Andersson                             https://www.chessprogramming.org/Dumb7Fill        
Kogge-Stone                        248.092038                    0       [0kb]       none                     no        Peter M. Kogge, Harold S. Stone              https://www.chessprogramming.org/Kogge-Stone_Algorithm
Rotated Bitboards                  224.494968                    1848    [14kb]      none                     no        Robert Hyatt                                 https://www.chessprogramming.org/Rotated_Bitboards
QBBEngine                          219.791507                    0       [0kb]       countr_zero, countl_zero yes       Fabio Gobbato                                https://www.chessprogramming.org/QBBEngine        
Classical Bob-Mike                 189.930082                    1024    [8kb]       countr_zero, countl_zero yes       Robert Hyatt and Michael Sherwin             https://www.chessprogramming.org/Classical_Approach
Leorik                             281.956972                    128     [1kb]       countl_zero              no        Thomas Jahn (lithander)                      https://github.com/lithander/MinimalChessEngine   
Leorik Inline                      300.741471                    0       [0kb]       countl_zero              no        Thomas Jahn (lithander)                      https://github.com/lithander/MinimalChessEngine   
Obstruction Difference             342.800257                    768     [6kb]       countl_zero              no        Michael Hoffmann                             http://www.talkchess.com/forum3/viewtopic.php?t=29087
Obstruction Difference Inline      337.997968                    0       [0kb]       countl_zero              yes       Michael Hoffmann                             http://www.talkchess.com/forum3/viewtopic.php?t=29087
Slide Arithmetic                   234.334412                    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            224.766979                    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)                   256.725302                    576     [4kb]       countl_zero, bswap       yes       Syed Fahad                                   http://www.talkchess.com/forum3/viewtopic.php?t=59845
SBAMG Inline                       296.763908                    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)    432.717956                    256     [2kb]       bswap                    no        Ryan Mack                                    https://www.chessprogramming.org/Hyperbola_Quintessence
Hyperbola Quintessence Inline      259.095627                    0       [0kb]       bswap                    yes       Ryan Mack                                    https://www.chessprogramming.org/Hyperbola_Quintessence
Kindergarten                       723.378918                    16640   [130kb]     imul64                   no        Urban Koistinen                              https://www.chessprogramming.org/Kindergarten_Bitboards
SISSY Bitboards                    179.911100                    180416  [1409kb]    none                     no        Michael Sherwin                              http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73083
Magic BB - Fancy variable shift    623.397370                    93376   [729kb]     imul64                   yes       Pradu Kannan                                 https://www.chessprogramming.org/Magic_Bitboards#Fancy
Magic BB - Plain                   469.690581                    295168  [2306kb]    imul64                   no        Lasse Hansen                                 https://www.chessprogramming.org/Magic_Bitboards#Plain
Black Magic BB - Fixed shift       591.846581                    88891   [694kb]     imul64                   no        Onno Garms and Volker Annuss                 https://www.chessprogramming.org/Magic_Bitboards#Fixed_shift_Fancy
Pext constexpr                     915.050827                    107904  [843kb]     pext_u64                 yes       Zach Wegner                                  https://www.chessprogramming.org/BMI2#PEXTBitboards
HyperCube                          142.127294                    107680  [841kb]     none                     yes       Daniel Infhr (dangi12012)                   http://www.talkchess.com/forum3/viewtopic.php?f=7&t=79004&p=916723&hilit=hypercube#p916723

Megalookups Multithreaded Random Positions/s:
Summary:
Name                               Performance [MQueens/s]       Threads             
Pext constexpr                     2088.741897                   8                   
Kindergarten                       1563.532787                   8                   
Black Magic BB - Fixed shift       1364.794811                   8                   
Magic BB - Fancy variable shift    1236.361054                   8                   
Hyperbola Quintessence o^(o-2r)    1109.982398                   4                   
Pext Emulated                      1084.087005                   8                   
Obstruction Difference             1008.941683                   8                   
Obstruction Difference Inline      1001.494449                   8                   
Magic BB - Plain                   960.477046                    11                  
Rotated Bitboards                  925.342660                    8                   
Leorik                             884.492065                    14                  
Leorik Inline                      862.632856                    10                  
SBAMG Inline                       806.501166                    4                   
SBAMG o^(o-3cbn)                   783.232059                    4                   
Classical Bob-Mike                 749.948353                    8                   
Hyperbola Quintessence Inline      697.802254                    4                   
Slide Arithmetic                   677.647935                    14                  
Slide Arithmetic Inline            662.674961                    8                   
QBBEngine                          628.705077                    15                  
HyperCube                          580.146949                    7                   
Exploding Bitboards                571.625438                    14                  
Kogge-Stone                        534.332513                    13                  
Dumb7 Fill                         459.821607                    8                   
Reference (Switch Lookup)          424.194042                    16                  
SISSY Bitboards                    353.144875                    8
Quite interesting that Black Magic and Plain BB are much faster on your Ryzen, but, for example, Fancy Magics or Kindergarten BB are much faster on my notebook i5, which I expected to be significantly slower for all methods.

By the way, when I compile with "-static" on Linux the program segfaults:

Code: Select all

(valgrind --leak-check=full ./movegen_compare)
... conditional jumps blablabla
==183764== Conditional jump or move depends on uninitialised value(s)
==183764==    at 0x5C213D: malloc (in /home/tsoj/Dokumente/Projects/Chess_Movegen/movegen_compare)
==183764==    by 0x4E30EC: operator new(unsigned long) (in /home/tsoj/Dokumente/Projects/Chess_Movegen/movegen_compare)
==183764==    by 0x460464: GetPerf() (in /home/tsoj/Dokumente/Projects/Chess_Movegen/movegen_compare)
==183764==    by 0x47CFBE: main (in /home/tsoj/Dokumente/Projects/Chess_Movegen/movegen_compare)
==183764== 
==183764== 
==183764== More than 100 errors detected.  Subsequent errors
==183764== will still be recorded, but in less detail than before.
==183764== Jump to the invalid address stated on the next line
==183764==    at 0x0: ???
==183764==    by 0x556327: std::thread::join() (in /home/tsoj/Dokumente/Projects/Chess_Movegen/movegen_compare)
==183764==    by 0x4606CA: GetPerf() (in /home/tsoj/Dokumente/Projects/Chess_Movegen/movegen_compare)
==183764==    by 0x47CFBE: main (in /home/tsoj/Dokumente/Projects/Chess_Movegen/movegen_compare)
==183764==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==183764== 
==183764== 
==183764== Process terminating with default action of signal 11 (SIGSEGV): dumping core
==183764==  Bad permissions for mapped region at address 0x0
==183764==    at 0x0: ???
==183764==    by 0x556327: std::thread::join() (in /home/tsoj/Dokumente/Projects/Chess_Movegen/movegen_compare)
==183764==    by 0x4606CA: GetPerf() (in /home/tsoj/Dokumente/Projects/Chess_Movegen/movegen_compare)
==183764==    by 0x47CFBE: main (in /home/tsoj/Dokumente/Projects/Chess_Movegen/movegen_compare)
==183764== 
==183764== HEAP SUMMARY:
==183764==     in use at exit: 0 bytes in 0 blocks
==183764==   total heap usage: 0 allocs, 0 frees, 0 bytes allocated
==183764== 
==183764== All heap blocks were freed -- no leaks are possible
==183764== 
==183764== Use --track-origins=yes to see where uninitialised values come from
==183764== For lists of detected and suppressed errors, rerun with: -s
==183764== ERROR SUMMARY: 135 errors from 101 contexts (suppressed: 0 from 0)
fish: Job 1, 'valgrind --leak-check=full ./mo…' terminated by signal SIGSEGV (Address boundary error)
Top
Harald
Posts: 318
Joined: Thu Mar 09, 2006 1:07 am

Re: Comparison of all known Sliding lookup algorithms

Post by Harald »

"This git repo contains one single header for any and all algorithms that you can think of in the best possible and most up to date version:
https://github.com/Gigantua/Chess_Movegen"

Please, change Exploading.hpp to Exploding.hpp. :-)

What was the reason to change the exploding rook algorithm? Better performance?
Top
tcusr
Posts: 325
Joined: Tue Aug 31, 2021 10:32 pm
Full name: tcusr

Re: Comparison of all known Sliding lookup algorithms

Post by tcusr »

in a chess engine in what scenario is having the square as a template parameter useful?
and even if it was useful the compiler will be smart enough to do all the optimizations even with a normal function parameter
Top
User avatar
lithander
Posts: 915
Joined: Sun Dec 27, 2020 2:40 am
Location: Bremen, Germany
Full name: Thomas Jahn

Re: Comparison of all known Sliding lookup algorithms

Post by lithander »

Could someone explain to me why changing for example

Code: Select all

const uint64_t ANTIDIAGONAL = 0x0102040810204080UL;
to

Code: Select all

static constexpr uint64_t ANTIDIAGONAL = 0x0102040810204080UL;
leads to better performance?

Shouldn't it mean exactly the same?
Minimal Chess (simple, open source, C#) - Youtube & Github
Leorik (competitive, in active development, C#) - Github & Lichess
Top
tcusr
Posts: 325
Joined: Tue Aug 31, 2021 10:32 pm
Full name: tcusr

Re: Comparison of all known Sliding lookup algorithms

Post by tcusr »

lithander wrote: ↑Sun Jan 30, 2022 1:51 pm Could someone explain to me why changing for example

Code: Select all

const uint64_t ANTIDIAGONAL = 0x0102040810204080UL;
to

Code: Select all

static constexpr uint64_t ANTIDIAGONAL = 0x0102040810204080UL;
leads to better performance?

Shouldn't it mean exactly the same?
it's a C++ thing. const means read-only, not constant, therefore the compiler can't perform some optimizations. constexpr is what you want for that.
static also helps because when used in global scope it means that the variable/function is only used in that translation unit.
edit:
static is probably redundant here since constexpr also implies that
Top
dangi12012
Posts: 1062
Joined: Tue Apr 28, 2020 10:03 pm
Full name: Daniel Infuehr

Re: Comparison of all known Sliding lookup algorithms

Post by dangi12012 »

Update: Binary Neural Networks Sliding Inference

This one has bugged me for a while. While board evaluations using neural networs exist there has been no publications that release a trained binary neural network that produces the sliding piece outputs. Until now! (the actual release will be in the corresponding thread - not here)
So there is "By Calculation", "By Occupancy Lookup" and the new method: "By machine learning"

Neural networks seem to be best suited for mailbox board representations because there the board is in a nice uint8_t array thats perfectly suited for all the different __mm256_imul intrinsics operations.
But this is a fallacy! In reality bitboard neural networks can be made an order of magnitude faster than even well optimized uint8_t networks.

A neural network can be reduced to a BINARY neural network which does not use uint8 or float but operates on single bits! I wont go into detail here but I will release the training code with all references and more information in a seperate thread. You can lookup a reference implementation right now: https://github.com/Gigantua/Chess_Moveg ... etwork.hpp

The performance on x64 is not good - but while implementing this I am looking forward for an implementation in cuda where there will be access to 2088Tflops of compute for this type of operation.
https://on-demand.gputechconf.com/gtc/2 ... n-cuda.pdf
One Cuda TensorOp can fit many of these networks and could calculate the output like below in a single clock cycle! (Per TensorCORE!)

Anyways this is one trained network per output bit. The thing about this is that machine learning is infinitely maluable so you can train against any feature you want to.

This is 14x 64x1 networks per square (so very wasteful for now). 64 being the input layer size of uint64_t (because its binary) and a single output bit which ored together with the other 13 networks will create the attacked squares uint64_t which is what we want from a Sliding piece algorithm!

The Tablesize will go down as improvements come and the performance will increase lineary. (For now its increadibly a very wasteful network size because its extremely hard to train a binary neural network efficiently).

This is one complete network which produces 1 bit and is completely independent of the others:
The AVX2 version does this whole loop including everything seen here in around 10! intrinsics operations.

Code: Select all

uint8_t* vals = (uint8_t*)results;
uint64_t target = 0;
for (int i = 0; i < 64; i++)
{
	target |= static_cast<uint64_t>((std::popcount(vals[i]) < 4)) << i; //64bit first layer
}
result |= static_cast<uint64_t>((std::popcount(target) > 16)) << bit;   //single bit output layer
But I really recommend checking it out on github! Especially the Vector version. 32 comparisons can be done in one operation and these can be reduced to a bitmask in another operation: _mm256_movemask_epi8. Really efficient stuff when compared to the serial code!

Code: Select all

Megalooks Known Positions/s:
Name                               Performance [MQueens/s]       Tablesize           Dependencies             Template  Author                                       Reference
Binary Neural Network              24.518934                     14336   [112kb]     pdep_u64, AVX2           no        Daniel Inführ                                Not released yet
Exploding Bitboards                148.039654                    768     [6kb]       imul64                   no        Harald Lüßen                                  http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=4523&start=80
Reference (Switch Lookup)          196.386187                    0       [0kb]       none                     yes       Daniel Inführ (dangi12012)                   http://www.talkchess.com/forum3/viewtopic.php?f=7&t=78235&p=907362&hilit=espresso#p907362
Pext Emulated                      97.352543                     107904  [843kb]     none                     no        Zach Wegner                                  https://randombit.net/bitbashing/posts/haswell_bit_permutations.html
Dumb7 Fill                         110.213540                    0       [0kb]       none                     no        Gunnar Andersson                             https://www.chessprogramming.org/Dumb7Fill
Kogge-Stone                        179.320884                    0       [0kb]       none                     no        Peter M. Kogge, Harold S. Stone              https://www.chessprogramming.org/Kogge-Stone_Algorithm
Rotated Bitboards                  59.689939                     1848    [14kb]      none                     no        Robert Hyatt                                 https://www.chessprogramming.org/Rotated_Bitboards
QBBEngine                          227.642566                    0       [0kb]       countr_zero, countl_zero yes       Fabio Gobbato                                https://www.chessprogramming.org/QBBEngine
Classical Bob-Mike                 253.597418                    1024    [8kb]       countr_zero, countl_zero yes       Robert Hyatt and Michael Sherwin             https://www.chessprogramming.org/Classical_Approach
Leorik                             226.579632                    128     [1kb]       countl_zero              no        Thomas Jahn (lithander)                      https://github.com/lithander/MinimalChessEngine
Leorik Inline                      315.276061                    0       [0kb]       countl_zero              no        Thomas Jahn (lithander)                      https://github.com/lithander/MinimalChessEngine
Obstruction Difference             252.106666                    768     [6kb]       countl_zero              no        Michael Hoffmann                             http://www.talkchess.com/forum3/viewtopic.php?t=29087
Obstruction Difference Inline      602.006752                    0       [0kb]       countl_zero              yes       Michael Hoffmann                             http://www.talkchess.com/forum3/viewtopic.php?t=29087
Slide Arithmetic                   260.965122                    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            299.453731                    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)                   287.344323                    576     [4kb]       countl_zero, bswap       yes       Syed Fahad                                   http://www.talkchess.com/forum3/viewtopic.php?t=59845
SBAMG Inline                       402.182342                    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)    310.452047                    256     [2kb]       bswap                    no        Ryan Mack                                    https://www.chessprogramming.org/Hyperbola_Quintessence
Hyperbola Quintessence Inline      369.667830                    0       [0kb]       bswap                    yes       Ryan Mack                                    https://www.chessprogramming.org/Hyperbola_Quintessence
Kindergarten                       394.269782                    16640   [130kb]     imul64                   no        Urban Koistinen                              https://www.chessprogramming.org/Kindergarten_Bitboards
SISSY Bitboards                    252.477335                    180416  [1409kb]    none                     no        Michael Sherwin                              http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73083
Magic BB - Fancy variable shift    282.249049                    93376   [729kb]     imul64                   yes       Pradu Kannan                                 https://www.chessprogramming.org/Magic_Bitboards#Fancy
Magic BB - Plain                   969.764559                    295168  [2306kb]    imul64                   no        Lasse Hansen                                 https://www.chessprogramming.org/Magic_Bitboards#Plain
Black Magic BB - Fixed shift       1196.554670                   88891   [694kb]     imul64                   no        Onno Garms and Volker Annuss                 https://www.chessprogramming.org/Magic_Bitboards#Fixed_shift_Fancy
Pext constexpr                     1706.739488                   107904  [843kb]     pext_u64                 yes       Zach Wegner                                  https://www.chessprogramming.org/BMI2#PEXTBitboards
HyperCube                          324.899154                    107680  [841kb]     none                     yes       Daniel Inführ (dangi12012)                   http://www.talkchess.com/forum3/viewtopic.php?f=7&t=79004&p=916723&hilit=hypercube#p916723
New ideas are fast to generate but not so easy to implement and release. But after 2 years I can say that I understand all algorithms above and that was (and is) a fascinating journey for me!
Worlds-fastest-Bitboard-Chess-Movegenerator
Daniel Inführ - Software Developer
Top
User avatar
lithander
Posts: 915
Joined: Sun Dec 27, 2020 2:40 am
Location: Bremen, Germany
Full name: Thomas Jahn

Re: Comparison of all known Sliding lookup algorithms

Post by lithander »

My first impulse was to check the calendar again because it seems like a 1st April joke. Why would you use machine learning for something where for each input there's exactly one right answer and (as you yourself have gathered here) several fast and correct algorithmic implementations to get from input to output already exist?

Neural networks are exciting, I get it. But why are you not trying to apply machine learning approaches to topics where there's potential benefit to real chess engines? Like the evaluation or move ordering or maybe even reductions and extensions? In all these situations all bits of gamestate are potentially relevant and exactly in what way the input correlates with the output is hard to define so it seems like a more promising area to try and apply machine learning approaches.

...but maybe I just don't get what the real world usecase for Binary Neural Networks Sliding Inference is. Is there one?
Minimal Chess (simple, open source, C#) - Youtube & Github
Leorik (competitive, in active development, C#) - Github & Lichess
Top
User avatar
j.t.
Posts: 263
Joined: Wed Jun 16, 2021 2:08 am
Location: Berlin
Full name: Jost Triller

Re: Comparison of all known Sliding lookup algorithms

Post by j.t. »

lithander wrote: ↑Wed Feb 09, 2022 1:48 pm ...but maybe I just don't get what the real world usecase for Binary Neural Networks Sliding Inference is. Is there one?
I could imagine that neural network move generation (probably not exactly this one) could be used to make engines capable of making more human blunders.

Interestingly, there exists a tree search approach, where the "move generation" is learned by a neural network.
Top
smatovic
Posts: 3223
Joined: Wed Mar 10, 2010 10:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic

Re: Comparison of all known Sliding lookup algorithms

Post by smatovic »

lithander wrote: ↑Wed Feb 09, 2022 1:48 pm ...
...but maybe I just don't get what the real world usecase for Binary Neural Networks Sliding Inference is. Is there one?
Daniel intends to use the TensorCores (matrix-multiply-accumulate units) of Nvidia RTX gpus for move generation.

--
Srdja
Top

Return to “Computer Chess Club: Programming and Technical Discussions”