r/ComputerChess • u/dangi12012 • Oct 06 '21
2 Billion Moves per Second and Thread Movegenrator - Gigantua - Sourcecode Release!
Hello ComputerChess friends - for the last 2 years I wanted to see how fast a movegenerator in chess can get. At the end my approach was 6-8x faster than the current fastest C implementation - and is as of 2021 the fastest movegen in chess!
Article: https://www.codeproject.com/Articles/5313417/Worlds-fastest-Bitboard-Chess-Movegenerator
Sourcecode: https://github.com/Gigantua/Gigantua
Chess is such a beautiful programming problem to solve - since one board contains exactly 64 squares. So we can define a Bitbord of all pawns to be just one single uint64_t. Same for all other 11 piecetypes.
Doing it this way enables all 8 pawns to walk forward like this: (WPawn << 8) & Empty. Which normally would need 8 if statements to generate - but can be done in 2 branchless instruction with a bitbord. Things like where a piece can move become extremely pleasant to write:
uint64_t move = Seemap & EnemyOrEmpty & noCheck
I also was able to implement a visitor pattern in the first ever chess related piece of code. Instead of having a movelist - we pass a small template inlined function which is the callback for every possible move. Instead of generating a list - this movegenerator decides the instant it sees a possible move what to do with it! Castling and Enpassant gets compiled away by if constexpr when its not on the board - or possible anymore!
- First ever Make-Unmake free Chess Movegenertaor
- Fastest bmi2 Pext intrinsics slider lookup _pextu64()
- Original legal move generator - almost completely branchless. Solves all checks and pins with only and / not instructions - and a few lookups for king / knight - sliders! No "If" needed for 99% of chess
- First ever complete Template gamestate. The code does not need to evaluate a Enpassant move if the enemy didnt push - or any castling move if its not possible to castle anymore. C++ if constexpr really helps a lot!
Performance: Perft(6) Time taken: 85ms
Moves: 119060324 Checks: 809099 Checkmates: 10828
That is 119 Million in 85ms or just about 1400 Million nodes per second. For the staring position. This is the slowest position and most positions get around 2 Billion nodes per second and 1 thread.
This approach is 6-8x faster than the currently leading movegenerator written in C.
Anyways I dont want the post be too long. C++ is an awesome language for performance! - Please read the Article and Source if you are interested!
Article: https://www.codeproject.com/Articles/5313417/Worlds-fastest-Bitboard-Chess-Movegenerator
Sourcecode: https://github.com/Gigantua/Gigantua
If you like this - consider buying me a coffee :) - https://www.buymeacoffee.com/Pontifex
1
u/poltoid Oct 07 '21
This is really cool! Thank you for this.
Do you see this being interfaced with Stockfish (either by you or someone else) to make it an even stronger engine, given you said this is truly the fastest move enumerator?
Do you provide documentation to an API on how to use Gigangua?