Search in chess: depth, plies, and principal variation

Search

Definition

In chess, “search” refers to the systematic exploration of possible move sequences to forecast future positions and evaluate which move is best. It is core to both human calculation (looking ahead through candidate moves) and computer chess (engines traversing a game tree of positions). Search depth is commonly measured in “plies,” where one ply equals a single move by one side (half-move).

Usage in Chess

Players and engines both use search to decide on moves, but they do it differently:

• Human search (calculation): Players develop a shortlist of candidate moves (Kotov’s method), then calculate forcing lines (checks, captures, threats), pruning bad branches using pattern knowledge and intuition. They often stop in “quiescent” positions—those free of immediate tactics—before evaluating.
• Engine search: Engines build and traverse a search tree, using depth limits, pruning, and transposition tables to reach many plies quickly. They combine search with an evaluation function and iterative deepening to refine the principal variation (best line) as time allows.

Key Concepts and Terminology

• Search tree: The branching structure of moves and replies. Typical branching factor in middlegames is high (≈30–40), so pruning is essential.
• Ply: One half-move. Depth “20” means 10 moves by each side.
• Principal Variation (PV): The current best line found by search.
• Iterative Deepening: Search to depth 1, then 2, etc., reusing information to improve move ordering.
• Alpha–Beta Pruning: A method that eliminates branches that cannot influence the final decision, dramatically reducing the number of nodes examined.
• Move Ordering: Trying likely best moves first (checks, captures, threats) makes alpha–beta far more effective.
• Transposition Tables: Hash tables storing previously evaluated positions so transposed positions don’t get re-searched.
• Quiescence Search: Extending the search in “noisy” positions (ongoing captures/checks) so the evaluation happens after tactical dust settles, mitigating the horizon effect.
• Pruning/Reductions: Techniques like null-move pruning, late move reductions, and singular extensions that cut or selectively deepen the tree.
• MCTS (Monte Carlo Tree Search): Used by systems like AlphaZero, guided by neural networks to evaluate and prioritize nodes without enumerating all tactics uniformly.

Strategic and Historical Significance

From Claude Shannon’s 1950 paper outlining “Type A” (brute force) and “Type B” (selective) search to modern neural-network-guided MCTS, search has defined the progress of computer chess. Alpha–beta pruning (formalized in the 1960s) enabled programs to look much deeper. IBM’s Deep Blue (1997) combined tremendous hardware with selective extensions, while AlphaZero (2017) showed that neural nets plus MCTS can discover powerful strategies with less brute-force enumeration. For humans, Alexander Kotov popularized the “tree of analysis” and candidate-move method (Think Like a Grandmaster, 1971), shaping how players learn to calculate.

Examples

1) Human calculation: a forcing line in the Italian/Two Knights

From the Two Knights Defense, White’s 4. Ng5 creates immediate tactical tension. A human “search” checks forcing replies and counter-replies to judge if ideas like Nxf7 or Bb5+ work in the concrete position:

Here, both sides must calculate accurately: White checks forcing tactics on f7, while Black weighs central counterplay with …e4 and the …Na5–c6 maneuver to challenge the bishop. The decision to continue tactical operations or to steer into a quieter structure comes from comparing final positions at the end of each branch.

2) Engine search and “deeper is different”

Engines often overturn shallow conclusions when they reach a higher depth. Consider a tactical motif where a seemingly safe material grab fails to a long forcing sequence. A shallow search might miss the final tactic; a deeper PV reveals it:

• Shallow PV (depth 10): 1. Qxe5? appears to win a pawn.
• Deeper PV (depth 18): …Qxf2+! 2. Kxf2 Ng4+ 3. Kg1 Nxe5 with an attack or material recovery, flipping the evaluation.
• Quiescence ensures the engine doesn’t evaluate immediately after 1. Qxe5? but continues through the forcing checks and captures first.

3) A calculation tree you can visualize: the Fried Liver spark

From the classic Fried Liver Attack, search quickly branches and must be pruned wisely. White’s 6. Nxf7!? forces concrete calculation and compels Black to find only moves:

Whether or not a player follows this forcing line in practice, the decision relies on accurately searching candidate branches and evaluating the resulting king safety—precisely what engines automate at massive scale.

Interesting Facts and Anecdotes

• Kotov’s “analysis tree” and candidate moves: Kotov advised listing all reasonable candidates and calculating each line “once and for all” to avoid going in circles—an early human analogue to structured search.
• Deep Blue (1997): Explored tens of millions of positions per second with selective extensions for checks and forcing moves, exemplifying brute-force plus pruning.
• AlphaZero (2017): Replaced hand-crafted evaluation and alpha–beta with neural networks guiding MCTS; its search emphasized quality of branches over sheer quantity.
• Horizon effect: A search that stops too early may miss a looming tactic just beyond its “horizon.” Quiescence and selective extensions were devised to reduce this.
• “Ply” and NPS: Engine strength grows with depth, but smart pruning/move ordering can outperform raw nodes-per-second; finding the right branch early is often worth millions of nodes.

Practical Tips: Improving Your Search (for Humans)

• Generate candidate moves first (checks, captures, threats), then add strong quiet moves.
• Calculate forcing lines deeply; in messy positions, don’t stop until you reach quiescence.
• Compare final positions, not just the first move; mentally note key “end nodes.”
• Use blunder checks: before playing, quickly search for the opponent’s strongest reply.
• Practice standard tactical motifs (pins, forks, discovered attacks) to prune faster by pattern.

Common Engine-Side Techniques (Conceptual)

• Alpha–beta with good move ordering (PV move first; then checks, captures, threats).
• Transposition tables to avoid re-searching equivalent positions.
• Iterative deepening to reuse information and allocate time intelligently.
• Quiescence search and check/capture extensions to avoid horizon pitfalls.
• Null-move pruning and late move reductions to cut unlikely branches.
• MCTS selection/expansion guided by policy and value nets in neural approaches.

Reference Games and Context

• Kasparov vs. Deep Blue, 1997: A landmark match highlighting the power of deep, pruned search at scale.
• Kotov’s writings (1971): Influential in teaching structured human calculation and avoiding “analysis paralysis.”
• AlphaZero self-play matches (2017): Demonstrated the effectiveness of neural-network-guided search (MCTS) over classical alpha–beta in some settings.