Since then I have continued to develop the engine much beyond the originally planned scope. It plays around 2300 ELO now and so my definition of "minimal" has obviously changed since. I still try to express algorithms as simple as possible and I measure the "minimalness" using the Visual Studio "Lines of Code" metric (LOC) and basically try to minimize the LOC/ELO ratio instead of pure LOC. That means I'm okay with adding features and complexity (and thus lines of code) as long as the playing strength also increases significantly enough that the ratio goes down. And I said to myself that as soon as I can't make the engine any better by that (quite esoteric) metric I wanted to slap a version 1.0 on it and call it done.
It seems I reached that point faster than I thought because in the last weeks I didn't manage to make any significant progress. But before I call it quits I wanted to see if any of the experienced chess programmers here have some last tips for me of what else I should try first.
I ask because I tend to misjudge the potential of some features. When Amanj explicity requested me to add a transposition table it was a huge step forward. Not only make it the engine much faster it also allowed me to get rid of the triangular PV table entirely and so the net increase of the codebase was pretty slim. My expectations where all wrong.
Here are the current set of features:
- A simple 8x8 Board representation: Just an array to represent the 64 squares and keep track of the pieces.
- A Transposition Table to store the score and best move of previously visited positions.
- Staged move generation: TT first, followed by the PV move, then MVV-LVA sorted captures, followed by known killer moves and finally the remaining quiet moves.
- Iterative Deepening Framework with PVS
- Null-move pruning with R=2 fixed reductions.
- Quiescence Search that plays only captures unless in check
- Tapered, tuned PSTs
- A 13th auto-tuned table for a dynamic, mobility-based evaluation component.
- I implemented SEE and BLIND to improve move ordering (playing bad captures after Killers)
Basically the cost of the algorithm negated the benefits (which are measurable) at fast time controls (5s + 0.5s inc) and of course it's a lot of extra code! - I used SEE in QSearch to not play "bad" captures at all. The QSearch concludes twice as fast on average and thus the engine searched a little deeper but didn't play better against it's opponent in the gauntlet. Presumably there's an accuracy loss in the evaluation if the positions are not fully quiet.
- I used a history heuristic to sort quiet moves but again it just introduced a lot of new code and the performance hit of sorting the quiet moves negated the benefit of a slimmer tree in the time controls I test in. (And slower time controls are not practical because it takes just too long to get statistically significant results)
- I tried a variety of naive search extensions and reductions. Like check extensions, recapture extensions, reducing all quiet moves by one... but I guess it was too blunt a tool for a rather slow engine.
But performance is nothing to just add in hindsight, it should be a concern from the beginning and ideally in an engine that doesn't also try to be simple to understand because optimizations are usually paid for with reduced maintainability. Imo this calls for me making a 2nd engine with a more ambitious goal in terms of strength and no self-imposed constraints otherwise.
If anyone would want to check the source code it's found here: https://github.com/lithander/MinimalChessEngine It's very likely that I do something in an odd way that could be simplified or otherwise improved.
If you got some ideas what feature I should try with an estimate of how much strength I should expect from a correct implementation please let me know! Otherwise I guess my first chess engine is going to see it's final release soon. I got mixed feelings about this! It's at only 556 lines of code (IL instructions, not text) which I'm quite proud of. For example MadChess 1.4 which is also written in C# involves 4438 LOC to achieve roughly the same playing strength. So I think I achieved my stated goals alright. But at the same time it's now just another engine with a mediocre 2300 CCRL rating... for most computer chess enthusiasts that's not yet interesting.