Writing the fastest move generator. Up to 4BNodes/s

[chessbit]

Hey chess community. I wanted to share my accomplishment.

Inspired by a post I saw a while ago (reddit thread), I decided to write my own move generator and try to beat it. The goal was to write a single threaded move generator, without hashing or other tools that may improve speed. Just going through every position.

I took some inspiration from Gigantuas' source code, as I had no idea about bmi instructions and templates before. So this was of immense help to achieve my goal! But because I had already written most of the code and found all ways to optimize the logic, refactoring my code with these instructions/templates immediately reached the target.

Running with my AMD Ryzen 7 9800x3d, my engine is able to calculate some positions at more than 4BNodes/s, while Gigantua (compiled with the same compiler and same specs) maxes out at ~3.1BNodes/s

Overall, my engine is about 25% faster, which is as far as I know the fastest move generator.

Another cool thing is that unlike usual perft engines, mine can actually make/unmake moves (with a limited performance impact), so it can be plugged to search the best moves for an actual chess engine! Unfortunately my chess knowledge is too bad to undertake this kind of project. I don't think I would be able to do more than 1500 elo.

I took the liberty of using the same benchmarking to have an exact comparison. Here are the results:

Mine:


Gigantua:


Happy to answer questions as well

[ZirconiumX]

mine can actually make/unmake moves

I think the community has settled on copy/make being superior to make/unmake, especially in light of NNUE updates. Modern SIMD makes copying even large boards cheap.

[chessbit]

mine can actually make/unmake moves

I think the community has settled on copy/make being superior to make/unmake, especially in light of NNUE updates. Modern SIMD makes copying even large boards cheap.

Not sure what you mean by "copy/make", but make/unmake is literally just incrementing/decrementing in a moves array (at least in my engine), I fail to see what can be cheaper than that.

[Steve Maughan]

That's awesome. The author of Gargantuan created some nice blog posts about his approach and what he learnt. Are you able to do something similar?

Is the source code available?

— Steve

[Steve Maughan]

<snip>Unfortunately my chess knowledge is too bad to undertake this kind of project. I don't think I would be able to do more than 1500 elo.<snip>

A chess engine with a basic search at this speed (I'm assuming it would slow down to <100 mnps) with Pesto piece-square evaluation would be easily north of 2300 ELO, and more likely closer to 2600 ELO.

— Steve

[chessbit]

That's awesome. The author of Gargantuan created some nice blog posts about his approach and what he learnt. Are you able to do something similar?

Is the source code available?

— Steve

Thanks. I will publish the source code once I'm done, as I'm still trying to optimize a little bit I will write a little explanation of the process then.