What pruning techniques should I add to my engine?

[OliveriQ]

So I've sort of hit a barrier. My engine's estimate rating is within the range [2130, 2200] elo, and improving its evaluation function doesn't seem to be very effective (makes it slower). Things that I've tried implementing include doubled pawn penalties, open file bonuses and basic piece mobility. I'm also using PeSTO's piece square tables. Based on these results, I've decided to just use PSQT's in my evaluation and just focus on improving my search function. So my question is what search techniques should I implement? As I believe that I've already implemented most of the standard ones (null move, static null move, futility, late move pruning, LMR and delta pruning). And I obviously make use of TT and iterative deepening.

[hgm]

There are some evaluation features that should not be very costly, and would improve the engine a lot. E.g. Pawn structure (in particular recognizing passers, and pushing those at the right moment) should be very helpful, and cheap when implemented through a Pawn hash table. The table could also be helpful in maintaining a healthy Pawn shield in front of the King, and cheaply identifying open files for the Rook evaluation. Recognizing drawishness in the end-game through a material hash table is usually also worthwile; the table can also take care of the Bishop-pair bonus.

Your search already looks pretty advanced. I you don't get above 2200 with that (and assuming it is all correctly implemented) this suggests the evaluation is not good enough. In that case better search might not help much.

[Tearth]

Also what is your move ordering? It's crucial to have a good one, since it can easily be a bottleneck for the search.

[lithander]

You didn't mention it but I assume you do MVV-LVA sorting or something equivalent? And that you have quiescence search implemented? Both is pretty fundamental!

Before you add more search techniques I would try to verify the correctness of the implemented techniques again. I believe your current Elo range should be almost reachable with just PeSTO's material evaluation and only the "safe" search optimizations such as PVS, iterative deepening and TT but none of the "risky/lossy" pruning techniques that you mentioned like null move, static null move, futility, late move pruning, LMR and delta pruning. With all lossy pruning disabled you should get the same results as plain alpha-beta just much faster. So it's easy to verify correctness at that stage.

Then with the risky pruning techniques I would add each of them step by step and make sure that they really benefit the engine as they should.

[abulmo2]

A good search with PeSTo eval should already bring your program over 2700 Elo. Based on the listing of the features you have already implemented I would not add anything but check everything and tune everything. The power of a bug to diminish Elo is impressive. Be aware that some algorithms are tightly related to each other. For example, a good ordering of quiet moves is necessary for late move reduction & pruning to work.

[Henk]

Also what is your move ordering? It's crucial to have a good one, since it can easily be a bottleneck for the search.

It's impossible to get a good move ordering. So LMR which depends on it cannot be trusted that much. O wait same holds for razoring or futility pruning when skipping remainder moves. It is just gambling.

TTable connot be trusted too. So gamble on.

[Tearth]

Also what is your move ordering? It's crucial to have a good one, since it can easily be a bottleneck for the search.

It's impossible to get a good move ordering. So LMR which depends on it cannot be trusted that much. O wait same holds for razoring or futility pruning when skipping remainder moves. It is just gambling.

TTable connot be trusted too. So gamble on.

No one prevents you from using only safe methods which won't introduce any hazard, but practice from the last dozens of years has shown that the big enough search tree is pretty resistant to some rare miscalculations, and at the same time benefits of using "risky" algorithms are huge if implemented correctly. Also "good move ordering" doesn't mean you have to have a perfect one every time, just good enough for 95% of cases which is completely sufficient.

[Henk]

"..but practice from the last dozens of years has shown that the big enough search tree is pretty resistant to some rare miscalculations ..."

That makes it difficult to test for correctness. For it hides bugs.

Reminds me of writing more Unit tests. Boring and tedious work.

[Tearth]

That makes it difficult to test for correctness. For it hides bugs.

My assumption is that the search trees thanks to modern processors are so huge, that you can't analyze them node by node anyway, so I treat it more like statistics where I change some value/implementation and check how will it behave based on a considerable test sample (like 20000 fast games).

[Henk]

That makes it difficult to test for correctness. For it hides bugs.

My assumption is that the search trees thanks to modern processors are so huge, that you can't analyze them node by node anyway, so I treat it more like statistics where I change some value/implementation and check how will it behave based on a considerable test sample (like 20000 fast games).

But you can still inspect small trees (if you hate yourself, for tough to debug)