trout

managed to update the website to the new version. It was much easier than I expected, considering the amount of changes I’ve made.
new version is better (besides just being stronger) in that I factored the iterative deepening code out, which means the website can have sensible time settings now instead of the stupid “max time per depth” thing it had before.

I also implemented IIR (internal iterative reductions). I’ve tried it like 10 times before, but this specific version worked for some reason. +28 elo! engine is now safely better than barbarossa.

2.0 release has been tagged! i set up a dockerfile to make static linux binaries and created a windows github action to make the windows binaries.

I also finished the test against the last version of the engine:

it is done….. i think trout is the strongest haskell engine now

(i made the passed pawn bonus tunable per-rank, which added around 20 elo. re-tested some other search stuff but they all kinda sucked)

i think i’m going to work on polishing the frontend now, tag a 2.0 release soon.

i’ve been doing some tuner work, it’s not great

the old tuner was pretty bad. very janky, repeated code, very hard to read, and sloooowwww….
i optimized it by precomputing the factors for each position so it’s just a bunch of multiplications to get the score. upside: order of magnitude speed improvement. downside: 20+ gb memory….
other problem is that the new tuner’s results are not great. they aren’t horribly bad like some other tests, but the gains aren’t as big as i was expecting. this might be a data quality issue? i might write proper datagen code at some point instead of just relying on the output of SPRT tests.

I did get a nice 7 elo from removing floating point ops in eval, so that’s nice i guess.

i can smell the goal already. Soon
(i would attach a picture of the 20gb but i’m kinda running a sprt right now… maybe next time)

big gap!

some stuff came up and i don’t fully remember what i’ve done since the last devlog. git log tells me i did some minor logic fixes and added SEE pruning in pvs (32 elo), which prunes nodes based on their static exchange evaluation.

i do remember that the current version of the engine can beat barbarossa at LTC now. STC it still loses (i.e. my engine scales better… glass half full), but I am now working on eval tuning to hopefully bump the elo up some more.

i am now working on this through ssh. negative: lag. positive: there is almost nothing running on my computer aside from the language server. should make testing easier and more predictable

i’m now within 100 elo of my target, but it’s still not looking great.

it seems i have hit another wall. there’s this copypasta around chess programming circles with a rough order of search features to implement, and i’ve tried 3 in a row, none doing much.

since last time, i’ve just added two things that have gained elo:

• history decay tweak (10 elo): after searching a position, decay history by 50% instead of 80%, helps retain memory from previous searches
• check extensions (23 elo): extend a search by 1 more move if in check. it’s very simple.

i’ve since tried IIR (internal iterative reductions), SEE pruning in PVS (more moveloop pruning), and continuation history (like the history heuristic, but More™️). only continuation history has kinda done something, but only when comparing against a version that’s just as slow; when comparing against the original, it’s much closer because for some reason continuation history slows down the search by almost 10% (??????). The main slow-down-er seems to be indexing the continuation history array, which is absolutely baffling to me. i’ve even tried to start reading the GHC Core again, until i remembered why it was so painful last time.

a lot of changes in this batch, but not all of them were for strength.

here’s a quick runthrough of the elo-affecting changes:

• add improving heuristic to rfp (prune more nodes while improving)
• add staticEval >= beta guard to nmp (restrict the usage of null move pruning to moves that already seem good from static eval)
• futility pruning (very similar to reverse futility pruning - removes quiet moves when static eval is pretty far below alpha)
• tempo bonus (side to move gets a bonus to eval for having tempo)
• add quiescence search results to transposition table (i had this in the old version but i guess i forgot to port it over until now)
• soft time bounds in search (instead of searching for as long as possible and nuking the search thread mid-search, stop iterative deepening if it looks like the next node will take too long)

to fix this, i moved the timing-out logic inside the search function, which is what most engines do. I didn’t do this earlier because 1. it’s marginally harder and 2. it would require making the search functions IO instead of ST. ST is escapable, so it’s more pure, so this was kinda a bummer to do, but i didn’t see any way to get around this.

here’s a graph i made while i was looking at aspiration windows more. it shows the average centipawn change between successive depths of search. the current aspiration window implementation assumes that depth and avg cp change is inversely related, but it doesn’t look like this is true. (what is the hump doing??) I tried a couple of aspiration window implementations that don’t make this assumption but didn’t get anything huge. I’ll probably replace it at some point.

the engine is finally in the strongest state it’s ever been! (i think)

for those who have not been obsessively following this project, the
search part of the engine has gone through two rewrites now. i kept
hitting walls where i really shouldn’t have; improvements that should
have been huge gains did a lot less than expected. i did the rewrites in
an attempt to find a potential bug that would kill future attempts at
improvements, but i never really found anything significant.

i never really got the engine to it’s pre-rewrites strength until now.
read it and weep (~17 elo gain)

--------------------------------------------------
Results of trout-exe-max vs trout-exe-asp-tweak (8+0.08, NULL, 
16.000000MB, UHO_Lichess_4852_v1.epd):
Elo: -16.96 +/- 14.18, nElo: -22.54 +/- 18.80
LOS: 0.94 %, DrawRatio: 33.99 %, PairsRatio: 0.82
Games: 1312, Wins: 380, Losses: 444, Draws: 488, Points: 624.0 (47.56 %)
Ptnml(0-2): [63, 175, 223, 153, 42], WL/DD Ratio: 1.79
LLR: -2.98 (-101.3%) (-2.94, 2.94) [0.00, 10.00]
--------------------------------------------------

it’s still not super great because elo improvements are coming slooowww
and we’re still only 17 elo up with many more features than before. it’s
still nice, though.

implemented since last devlog:

• “improving” heuristic (13 elo): a position is said to be “improving” if the static evaluation now is higher than the one from a move ago. we can use this to tweak some parameters in the search, like when to cut off for LMP, which is what i did. need more testing for the other features.
• lmr limit (16 elo): my LMR implementation was slightly bugged and would reduce too many moves; normally the first couple are spared, but i had every move except the first reduced.
• negative captures below quiet moves (13 elo): for some reason, i had captures that were deemed negative by SEE (bad captures, basically - trading a queen for a pawn would be one) sorted above all quiet moves. i moved them to the bottom of move sorting.
• redo aspiration windows (36 elo): i redid the implementation for aspiration windows slightly. it should be smarter about bounds now. that makes around 100 elo for aspiration windows cumulatively now, which is kinda crazy

here’s a picture of htop when i was running the engines against each othe for elo testing. i thought it was kinda funny

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)