Search Algorithms
Pikafish does not search every variation to the same depth. It tries promising moves first and looks further into critical lines, while spending less time on less promising branches or stopping them early. NNUE scores positions; search compares what happens after further moves.
This page was checked against official Pikafish commit 1c66b9b. Every method described below appears in that code. Thresholds change between versions, so the focus is on what each method does, rather than treating tuning constants as fixed rules. Source links and further reading from Chessprogramming Wiki and other sources are listed at the end.
Related pages: Source Code Guide, Position Evaluation and NNUE, Position State and Rules, Engine Runtime and Communication.
The Big Picture: What Happens During a Search?
Think of search as repeatedly doing a few things:
- Check whether the position has triggered a win, loss, draw, repetition, or another rule.
- Check the cache for an earlier result or a useful move.
- Generate candidate moves, try promising ones first, and reject illegal moves such as those that leave the king in check.
- Make a move, let the opponent take their turn in the search, and bring the result back; then undo the move.
- Use the result to decide whether to search deeper, search again, or stop some branches.
This outlines a search. Evaluation, pruning, and depth adjustments are interleaved in the implementation; the sections below explain the problem each method solves.
| Problem to solve | Methods used by Pikafish |
|---|---|
| How do we compare moves when both sides choose what is best for them? | Alpha-Beta in Negamax form, Principal Variation Search (PVS) |
| With limited time, how deep should we search first? | Iterative deepening, aspiration windows, time management |
| Which move comes first, and can earlier work be reused? | Move ordering, history heuristics, Static Exchange Evaluation (SEE), transposition table (TT) |
| What if the depth limit is reached halfway through an exchange? | Quiescence search |
| Where should we search less, and where should we search more? | Null-move pruning, ProbCut, futility pruning, LMR, IIR, singular extensions, and more |
| How are Xiangqi moves and rules handled? | Bitboards and attack tables, legality checks, checks/chases/repetition and move-limit adjudication |
Minimax and Negamax: Whose Score Is It?
First, suppose every score is from Red's perspective: a larger value favors Red, and a smaller value favors Black. Red chooses the maximum on Red's turn; Black chooses the minimum on Black's turn. This is Minimax. The engine must consider not just what it can capture, but also the opponent's strongest reply.
Negamax combines the two cases: the score is always from the side-to-move's perspective, so changing sides reverses the sign. If the opponent sees a score of -80 after our move, that is +80 for us. Both sides can then simply choose the maximum, with recursion written as score = -search(...).
One ply means one move by one side; one move each by Red and Black makes two plies. The example scores only illustrate comparisons, not the fixed value of any piece.
Alpha-Beta: Stop When More Work Cannot Change the Choice
Suppose Red already has a line worth +50, even against Black's best reply. While checking another line, Red finds a reply that lets Black hold the score to +30. That line cannot improve on the first one. Whether Black can push it down further to +10 no longer affects Red's choice, so the remaining work can be skipped.
Alpha-Beta uses alpha and beta to describe the score window that matters to this search:
alpha: the threshold to beat. A result no higher than this cannot improve the current choice.beta: reaching this is enough for the parent to reject the line, without needing its exact score.
The window specifies the score thresholds relevant to this search. A result no higher than the original alpha is a fail-low and provides an upper bound; a result at least as high as beta is a fail-high and provides a lower bound. A result inside the window is exact for that depth and evaluation scheme. Fail-soft permits scores outside the window, retaining their associated bound types.
Basic Alpha-Beta alone gives the same result as full Minimax when searching the same tree with the same leaf evaluations. Null-move pruning, futility pruning, and reductions add heuristic assumptions, so that guarantee does not automatically extend to them.
Expand: a basic Negamax / Alpha-Beta example
The teaching pseudocode below shows the Negamax and Alpha-Beta skeleton. terminal_score() handles terminals and rules first, including a loss for having no legal move in Xiangqi. Scores are from the side to move. This example evaluates at the depth limit; the corresponding Pikafish path enters quiescence search.
int search(int depth, int alpha, int beta) {
if (auto result = terminal_score(); result.has_value())
return *result;
if (depth <= 0)
return evaluate_side_to_move();
int best = -INF;
for (Move move : ordered_legal_moves()) {
make_move(move);
int score = -search(depth - 1, -beta, -alpha);
undo_move(move);
best = std::max(best, score);
alpha = std::max(alpha, score);
if (alpha >= beta)
break;
}
return best;
}The sign reversal applies to both the returned score and the child window, which becomes (-beta, -alpha). Use a safely chosen, sufficiently large constant for INF; negating the minimum integer value can overflow.
PVS: First Ask Whether Another Move Can Do Better
PVS (Principal Variation Search) relies on good moves often appearing early in the move order. At a principal-variation node, it searches the first move with the full window to establish a useful candidate. Later moves first get a very narrow window: “Can this beat the current best?” If a move looks promising, it is searched again with the full window when needed.
For integer scores, a window such as (alpha, alpha + 1) is usually called a zero window. It mainly answers whether the threshold can be beaten; no integer score lies strictly between its endpoints.
Pikafish combines PVS with LMR: later candidates may be searched shallowly, then deeper if promising. Window width determines the precision of the question; depth determines how far ahead it looks. Zero-window search plays real moves; null-move search temporarily changes turns to test the result of passing.
Source: recursive search with PVS and LMR.
A PVS Probe with Concrete Numbers
Suppose the first move returned +50. Later moves are initially tested with (50, 51):
| Returned result | Information obtained | Next step |
|---|---|---|
| At most 50 | An upper bound that fails to beat the threshold. | Try the next candidate. |
| At least 51 | A lower bound that beats the threshold. | Widen the window and restore depth when re-search conditions hold. |
A fail-soft return of 65 still carries its lower-bound meaning; a re-search establishes how good the candidate is. See recursive search for the PVS/LMR combination.
Iterative Deepening and Aspiration Windows: Get an Answer, Then Improve It
Pikafish starts at a shallow depth and raises the target depth in successive passes. This is iterative deepening. The best move, principal variation, score, and cached results from a shallow search help the next pass find the important lines faster. When time runs out, the engine also has a result already available.
The root aspiration window starts around a candidate’s recent average score and considers score variability. A result far outside it triggers a wider window on the relevant side and another search, saving work on stable candidates while investigating unexpected changes.
depth 20 is an iteration’s target depth. Reductions, extensions, and quiescence search give branches different actual depths. The principal variation (PV) shows the main line currently expected from both sides and can change with further work.
Source: the iterative loop and window adjustments.
Move Generation: List the Candidates, Then Check Legality
Generation, legality checks, and ordering answer three different questions: what are the candidates, which are legal, and which should be searched first?
The generator can produce captures (CAPTURES), non-captures (QUIETS), check evasions (EVASIONS), or all pseudo-legal moves (PSEUDO_LEGAL). Pseudo-legal means a move follows the basic movement rules but may still leave its own king in check. The main search calls pos.legal() after taking a candidate. When a complete legal list is needed directly, LEGAL generation also filters the moves.
Here, “quiet” simply means a non-capture; it can still give check.
Cases That Need Special Care in Xiangqi
- Cannons: a non-capturing move follows an unobstructed straight line; a capture must jump exactly one screen. Moving a friendly screen away can sometimes evade a cannon check.
- Horses and elephants: attacks must account for blocked horse legs, blocked elephant eyes, and the elephant's river restriction. The corresponding attack rules also handle sideways pawn moves after crossing the river and the palace boundaries for kings and advisors.
- King safety: a move must not leave its own king under attack, including directly facing the opposing king.
- Multiple checks: the chess rule that “only a king move can answer a double check” cannot simply be copied into Xiangqi. When there are multiple checking pieces, the current implementation generates all pseudo-legal moves and filters for legal responses.
Given a candidate that already follows the basic movement rules, legal() mainly checks whether its own king is safe after the move. History-dependent issues such as perpetual check and perpetual chase are handled by the rule logic described later.
Sources: move categories and evasion generation, king-safety checks.
Bitboards and Attack Tables: Handle Many Squares at Once
A bitboard represents a set of squares as bits, such as “all squares occupied by Red” or “all squares this horse attacks.” Bitwise operations such as intersection and union then process many squares at once. Pikafish uses 128-bit bitboards for Xiangqi's 90 squares, alongside an array for looking up the piece on each square.
Attacks by chariots, cannons, horses, elephants, and other pieces are looked up in precomputed tables. The normal compilation path uses magic multiplication and shifts to calculate an index; the USE_PEXT path uses PEXT / PDEP instructions. Which path is used depends on the build. This does not imply that one instruction is faster on every CPU.
Search makes a move when entering a branch and undoes it on return. Position state and hash keys are updated incrementally, avoiding a fresh scan of the entire board after every move.
Sources: the bitboard type, attack tables and indexing, making and undoing moves.
Move Ordering and History Heuristics: Try Promising Moves First
Good ordering finds strong moves sooner, helping Alpha-Beta stop other branches earlier. In the regular main search, the approximate move-picking order is:
- The candidate stored in the transposition table (TT move).
- Captures judged promising by quick checks such as SEE.
- Non-captures with good history scores.
- Less promising captures.
- Less promising non-captures.
MovePicker generates, scores, and picks candidates in stages, with separate flows for evasions, quiescence search, and ProbCut. “Good” and “bad” indicate priority; less promising captures can still be searched. High-history non-captures can precede less promising captures. This ordering mainly uses TT moves, capture history, and the different non-capture histories.
The history heuristic records move performance during search. Moves producing useful cutoffs or other results gain priority, while repeated poor results reduce it. These statistics live in the engine’s history tables.
The code uses main history, capture history, continuation history (which considers earlier moves), pawn-structure history, and history for plies near the root. Capture scoring combines the victim's value with capture history. Non-capture scoring also considers checks, escaping attacks by lower-value pieces, and moving into such attacks.
Sources: MovePicker stages and scoring, history table definitions.
SEE: A Quick Estimate of Whether an Exchange Loses Material
SEE (Static Exchange Evaluation) quickly estimates whether a sequence of exchanges on one square meets a gain threshold: we capture, the opponent recaptures, perhaps we capture again—roughly, do we gain or lose material? Pikafish's see_ge() answers whether the result is at least the given threshold.
SEE supports capture ordering, pruning, and screening non-captures for hanging pieces. It concentrates on exchange gains around the destination. Threats elsewhere and the follow-up to a sacrifice require further search.
Source: Static Exchange Evaluation.
The Transposition Table: Reuse Earlier Work
Different move orders can reach the same position. A transposition table (TT) uses a hash key to look up earlier search records, storing a candidate move, depth, score, bound type, static evaluation, and other information.
Recorded bounds belong to the depth, evaluation, and selective-search strategy that produced them; reuse requires checking those conditions.
| Entry type | Meaning |
|---|---|
EXACT | An exact returned value under the conditions of that search |
LOWER | A lower bound: the result is at least this good, often from a fail-high |
UPPER | An upper bound: the result is no higher than this, often from a fail-low |
A score can be reused to stop the search only when the depth, node type, bound, and other conditions permit it. Otherwise, the cached move can still be tried first. EXACT does not mean the final outcome of the game has been mathematically solved.
A Xiangqi position's value can also depend on move history and move limits. The current implementation includes rule checks and some safeguards when reusing cached results. Identical piece placement does not mean that the same result is unconditionally valid for every history.
Sources: TT data structures, probing and cutoffs in the main search. For memory settings, see Hash.
Quiescence Search: Do Not Stop Halfway Through an Exchange
Suppose the search reaches its depth limit just after we capture an enemy piece. An immediate evaluation might count a material gain while missing the opponent's recapture on the next move. Quiescence search (qsearch) continues selected tactical lines after the regular depth runs out, reducing errors caused by stopping midway through an exchange.
Current Pikafish normally continues with captures. When in check, it switches to evasion candidates instead of generating only captures.
- When not in check, the current static evaluation can serve as a stand-pat baseline, then worthwhile captures are searched to see whether they improve it. Stand pat is an approximate search baseline; play still requires a legal move.
- When in check, stand pat cannot be used: evasions must be considered. No legal response means a loss.
- Qsearch uses the transposition table, futility pruning, SEE, and other filters of its own. It does not exhaustively search every capture or every check.
- In Xiangqi, having no legal moves is a loss even when not in check. The current code also checks for this; the chess rule that stalemate is a draw does not apply.
Quiescence search still makes moves recursively. Static evaluation scores the current position. The two should not be confused.
Source: qsearch.
Pruning: Spend Time on Branches That Are More Likely to Matter
All the selective methods below appear in current Pikafish. They use static evaluation, depth, history, and the score window to decide where less work may be enough. They rely on heuristic assumptions and can be wrong; conditions, margins, and verification searches help control that risk. The table explains their purpose, not a complete set of trigger conditions.
| Method | Plain-language explanation |
|---|---|
| Razoring | When conditions such as a static score far below alpha hold, hand the position to quiescence search to check immediate tactics instead of continuing the original deeper search. |
| Reverse futility pruning | If the static score remains high enough after subtracting a margin, some nodes can return early and skip further search. |
| Null-move pruning | Internally try passing a turn. If a shallower search still gives a good enough result, searching every real move may be unnecessary. See below. |
| ProbCut | Try promising captures with quiescence search, then a shallower search if needed. A result above a threshold higher than beta may end the current subtree early. |
| Small ProbCut | Return early using a sufficiently deep TT lower bound that clearly exceeds an extra threshold, without repeating the full capture-testing process. |
| Move-count pruning / LMP | After enough candidates have been tried and other conditions hold, skip later non-captures. The move-count threshold varies. |
| Futility pruning of candidate moves | Use static evaluation, potential captured material, history, and expected depth to skip candidates that look unlikely to catch up with alpha. |
| History pruning | Stop investing search in some non-captures whose continuation or pawn-structure history is too poor. |
| SEE pruning | Skip some candidates when the quick exchange estimate shows too much of a loss. Thresholds vary with depth and other factors. |
Node type, check status, mate scores, material, history, and other conditions restrict these decisions. None of these methods should be read as applying to every position.
Separately, mate-distance pruning uses the number of plies from the root to tighten the possible bounds on mate scores. It removes searches that cannot improve the mate distance. This follows from score bounds and should be distinguished from the heuristic assumptions above.
Sources: node-level pruning, per-move filtering, mate-distance pruning.
Why Does a Null Move Help, and Where Can It Fail?
Null-move pruning tests the heuristic that a position remaining good enough after letting the opponent move should also have an adequate real move. It temporarily changes the turn and searches at reduced depth. This pass is an internal search device.
A position that worsens because the side must move is called zugzwang and breaks that assumption. The code restricts null moves using conditions such as being out of check and retaining a chariot, horse, or cannon. Deeper searches may verify from the original position. Reduction varies with conditions; verification reduces the risk of a wrong cutoff.
Reductions and Extensions: Look Further Where It Matters
Pruning skips some search; reductions initially search less deeply; extensions search further. Pikafish adjusts depth dynamically during search.
| Method | Role in the current implementation |
|---|---|
| LMR (Late Move Reductions) | Search later, less promising moves at lower depth first. If the result exceeds alpha, add depth as needed. The reduction depends on history, node type, and other factors, and can also apply to captures. |
| IIR (Internal Iterative Reductions) | Reduce the current node's depth when conditions such as the absence of a TT candidate hold. IID instead uses a preliminary shallow search to find a candidate. |
| Singular extension | Temporarily exclude an eligible TT candidate and search the other moves at reduced depth. If all alternatives fall well short, give the candidate more depth. |
| Multi-cut and negative extensions | During that search with the candidate excluded, alternatives that are still good enough may allow a cutoff. Under other conditions, the TT candidate's depth is reduced. |
A singular extension measures the gap between a TT candidate and alternatives in a restricted search. A standout candidate can gain depth even with several legal moves. Other depth adjustments also use node type, history, and search results.
Sources: IIR, singular extensions and related handling, LMR and re-searches.
NNUE and Evaluation Corrections: Scores Also Guide the Search
Search often needs an estimate of a position without playing further moves. Pikafish calls NNUE evaluation and uses the score together with corrections gathered during search. This helps evaluate leaves and also affects some pruning and depth-allocation decisions.
Correction history records discrepancies between static estimates and later search results. Statistics organized by pawn structure, other pieces, and earlier moves adjust relevant static scores. They are stored in search history tables; NNUE weights come from the loaded network file.
Keep the three roles distinct: NNUE estimates positions, history tables help with ordering or corrections, and search compares continuations. Together, they guide where the engine spends its time.
Sources: calculating and updating evaluation corrections, evaluation entry points in search.
Xiangqi Rules: The Same Board Can Be a Different Problem
Search must handle not only check and the absence of legal moves, but also perpetual check, perpetual chase, repetitions, move limits, and related rules. Seeing the same board again does not necessarily mean a draw.
rule_judge() first uses quick filters to determine whether history needs examination, then traces the state chain for checks and chases. Established rulings can return directly; some search repetitions provide bounds and continue with a narrower window.
Check move legality, historical adjudication, and cache applicability separately. See Position State and Rules for generation steps, cycle tracing, and intersections of chased-piece identities.
Source: repetition and rule handling. For background, see Questions About Xiangqi Rules.
Threads, MultiPV, and Time: Sharing the Search Budget
Multiple threads advance their own searches while sharing the transposition table; some history data is shared within NUMA nodes. Workers both duplicate work and benefit from information left by others. Gains depend on the position, hardware, and search conditions.
MultiPV keeps principal variations for several root candidates and requires additional root searches. It supports comparing alternatives; more candidates divide the computation budget available for one line.
Time management first sets a budget from remaining time, increment, moves to go, Move Overhead, and other inputs. It then adjusts this using factors such as a falling score and whether the best move is stable. Fixed time, node limits, and other constraints also affect when search stops. Iterative deepening lets the engine keep improving an available answer within these limits.
Sources: starting threads and selecting results, time budgeting, time adjustments during search. For related settings, see UCI Options.
Source Code and Further Reading
Where to Start in the Pikafish Source
All the links below are pinned to the commit checked for this page, so future changes will not shift the referenced lines:
search.cpp: iterative deepening, PVS, pruning, reductions, extensions, and quiescence search.movepick.cppandhistory.h: move-picking stages, ordering scores, and history statistics.movegen.cppandattacks.h: move generation and attacks.position.cpp: legality, making and undoing moves, SEE, and Xiangqi rules.tt.h,thread.cpp, andtimeman.cpp: caching, threads, and time allocation.
Understanding the Algorithms Further
Chessprogramming Wiki is useful for terminology and general ideas, but many of its examples concern chess. Distinguish general search techniques from game-specific rules. Whether Pikafish actually uses a method should be checked against the source linked on this page.
- Foundations and windows: Alpha-Beta, PVS, iterative deepening, aspiration windows.
- Ordering and reuse: move ordering, history heuristic, transposition table, SEE.
- Allocating search effort: quiescence search, null-move pruning, LMR, singular extensions.
- Supporting mechanisms: move generation, correction history.
- Original papers: Jonathan Schaeffer's The History Heuristic and Alpha-Beta Search Enhancements in Practice; David-Tabibi and Netanyahu's Verified Null-Move Pruning. These papers explain design ideas; their historical experiments and specific implementations are not equivalent to current Pikafish.
