Sapeli 1.0 - New chess engine

[Ras]

How much time do you spend in sorting routines? I suspect that might be a target for some optimisation. I pick the first move with linear search and swap it to top, and only if that doesn't already give a beta cut-off, I sort the remaining list using Shellsort.

[brianr]

You can search for old posts about this, but the general thinking was that "fancy" sorting does not pay as so much of the tree is pruned in the first place, and then the few times sorting is done, the number of moves is too small to offset the overhead of setting up the "smart" sort routines. It might be difficult to even measure differences.

[Ras]

the general thinking was that "fancy" sorting does not pay as so much of the tree is pruned in the first place

That holds only for the "pick the best of the remaining list and put it to the current place" sort, but not compared to sorting the whole move list up-front with an n^2 algo.

[JohnWoe]

In Sapeli I use the selection sort algorithm for all the sorting. I guess this is the same algorithm as Stockfish uses (or insertion sort ?).

Root nodes: I sort at depth 0 with Eval + random noise(to avoid repetiting games). Then the best move is put on the top after every iteration.
Search nodes: I sort only killer moves(cut offs), good moves (that raises alpha) and tactical moves ( + castling). Sorting all moves took too much time.
QSearch: I sort all moves. They are very few anyway.

In long matches Sapeli keeps improving score as those goodmoves+killermoves+eval hashtables are filling. So it kinda "learns".

[brianr]

the general thinking was that "fancy" sorting does not pay as so much of the tree is pruned in the first place

That holds only for the "pick the best of the remaining list and put it to the current place" sort, but not compared to sorting the whole move list up-front with an n^2 algo.

All the moves generally are not sorted together. After the one hash move, then come winning captures (very few, maybe plus promotions), then maybe killers (no sorting) , then non-captures, and finally losing captures. 90% of the time the search never gets past a few of these categories such that by the time the non-captures are considered (that have not already been tried as hash or killer moves), the rest can be tried with a selection sort. Others have reported similar findings.

Does something different work better in your engine?

[Ras]

Does something different work better in your engine?

It doesn't have winning/losing captures because there's only MVV-LVA, no SEE. PV move, hash move, null move threat, and quiet killers get a priority adjustment. Quiet moves that aren't killers are ranked by history, and if there is none, just moving forward is rewarded.

I pick the first move using selection sort because that already cuts in many cases. For hash moves, I don't even generate moves until the hash move has failed to cut (but I do verify the hash move for full legality). If it gets past the first move, I sort the rest using Shellsort to avoid n^2 worst case. In QS, I only do that if there is more than one other move left. The time spent in the Shellsort is about 5%.

That's an improvement from the initial stage when I forked the engine from NG-Play and had to eliminate Quicksort to keep recursion to the necessary minimum, and it didn't do the first move selection sort. Initially, I had Mergesort as 1:1 replacement, and I remember 15% spent in sorting.

[hgm]

90% of the time the search never gets past a few of these categories ...

I suppose you mean in 90% of the cut-nodes. Aren't there about as many all-nodes as cut-nodes in a typical alpha-beta tree? In the all-nodes you do have to search all non-captures, and I suppose you do want to sort them by history to determine the amount of LMR you are going to give each one.

The sorting algorithm I prefer just bins the moves by history in a large set of narrow bins (logarithmically spaced) that are unlikely to get more than a single move each. And then run through the bins top-down. This is O(N).

[brianr]

Move ordering and pruning is getting to the heart of the individual ecosystem that each engine has, so what works in one may not help at all in another. I've just never found anything other than scanning the current move list subset and picking the highest value to be any improvement. The first move fail high cut rate is generally about 90% IIRC.

Tinker is not that strong, so FWIW: the hash move is tried first before generating any other moves. Then just captures picking out the winners from the losers. There are only two slots for quiet killer moves. Then the non-captures, etc. This is done in phases and only the moves for the current phase are generated and tried in the tree, except for losing captures that are put in a separate place to be looked at last but generated with all captures.

I haven't looked at Tinker in several years and am now focused on Lc0 net training and testing. Even after more than two years, I still find it simply astounding how well it seems to work. I understand a little bit about it, but frankly it still seems like magic.

[JohnWoe]

Tons of speedups, bug fixes and tuning.
Trying PEXT stuff to get rid of Magic index lookup tables. Tiny speed up in move generation.
Those lookup tables might come back if my old AMD CPU doesn't have the instruction. My Intel CPU has it.

To me this must be the best Sapeli ever.

Sapeli 1.91: https://github.com/SamuraiDangyo/Sapeli ... /tag/v1.91

Very quick and dirty tests:

Code: Select all

Finished game 1010 (Stockfish 12 vs Sapeli 1.91): * {No result}
Score of Sapeli 1.91 vs Stockfish 12: 42 - 921 - 46  [0.064] 1009
Elo difference: -464.82 +/- 39.82

Code: Select all

Finished game 441 (Sapeli 1.91 vs Fairy-Max 5.0b): * {No result}
Score of Sapeli 1.91 vs Fairy-Max 5.0b: 398 - 8 - 34  [0.943] 440
Elo difference: 488.04 +/- 57.72

[Graham Banks]

Tons of speedups, bug fixes and tuning.
Trying PEXT stuff to get rid of Magic index lookup tables. Tiny speed up in move generation.
Those lookup tables might come back if my old AMD CPU doesn't have the instruction. My Intel CPU has it.

To me this must be the best Sapeli ever.

Sapeli 1.91: https://github.com/SamuraiDangyo/Sapeli ... /tag/v1.91

Very quick and dirty tests:

Code: Select all

Finished game 1010 (Stockfish 12 vs Sapeli 1.91): * {No result}
Score of Sapeli 1.91 vs Stockfish 12: 42 - 921 - 46  [0.064] 1009
Elo difference: -464.82 +/- 39.82

Code: Select all

Finished game 441 (Sapeli 1.91 vs Fairy-Max 5.0b): * {No result}
Score of Sapeli 1.91 vs Fairy-Max 5.0b: 398 - 8 - 34  [0.943] 440
Elo difference: 488.04 +/- 57.72

A popcount without bmi2 exe and a non-popcount exe would be useful too.