Advice on optimizing my move generation

[Ras]

UCI has tons of overhead too. You are starting from "tabula rasa" every move and playing a long list of moves to empty board...

This doesn't take any measurable amount of time. Even my slow move generator plus move/undo plus legality verification gets to 20M NPS in perft (no TT, no bulk counting). If a game is a 100 moves in, that's 200 plies, and we're talking about 10 microseconds. That's not "tons of overhead".

[algerbrex]

I am happy to say that after running my move generator through a perft suite of 30-40 different positions at depth=5, it seems to be working correctly. My issue now is the speed.

Hi Christian. Welcome to the chess programming community. Congrats on writing a correct move generator. That's a big milestone! Are you sure it's correct? Here's a good perft test suite that has many corner cases.

In my opinion, you should focus on perft correctness and and search speed. Perft speed is not important for the primary purposes of chess engines: playing games against other engines and aiding us humans in analyzing games. Perft doesn't do any of the "bookkeeping" necessary for good move ordering, which is critical for engine strength. So fast perft doesn't imply strong engine.

I go further than most, in that I've designed my perft method to execute the same call stack as the search method does. So correct perft counts give me confidence search is examining all the moves it should (exempting pruning).

Others have given good advice in previous comments, especially cautioning against allocating memory during search. That kills performance, especially in a garbage collected language like Go. Allocate all data structures when the engine starts. Use statically-sized arrays, not dynamically sized lists (for the same reason, to avoid alloc and GC). Iterate over arrays using for loops, not foreach (for the same reason, avoiding alloc and GC). In C# enumerators alloc. Not sure about Go. Avoid other language features during search that harm performance: no floating point math (instead calc at engine start and store ints in arrays for lookup during search, eval should be pure int math), no lambda methods (they allocate a delegate, at least in C#), etc.

Hi, and thank you for all the advice. I think for now I'll do what other's such as yourself are suggesting and focus on perft correctness and fast search time using alpha-beta pruning, transposition tables, etc.

[algerbrex]

My goal ELO would be anywhere between 2000-1500 ELO, so if my move generator will get me there, I can work with that!

An elo below 2000 doesn't require a good move generator at all. I think with a descent evaluation (material and psqt) and a bug-free search, you can definitely get to 1800 with a, relatively, slow move generator.
Additionally, some tricks can be done in search to completely avoid generating some of the moves. Since captures are usually better than quiet moves, you can start by generating the captures and trying them. If they are not good enough, you can then generate the quiets, but if the captures are good enough, you saved time by not generating the rest of the moves. This is called staged move generation. Once you're at 2000, you can look into that and move generator speedup

Wow, that's great to hear! I have been a little frustrated because I felt that my move generator's speed would be an indication of my chess engine's rating, but I'm really starting to realize that's not the case at all. I think, since I've done all of this work to make a good move generator, I'll focus my efforts now on implementing a good search and evaluation phase! Thanks!

[spirch]

Perft to me is pointless. Mayhem has no perft and never will. Havoc has it but it's probably going to removed. I can't even remember the time Mayhem had mgen bugs.

perft is the same thing as what is called integration testing, if you have some perft that get automatically run when you "commit" your code to any repository, you can catch if any changes made broke or made any major slowdown your logic / code. that way you notice it now and not few weeks / months when you are doing something and notice "something seem wrong here..." and start losing hours debugging everything and remembering what changed since "this seem correct now"

[spirch]

My issue now is the speed. I'd like to test up to at least depth=6, but that just isn't feasible right now given how slow my move generator is. For example, my engine takes almost two minutes just to go up to depth=4 in the kiwipete position:

keyword: profiling

find a profiler that work for you, run it, look at the result, find bottleneck, fix, re-run

you will eventually run out of code that are slow and get into design issue and this is where the fun start, refactoring

[spirch]

So don't be disappointed about your current performance. I just ran Myrddin on the kiwipete position, perft 6, WITH bulk counting (but no hash), and it took 3 minutes.

can you confirm this is the proper FEN and proper result?

(in my case I do not do bulk counting, every move are done and undone, and I have no hash done)

