trout

oh no, 8 hours i need to devlog more holy moly
from last devlog, i kinda found a solution to the fail-soft problem?
Most engine’s LMR implementations will re-search twice if the previous search went over alpha (lower bound). The first search has reduced depth AND a null-window around alpha (search window of 1 centipawn; searches faster, but can only tell the direction of the true search result); if this is over alpha, it’ll re-search with full depth; if this is again over alpha, it’ll re-search with full depth and full bounds. My engine was skipping the middle step and jumping from reduced depth + null window -> full depth + full bounds. Apparently this is an accepted method and it was working fine compared to the other version, EXCEPT once I switched to fail-soft on beta.

in other news, I added:

• aspiration windows (75 elo): the initial search is normally unbounded, but aspiration windows try to clamp the search around a “guess” based on the previous depth of iterative deepening, and widen if it fails high or low. it did almost nothing before, and randomly became really good. don’t ask me why.
• razoring (22 elo): prunes a node if quiescence search says it’s too far below alpha. I already had it in a previous version and brought it over to the search rewrite. pretty simple, smallish elo boost.
• late move pruning (39 elo): prunes the latter part of move list; moves are sorted by how good they’re predicted to be, so latter moves are usually pretty garbage
• fixes (23 elo): small logic changes to LMR and LMP. don’t know how they didn’t lose more elo, the LMR bug was kinda bad.
• separate PV tracking: the PV (principal variation, the best moves for each player as calculated by the engine) was previously tracked by the transposition table, but that meant i didn’t have a lot of flexibility with the replacement strategy for the table, lest it wipe an important PV entry. tracking it separately lets me fiddle with the replacement strategy more, although I haven’t actually found one better than what I have now

here’s a graph generated from a google sheet with 100k rows (!?). it’s a histogram of every time a move was marked as “currently the best”, indexed by entry. ideally, it’d be all 0, meaning the best move was searched first every time, meaning there was basically no wasted effort.

6.5 hours? oh man
i was right, nmp only gained like 30 elo, gained much much more before. i tried to hunt down anything weird but i had to leave it at that. i also implemented pruning in quiescence search, so the engine only searches moves that have a positive static exchange evaluation (essentially, the result of all trades on a particular square).
i also accidentally found out my engine was doing fail-hard on beta cutoffs instead of fail-soft! in a fail-soft framework, the search is allowed to return outside of the bounds set by the alpha and beta parameters (it’s hard to explain succinctly here and i don’t want to keep doing it, search up alpha-beta search if you’re interested). thus, alpha and beta are soft bounds. this means each search returns more information about the move score.
i successfully did fail-soft on the alpha (lower bound) side, but not on the beta side due to what i can only assume is a coding mistake. the problem is, when switching to fail-soft on beta, the engine lost like 30 elo! i bisected the change to the LMR (late move reductions) patch, but still have no idea why LMR doesn’t play nice with fail-soft beta. i’m kinda at the end of my rope here, i might just have to eat the elo loss…

I finally got RFP to gain! but it might not be as good as it seems…

ive been struggling to get rfp, a pretty basic improvement, to actually do anything, and redid everything search step-by-step to make sure i didn’t do anything wrong. so far, i’ve added back SEE move ordering, butterfly heuristic, PVS, transposition table move ordering, and RFP. however, i don’t think this actually fixes my problem; the code is largely the same aside from some parameter changes, so my theory is that rfp is only working now because i added everything back in a different order, and now i might struggle with adding back different features that aren’t gaining anymore.

i’m currently testing null move pruning (based on the null move observation: doing something is basically always better than doing nothing), and it’s not doing as much as it used to… disturbing

ive nuked it….

i kept fighting rfp and talking with other people about this. apparently, rfp is one of the easiest gainers (something that gains elo/strength), and usually gains a lot, but again, nothing. i ran an overnight test of like 5000 games and the rfp version manages to LOSE 8 elo, where other people have gained 80.
i’m gonna try to restart search again, but basically fully. i don’t know if this will actually do anything, but i don’t see many other choices…

i’ve reentered the nightmare

when i last left off this project in ~september, I basically hit a wall with optimizations. I had a crapload of pruning and whatnot, but the elo of the engine didn’t really reflect it. I then did a search rewrite but got stuck on RFP (reverse futility pruning), which is supposed to gain a lot of strength but did basically nothing for me.

brief (??) aside: reverse futility pruning, in simple terms, checks if the static evaluation (evaluation without searching moves) is above beta (if a move scores above beta, it’s “too good,” and the opponent won’t allow that position to happen in the first place) by some margin. if it is, it’ll return without searching any moves, because it’s not likely that the player can lose that much material/positional advantage in whatever depth is left to search.

anyway, i’m still stuck on this. I’ve re-reimplemented half the search to recheck its correctness, because correctness issues can sometimes stuff new optimizations, but it seems to be all good. RFP still doesn’t do jack.

i don’t really know where to go from here. I could just ignore it, but the fact that RFP doesn’t do anything (for reference, another engine dev i talked to got like 80 elo out of RFP, which is insane) is a troubling sign and might mean something else is wrong.

hello! trout again. i’m gonna try to get this to #1 haskell engine, but it’s been such a pain…

after summer of making I did some more work on this, but hit a wall where all my changes either did nothing or gained like 10elo (which is not enough for the hundreds i need). I tried rewriting part of search but hit a wall again with the same problem, on features that should have made improvements!

i’ve been fighting with the search some more trying to get reverse futility pruning to do something meaningful. in someone else’s engine, it gained i think 80+ elo in total (!!!), which is bonkers compared to the 20 or something i get on a good day. it’s not a good day, so RFP actually manages to lose elo here.

i might have to rewrite search again. i don’t know how much of this is just wrong.

(here’s the commented out old search)