Compare your engine's performance: Corrections +++

[klx]

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...

I took a look at Stockfish source code, and as far as I can tell it's doing exactly what I suggested: lazy selection sort, see this line:

https://github.com/official-stockfish/S ... k.cpp#L136

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?

If 5% of the entire run time is spent on sorting alone -- not move gen, not scoring, just pure sort -- then in my experience that doesn't sound right. Have you checked how much it takes in your engine? In my post I kindly suggested trying lazy sort. If implemented right I think that would benefit here.

[amanjpro]

I took a look at Stockfish source code, and as far as I can tell it's doing exactly what I suggested: lazy selection sort, see this line:

https://github.com/official-stockfish/S ... k.cpp#L136

You need to look further, https://github.com/official-stockfish/S ... k.cpp#L205

Now go ahead, and create a topic about Emanuel's partial insertion sort

[klx]

You need to look further, https://github.com/official-stockfish/S ... k.cpp#L205

I see, that's a peculiar choice, there may be a reason for that which I don't know, perhaps some Stockfish auther could tell us, eg:

- Perhaps they need the full list sorted anyway for some reason
- Perhaps the input is already almost sorted, in which case insertion sort is very fast
- Perhaps they profiled this and determined that the sort is so cheap (not 5%) that it's not worth the complication to make it "lazy"

Or, perhaps this is a potential for future optimization. So I looked at your code and you are doing exactly what I'm suggesting. If you don't mind, it'd be interesting if you could profile that section and let us know:

- How much time (in %) is spent in the selection sort itself (for loop and swap essentially)
- If you change it to sort all moves, then how much time is spent?

[j.t.]

...

You seem to be quite interested in chess engines, and by your comments I assume you already know how to code. I can really recommend trying to write an engine, it is really fun and rewarding (arguably the beginning of writing an engine is more fun than grinding Elo point from 2700 to 2800. At this point, I think it's a (tolerable) addiction for me). Take your favorite programming language, or even better a programming language that you want to learn (Rust, Nim, Zig, V, Objective-C) and start programming!

(I am just kidding, don't try doing anything with Objective-C.)

I think there are currently no chess engines written in Zig or V, so maybe this could be something new. I already know a good name for a chess engine in Zig: Zigzwang

[Ras]

Perhaps they profiled this and determined that the sort is so cheap (not 5%) that it's not worth the complication to make it "lazy"

Actually, I did give it a shoot-out, i.e. a selection sort vs. shellsort after the first move. The selection sort lost a few Elo, as well as being inferior in terms of time to depth, nodes searched to depth, and even NPS. That may be due to worst case O(n²) vs. O(n log n), or because the unstability of the shellsort is actually beneficical, but it is what it is for my engine.

[hgm]

My favorite methods for sorting are all O(n). This works by mapping all possible sort keys to bits in a word in the desired order, set the bits for the moves that are present, and then use bit extraction (BSF) to extract the moves.

[lithander]

My favorite methods for sorting are all O(n). This works by mapping all possible sort keys to bits in a word in the desired order, set the bits for the moves that are present, and then use bit extraction (BSF) to extract the moves.

I don't understand this. BSF gives you the index of the least significant bit? The words are probably 64bit integer? But how does that help with extracting the right move from a list of moves?

[klx]

My favorite methods for sorting are all O(n). This works by mapping all possible sort keys to bits in a word in the desired order, set the bits for the moves that are present, and then use bit extraction (BSF) to extract the moves.

I don't understand this. BSF gives you the index of the least significant bit? The words are probably 64bit integer? But how does that help with extracting the right move from a list of moves?

You just need a word of sufficient size.

[emadsen]

My favorite methods for sorting are all O(n). This works by mapping all possible sort keys to bits in a word in the desired order, set the bits for the moves that are present, and then use bit extraction (BSF) to extract the moves.

I haven't tried that in my chess engine. But I did it here: Programming Pearls : Sorting Phone Numbers.

Well, I didn't do it. I implemented an idea Jon Bentley described in Programming Pearls. The same idea you describe above.

[klx]

I haven't tried that in my chess engine. But I did it here: Programming Pearls : Sorting Phone Numbers.

For anyone reading, that's a pretty inefficient implementation. It probably doesn't matter here since the runtime is likely dominated by the disk writes, but for the sort itself a much faster implementation would use UInt64 + BLSR + TZCNT, and of course concurrency.