MinimalChess - how to move forward?

[lithander]

When I started writing my chess engine half a year ago I thought it would be a one-weekend project. I just planned to do the bare minimum to get the computer play chess and so I named the engine MinimalChess.

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.

What I tried and removed again:

• 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.

The best and obvious step towards a stronger engine at this point would be to improve the speed of the engine which explores less then a million nodes per second. If the engine would search deeper than a lot of the above mentioned discarded features would also probably have a greater effect as even a tiny reduction in the branching factor has a significant compound benefit if you search deep enough.
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.

[algerbrex]

Otherwise I guess my first chess engine is going to see it's final release soon. I got mixed feelings about this!

I'm afraid I can't offer any advice, as I'm not at all an experience chess programmer, but if you do conclude MinimalChess, I would like to thank you for your work on the project! It's been an invaluable resource for my improvement of Blunder, especially as a sparing partner.

[amanjpro]

Let me start by saying, I really like MMC, it is my favourite engine after Zahak, and what you have achieved so far is unparalleled, so congrats

A few ideas you could try:

- A more aggressive Null Move Pruning. make R=min(depthLeft-1, 4), and limit the depth to > 4 and see if it helps...
- If your eval is cheap to compute, Reverse Futility Pruning is another quick win: if eval+PawnValue * depthLeft <= beta, return
- Late Move Reduction is another one, basically if you have already searched 5 moves, and you are currently searching a quiet move (which is not check, and position is not in check), reduce depth by 1. This works best if you also have history heuristics, but it still makes the engine stronger even without it

All the above can be implemented in a few lines, they won't give you the maximum elo possible (at least the descriptions above, but give you enough strength to add another 100 elo to the engine hopefully)

[mclane]

I would try with knowledge about king safety and attacks against king.

[j.t.]

Futility reductions, though they require SEE to work properly. Generally, I found that correctly implemented SEE helps at many places (move ordering, delta pruning, fail-high delta pruning, futility reductions). Did you use a test set to test SEE?

[lithander]

I would like to thank you for your work on the project! It's been an invaluable resource for my improvement of Blunder, especially as a sparing partner.

Let me start by saying, I really like MMC, it is my favourite engine after Zahak, and what you have achieved so far is unparalleled, so congrats

That's really great to hear! Thanks!

- If your eval is cheap to compute, Reverse Futility Pruning is another quick win: if eval+PawnValue * depthLeft <= beta, return

Hmm... what's the intuition behind it? I can't really make sense of it.

Futility reductions, though they require SEE to work properly. Generally, I found that correctly implemented SEE helps at many places (move ordering, delta pruning, fail-high delta pruning, futility reductions).

So you would get the SEE value of a capture in QSearch and add it to the current eval and if that doesn't raise alpha you skip it? Or how exactly does SEE help with pruning and reductions?

Did you use a test set to test SEE?

The recent thread on Static exchange evaluation with promotion made me aware that my SEE didn't handle promotions correctly. But after the fix I get the correct results in the 25 positions from Arasans unit tests. Do you have a more extensive test set?

[j.t.]

So you would get the SEE value of a move and add it to the current eval and if that doesn't raise alpha you skip it? Or how exactly does SEE help with pruning and reductions?

For delta pruning, it works exactly like this. For fail-high delta pruning, it works very similar (both in quiesce):

Code: Select all

if standPat + position.see(move) + 150 < alpha:
    skipThisMove()
if standPat + position.see(move) - 50 >= beta:
    return standPat + position.see(move) - 50
# obviously I implemented this without calling SEE three times for the same move :)

For futility reductions, it works also quite similar:

Code: Select all

let doFutilityReduction = alpha > -valueInfinity and beta - alpha <= 10 and not inCheck
let futilityMargin = alpha - position.evaluation()
for move in moves:
    ...
    if doFutilityReduction and (not givingCheck) and bestValue > -valueInfinity:
        newDepth -= futilityReduction(futilityMargin - position.see(move))
        if newDepth <= 0:
            continue

Code: Select all

func futilityReduction(value: Value): Ply =
    if value < 150: return 0
    if value < 200: return 1
    if value < 300: return 2
    if value < 500: return 3
    if value < 750: return 4
    if value < 1050: return 5
    if value < 1400: return 6
    7

Do you have a more extensive test set?

No, I just thought that that could have been the issue (maybe I am projecting a bit much: I myself used a flawed SEE for quite some time, and then I was surprised that it performed better when I fixed it ).

[amanjpro]

- If your eval is cheap to compute, Reverse Futility Pruning is another quick win: if eval+PawnValue * depthLeft <= beta, return

Hmm... what's the intuition behind it? I can't really make sense of it.

That's because I blundered. I meant to say eval - pawnvalue*depth >= beta.

And the reasoning is that, this position is so good for you, that your opponent won't play it

Reverse Futility Pruning is a concept well described in the chess programming wiki.

[mvanthoor]

I'm convinced that, at some point, increasing speed is not going to be enough, because if the engine doesn't have an extensive evaluation, it will just find bad moves faster, or deeper.

Maybe the first step would therefore be to re-tune the evaluation using a much bigger data-set, and then see if some of the features you discarded start to work better. Also, some features seem to only be useful when you can reach deep enough. For example, aspiration windows don't seem to work in Rustic, but it only searches 7-9 ply in the middle game Many engines only start to apply the aspiration search at depth 6, so if I do this, I have an aspiration search for only 1-3 depths, which probably isn't enough to make a significant difference. The reason for only applying aspiration search at depth 6 and further, is because lower than depth 6, the search takes less than half a second; even on this somewhat old system.

The one thing that does add a lot of elo and is relatively easy to implement (at least in a bit-board engine) is an evaluation term for passed pawns. In Madchss, that gained somewhere around 120 Elo.

I really have to get back to chess programming myself, now that my crazy month of July is over...

[pedrojdm2021]

I tried SEE too, and it did not worked to me, too i fact, i made it work but that thing is VERY expensive, at least the normal SEE, the non recursive SEE seems to be the solution to make it less expensive, i see that hard to understand

I hope i would ended up with an engine like yours, i saw your minimal chess on github and i played with it a little and your speed is amazing to me, mine actually is only ~700k NPS on the AI search

i would say, try to search less nodes, try bobby's strategic quiescense search, that would be amazing, anyways, congrats for your engine and how it is now, that is something that not everyone can do