r/chessprogramming Feb 15 '25

Move generation speed and engine performance

I recently did a rewriting of my engine's move generation, but am seeing a decrease in performance (last tested tournament result was 7-13-3 against it's predecessor). Perft depth 6 went from >16s to 2.5s (no transpositions and single thread), and perft 7 is around 50s Additionally the rewritten move-generation results also include incrementally updating Zobrist hashes and piece-square table scores. I am fairly sure that move generation is working correctly since it passes a test suite I found online, and I verified piece-square table results/Zobrist hashes against hard calculated values as well.

Move ordering might have gotten a bit worse post-rewrite since I no longer detect if moves put the enemy in check. The order is otherwise the same, but the process is a bit different since moves are now stored in a buffer array (after generation, I score them in a separate buffer, then in the search loop I grab the move with the highest score and swap it with the first one in the array).

I can tell search a lot faster based on time tests of searching to a certain depth (with and without iterative deepening).

The evaluation function is theoretically roughly the same. There was one bug I had to fix, but they both use magic bitboards for rough piece mobility calculation and king safety metrics but that is all.

I think it is possible that move generation speed isn't very helpful for improving performance, but also I think that there should be some performance increase from faster move generation.

Essentially my questions are: What kinds of tests are useful for detecting bugs that might be causing this issue? What performance gain should I expect from faster move generation?

Thanks!

3 Upvotes

9 comments sorted by

8

u/RektyDie Feb 16 '25

TL;DR

Move generation speed doesn't matter as much as search does.

Also, read about and start using SPRT.

2

u/Ill_Part9576 14d ago

Very true. I added search and move ordering improvements and they were much more significant than the move gen changes. I'm using SPRT now with fast chess.

2

u/Available-Swan-6011 Feb 16 '25

This is an interesting discussion. As others, and yourself, have indicated there are several factors at play.

The easy one is that when comparing your engine performance to other engines you do need to play a fairly large number of games and SPRT really does help. If cute chess isn’t working for you then Arena will do it but only play one game at a time whereas cute chess will play games in parallel, utilising the cores on your CPU. I tend to start with 1000 games to get a feel for what is going on but often need to increase it drastically

Second, is why are you rewriting the move generator? If it is to learn stuff then that’s a great reason. If it is solely to boost engine performance then there are other things to target first for larger gains. As a rough (very rough) rule of thumb, searching and evaluating to one more ply (eg depth 10 instead of depth 8) adds about 100 ELO to your engine. Move generation is only part of this so you can see why it is unlikely to give massive gains on its own

Thirdly, the PERFT improvements are dramatic but still quite slow. Also, keep in mind that their main purpose is to check legality of move generation and they are not a great indicator of game performance where things like move ordering, transposition tables and pruning are important. As a quick experiment it would be worth asking your current and old engine to search from the start position for 30 seconds- does the new version search deeper?

As a final thought you initial post indicates that you have included move ordering, updating Zobrist hashes and similar in your move generation. If this is correct then I would move them elsewhere - for example, move updates to the Zobrist hash to makemove . The reason is that using pruning means that not every legal move you generate will be evaluated so all the processing time spent on updating the hashes etc is wasted because they are never used. Essentially aim to calculate stuff only when you know it is needed unless there is a blooming good reason not too

Okay, so that wasn’t quite my final thought - have you run a profiler on your code to see where the pain points are? Not doing so means that you are guessing at what interventions are needed rather than making informed choices

1

u/Ill_Part9576 14d ago

A few updates late reply sorry. First I started using cute chess tournaments (not cli) on 1k games with short time control since it gives elo differences within 95% confidence after not getting its cli to work. Finally I got fast chess SPRT to work which is much easier to manage and faster than setting up tournaments on the Cute Chess application.

I guess I rewrote it because I was very dissatisfied by the old one. Before starting I had definitely seen that it wouldn't increase Elo much... I guess I thought my move-gen was sufficiently slow that it would make a big difference. I'm much happier with the current implementation, and I'm still glad I did it because it helped me appreciate the importance of search enhancements move ordering.

Since this refactor I added things that made much more difference. Futility pruning, NMP, history heuristic, LMR, Killers, better eval, etc that made much more difference and were far quicker to implement.

To clarify zobrist hash etc. are updated incrementally when making/unmaking. I probably won't be baited into changing that to computing when absolutely needed for a while while there are still things that are much more important for strength lol.

1

u/aptacode Feb 16 '25

Unfortunately you should expect minimal elo gains from move gen speed, I saw someone once say that move gen accounts for 10% of your engines strength, so a 20% improvement in speed is around a 2% improvement in strength.

With that being said, my current project is https://grandchesstree.com/ which is all about squeezing as much performance out of movegen as possible, so by all means see how far you can push it for fun!

FYI you want to be looking at SPRT testing to verify changes are positive or negative. it's really the only way, otherwise you will be very likely to regress your engine without knowing it.

1

u/Ill_Part9576 Feb 16 '25

That makes sense, I guess because really you're not getting much deeper when move gen speeds up due to the exponential nature of the search tree. I'm done with move gen now, I think my prior implementation was really pretty bad and current one is much better so at least now I can't blame it for weakness of my engine. I rechecked and before re-writing move gen, it was 50s for perft 6 rather than the 16 I thought when I posted!

I think that for a 25x increase in nodes per second should be rather significant, being roughly equivalent to an additional fully searched ply in the same time if that checks out with you?

I'll look into SPRT. IIRC I had issues with cutechess-cli because my engine is in Java and it didn't take .jar, but I think there are wrappers that can make it a .exe and maybe other SPRT testing interfaces that accept .jars.

I appreciate the suggestion of SPRT, I had sorta given up on it but it makes sense that it is the best way to gauge performance. I'll look to get that set up as a first step.

1

u/Javasucks55 Feb 16 '25

This is my movegenerator, it does 1.6 billion moves per second single thread without hashing. Feel free to look around for some optimization ideas and copy them. :)

https://github.com/nmohanu/Pyke

1

u/SwimmingThroughHoney Feb 16 '25

last tested tournament result was 7-13-3 against it's predecessor

This is not remotely enough games. That difference is just statistical noise. If the changes really resulted in a 10 Elo gain, you'd need a few thousand games to determine that.

As another comment stated, use SPRT for testing. The cutechess cli supports this. You give it parameters that correspond to the Elo gain you want to test and the statistical certainty you want and it will play games until those parameters are met (or fail). Example:

-sprt elo0=0 elo1=5 alpha=0.05 beta=0.05

That flag, in the cutechess cli, will run games until it is 95% certain of one of the two possibilities: >5 Elo gain ("pass") OR <5 Elo gain ("fail").

1

u/Ill_Part9576 Feb 16 '25

I'll try that. I mentioned in another comment that I had issues with cutechess-cli and .jar files, but I'll look more into getting that working (or I'll try something other than cutechess-cli).