Compare your engine's performance: Corrections +++

[Ras]

You should not be doing move sorting at all, most of that will be wasted effort due to cutoffs.

I get 50% cut-offs on the first move so that my hybrid algo will have only looped once through the movelist and swapped two entries. Sorting the remaining movelist with Shellsort if the first move is no cut-off amounts to 5% of the total runtime according to my profiling. So, no big potential, but it guards against pathological behaviour.

[JohnWoe]

Some people are skilled taking somebody's code and improving/speeding up it. But unable to come up with something from nothing in the first place.
In C++ all statistical analysers are really bad. Which is sad. For example cppcheck can't handle C++17. Maybe there are some good ones I've missed. In C there's more due to OS legacy. But C is not good. Too verbose.

Speed can overcome lots of smartness. Deep Blue was awful but it was ripping the game tree apart at 1G NPS,

[klx]

I get 50% cut-offs on the first move so that my hybrid algo will have only looped once through the movelist and swapped two entries. Sorting the remaining movelist with Shellsort if the first move is no cut-off amounts to 5% of the total runtime according to my profiling. So, no big potential, but it guards against pathological behaviour.

5% is pretty substantial IMO if that's just for the sorting itself (not including move generation and prioritization). Now imagine if you sorted that through linq sort... Have you tried lazy sorting? The idea is only sort as many moves as you need. If there's a cut-off after move 3, you only sort 3 moves, etc. (This is what I mean by not doing move sorting.)

[lithander]

linq is bad for sorting

This sentence alone tells me so much. First, while C# is not terrible, I'd expect a ~2x slowdown over a language like C++. Second, linq is not something I'd ever want to see in performance critical code due to lack of control of allocations and work done. Third, sorting? For moves? You should not be doing move sorting at all, most of that will be wasted effort due to cutoffs. While performance is not a goal of yours I hope this illustrates the potential.

Who says the code is performance critical? I'd argue the engines of beginners and intermediate chess programmers lose more ELO from a lack of features and from having bugs then from lack of micro optimizations.

If you can sort your moves with one line of code (with LINQ) you save massive amounts of time (not only raw development time but also the time testing different possible variants of how exactly you want to implement your custom, optimized sorting) that you can invest in features that are are actually interesting (sorting algorithms... *yawn*) and your code is less likely to have bugs because there's just less code in the first place. And what you have is simpler to understand.

You can trust the .Net framework to have working, bugfree solutions. Do you really trust yourself to always write bugfree, faster alternatives? Do you have the time? Do you want to spend it on *that*?

[Ras]

5% is pretty substantial IMO if that's just for the sorting itself

First, that is an upper bound that could be gained, assuming that always "swapping the next to the top" would cost no computing time at all. Second, 5% translates into roughly 4 Elo, that's measurement noise. Third, it does guard against pathological O(n²) cases, similarly to how IID mainly reduces the amount of worst cases.

Have you tried lazy sorting?

I don't even generate the moves at all if I have a hash move, and in that case, I get a 90% cut-off rate. But otherwise, sorting after trying the first move is a sort of lazy sorting.

If there's a cut-off after move 3, you only sort 3 moves, etc.

If I knew in advance that I'd have a cut-off after the third move, I would have tried that move first, obviously.

[Chessnut1071]

Some people are skilled taking somebody's code and improving/speeding up it. But unable to come up with something from nothing in the first place.
In C++ all statistical analysers are really bad. Which is sad. For example cppcheck can't handle C++17. Maybe there are some good ones I've missed. In C there's more due to OS legacy. But C is not good. Too verbose.

Speed can overcome lots of smartness. Deep Blue was awful but it was ripping the game tree apart at 1G NPS,

"Speed can overcome lots of smartness. Deep Blue was awful but it was ripping the game tree apart at 1G NPS,"

The author of Deep Blue was a Korean EE and Comp Sci major at CMU. He couldn't take Hans Berliner, the real genius and invertor of Deep Thought. The "Korean Kid" developed his own chess chip and achieved tremendous speed. He played around 1400-1450 OTD, not even an average tournament player. Hans was an IM, rated about 2450, about the same as Deep Thought. Deep Blue, before IBM bought it, had almost no chess smarts, just raw speed. It was a shame, an IM losing to an 1450 player only because of speed. He never even invited Hans to make suggestions. The two together could have really made a difference. Most of Deep Blue was database tables, very little in the way of tactical searching. This implies deep is better than a broad search. I get it.

The question I'm interested in is there a way to optimize the evaluation function to overcome speed optimization. I developed a modified Hooke-Jeeves optimization program to test that question within a few specific defenses. So far, I've had mixed results; however, I really can't judge how well it does because I have a very weak end game database, and even a weak engine can destroy my engine in an end game battle. I just wish I had Hans here now, because I don't think you can beat speed with smarter chess.

[emadsen]

This thread is a hot mess. I'll offer my advice:

