Do Iterative Deepening Timed Search

We noted earlier that picking a depth limit for a negamax search is hard. In a tournament game, there is usually a time limit of some kind on moves. You want your player to use all the time it can to search deeper, but to be ready with an answer any time it runs out of time.

The key to "iterative deepening" is to notice that each extra level of recursion depth consists of as many calls as the total number of calls at lower depth. A search tree of depth d has b**d nodes. A search tree of depth d+1 has b**d leaf nodes.

To iterative deepen, make calls to best_move with depth 1, 2, 3, etc and remember the latest result returned. When it is time to make a move, stop the current recursion, and return the move given by the last complete recursion.

best_move(s1) = do
  d0 = 1
  while time remains
    m0 = argmin(m in moves(s1) | negamax(move(s1, m), d0))
    d0 = d0 + 1
  return m0


Missed Opportunity: In most game tournaments, one does not have a time limit per move, but instead has to make hard decisions about how to spend time over a series of moves. Clock management is hard; in our tournament, we will just set a per-move time limit.


prev index next