algerbrex wrote: ↑Fri Aug 19, 2022 2:09 am
lithander wrote: ↑Thu Aug 18, 2022 4:39 pm
The original post resonates strongly with me. I've just had a few weeks vacation that I could have spent on a thousand things but instead I've invested my spare time mostly into making zero progress with Leorik. I tried dozens of things that seem to work for everyone else but for me nothing sticks. Now the sunk cost fallacy causes me to orbit my computer in ever shrinking intervals. I'm desperate to get *something* working so that it doesn't feel like I wasted a huge part of my vacation on nothing. My wife is losing patience with my "hobby" at inflationary speed and I can't blame her.
I think there needs to be a public health warning to not get involved with chess programming.
If you don't mind sharing, I'd be curious to know what you've tried that hasn't worked for you.
Don't want to hijack the thread and will reply in Leoriks Devlog instead...
I don't mind sharing, it's just that I'd rather share good news than bad ones. Version 2.2 released a months ago and it was mostly about improving the evaluation. So I thought for version 2.3 I should revisit the search. It's mostly the same as what I did in MinimalChess so not very sophisticated.
Things I tried:
- Using SEE to prune bad captures in QSearch. (maybe my implementation is too slow but it was just less nodes searched but not stronger)
- Using SEE to sort captures in normal search
- Using SEE to prune bad captures in frontier nodes
- Extending by 1 ply when being in check (and other simple extensions)
- Using float instead of integers to store the remaining depth, then try extensions like check-extensions with different non-integer values (half a ply etc)
- A history heuristic but not for good quiets but for bad captures. It predicted bad captures well enough but like with SEE I didn't manage to use the knowledge to my advantage.
- Making sure that no move is played twice (e.g. the PV move or the killer moves could come up again later if they are not causing a beta cutoff)
- Tried to improve my history heuristic in a bazillion ways. The most significant change was to make it use much more storage and not only use the current move as key but also the previous (counter move) and the one before that (follow up)...
When all this didn't work out I started to suspect that a few exotic choices I made *earlier* where to blame. Leorik does late move reductions in a somewhat peculiar way. I use a staged move generation: First the hash-move, than the captures, then killers... The remaining quiets are plenty and I pick a few based on the history value and play them first. When the history score is below average I decide that the remaining quiets must be quite bad: I play with a null-window around alpha to prove that they are bad but I also reduce by 2 plys so this proof is cheaper. When it does not result in an alpha-cut I search the move again with the normal window and full depth.
This means that the history heuristic not only decides the order of quiet moves but also which ones get reduced. This makes it complicated to test because when I make a change that is supposed to improve the move ordering but this somehow moves the point where I transition between sorted quiets and unsorted quiets this will influence the behavior and strength of the engine significantly.
So I tried moving away from this and employ a Late-Move-Reduction scheme that is literally just about how late a move is so that even captures and killers could be reduced in which case their order would matter much more and then maybe SEE-move ordering etc would finally be worthwhile.
But whatever I tried it never got stronger than my old way of doing things. A reduction always risks missing something important. My old way of reducing only quiet moves that have a bad history score was apparently not missing a lot. And the threshold when to start reducing was not constant and stupid based on the #number of the move but based on statistics so it served me well. But apparently it's a dead-end because now I can't improve the search by better move-ordering.
Or maybe I do improve the engine? But it takes a certain search depth before it really becomes beneficial... and my 5s + 100ms increment tests are just too shallow?
Sure, I could just use longer time controls but I had it often enough that a change looked like +10 Elo after 1000 games only to end up as 0 Elo after 3000 more games. So longer time controls and thousands of games... that's just not very practical on my PC.
To compensate for that I tried to understand the internal workings of my engine better to maybe improve the engine by improving some critical metrics first.
I can for example search the 300 positions from the WAC testset (I should probably replace it because it's become too easy) and get a summary after each position or at the end that looks like this:
Code: Select all
[BETA CUTOFFS]
Ply: 0 || New: 0 | Captures: 0 | Killers: 0 | SortedQuiets: 0 | Quiets: 0 |
Ply: 1 || New: 41861 | Captures: 8992 | Killers: 2023 | SortedQuiets: 195 | Quiets: 236 |
Ply: 2 || New: 53047 | Captures: 16386 | Killers: 3956 | SortedQuiets: 1073 | Quiets: 1006 |
Ply: 3 || New: 275257 | Captures: 236892 | Killers: 28429 | SortedQuiets: 4320 | Quiets: 2311 |
Ply: 4 || New: 237416 | Captures: 215854 | Killers: 29048 | SortedQuiets: 7891 | Quiets: 4510 |
Ply: 5 || New: 537570 | Captures: 897825 | Killers: 127725 | SortedQuiets: 23261 | Quiets: 9040 |
Ply: 6 || New: 310939 | Captures: 548935 | Killers: 81977 | SortedQuiets: 20649 | Quiets: 12123 |
Ply: 7 || New: 322937 | Captures: 1180096 | Killers: 203449 | SortedQuiets: 55270 | Quiets: 16856 |
Ply: 8 || New: 136848 | Captures: 373096 | Killers: 64783 | SortedQuiets: 20424 | Quiets: 13786 |
Ply: 9 || New: 102770 | Captures: 529976 | Killers: 91696 | SortedQuiets: 43087 | Quiets: 12339 |
Ply: 10 || New: 22994 | Captures: 86525 | Killers: 19309 | SortedQuiets: 7023 | Quiets: 5616 |
Ply: 11 || New: 10388 | Captures: 103679 | Killers: 19079 | SortedQuiets: 11585 | Quiets: 3626 |
=============================================================
Cutoffs || New: 2052027 | Captures: 4198256 | Killers: 671474 | SortedQuiets: 194778 | Quiets: 81449 |
|| New: 28,51% | Captures: 58,33% | Killers: 9,33% | SortedQuiets: 2,71% | Quiets: 1,13% |
[MOVE COUNTS]
Ply: 0 || New: 3300 | Captures: 11124 | Killers: 4994 | SortedQuiets: 5223 | Quiets: 122203 | Sorted:4,10%
Ply: 1 || New: 46681 | Captures: 26208 | Killers: 8236 | SortedQuiets: 7631 | Quiets: 91221 | Sorted:7,72%
Ply: 2 || New: 67859 | Captures: 289608 | Killers: 77351 | SortedQuiets: 140307 | Quiets: 2731299 | Sorted:4,89%
Ply: 3 || New: 291849 | Captures: 463777 | Killers: 95777 | SortedQuiets: 147686 | Quiets: 1327562 | Sorted:10,01%
Ply: 4 || New: 266614 | Captures: 2210364 | Killers: 382294 | SortedQuiets: 941776 | Quiets: 19050529 | Sorted:4,71%
Ply: 5 || New: 565322 | Captures: 1984591 | Killers: 429918 | SortedQuiets: 926100 | Quiets: 7804688 | Sorted:10,61%
Ply: 6 || New: 341521 | Captures: 3513645 | Killers: 586502 | SortedQuiets: 1392035 | Quiets: 27717614 | Sorted:4,78%
Ply: 7 || New: 340072 | Captures: 2340983 | Killers: 552765 | SortedQuiets: 1166212 | Quiets: 9113605 | Sorted:11,34%
Ply: 8 || New: 153965 | Captures: 1776047 | Killers: 358085 | SortedQuiets: 789929 | Quiets: 13156616 | Sorted:5,66%
Ply: 9 || New: 110619 | Captures: 1003462 | Killers: 245941 | SortedQuiets: 552742 | Quiets: 3979038 | Sorted:12,20%
Ply: 10 || New: 28266 | Captures: 413179 | Killers: 103572 | SortedQuiets: 227419 | Quiets: 3382287 | Sorted:6,30%
Ply: 11 || New: 12207 | Captures: 192467 | Killers: 50642 | SortedQuiets: 117751 | Quiets: 771339 | Sorted:13,24%
=============================================================
Total || New: 2228275 | Captures: 14225455 | Killers: 2896077 | SortedQuiets: 6414811 | Quiets: 89248001 | Sorted:6,71%
|| New: 1,94% | Captures: 12,37% | Killers: 2,52% | SortedQuiets: 5,58% | Quiets: 77,60% |
[BETA CUTOFF RATIOS]
Ply: 0 || New: 0,00% | Captures: 0,00% | Killers: 0,00% | SortedQuiets: 0,00% | Quiets: 0,00% |
Ply: 1 || New: 89,67% | Captures: 34,31% | Killers: 24,56% | SortedQuiets: 2,56% | Quiets: 0,26% |
Ply: 2 || New: 78,17% | Captures: 5,66% | Killers: 5,11% | SortedQuiets: 0,76% | Quiets: 0,04% |
Ply: 3 || New: 94,31% | Captures: 51,08% | Killers: 29,68% | SortedQuiets: 2,93% | Quiets: 0,17% |
Ply: 4 || New: 89,05% | Captures: 9,77% | Killers: 7,60% | SortedQuiets: 0,84% | Quiets: 0,02% |
Ply: 5 || New: 95,09% | Captures: 45,24% | Killers: 29,71% | SortedQuiets: 2,51% | Quiets: 0,12% |
Ply: 6 || New: 91,05% | Captures: 15,62% | Killers: 13,98% | SortedQuiets: 1,48% | Quiets: 0,04% |
Ply: 7 || New: 94,96% | Captures: 50,41% | Killers: 36,81% | SortedQuiets: 4,74% | Quiets: 0,18% |
Ply: 8 || New: 88,88% | Captures: 21,01% | Killers: 18,09% | SortedQuiets: 2,59% | Quiets: 0,10% |
Ply: 9 || New: 92,90% | Captures: 52,81% | Killers: 37,28% | SortedQuiets: 7,80% | Quiets: 0,31% |
Ply: 10 || New: 81,35% | Captures: 20,94% | Killers: 18,64% | SortedQuiets: 3,09% | Quiets: 0,17% |
Ply: 11 || New: 85,10% | Captures: 53,87% | Killers: 37,67% | SortedQuiets: 9,84% | Quiets: 0,47% |
=============================================================
300. [X] g5g6 h7h6 h5h6 g7h6 g6g7 h8g8 g7f8q g8f8 d7d8 e6e8 d8e8 f8e8 = +250,00, 473434 nodes, 130ms
142240703 nodes, 49 seconds, 285 solved.
Searched 300 positions with (12)
142240703 nodes visited. Took 49,625 seconds!
2866K NPS.
Best move found in 285 / 300 positions!
So... when I'm using a simple history heuristic that just uses [piece, to-square] as an index for the lookup I would expect some good quiets to slip from the sorted (and unreduced) ones into the normal quiets and drive up the cut-off ratio there. When I try to improve the history heuristic I wouldn't want more sorted-quiets (because that means it takes an higher number nodes to reach a fixed depth, not noticable at shallow searches but a real problem at very long time controls) but I'd want the sorted quiets to produce more cutoffs and the unsorted ones less. Or the number of sorted-quiets to increase proportionally without causing more nodes to be searched in total, which is going to happen if the heuristic really helps me to pick the good quiets in the given position.
And based on these metrics it looks like I can improve upon my simplistic history heuristic (Cutoffs in SortedQuiets: 3,08%, Quiets: 1,33%) to something like SortedQuiets: 3,17%, Quiets: 1,22% and have the number of sorted quiets go up from 4,81% to 5,39% and *still* search less nodes total when I search all 300 positions to a fixed depth of 18 for example. All this are signs of better move ordering of non-captures...
But then I make a build and test that and at least at fast time controls it's not better. The more complicated heuristic is of cause making the engine a bit slower in total. And maybe that speed-loss is eating up whatever gain I should otherwise see...