Lc0 sometimes uses too little time (much less than budgeted)

[mooskagh]

Example, in TCEC, in this situation:

1.d4 Nf6 2.c4 g6 3.Nf3 Bg7 4.g3 O-O 5.Bg2 d6 6.O-O Nbd7 7.Nc3 e5 8.e4 c6 9.h3 Qb6 10.c5 dxc5 11.dxe5 Ne8 12.e6 fxe6 13.Ng5 Ne5 14.f4 Nf7 15.Nxf7 Bd4+ 16.Kh2 Rxf7 17.e5 Nc7 18.a4 a5 19.Ne4 Nd5 20.h4 Qc7 21.h5 Rg7 22.Nd6 Bd7 23.h6 Re7 24.Ra3 b6 25.Qg4 Rf8

It almost immediately moved 26. Rd3 (see white time graph drop at ~move 26)

Seems that smart pruning triggered too soon.

[dubslow]

This is probably an artifact of tree reuse, is it not?

[dubslow]

Actually I wonder if this is related to #167 ? Some key quotes:

While doing some deep analysis of several positions, I've noticed that lc0 will sometimes show an incorrect PV under the following conditions:

A search from some position is started After some time, the analysis is stopped, and lc0's top move is played From the resulting position, analysis is restarted Several times in these conditions, I've seen the PV show a first move that was clearly not the top move at any point in the current search.

And from the corresponding fix commit:

Both bugs arose from circumstances where best_moveedge differed from what GetBestChildNoTemperature(rootnode) would report.

One such circumstance was that, after tree reuse, when starting a second Search, best_moveedge was null, which means if the subsequent search failed to playout the previous/actual best node (from the reused tree), then by the updates in DoBackupNode, best_moveedge would be incorrectly set to recently searched nodes, which didn't include the previous most searched node, and thus disagree with GBCNT. (Such a circumstance can arise either by contrived FPUR hacks, or in certain super long tactical searches, each as reported in the issue by apleasantillusion.)

Then again, maybe not, since this would make best_move_edge_.GetN() lower than it otherwise should be, which should lead to less smart pruning, not more smart pruning.

[dubslow]

Another possible culprit is the various nps fluctuations reported by Cyril and TheAnswer -- if "this" Search is one of the bugged ones seen in the TCEC bonus matches, with hundreds of nps instead of thousands, then the smart pruning estimates would be thrown off entirely. Enforcing a minimum usage of budgeted time wouldn't even help because then that time is spent with the bugged nps.

[Tilps]

I looked at some tcec debug logs of multiple moves in a row of almost no time spent, and they all looked like basically legitimate time prunings based on a tree reuse of basically 1.7M visits to one child. There was some evidence that probably not enough time was spent working out the nps average before applying it, but it didn't look like it would have significantly affected the outcome.

[dubslow]

Maybe the minimum fraction of time spent before pruning should be a function of the total search time -- perhaps a logarithm or square root?

[mooskagh]

Probably caused by #173 With low nps (for unknown reason because of the bug), predicted number of nodes for remaining move time is very low, and it immediately realizes that what was inherited from tree reuse is unbeatable.

[mooskagh]

We need either to have better nps prediction (e.g. moving average which also takes previous move into account) or at least some hack. (e.g. never trigger smart pruning before the first second)

In general, for nps prediction, here is kind of list of requirements:

1. It must almost never underestimate number of remaining nodes.
2. It should not overestimate too often/much.
3. It should still instamove in perfectly clear positions. (So solution with always using 20% of time budget is not that nice, it will cause 1 minute thinking if time budget is 5 minutes for example)
4. It should behave sanely on slow start (if first few batches take longer to compute than later batches).
5. Preferably, smart pruning should still work in bullet games. (that's pretty incompatible with other points though)
6. It should behave sanely in very slow (1nps) and very fast (200knps) configurations. (So current approach of fixed 100ms and 1000 nodes is not very nice).

[oscardssmith]

Won't just taking the 75th percentile of npm over the past 5 moves do the trick?

[mooskagh]

450 starts nps prediction after the first batch is completed.

[oscardssmith]

this has been resolved, right? If so close? @mooskagh