Time Management

From Chessprogramming wiki

Home *Search * Time Management

Time management refers to algorithms and heuristics to allocate time for searching a move undertime control requirements in agame of chess. The playerto move consumes his time, and if he exceeds his time limit, thegame is lost on demand of the opponent player, or in automatic computer chess play by an arbiter instance.

Iterative deepening in conjunction with its predictableeffective branching factor allows a flexible time management either to terminate the currentiteration and to fall back onbest move andPV of the previous iteration, or to decide about termination prior to start a new iteration or to search a next root-move.

Time Controls

Fast chess is usually played with an immediatesudden death time control, while others may have one or more regular time controls before the sudden death control applies there as well.

Sudden Death

Sudden death refers to a requirement that all the remaining moves, rather than a fixed number of moves, need to be played within the remaining time. Typically programs estimate the game will last further 25..40 moves, and divide the remaining time by this number.

Cyclic Time Controls

Cyclic time controls define a number of moves to be made in a fixed amount of time. We don't have to make estimations for how long the game will last. However, some time should be saved in order to have a buffer in case later moves warrant longer thinking times.

Time Control with Increment

To avoid time trouble where often blunders decide the game, chess champions, most notableBobby Fischer andDavid Bronstein, proposed a delay or increment of time for each move made. It requires a special delay clock, which became handy with thedevelopment of digital chess clocks in the 70s and 80s^[2] .

Time trouble is also an issue in computer chess, either due to operators in over the board chess, boosted by deviation of internal and external clock, or in transmitting move transfer latencies in automatic play, where it is quite common nowadays to play with increment per move.

Fischer Time

In 1988Bobby Fischer proposed an unconditional increment per move, no matter whether the delay was exhausted or not. With Fischer time one may therefor increase the remaining time if one moves faster than the delay^[3] .

Bronstein Time

Bronstein's time works similar, but never increases the remaining time. It was for instance used during the lateAegon Tournaments.

Basic TM

A basic time management technique is to usebase / 20 + increment / 2 time per move. This is very competitive with advanced time management schemes, and is typically chosen as the foundation to build upon.

Enhancements

Human chess players often wonder about the inflexible time management of various programs. A basic time management scheme might be enhanced in several ways, considering dynamic, statistical as well as static features of the search, thebest move and itsPV.

Soft Bound

Drawing on the observation that terminating a depth halfway is wasteful, a large enhancement to a basic time management scheme is to introduce two levels of time allocation. Namely, one optimium time threshold (soft bound), and one maximum time threshold (hard bound). During search, the optimum time threshold is checked on each iteration ofiterative deepening, while the maximum time threshold is checked periodically, usually by every set amount of nodes.

Considerations

How often did thebest move change during the (last N) previous iterations?
The score function over iterations and best moves, increase or decrease and/or oscillation, score amplitude, etc.
The ratio of the size of the subtree under the best move versus the size of the wholesearch tree
Only one obvious way to recapture in an otherwise quiet position

Premature Termination

Only one legal move
Prior a start of a new iteration, the relation of elapsed and allocated time (f.i. > 50%)^[4]

Historical Techniques

These techniques saw use in older programs, but have fallen out of use with the advent of modern testing and tuning.

Fail low situations, a severe drop of the score may cause programs to allocate "panic time" to hopefully solve the critical situation
During the first moves out of theopening book programs often allocate more time

For instance,Robert Hyatt gave following formula fromCray Blitz inUsing Time Wisely^[5]

   nMoves =  min( numberOfMovesOutOfBook, 10 );   factor = 2 -  nMoves / 10    target = timeLeft / numberOfMovesUntilNextTimeControl   time   = factor * target

inspired by following graph of human timing from several grandmaster tournament games

Note that good time management for humans differs greatly from good time management for engines, and this graph should not be taken as a way to shape your engine's time usage.

New and therefor likely not singular best moves, but statically "suspect", like weakening thepawn structure or asacrifice favors to allocate extra time and to start a further iteration, even if the score is fine.