Iterative deepening and time management
Stage 6 · tag stage-06-iterative · code in crates/engine/src/lib.rs and time.rs
Stage 5 searched to a fixed depth. That’s fine for a puzzle, but in a real game the engine has a clock, and it can’t know in advance how long depth 7 will take in a given position. Too shallow wastes time it could have used, and too deep can lose on time. This stage fixes that with two ideas found in every modern engine:
- iterative deepening: search depth 1, then 2, then 3, and so on, until the time is up;
- time management: decide, from the clock, how long that is.
Iterative deepening
Searching depth 1, then depth 2, then depth 3 sounds wasteful, since each search repeats all the work of the one before. In practice it costs little. Each depth takes several times longer than the previous one (the effective branching factor: between 5 and 15 for cb2026 right now), so all the shallower searches together add only a fraction of the last one.
In return:
- There’s always an answer. When time runs out in the middle of depth 8, the engine still has the complete result of depth 7 to fall back on.
- Each depth helps the next. The best move from depth d is searched first at depth d + 1. Alpha-beta prunes best when the best move comes first (chapter 5), so this ordering pays for much of the repeated work. Stages 8 and 10 add a transposition table and better move ordering, which use the shallower searches even more, until iterative deepening is faster than going straight to the final depth.
- GUIs see progress. After each depth the engine reports what it found, which is what scrolls by in a GUI’s analysis pane.
/// Chooses a move in `position`.
///
/// `history` holds the hash keys of the earlier positions in the game. `stop` may be set by
/// another thread to end the search early. `on_info` is called after each completed depth,
/// and once more for a depth cut short if it found a move worth playing.
///
/// The search uses **iterative deepening**: it searches to depth 1, then 2, then 3, and so
/// on, until a limit says stop. Each depth starts with the best move of the one before,
/// and when time runs out mid-depth the engine still has a complete answer to fall back on.
pub fn search(
&mut self,
position: &Position,
history: &[u64],
limits: &Limits,
stop: &AtomicBool,
on_info: &mut dyn FnMut(&SearchInfo),
) -> SearchResult {
self.search_following_root(position, history, limits, stop, on_info, None)
}
/// [`Engine::search`], also telling `on_root`, if given, where the main thread's root loop
/// is as it goes: at each root move, whenever the search looks at the clock, and at once
/// when the search goes back over something ([`root`]). The search is the same, node for
/// node, followed or not.
pub fn search_following_root(
&mut self,
position: &Position,
history: &[u64],
limits: &Limits,
stop: &AtomicBool,
on_info: &mut dyn FnMut(&SearchInfo),
on_root: Option<&mut dyn FnMut(&RootInfo<'_>)>,
) -> SearchResult {
let start = Instant::now();
let mut root_moves: Vec<Move> = position
.legal_moves()
.iter()
.copied()
.filter(|mv| limits.search_moves.is_empty() || limits.search_moves.contains(mv))
.collect();
if root_moves.is_empty() {
return SearchResult::default();
}
// The opening book: play its move at once (unless asked to analyse).
if self.own_book
&& !limits.infinite
&& limits.search_moves.is_empty()
&& let Some(book) = &self.book
{
// The dice: the clock's nanoseconds, mixed with the position.
let nanos = std::time::SystemTime::now()
.duration_since(std::time::UNIX_EPOCH)
.map_or(0, |d| d.subsec_nanos());
let random = u64::from(nanos) ^ position.hash();
if let Some(mv) = book.pick(position, random)
&& root_moves.contains(&mv)
{
return SearchResult {
best_move: Some(mv),
..SearchResult::default()
};
}
}
if self.techniques.mvv_lva {
ordering::order_moves(position, &mut root_moves);
}
self.tt.set_buckets(self.techniques.tt_buckets);
// The previous search often left a best move for this position.
self.tt.new_search();
self.ordering.new_search();
if self.techniques.tt
&& let Some(mv) = self.tt.probe(position.hash()).and_then(|e| e.best_move)
&& let Some(at) = root_moves.iter().position(|&m| m == mv)
{
root_moves[..=at].rotate_right(1);
}
// In a tablebase position, keep only the move the tables recommend: it keeps the best
// result and makes progress under the fifty-move rule. The search still runs (and
// reports), but can only choose that move.
if let Some(tb) = &self.tablebase
&& tablebase::covers(tb.as_ref(), &self.tablebase_params, position)
&& let Some((_, mv)) = tb.probe_root(position)
&& root_moves.contains(&mv)
{
root_moves = vec![mv];
}
// A weaker level searches fewer nodes and several lines to choose from.
let level = levels::settings_at(self.level());
let mut level_limits = limits.clone();
if let Some(nodes) = level.nodes {
level_limits.nodes = Some(limits.nodes.map_or(nodes, |n| n.min(nodes)));
}
// Now and then, only as far ahead as a person would look (see `levels`), on one
// thread. Never when analysing.
let horizon = (!limits.infinite)
.then(|| levels::horizon(&level, dice(position)))
.flatten();
if let Some(plies) = horizon {
level_limits.depth = Some(plies);
}
let limits = &level_limits;
let lines = self.multipv.max(level.candidates).max(1);
// The levels were calibrated with the hand-crafted evaluation (chapter 19), so below
// full strength the search keeps it: their ratings stay true. Calibrating them again
// with a network is for later.
let full_strength = self.level() >= f64::from(levels::FULL_STRENGTH);
let budget = time::budget(limits, position.side_to_move(), &self.time);
let unlimited = limits.depth.is_none()
&& limits.nodes.is_none()
&& limits.mate.is_none()
&& budget.hard.is_none()
&& !limits.infinite;
let mut max_depth = limits
.depth
.unwrap_or(if unlimited { DEFAULT_DEPTH } else { MAX_PLY });
if let Some(moves) = limits.mate {
// A mate in N moves is 2N - 1 plies away.
max_depth = max_depth.min(2 * moves);
}
let max_depth = max_depth.clamp(1, MAX_PLY);
let deadline = budget.hard.map(|hard| start + hard);
let root_fallback = root_moves.first().copied();
// Lazy SMP (stage 17): helper threads search the same position, sharing only the
// transposition table. They stop when the main thread is done.
let helpers_stop = AtomicBool::new(false);
let helper_nodes = AtomicU64::new(0);
let Engine {
params,
techniques,
search_params,
tt,
ordering,
correction,
threads,
tablebase,
tablebase_params,
multipv,
time,
network,
..
} = self;
let tablebase = tablebase.as_deref();
// The network, if the search is to evaluate with one.
let network = network
.as_deref()
.filter(|_| techniques.nnue && full_strength);
let self_multipv = (*multipv).max(1);
let tablebase_params = *tablebase_params;
let techniques = match horizon {
Some(_) => Techniques::horizon(),
None => *techniques,
};
let threads = if horizon.is_some() { 1 } else { *threads };
let (params, search_params, tt) = (&*params, *search_params, &*tt);
thread::scope(|scope| {
let mut helper_threads = Vec::new();
for helper in 1..threads {
let root_moves = root_moves.clone();
let (helpers_stop, helper_nodes) = (&helpers_stop, &helper_nodes);
helper_threads.push(scope.spawn(move || {
let mut ordering = OrderingTables::default();
let mut correction = CorrectionHistory::default();
let mut searcher = Searcher::new(
params,
search_params,
tt,
&mut ordering,
techniques,
StopConditions {
stop: helpers_stop,
deadline,
max_nodes: None,
},
history,
);
searcher.count_nodes_in(helper_nodes);
searcher.use_correction(&mut correction);
if let Some(tb) = tablebase {
searcher.use_tablebase(tb, tablebase_params);
}
if let Some(net) = network {
searcher.use_network(net);
}
run_helper(&mut searcher, position, root_moves, max_depth, helper);
searcher.stats()
}));
}
let mut searcher = Searcher::new(
params,
search_params,
tt,
ordering,
techniques,
StopConditions {
stop,
deadline,
max_nodes: limits.nodes,
},
history,
);
searcher.use_correction(correction);
if let Some(tb) = tablebase {
searcher.use_tablebase(tb, tablebase_params);
}
if let Some(net) = network {
searcher.use_network(net);
}
if let Some(on_root) = on_root {
let follower = RootFollower::new(on_root, start, &helper_nodes, self_multipv);
searcher.follow_root(follower);
}
let result = main_search(
&mut searcher,
MainSearch {
position,
root_moves,
max_depth,
start,
budget,
time,
helper_nodes: &helper_nodes,
lines,
reported: self_multipv,
},
on_info,
);
helpers_stop.store(true, Ordering::Relaxed);
let mut stats = searcher.stats();
for helper in helper_threads {
if let Ok(helper_stats) = helper.join() {
stats.add(&helper_stats);
}
}
let Some(best) = result.first() else {
return SearchResult {
best_move: root_fallback,
ponder_move: None,
stats,
};
};
// At full strength, the best line; at a lower level, one of the candidates.
let candidates: Vec<(Move, i32)> = result
.iter()
.filter_map(|line| line.best_move.map(|mv| (mv, line.score)))
.collect();
let chosen = levels::choose(&candidates, &level, dice(position)).or(best.best_move);
let line = result
.iter()
.find(|line| line.best_move == chosen)
.unwrap_or(best);
let best_move = chosen.or(root_fallback);
// The expected reply is the line's second move. A line cut short (by a
// transposition table cutoff just below the root) may not have one; then the
// table's best move for the position after ours is the next best guess.
let ponder_move = line.pv.get(1).copied().or_else(|| {
let mut after = position.clone();
after.make_move(best_move?);
tt.probe(after.hash())
.and_then(|entry| entry.best_move)
.filter(|mv| after.legal_moves().contains(mv))
});
SearchResult {
best_move,
ponder_move,
stats,
}
})
}When the search is stopped in the middle of a depth, the moves already searched at that depth are still useful. The first one is last depth’s best move, searched deeper, so if any move finished, the engine plays the best of those. If none finished, it plays the best move from the previous depth.
The loop also ends early when it finds a forced mate: a mate within d plies found by a full-width search can’t be improved by searching deeper.
Time management
With a clock, the engine has to share its remaining time among all the moves still to play. cb2026 sets two limits per move:
- Soft limit: after finishing a depth, don’t start the next one if this much time has gone. The next depth would probably take several times longer, so starting it late mostly wastes time.
- Hard limit: stop at once, even mid-depth. It is the safety net for a depth that takes far longer than expected.
/// The time manager's tunable numbers.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct TimeParams {
/// When the time control doesn't say, plan as if this many moves remain.
pub moves_to_go: u32,
/// Percentage of the increment added to each move's budget.
pub increment_percent: u32,
/// The hard limit is this many times the soft limit.
pub hard_factor: u32,
/// Time held back for communication delays (the UCI option `Move Overhead`).
pub move_overhead: Duration,
/// Scale the soft limit by how long the best move has stayed the same (`set tmstability`).
pub best_move_stability: bool,
/// The soft limit's scale, in percent, when the best move has stayed the same for 0, 1, 2,
/// 3, and 4 or more depths in a row.
pub stability_percent: [u32; 5],
/// Think longer when the score falls from one depth to the next (`set tmscore`)...
pub falling_score: bool,
/// ...by this many percent per centipawn it fell...
pub falling_score_percent_per_cp: u32,
/// ...counting at most this many centipawns.
pub falling_score_max_cp: u32,
}
impl Default for TimeParams {
fn default() -> TimeParams {
TimeParams {
moves_to_go: 30,
increment_percent: 75,
hard_factor: 3,
move_overhead: Duration::from_millis(30),
best_move_stability: true,
stability_percent: [180, 140, 110, 90, 75],
falling_score: true,
falling_score_percent_per_cp: 1,
falling_score_max_cp: 100,
}
}
}(The fields after move_overhead came later, in chapter 6.1.)
/// The time budget for a search with `limits`, with `side` to move.
pub fn budget(limits: &Limits, side: Color, params: &TimeParams) -> TimeBudget {
if let Some(movetime) = limits.movetime {
let usable = movetime.saturating_sub(params.move_overhead);
return TimeBudget {
soft: Some(usable),
hard: Some(usable),
adaptive: false,
};
}
let Some(remaining) = limits.time[side.index()] else {
return TimeBudget::default();
};
let remaining = remaining.saturating_sub(params.move_overhead);
let increment = limits.increment[side.index()].unwrap_or(Duration::ZERO);
let moves_left = limits
.moves_to_go
.unwrap_or(params.moves_to_go)
.clamp(1, params.moves_to_go);
let ceiling = remaining / 2;
let soft = remaining / moves_left + increment * params.increment_percent / 100;
TimeBudget {
soft: Some(soft.min(ceiling)),
hard: Some((soft * params.hard_factor).min(ceiling)),
adaptive: true,
}
}For example, with 60 seconds left and a 1-second increment:
- the soft limit is (60 s − 30 ms) / 30 + 0.75 s = 2.75 s;
- the hard limit is three times that, 8.25 s.
Neither limit may exceed half the remaining time, so a short clock with a large increment
can’t flag. Move Overhead (a UCI option, 30 ms by default) is held back for the time the GUI
and operating system take to pass messages. Raise it if cb2026 ever loses on time in a GUI or
on a server.
Here’s what that looks like in UCI with go wtime 60000 btime 60000 winc 1000 binc 1000 from the
starting position:
info depth 5 seldepth 5 score cp 100 nodes 38434 time 5 pv b2b3 b8a6 c1b2 a6b4 b2g7
info depth 6 seldepth 6 score cp -100 nodes 289817 time 40 pv b2b3 b7b6 b1a3 c8a6 g1f3 a6e2
info depth 7 seldepth 7 score cp 100 nodes 1522091 time 194 pv b2b3 b8a6 b1a3 a6b4 a3b5 b4d5 b5a7
info depth 8 seldepth 8 score cp -100 nodes 21698796 time 3096 pv b2b3 b8c6 b1a3 g8f6 g1f3 c6b4 a3b1 b4a2
bestmove b2b3 ponder b8c6
Depth 7 finished at 0.19 s, well under the 2.75 s soft limit, so depth 8 started. It finished at 3.1 s, past the soft limit, so the engine stopped there instead of starting depth 9, which would have taken far longer. The scores also flip between +1 and −1 from one depth to the next. That is the horizon effect: the search stops in the middle of an exchange and counts a piece that is about to be recaptured. Stage 7’s quiescence search fixes it.
In the shell
The shell now thinks for one second per move by default and shows each depth as it goes:
> fen r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1
> go
depth 1 +3.30 48 nodes 0 ms Bxa6
depth 2 +0.10 202 nodes 0 ms Bxa6 bxc3
depth 3 +3.30 7466 nodes 1 ms Bxa6 bxc3 Qxf6
depth 4 +0.10 29664 nodes 5 ms Bxa6 hxg2 Qxg2 bxc3
depth 5 +2.30 2105269 nodes 401 ms Bxa6 hxg2 Rg1 bxc3 Qxf6
depth 6 -0.90 4734976 nodes 970 ms Bxa6 bxc3 bxc3 exd5 Nd3 Nxe4
cb2026 plays Bxa6 (depth 6, -0.90, 4734976 nodes, 970 ms)
Depth 6 didn’t finish within the second. The line shown for it covers only the moves searched before time ran out, starting with Bxa6.
set movetime MSsets the thinking time;set depth Nswitches back to a fixed depth;think offhides the per-depth lines.
Pitfalls
- Checking the clock too often is slow. Reading the time costs far more than visiting a node, so the search checks it every 1024 nodes.
- Trusting an unfinished depth too much. Its result is only reliable for the moves it finished. That’s why the previous best move is always searched first, and why an iteration that finished no move is thrown away.
- Forgetting the overhead. An engine that plans to use exactly its remaining time
loses on time, because the GUI measures from when it sent
goto when it receivedbestmove.
What it’s worth
| Test | Result |
|---|---|
| Stage 6 vs stage 5, 8+0.08, SPRT [0, 5] | +33 −0 =8 over 41 games: passed (about +390 ± 140 Elo) |
Most of the gain comes from using the clock well: stage 5 always searched to depth 4, which took a few milliseconds in quiet positions and far too long in sharp ones.
Further reading
- Chess Programming Wiki: Iterative Deepening, Time Management, Horizon Effect.
- David Slate and Larry Atkin, “CHESS 4.5 – The Northwestern University Chess Program”, in Chess Skill in Man and Machine (1977): where iterative deepening became standard.