1. Optimizing an engine for solving mate-in-x puzzles (or scoring well in any test suite: mate, best move, avoid move) or for playing games are two separate objectives, requiring separate algorithms. Be clear about your aims.
2. 23,500 NPS is very slow. It's impossible for me to diagnose why without the source code. But if I had to guess, I'd say memory allocation inside search causing GC thrashing.
3. What in the hell are people who haven't written an engine from scratch doing commenting on performance issues? Engineering is required. Not observation & aspiration.
4. Move sorting is critical for improving engine strength in timed games. LMR reduces later quiet moves more than earlier quiet moves. They must be sorted or "later" has no meaning. "Later" should correlate with "less likely to raise alpha or cause a beta cutoff." Though, are you optimizing for strength in timed games? See #1.
5. Do not sort moves via LINQ. LINQ allocates a delegate and enumerator each invocation. Kills perf. Use the .NET Base Class Library's Array.Sort method with a custom IComparer or write your own Sort method. Of course, allocate the IComparer once, at engine startup, not in each invocation of the Sort method.

See one and two for more details re: C# performance and over-reliance on code profilers.

MadChess doesn't find mate in 7. Too much pruning. It finds mate in 8.

26,017,644 nodes
5,518,216 evals
6.977 seconds = 3,728,994 NPS
C#
AMD Ryzen Threadripper 1950X (engine is single-threaded)

Code: Select all

position fen 5k2/ppp2r1p/2p2ppP/8/2Q5/2P1bN2/PP4P1/1K1R4 w - -
debug on
go infinite
info depth 1 seldepth 4 time 36 nodes 270 score cp 1531 nps 7404 pv d1d8
info depth 2 seldepth 6 time 38 nodes 381 score cp 1531 nps 10026 pv d1d8 f8e7
info depth 3 seldepth 9 time 40 nodes 1861 score cp 1657 nps 46031 pv d1d8 f8e7 d8d7
info depth 4 seldepth 9 time 41 nodes 2436 score cp 1657 nps 58905 pv d1d8 f8e7 d8d7 e7d7
info depth 5 seldepth 10 time 42 nodes 3754 score cp 1657 nps 88395 pv d1d8 f8e7 d8d7 e7d7 c4f7
info depth 6 seldepth 10 time 44 nodes 5260 score cp 1657 nps 118847 pv d1d8 f8e7 d8d7 e7d7 c4f7 d7d6
info depth 7 seldepth 12 time 46 nodes 8452 score cp 1657 nps 182082 pv d1d8 f8e7 d8d7 e7d7 c4f7 d7d6 f7h7
info depth 8 seldepth 12 time 49 nodes 12421 score cp 1741 nps 253648 pv d1d8 f8e7 d8d7 e7d7 c4f7 d7d6 f7h7 g6g5
info depth 9 seldepth 16 time 52 nodes 17837 score cp 1919 nps 340362 pv d1d8 f8e7 d8d7 e7d7 c4f7 d7d6 f7h7 e3h6 h7h6
info depth 10 seldepth 16 time 66 nodes 40328 score cp 2191 nps 610655 pv d1d8 f8e7 c4d3 f6f5 d8d7 e7e8 d7f7 e8f7 d3e3 f7f6
info depth 11 seldepth 16 time 85 nodes 70749 score cp 2420 nps 836662 pv d1d8 f8e7 c4d3 f6f5 f3e5 e3h6 d3d7 e7f6 e5f7 h6d2 d7c7
info depth 12 seldepth 16 time 102 nodes 99022 score cp 2296 nps 971977 pv d1d8 f8e7 c4d3 f6f5 f3e5 e3h6 d3d7 e7f6 e5f7 h6f4 d7d4 f6f7
info depth 13 seldepth 20 time 198 nodes 265805 score cp 2350 nps 1340616 pv d1d8 f8e7 c4d3 f6f5 f3e5 e3h6 d8d7 e7e6 e5f7 h6f4 f7d8 e6f6 d7h7
info depth 14 seldepth 18 time 238 nodes 334789 score cp 2408 nps 1405143 pv d1d8 f8e7 c4d3 f6f5 f3e5 e3h6 d8d7 e7e6 e5f7 h6f4 f7d8 e6f6 d7h7 f6g5
info depth 15 seldepth 22 time 474 nodes 1006096 score cp 2668 nps 2123031 pv d1d8 f8e7 c4d3 f6f5 f3e5 e3b6 d3d7 e7f6 e5f7 g6g5 d8e8 f6g6 e8g8 g6h5 d7f5
info depth 16 seldepth 22 time 618 nodes 1584418 score cp 2774 nps 2565320 pv d1d8 f8e7 c4d3 f6f5 f3e5 e3b6 d3d7 e7f6 e5f7 g6g5 d8g8 g5g4 f7g5 f6e5 d7e7 e5f4
info depth 17 seldepth 25 time 1017 nodes 3158795 score cp 3107 nps 3106255 pv d1d8 f8e7 c4d3 f6f5 d8g8 e3c5 d3d8 e7e6 f3g5 e6e5 g5f7 e5e6 f7g5 e6e5 d8e8 e5f4 g5e6
info depth 18 seldepth 24 time 1372 nodes 4585188 score cp 3025 nps 3341895 pv d1d8 f8e7 c4d3 f6f5 d8g8 e3c5 d3e2 e7d7 e2e8 d7d6 e8f7 c5b6 f7h7 d6d5 h7g6 f5f4 g6f5 d5c4
info depth 19 seldepth 26 time 1753 nodes 6104415 score cp 3223 nps 3482077 pv d1d8 f8e7 c4d3 f6f5 d8g8 e3c5 d3e2 e7d7 e2e8 d7d6 e8f7 c5f2 f7h7 a7a5 h7g6 d6c5 g6f5 c5b6 h6h7
info depth 20 seldepth 26 time 6977 nodes 26017644 score mate 8 nps 3728994 pv c4e6 e3h6 f3e5 f6e5 d1d8 f8g7 e6e5 f7f6 d8d7 g7f8 e5f6 f8g8 d7d8 h6f8 d8f8
info hashfull 206 currmove c4e2 currmovenumber 46
info string Cache Hit = 27.40% Score Cutoff = 31.92% Best Move Hit = 24.12% Invalid Best Moves = 0
info string Null Move Cutoffs = 94.84% Beta Cutoff Move Number = 1.52 Beta Cutoff First Move =  89.04%
info string Evals = 5,518,216

