Sapeli 1.0 - New chess engine

Discussion of anything and everything relating to chess playing software and machines.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Ras
Posts: 1424
Joined: Tue Aug 30, 2016 6:19 pm
Full name: Rasmus Althoff
Contact:

Re: Sapeli 1.0 - New chess engine

Post by Ras » Fri Apr 24, 2020 9:33 pm

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.
Rasmus Althoff
https://www.ct800.net

brianr
Posts: 443
Joined: Thu Mar 09, 2006 2:01 pm

Re: Sapeli 1.0 - New chess engine

Post by brianr » Fri Apr 24, 2020 9:48 pm

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
Posts: 1424
Joined: Tue Aug 30, 2016 6:19 pm
Full name: Rasmus Althoff
Contact:

Re: Sapeli 1.0 - New chess engine

Post by Ras » Fri Apr 24, 2020 10:02 pm

brianr wrote:
Fri Apr 24, 2020 9:48 pm
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.
Rasmus Althoff
https://www.ct800.net

JohnWoe
Posts: 189
Joined: Sat Mar 02, 2013 10:31 pm

Re: Sapeli 1.0 - New chess engine

Post by JohnWoe » Fri Apr 24, 2020 10:32 pm

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". :P

brianr
Posts: 443
Joined: Thu Mar 09, 2006 2:01 pm

Re: Sapeli 1.0 - New chess engine

Post by brianr » Sun Apr 26, 2020 8:25 pm

Ras wrote:
Fri Apr 24, 2020 10:02 pm
brianr wrote:
Fri Apr 24, 2020 9:48 pm
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
Posts: 1424
Joined: Tue Aug 30, 2016 6:19 pm
Full name: Rasmus Althoff
Contact:

Re: Sapeli 1.0 - New chess engine

Post by Ras » Sun Apr 26, 2020 8:51 pm

brianr wrote:
Sun Apr 26, 2020 8:25 pm
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.
Rasmus Althoff
https://www.ct800.net

User avatar
hgm
Posts: 24737
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Sapeli 1.0 - New chess engine

Post by hgm » Sun Apr 26, 2020 9:24 pm

brianr wrote:
Sun Apr 26, 2020 8:25 pm
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
Posts: 443
Joined: Thu Mar 09, 2006 2:01 pm

Re: Sapeli 1.0 - New chess engine

Post by brianr » Sun Apr 26, 2020 11:04 pm

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.

Post Reply