Estimating search times for time control

[gflohr]

I am thinking about modifying my iterative deepening.

The idea is that I want to estimate how much time it will take to search at least the first move with depth + 1. If that will probably take longer than the remaining time left for searching, I want to return immediately so that I do not waste thinking time.

Unfortunately, my engine is too slow to test the idea with a couple of 1000 games and at small depths the effect will not be measurable because of rounding issues.

Has anybody tested such an approach before? Is the rationale valid?

My estimation is currently very simple: I remember how much time the last 3 searches at depth n have taken and I simply take the average as the estimate for the next search. If there is no data available I assume that the next depth will take 8 times the time that the engine has already spent on thinking. Whenever I receive "ucinewgame" I clear the current data. That does not seem to work well.

In a previous version I terminated the iterative deepening, when I had spent more than 1/8 of the allocated time. Surprisingly that seemed to work quite well. But, as already mentioned, I am not able to test that seriously. I usually just played 2 x 10 games with the same opening position for both versions of the program.

[dangi12012]

The problem here is that you cannot rely on statistics of how long the previous moves needed to be expanded.
For example when there is a promotion to a knight vs a queen the nodecount will be very different at depth 3.

What your real question is - how long to "think" on each move is one of the very hard problems. That heuristic is very hard to get right.

I dont see how you can "waste" time. If you have allocated n seconds for this move you can calculate for N seconds.
Every move needs to check system_clock::now() against the "abort time".
At the end you will have expanded as far as you can go in that time. Or is it more about focusing on one specific branch?

Could you clarify the question a bit more?

[gflohr]

I will clarify. But reading helps as well.

When you have searched to depth n, going to depth n + 1 can only change the currently selected move if you are able to search more than just the 1st move which is the pv move. That will at most adjust the static evaluation of the position.

But if you are already close to the allocated time you will not be able to complete the search that far, and then you can just as well save that time and return right away.

As for statistics, it is not important to be accurate. You just have to be careful to not be too pessimistic. When you are too optimistic, simply nothing will change. But if you are too pessimistic you will constantly increase the spare thinking time without any value.

[bob]

BUT

What if searching the first move results in a big fail-low? you now know it is bad. Should you just stop, or keep searching to find a better move.

Or

What if the same first move has been found for N iterations. When do you decide to stop searching and wasting time on what we used to call "an easy move?"

This is all not so simple.

[gflohr]

What if searching the first move results in a big fail-low? you now know it is bad. Should you just stop, or keep searching to find a better move.

When time is up, the engine has to present its best move.

When it enters the next iteration it already has a best move and before it can consider its next best move it has to first search the old one at the new depth. But if it is obvious that the first move cannot be examined in the time remaining, why should the engine re-start searching in the first place?

My engine does not do any pruning, it is just plain pv search. And so far it holds true that at root level, searching the first move always takes longer than time has elapsed so far. So, if at root level the engine sees that half of the allocated time is already used up, it can actually be sure that the best move will not change, simply because there is 0 probability that it will even look at the second move.

Comparing my engine's search time characteristics with that of Stockfish suggests that for stronger engines such simple assumptions cannot be made. So in that respect, you are, of course, right. But to me it looks like I can make my weak engine a little stronger by not wasting the search time for filling up the TT and just getting a better evaluation of the position.

[bob]

The idea is that in general, a fail low happens more quickly than a fail high.

So, if you start the next iteration, even with a relatively small amount of time left, it might fail low and that gives you a sense that you need to invest even more time here to try to fix the problem the first move has...

Doesn't always work, but it pays off in more cases than it fails.

[mhouppin]

I am thinking about modifying my iterative deepening.

The idea is that I want to estimate how much time it will take to search at least the first move with depth + 1. If that will probably take longer than the remaining time left for searching, I want to return immediately so that I do not waste thinking time.

Unfortunately, my engine is too slow to test the idea with a couple of 1000 games and at small depths the effect will not be measurable because of rounding issues.

Has anybody tested such an approach before? Is the rationale valid?

My estimation is currently very simple: I remember how much time the last 3 searches at depth n have taken and I simply take the average as the estimate for the next search. If there is no data available I assume that the next depth will take 8 times the time that the engine has already spent on thinking. Whenever I receive "ucinewgame" I clear the current data. That does not seem to work well.

In a previous version I terminated the iterative deepening, when I had spent more than 1/8 of the allocated time. Surprisingly that seemed to work quite well. But, as already mentioned, I am not able to test that seriously. I usually just played 2 x 10 games with the same opening position for both versions of the program.

If running 1000 games takes you too much time, you might want to reconsider the TC you're using. Even at short TCs (like 10+0.1) improvements on time management will be apparent. Here's how I do it in Stash:

- If movesToGo isn't set, set it to 40. (This is necessary for further calculations.)
- Define two time limits, "average time" and "maximal time", representing the average max maximal times I should use for this move. (Maximal time is a hard limit: I get out of search as soon as this limit triggers, and I check the clock every 1000 nodes to avoid a huge speed drop from syscalls).

Code: Select all

averageTime = max(baseTime - moveOverhead, 0) / movesToGo + increment
maximalTime = max(baseTime - moveOverhead, 0) / sqrt(movesToGo) + increment

What this means is that for example, If I still have 36 moves to play before next time checkpoint, I allow Stash to crunch "6 moves" of time before stopping search. (This helps for example in the case of a complex fail-low.)

- Then, after each search iteration, I compute another time limit based on "average time": "optimal time".

Code: Select all

optimalTime = averageTime * bmTypeScale * bmStabilityScale * scoreDiffScale

- bmTypeScale is a value that changes based on the type of bestmove you have (for example, pawn promotions are 0.45, captures with very high SEE are 0.5 since it's generally the recapture of a piece, standard quiet moves are 1.0, unique legal moves are 0.2, etc.)
- bmStabilityScale is a value depending on the number of successive search iterations you made with the same bestmove. It starts at 2.5 (meaning that if you suddenly change your bestmove, it is generally wise to search it again to verify it is correct), and settles at 0.75 after 4 successive iterations.
- scoreDiffScale is a value that depends on the score difference between the two last search iterations:

Code: Select all

scoreDiffScale = pow(2.0, min(max(scoreDiff, -100), 100) / 100.0))

So, if the score drops by 100 cp, the search gets twice as long, and if the score raises by 100 cp, the search time is divided by two.

Doing all of this was worth 30 Elo against a static "optimal time" value, so I think it works quite well.
Another thing that you could try is Koivisto's time management, which uses the node repartition between the root moves to compute the optimal time (the more nodes the bestmove gets proportionally to the other root moves, the shorter the search gets).