[klx]

What in the hell are people who haven't written an engine from scratch doing commenting on performance issues? Engineering is required. Not observation & aspiration.

What in the h... are people who never played football doing coaching football? And I think you agreed with / repeated what I already wrote btw, so I find this statement quite odd and unhumble.

Move sorting is critical for improving engine strength in timed games. LMR reduces later quiet moves more than earlier quiet moves. They must be sorted or "later" has no meaning. "Later" should correlate with "less likely to raise alpha or cause a beta cutoff." Though, are you optimizing for strength in timed games? See #1.

Move sorting is also critical for speeding up mate finding since it increases the chance of early cut-offs thus reduce the total number of nodes.

Do not sort moves via LINQ. LINQ allocates a delegate and enumerator each invocation. Kills perf. Use the .NET Base Class Library's Array.Sort method with a custom IComparer or write your own Sort method.

Again, I'd recommend not sorting all moves at all. The way lazy move sorting works is sort one move at a time. Think selection sort.

If I knew in advance that I'd have a cut-off after the third move, I would have tried that move first, obviously.

The "lazy" part of sorting refers specifically to the fact that you don't know that in advance. See above.

5% translates into roughly 4 Elo, that's measurement noise.

5% would save the OP half an hour. Sure, by itself it might not make a huge difference, but a few percent here and there adds up. If you want to make the fastest or strongest possible engine you can't have that attitude IMO when it comes to such easy "wins".

[amanjpro]

What in the hell are people who haven't written an engine from scratch doing commenting on performance issues? Engineering is required. Not observation & aspiration.

What in the h... are people who never played football doing coaching football? And I think you agreed with / repeated what I already wrote btw, so I find this statement quite odd and unhumble.

Move sorting is critical for improving engine strength in timed games. LMR reduces later quiet moves more than earlier quiet moves. They must be sorted or "later" has no meaning. "Later" should correlate with "less likely to raise alpha or cause a beta cutoff." Though, are you optimizing for strength in timed games? See #1.

Move sorting is also critical for speeding up mate finding since it increases the chance of early cut-offs thus reduce the total number of nodes.

Do not sort moves via LINQ. LINQ allocates a delegate and enumerator each invocation. Kills perf. Use the .NET Base Class Library's Array.Sort method with a custom IComparer or write your own Sort method.

Again, I'd recommend not sorting all moves at all. The way lazy move sorting works is sort one move at a time. Think selection sort.

If I knew in advance that I'd have a cut-off after the third move, I would have tried that move first, obviously.

The "lazy" part of sorting refers specifically to the fact that you don't know that in advance. See above.

5% translates into roughly 4 Elo, that's measurement noise.

5% would save the OP half an hour. Sure, by itself it might not make a huge difference, but a few percent here and there adds up. If you want to make the fastest or strongest possible engine you can't have that attitude IMO when it comes to such easy "wins".

Just so you know, stockfish does something similar to what Ras is doing

I'm doing what you suggest, and guess what? When I profiled the code the lazy sort was the hottest path... You really need to do some homework before writing your claims...

[lithander]

If you want to make the fastest or strongest possible engine you can't have that attitude IMO when it comes to such easy "wins".

I think we can all agree on that: When you want to make the fastest or strongest possible engine every little bit counts.*

But how do you know 5% is too much and can be significantly improved? How can you know just exactly what technique would be best? That you claim to know these things better then the actual authors of the engines is what rubs people the wrong way, here.

*) But not everyone is delusional enough to believe they can make the fastest strongest possible engine all by themselves.