Time Management

[BrandonSi]

Can anyone point me in the direction of higher-level discussion regarding engine time management? Just looking for the basic theories on this, not actual code. Are there just a few overall methods for this, or are there wide variations between engine implementations?

I see quite a bit of discussion regarding searching / pruning (and rightly so) but not so much on how that searching / pruning is handled given certain time constraints. It would seem to follow that optimizing time management would ultimately improve search and pruning efficiency as well.. At least that's the theory I'm going with for now.

[hgm]

I would be surprised if there is any theory on this at all. Basically the only thing known is that for any given time-management algorithm doubling the search time gives you about 70 Elo.

AFAIK it is totally unknown how much you suffer if you reduce only the search time for alternate moves. If that would cost only 35 Elo, because you only make half the moves 70 Elo weaker, or nearly 70, because it is the weakest moves that count, is really anybody's guess.

[BrandonSi]

Thanks, HGM!

I'm curious as to the flow of logic around this.. For example in a 1 minute game how does the engine make the decision to spend 10% of its time on move x, and only 2% of its time on move y. Obviously evaluation should play a role, if you run into a move that significantly improves the evaluation, it is worthy of more time than a simple piece exchange.

I've never seen any theory on the topic, perhaps because as you said, there may not be very much in existence. I suppose I may have to end up digging through engine code and see how it has been previously addressed.

[hgm]

One thing people do is give extra time when the best move of the previous iteration suddenly drops a lot in score, to at least finish the iteration, to make sure there isn't a move at that depth that can replace it. How many Elo this is worth is any body's guess.

I have also never seen any reporting on the effect of allocating more time to beginning or end of the game. An average game last ~60 moves (at the level of my engines; higher level might cause longer games). But would it be better to spend 50% of the total time (in sudden-death TC), 70% or 90% on the first 30 moves?

And these are still the simple questions. It becomes really interesting if you also take into account how much time the opponent is using. If he thinks much longer initially than you know is optimal for you, would you stick to your own 'ideal' time usage (and run the risk of being outsearched)?

[BrandonSi]

One thing people do is give extra time when the best move of the previous iteration suddenly drops a lot in score, to at least finish the iteration, to make sure there isn't a move at that depth that can replace it. How many Elo this is worth is any body's guess.

I have also never seen any reporting on the effect of allocating more time to beginning or end of the game. An average game last ~60 moves (at the level of my engines; higher level might cause longer games). But would it be better to spend 50% of the total time (in sudden-death TC), 70% or 90% on the first 30 moves?

And these are still the simple questions. It becomes really interesting if you also take into account how much time the opponent is using. If he thinks much longer initially than you know is optimal for you, would you stick to your own 'ideal' time usage (and run the risk of being outsearched)?

I agree, it seems like this topic is full of possibilities. I especially like your idea of analyzing opponents time usage. I suppose one could always allocate the exact time used by the oponnent, less a fraction of a second, and then never worry about running out of time before your opponent. In this manner you wouldn't even need to devote much effort into time management. Of course this is clearly not "the right way" to do it.

I was thinking about this, and I wonder if it would make sense for an engine to take the first few seconds of every game not to "play chess", but to establish a performance baseline.

Since the starting position is known, and assuming a standard search algorithm, the engine could measure how quickly the hardware it is running on can process a search. Once the engine is aware of the speed of the hardware it could adjust values appropriately.

For example if the initial test / baseline determines we're running on a very old computer, maybe it limits AB pruning to a ply of 2.. If the initial test determines very fast hardware (maybe an 8-core PC), perhaps it extends the AB depth to a ply of 6..

Just a thought.. A very interesting topic indeed.

[Milos]

I have also never seen any reporting on the effect of allocating more time to beginning or end of the game. An average game last ~60 moves (at the level of my engines; higher level might cause longer games). But would it be better to spend 50% of the total time (in sudden-death TC), 70% or 90% on the first 30 moves?

All the tests I've ever conducted support the idea that is better to have an equal time for most of the moves (like first 60 or 80).
Having more time for first 20 or 30 moves eventually hurts performance.

It becomes really interesting if you also take into account how much time the opponent is using. If he thinks much longer initially than you know is optimal for you, would you stick to your own 'ideal' time usage (and run the risk of being outsearched)?

Using opponent time as a marker is generally not a good idea. Move times should be balanced.
However, it's a bit of philosophical question. If the chess is about finding once the best move, or always the least bad move. Rybka learned us so far it's the later.

[BrandonSi]

However, it's a bit of philosophical question. If the chess is about finding once the best move, or always the least bad move. Rybka learned us so far it's the later.

I think by definition the best move is the same as the least bad move..

I'm only playing with words, I understand what you mean.

[Aser Huerga]

A very interesting post!

One of the few things a human makes better than a engine when playing chess, it's to recognize unique moves. So when the human player see there's no good move but one and only one, he waste no time and he play that move.
This is applicable specially in combinations involving piece changes.

I think only top engines do this to a certain degree, and sure there is a lot of room for work in this question.

Regards.

[Greg Strong]

Yes - the "Easy move" idea. Stockfish and others have this. If one move looks significantly better than the others, allocate more time.

I've tried it, but I haven't been able to get it to work.

[Mincho Georgiev]

What I do is this. Before starting new iteration, I'm checking the remaining time with the time used by the last iteration. In a perfect world, one would know the exact branching factor, but unfortunately this is not possible due to
extensions and other dynamic factors. So I'm picking an average branching factor (which currently is 2.5) and multiply it by the last iteration time. If the result is higher than the remaining time, a new iteration is omitted.
This idea thought, fails, if the above mentioned happens, i.e. the search result drops suddenly, but still spares time in opening and midgame, which gives small advantage in the endgame, when time becomes critical.
I have a separated 'DTC' UCI option that allows this to be turned off, but still didn't have free time to test ON vs OFF, so I don't really know the exact benefit of it. It's just an idea.