Time Management
Home * Search * Time Management
Time management refers to algorithms and heuristics to allocate time for searching a move under time control requirements in a game of chess. The player to move consumes his time, and if he exceeds his time limit, the game is lost on demand of the opponent player, or in automatic computer chess play by an arbiter instance.
Iterative deepening in conjunction with its predictable effective branching factor allows a flexible time management either to terminate the current iteration and to fall back on best move and PV of the previous iteration, or to decide about termination prior to start a new iteration or to search a next root-move.
Contents
Time Controls
Fast chess is usually played with an immediate sudden 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.
Regular Time Controls
Regular 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 notable Bobby Fischer and David Bronstein, proposed a delay or increment of time for each move made. It requires a special delay clock, which became handy with the development 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 1988 Bobby 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 late Aegon Tournaments.
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, the best move and its PV.
Considerations
- How often did the best 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 whole search 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]
Extra Time
- 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 the opening book programs often allocate more time
- For instance, Robert Hyatt gave following formula from Cray Blitz in Using 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
- New and therefor likely not singular best moves, but statically "suspect", like weakening the pawn structure or a sacrifice favors to allocate extra time and to start a further iteration, even if the score is fine.
Losing on Time
- Tech 2 versus Ribbit at ACM 1974
- Duchess vs. T. Belle at ACM 1974
- Chess Tiger X - Pharaon 2.65 at Massy 2002
See also
- CPW-Engine_chronos
- Iterative Deepening
- Playing Strength
- Pondering
- Search Explosion
- Search Statistics
Publications
- Robert Hyatt (1984). Using Time Wisely. ICCA Journal, Vol. 7, No. 1
- Robert Hyatt, Albert Gower, Harry Nelson (1985). Using Time Wisely, revisited (extended abstract). Proceedings of the 1985 ACM annual conference on The range of computing: mid-80's perspective, p. 271, Denver, Colorado. ISBN 0-89791-170-9.
- Shaul Markovitch, Yaron Sella (1993). Learning of Resource Allocation Strategies for Game Playing, The proceedings of the 13th International Joint Conference on Artificial Intelligence, Chambery, France. pdf
- Ingo Althöfer, Chrilly Donninger, Ulf Lorenz, Valentin Rottmann (1994). On Timing, Permanent Brain and Human Intervention. Advances in Computer Chess 7
- Chrilly Donninger ('1994). A la Recherche du Temps Perdu: 'That was easy. ICCA Journal, Vol. 17, No. 1
- Levente Kocsis, Jos Uiterwijk, Jaap van den Herik (2000). Learning Time Allocation using Neural Networks. CG 2000, postscript
- Vladan Vučković, Rade Šolak (2009). Time Management Procedure in Computer Chess. Facta Universitatis, Automatic Control and Robotics, Vol. 8, No. 1
- Rade Šolak, Vladan Vučković (2009). Time Management during a Chess Game. ICGA Journal, Vol. 32 No. 4
- Shih-Chieh Huang, Rémi Coulom, Shun-Shii Lin (2011). Time Management for Monte-Carlo Tree Search Applied to the Game of Go. TAAI 2010, pdf
- Hendrik Baier, Mark Winands (2011). Time Management for Monte-Carlo Tree Search in Go. Advances in Computer Games 13
- Hendrik Baier, Mark Winands (2016). Time Management for Monte Carlo Tree Search. IEEE Transactions on Computational Intelligence and AI in Games, Vol. 8, No. 3, draft as pdf
Forum Posts
1993 ...
- Open Letter To Chess Computer Programmers by Kevin Gowen, rec.games.chess, December 26, 1993
- Computer chess strategy by Al, rgcc, April 22, 1997
- Time usage by John Bartkiw, CCC, December 08, 1997
- How to program search timeout ? by Rudolf Posch, CCC, February 04, 1998
- How much time per move? by Andrew Williams, CCC, March 02, 1998
- Time control legend by Don Dailey, CCC, May 13, 1998
2000 ...
- Question: Fail low at root and time management by William Bryant, CCC, February 08, 2000 » Fail-Low, Root
- new idea on managing time using depth reduction at root by Scott Farrell, CCC, February 08, 2003
- finding when a move is obvious by Eric Oldre, CCC, April 13, 2004
- question about fixing the time management of movei by Uri Blass, CCC, July 25, 2004
2005 ...
- Where to put timeout() code in search? by Stuart Cracraft, CCC, July 18, 2007
- obvious/easy move by Charles Roberson, CCC, March 12, 2008
- Crafty (and others?) time management question by John Merlino, CCC, April 14, 2009
- Time managment on ponder hit by Mathieu Pagé, CCC, June 16, 2009 » Pondering
- Info from timeout search by Michel Van den Bergh, CCC, October 26, 2009
2010 ...
- As though they were pondering by Gabor Szots, CCC, July 23, 2010 » Pondering
- Move on Hash Hit by kingliveson, OpenChess Forum, August 18, 2010 » Pondering
- New Time Controls for WB by Matthias Gemuh, CCC, August 30, 2010 » Chess Engine Communication Protocol, WinBoard, ChessGUI
2012
- Sudden death time controls by Larry Kaufman, CCC, May 10, 2012
- Winboard protocol and fractional increments by Jon Dart, CCC, September 25, 2012 » Chess Engine Communication Protocol, WinBoard
- Adjustable search pruning depending on time control by Jerry Donald, CCC, December 20, 2012 » Pruning, Late Move Reductions
2013
- "panic time" and "easy moves" by Robert Hyatt, CCC, February 16, 2013
- Yet another time allocation heuristic by Steven Edwards, CCC, February 17, 2013
- easy-hard moves (again) by Robert Hyatt, CCC, March 08, 2013
- Easy easy move by Harm Geert Muller, CCC, August 02, 2013
- out-of-time: what to do? by Folkert van Heusden, CCC, August 09, 2013
- Losing on time by Gregory Strong, CCC, December 31, 2013
2014
- Time control comparison between engines by Ed Schroder, CCC, January 01, 2014
- fixed time control management by Daniel Shawul, CCC, February 01, 2014
- Question about Time Management by ambrooks1, Winboard Forum, February 06, 2014
- Move time and compiler optimization by Edmund Moshammer, CCC, March 23, 2014
- Playing strength development - increasing time control by Andreas Strangmüller, CCC, April 17, 2014
- Time based contempt by Michel Van den Bergh, April 20, 2014 » Contempt Factor
- Time Management by Larry Kaufman, CCC, May 29, 2014
2015 ...
- Elo gain and optimal time management by Kai Laskos, CCC, January 11, 2015
- What's the fastest time control you can effectively test at? by Jordan Bray, CCC, May 30, 2015
2016
- Photographing Chess Clock by Harm Geert Muller, CCC, October 10, 2016
- Doubling of time control by Andreas Strangmüller, CCC, October 21, 2016 » Doubling TC, Diminishing Returns, Playing Strength, Komodo
- New idea for "easy move detection" by Rasmus Althoff, CCC, November 05, 2016 » CT800
- Stockfish 8 - Double time control vs. 2 threads by Andreas Strangmüller, CCC, November 15, 2016 » Doubling TC, Diminishing Returns, Playing Strength, Stockfish
- On time management by Rasmus Althoff, CCC, December 24, 2016
2017
- Time managment ? by Mahmoud Uthman, CCC, March 07, 2017
- Time management ideas by lucasart, OpenChess Forum, April 03, 2017
- Invariance with time control of rating schemes by Kai Laskos, CCC, July 22, 2017 [6]
- Time Managment translating to SMP by Andrew Grant, CCC, December 23, 2017 » Parallel Search
2018
- Time control envelope in top engines could be improved? by Kai Laskos, CCC, March 13, 2018 » Match Statistics, Playing Strength
- easy move? by Folkert van Heusden, CCC, October 19, 2018
- Re: easy move? by Álvaro Begué, CCC, October 19, 2018
External Links
- Time Allocation from Bruce Moreland's Programming Topics
- Time control from Wikipedia
- Time management from Wikipedia
- Time Management by Edward Scimia from About Chess
- Timing with a neural network by Volker Annuss, March 23, 2005, from Free chess graphical user interface (GUI) Arena for chess engines, News-Ticker, Page 6, 86, FQ
- Time Management During a Chess Game by Dan Heisman
- Time of check to time of use from Wikipedia
- Buddy Rich - Time Check, at The Top of the Plaza in Rochester, NY, February 6, 1973, YouTube Video
- Hiromi’s Sonicbloom - Time Difference, 2007, YouTube Video
- Hiromi Uehara, David Fiuczynski, Tony Grey, Jordan Perlson - Time Out, XI Festival de Jazz de San Javier, 2008, YouTube Video
References
- ↑ The Streatham & Brixton Chess Blog: Chess in Art Postscript: Chess-in-Artists do for Christmas The site Roland La Tuffo Barczik Hungarian artist, La Tuffo's Artwork, Barcsik's Chess Art no longer available
- ↑ History of the clocks from DGT - Digital Game Technology
- ↑ Digital chess clock - Google Patent Search
- ↑ question about fixing the time management of movei by Uri Blass from CCC, July 25, 2004
- ↑ Robert Hyatt (1984). Using Time Wisely. ICCA Journal, Vol. 7, No. 1
- ↑ Normalized Elo (pdf) by Michel Van den Bergh