Code: Select all

  A B C D E F G H
1 R ■ ■ ■ K ■ ■ R  Kind of perft: Full Perft, doing all move/undo to the last depth
2 P P P B B P P P  Started 6 depths at 2021-06-12 15:12:15 finished at 2021-06-12 15:17:33
3 ■ ■ N ■ ■ Q ■ p  FEN: r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -
4 ■ p ■ ■ P ■ ■ ■
5 ■ ■ ■ P N ■ ■ ■  Expected Moves   : ?????????
6 b n ■ ■ p n p ■  Total Moves Done : 8,031,647,685    
7 p ■ p p q p b ■  Time Taken       : 317,958ms
8 r ■ ■ ■ k ■ ■ r  Moves per second : 25,260,089

if I turn on multi thread on my engine, I get this

Code: Select all

Time Taken       : 23,129ms
Moves per second : 347,254,428

[JohnWoe]

UCI has tons of overhead too. You are starting from "tabula rasa" every move and playing a long list of moves to empty board...

This doesn't take any measurable amount of time. Even my slow move generator plus move/undo plus legality verification gets to 20M NPS in perft (no TT, no bulk counting). If a game is a 100 moves in, that's 200 plies, and we're talking about 10 microseconds. That's not "tons of overhead".

It just doesn't feel like the right design to parse long movelists every move. Elowise that's nickel-and-dimeng sure

Perft to me is pointless. Mayhem has no perft and never will. Havoc has it but it's probably going to removed. I can't even remember the time Mayhem had mgen bugs.

perft is the same thing as what is called integration testing, if you have some perft that get automatically run when you "commit" your code to any repository, you can catch if any changes made broke or made any major slowdown your logic / code. that way you notice it now and not few weeks / months when you are doing something and notice "something seem wrong here..." and start losing hours debugging everything and remembering what changed since "this seem correct now"

I'm so lazy I just type "cat games.pgn | grep illegal" to catch illegal moves. For 1M games or smt.
And besides that I don't write bugs. I don't touch my move generator at all. If I touch it's just some trivial speed up.
I don't write asserts() I just write clean bug free code.

[JVMerlino]

can you confirm this is the proper FEN and proper result?

(in my case I do not do bulk counting, every move are done and undone, and I have no hash done)

Code: Select all

  A B C D E F G H
1 R ■ ■ ■ K ■ ■ R  Kind of perft: Full Perft, doing all move/undo to the last depth
2 P P P B B P P P  Started 6 depths at 2021-06-12 15:12:15 finished at 2021-06-12 15:17:33
3 ■ ■ N ■ ■ Q ■ p  FEN: r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -
4 ■ p ■ ■ P ■ ■ ■
5 ■ ■ ■ P N ■ ■ ■  Expected Moves   : ?????????
6 b n ■ ■ p n p ■  Total Moves Done : 8,031,647,685    
7 p ■ p p q p b ■  Time Taken       : 317,958ms
8 r ■ ■ ■ k ■ ■ r  Moves per second : 25,260,089

That is the number I get. My perft also does full make/unmake.

[spirch]

I don't write asserts() I just write clean bug free code.

That is the number I get. My perft also does full make/unmake.

I really need to think about switching from 0x88 to bitboard at some point, i just need to find the will

I just tried with 0.87 and i got ~170seconds, with 0.85 (i believe this was your last with 0x88) I got ~440seconds but a -558286907 move count

[JVMerlino]

I really need to think about switching from 0x88 to bitboard at some point, i just need to find the will

I just tried with 0.87 and i got ~170seconds, with 0.85 (i believe this was your last with 0x88) I got ~440seconds but a -558286907 move count

It was a pretty big undertaking, and yes, you're correct that 0.85 was the last 0x88 version. But converting to bitboard (according to CCRL) got +140 ELO.

Kind of surprised anybody (other than ratings list folk) bother to download my engine at all. But not surprised the old version gave that number. I didn't have a 64-bit computer back then and was too lazy to do perft tests that would go past 32 bits. Hell, the biggest number in my perft test is still <1B nodes.