Depth reduced but ELO increased

[silentshark]

This was interesting.. I've been playing around with the 'countermove history' idea. At this point, I'm just using the countermove history data built up during the search to help with move ordering.

I expected this approach to improve move ordering, and thus allow my engine to search a bit deeper. What I found was that it didn't change the depth (in fact the countermove history version is searching very slightly shallower). But despite going shallower, I'm seeing a slight ELO increase.

I'm thinking that with all the reductions we have in engines these days (LMR, LMP, nullmove etc.) interesting properties emerge when tweaking things like move ordering in the search. My theory on the above is that *maybe* the counter move stuff is improving move ordering, meaning I'm not pruning or reducing better moves as much as before, hence the ELO increase.

Anyway, just a little musing for a Saturday morning What do others think?

Here's my data around depth searched from versions with and without the countermove stuff. _13 has the countermove bits.

Code: Select all

Engine                 Depth       Time   Games     Moves  Average Forfeit  Book Depth     MIDG   EARLY    ENDG    LATE
mar2019_12             19.72  103:55:40    5743    341647    1.10     0    47412  8.26    17.15 | 18.02 | 20.30 | 28.22
mar2019_13             19.52  103:39:11    5743    341512    1.09     0    47345  8.24    16.99 | 17.82 | 20.07 | 27.92

[cdani]

Yes, it happens often that a change increases branching factor instead of reducing it, but the tendence is, if the engine is improving, to reduce it.

[hgm]

It is quite easy to enormously increase depth by hugely reducing non-PV moves, but at some point this will backfire, because the engine will be blind even to shallow tactics that would refute its PV. One can also reduce too much. And if strength can go down by reducing more, it is not really remarkable that it can go up when you reduce less, beyond the optimum.

But if not every move is reduced by the same amount, the depth would only be sensitive to the fraction of moves that receives a given reduction. While the strength would be highly dependent on whether you heavily reduce the good moves (which would hurt), or the poor moves (the search of which was only a waste of time). So yes, your explanation sounds very plausible (if you use order-dependent reductions).

I want to point out that search priority and reduction do not necessarily perfectly correlate. I guess null move already demonstrates that: you search it first, but reduce it heftily compared to the move you search second. Ordering serves to get a beta cutoff (on average) in the cheapest possible way. Reduction/extension serves to equalize the reliability of the search results for the individual moves (as the reliability of the node result will be determined by that of the least-reliable move result, so that putting extra effort in improving relatively reliable move results is mostly wasted effort).

So having the reduction purely determined by move order is unlikely to be optimal. For this reason it was once suggested here to use two history tables, one for cut-moves in shallow searches, and one for cut-moves that only became cut-move at a larger depth. It would be unwise to reduce the latter, but it could still be smart to order them in the tail of the move list, as reduced searching of a number of 'shallow' cut-move candidates with each a lower cut probability (i.e. worse history) can still in total provide better chances for an early cutoff at smaller cost.

[Hrvoje Horvatic]

My analysis and testing have lead me to conclusion that countermove & follow-up history counters help with move ordering at all-nodes, because cut-nodes are already almost optimally ordered... what happens is that at all-nodes this history counters help with finding out new PV lines... because of super-aggresive null move and LMR/LMP, moves that end up near the end of the list at all-nodes never get enough depth to prove their value as new PV lines, so moving them a little bit up the list sometimes can help...

Try disabling LMR/LMP, or CM & FU histories only at certain type of (predicted) node types and find out for yourself... you may find out, like I did, that CM & FU histories don't help much with regular PVS search without reductions, contrary to "normal" history heuristics, which can significantly improve plain PVS search...