Game-Tree Search

Why Game-Tree Search Matters

A game opponent chooses moves too. A puzzle solver may ask whether some path reaches a goal; a game-playing program must ask which move remains good after the opponent chooses the least favorable reply. A promising one-move gain can become a loss after a forced response. Minimax turns that alternating choice into a precise value, and alpha-beta pruning avoids exploring replies that cannot change the decision.

The model here is a deterministic, alternating, two-player, zero-sum, perfect-information game. Every score is from one fixed player's perspective: MAX prefers larger scores; MIN prefers smaller scores. Terminal utilities are exact under the game rules; a static evaluation at a depth boundary is an estimate. A completed depth-limited search is exact for its specified evaluation tree, which can still misjudge the actual game.

This lesson builds from minimax to alpha-beta, then adds move ordering, iterative deepening, a bound-aware transposition table, and bounded quiescence search. The runnable example uses a small acyclic game graph so every value and cutoff can be checked without a board-game library. It also makes an interrupted search return the last fully completed iteration, a useful behavior when a game engine must choose under a budget.

Core Concepts and Terminology

A position is a complete game state, including whose turn it is and every rule-relevant right or history item. A move leads to another position. A ply is one player's move, so depth $2$ includes our move and the opponent's reply. Different move sequences may reach the same position: those are transpositions, even though they occupy different nodes in the expanded search tree.

Let $U(s)$ be a terminal utility, $E(s)$ a static evaluation in the same MAX-oriented score system, and $A(s)$ the legal moves. Define $\operatorname{opt}_s$ as maximum on MAX turns and minimum on MIN turns. Without quiescence, depth-limited minimax is

$$V_d(s)=\begin{cases}U(s)&\text{if }s\text{ is terminal},\\E(s)&\text{if }d=0,\\\operatorname{opt}_s\{V_{d-1}(\operatorname{result}(s,a)):a\in A(s)\}&\text{otherwise}.\end{cases}$$

The search carries an open alpha-beta window $(\alpha,\beta)$. Alpha reflects a lower alternative already available to MAX, and beta an upper alternative available to MIN. At a MAX node, increase alpha as better children appear; at a MIN node, decrease beta. If $\alpha\ge\beta$, remaining children cannot change the relevant ancestor's choice. A returned score outside the caller's window may be only a bound; it must not automatically be treated as an exact minimax value.

The diagram shows the depth-$2$ worked tree. Scores at leaves are MAX's utilities. After MIN branch $1$ establishes $3$, MAX can reject branch $2$ as soon as MIN finds reply $2$, and branch $3$ as soon as MIN finds reply $0$. The skipped replies are shown only to define the full input; the search does not evaluate them.

How Game-Tree Search Works, Step by Step

1. Set a score convention and terminal rules. Every utility and evaluation in these programs is from MAX's viewpoint. A position with no outgoing moves is terminal, and its supplied score is its utility. Real adapters must distinguish wins, losses, draws, stalemate, and forced passes according to their rules.
2. Start an iteration with a full window. For requested depth $d$, search the root with $(-\infty,+\infty)$. The driver tries $d=1,2,\ldots,D$. Keep a committed root score and move separate from the in-progress result.
3. Admit and probe. Before each call, enforce the global node budget. Count an admitted call, update peak active depth, and form the table key $(s,d,q)$. A matching EXACT entry can return directly; LOWER can return when its score is at least beta; UPPER can return when its score is at most alpha. Otherwise search normally. This implementation uses cache bounds only for immediate returns and does not tighten a non-cutting window.
4. Handle a terminal or horizon position. Terminal utility takes precedence. At depth zero with no tactical budget left, read the static evaluation. Otherwise depth zero enters the bounded quiescence policy described below.
5. Order and try moves. With ordering enabled, try the most recently recorded move for this state first, then sort by successor evaluation: descending for MAX, ascending for MIN, breaking remaining ties by original move index. At ordinary depth, all legal moves are candidates; during quiescence, only marked tactical moves are candidates.
6. Apply, recurse, undo. Append the child to the active path, search it, then remove it before processing its score. Python and Java use finally; C++ uses a scope guard whose destructor pops the path. An interruption unwinds through those same cleanup steps.
7. Back up and test the window. MAX raises its best score and alpha; MIN lowers its best score and beta. Stop scanning moves when $\alpha\ge\beta$. Update the selected move only on a strict improvement, so ties keep the first searched candidate. A cached bound's associated move is an ordering hint, not a promised exact principal variation.
8. Store what was proved. Save the caller's original window $(\alpha_0,\beta_0)$. After a searched non-base node returns $v$, store UPPER if $v\le\alpha_0$, LOWER if $v\ge\beta_0$, otherwise EXACT. Direct terminal/static reads are known exact for that horizon even when outside the window. An aborted call stores no result for itself; completed descendants may have valid entries.
9. Commit only after root completion. A completed full-window root result becomes the new committed answer. If a later iteration aborts, return the previous completed depth. If depth $1$ never completes, report NO_COMPLETED_DEPTH; its dummy score is not an evaluation and its move is not playable.

The quiescence policy is part of the searched model. The toy graph marks tactical edges explicitly. At depth zero, a nonterminal position can either stop with $E(s)$, called stand pat, or follow a tactical edge while decrementing $q$. At $q=0$ it must stop. Thus, with $T(s)$ the tactical successors,

$$Q_0(s)=E(s),\qquad Q_q(s)=\operatorname{opt}_s\left(\{E(s)\}\cup\{Q_{q-1}(t):t\in T(s)\}\right)\quad(q\gt0),$$

with terminal positions always returning $U(s)$. Ordinary-depth recursion decrements $d$ and preserves $q$; depth-zero tactical recursion preserves $d=0$ and decrements $q$. This bounds an active line by $D+Q$ plies. Stand pat is an explicit option in this demonstration's evaluation model. In chess it relies on additional assumptions, can fail in zugzwang, and must not be used to ignore check; checked positions require legal evasions. The sample has no check or repetition rules and is not a complete chess searcher.

flowchart TD
    A["Driver: next depth, full root window"] --> B["Search root"]
    B --> C{"Iteration completed?"}
    C -->|Yes| D["Commit root score and move"]
    D --> E{"Requested depth reached?"}
    E -->|No| A
    E -->|Yes| F["Return COMPLETE"]
    C -->|No| G["Return last completed result or NO_COMPLETED_DEPTH"]
    subgraph AB["Alpha-beta call"]
        H{"Node budget available?"} -->|No| I["Throw cancellation; unwind all path edits"]
        H -->|Yes| J["Count call; probe matching TT horizon"]
        J --> K{"Exact or cutoff-compatible entry?"}
        K -->|Yes| L["Return cached score and move"]
        K -->|No| M{"Terminal or depth-zero with no q budget?"}
        M -->|Yes| N["Read utility or evaluation; store EXACT"]
        M -->|No| O["At q node: initialize stand pat and test cutoff"]
        O --> P["Order all legal or tactical moves"]
        P --> Q{"Candidate left and window open?"}
        Q -->|Yes| R["Apply child; recurse; always undo"]
        R --> S["Back up score; update alpha or beta"]
        S --> Q
        Q -->|No| T["Store EXACT, LOWER, or UPPER; return"]
    end
    B -. "call entry" .-> H
    I -. "propagate abort" .-> C
    O -. "stand-pat cutoff" .-> T

Worked Example with a Full Trace

Use the exact graph in the first program fixture. Root $0$ is MAX with moves indexed $0,1,2$, leading to MIN positions $1,2,3$. Their static evaluations are $3,2,4$. MIN $1$ has terminal replies $4:3$ and $5:5$; MIN $2$ has $6:2$ and $7:9$; MIN $3$ has $8:0$ and $9:7$. All terminal positions are labeled MAX-to-move, keeping turn alternation consistent, though the label does not affect a terminal utility.

Enable the transposition table, disable move ordering, set quiescence limit $Q=0$, and request maximum depth $D=2$ with a total budget of $1{,}000{,}000$. Every iteration starts with empty active path and full root window, while the cache and ordering hints persist within the run. This tree has no useful transposition hits.

At depth $1$, only the child estimates are visible: $\max(3,2,4)=4$, so the provisional choice is move $2$, leading to state $3$. At depth $2$, the full minimax value is

$$\max\bigl(\min(3,5),\min(2,9),\min(0,7)\bigr)=\max(3,2,0)=3.$$

The complete call trace follows. A row is listed at admission time; its return and stored flag are determined after its descendants finish. All calls use $q=0$. Path length minus one is active ply depth; the remaining-depth column is the separate recursion argument. Every child is popped after its return.

The entry for MIN $2$ proves only that its value is at most $2$. Its true value happens to equal $2$ in this input, but that fact was not established by examining every reply. A cache must retain the weaker proven claim. Static and terminal reads, by contrast, establish exact values of their own requested horizons even when outside the caller's window.

After each pass, the active path is empty. The table contains $12$ distinct horizon entries; no lookups return early in this fixture. Move $0$ leads to state $1$, whose best MIN reply is state $4$. The returned move is a root action index, not an entire principal variation.

Implementation in Python, C++, and Java

Each complete program implements the same recurrence and prints the same output. The adapter represents a node as a MAX/MIN label, a bounded static or terminal score, and an ordered list of moves (child, tactical). Normal search uses every move. Quiescence uses only marked tactical moves plus the explicit stand-pat option. The active state is a path of immutable node IDs, so apply/undo is append/pop; a mutable board adapter must also restore pieces, side to move, rule rights, and its position key.

Input contract. Supply $1\le V\le64$ non-null nodes, at most $4096$ total edges, Boolean player/tactical labels, and integer scores in $[-1000,1000]$. A successor of state $s$ must have ID $t$ with $s\lt t\lt V$ and the opposite player label. This topological numbering deliberately excludes cycles and repetition adjudication; duplicate moves and transpositions are allowed. An empty move list means terminal, and its score is the supplied exact utility. The constructor copies the graph's move lists; a run does not change the caller's graph.

The start ID lies in $[0,V-1]$, requested depth in $[1,12]$, quiescence budget in $[0,6]$, and global admission budget in $[1,1{,}000{,}000]$. These finite limits keep demonstration recursion and counters bounded. A sentinel INF = 1_000_000 lies strictly outside all scores; C++ and Java use 64-bit counters. Invalid numeric sizes, scores, edges, and search ranges are rejected. The public operation is run; the recursive helper assumes those validations and initialized per-run state.

Cache compatibility. The exact key is $(s,d,q)$, including remaining normal depth and remaining tactical depth. A deeper heuristic search can return a different score, so this lesson does not substitute a deeper horizon's value for a shallower one. Hints can cross horizons because they only reorder legal candidates. Evaluation policy and graph are fixed throughout a run, the table is cleared for the next run, and integer IDs uniquely identify complete toy positions. Production hashing needs collision handling and all rule-relevant state in its identity.

Results and counters. run returns status, completed depth, committed score, committed root move index, six statistics, and history. Statistics are [nodes,evals,cutoffs,tt_hits,qnodes,peak]: admitted calls including table returns; actual score reads; move-loop or stand-pat window cutoffs; usable cache returns; all calls with normal depth zero, including terminal/cache calls; and maximum admitted active ply depth. A window cutoff counts even if it occurs on the last candidate, so it is not the number of skipped moves. History records each attempted depth, DONE or ABORT, its score/move, and five counter deltas; peak is a global maximum. An aborted history row has dummy score $0$ and move $-1$.

COMPLETE means every requested depth finished. PARTIAL returns the last finished depth and its legal root move when the root is nonterminal. NO_COMPLETED_DEPTH has completed depth $0$, dummy score $0$, and move $-1$; callers must choose a separate legal fallback. A terminal root also has move $-1$, but its score is meaningful. Budget exhaustion is detected on the next attempted admission: exactly consuming the budget does not invalidate a pass that already finished. Counters include work from an aborted iteration, and the path is restored before status is returned.

Python 3, C++14 or newer, and Java 17 or newer run the samples below; save the Java panel as Main.java. The fixtures cover pruning, ordering that hurts, transposition reuse, a horizon mistake corrected by a tactical extension, interruption, no completed pass, and a terminal root.

INF = 1_000_000


class Stopped(Exception):
    pass


class GameSearch:
    # A node has (MAX-to-move, static/terminal score, [(child, tactical), ...]).
    def __init__(self, nodes):
        if not 1 <= len(nodes) <= 64:
            raise ValueError("invalid state count")
        total = 0
        for s, (maximizing, score, moves) in enumerate(nodes):
            if type(maximizing) is not bool or type(score) is not int or not -1000 <= score <= 1000:
                raise ValueError("invalid node")
            total += len(moves)
            for child, tactical in moves:
                if (type(child) is not int or not s < child < len(nodes) or
                        type(tactical) is not bool or nodes[child][0] == maximizing):
                    raise ValueError("edges must go forward and alternate players")
        if total > 4096:
            raise ValueError("too many moves")
        self.game = [(m, v, [(child, tactical) for child, tactical in edges]) for m, v, edges in nodes]

    def save(self, key, value, move, flag):
        if self.use_tt:
            self.tt[key] = (value, move, flag)
        if move >= 0:
            self.hint[key[0]] = move
        return value, move

    def search(self, state, depth, qleft, alpha, beta):
        if self.stats[0] >= self.budget:
            raise Stopped()
        self.stats[0] += 1
        self.stats[5] = max(self.stats[5], len(self.path) - 1)
        if depth == 0:
            self.stats[4] += 1
        key = (state, depth, qleft)
        alpha0, beta0 = alpha, beta
        if self.use_tt and key in self.tt:
            value, move, flag = self.tt[key]
            if flag == "EXACT" or (flag == "LOWER" and value >= beta) or (flag == "UPPER" and value <= alpha):
                self.stats[3] += 1
                return value, move
        maximizing, evaluation, moves = self.game[state]
        if not moves or (depth == 0 and qleft == 0):
            self.stats[1] += 1
            return self.save(key, evaluation, -1, "EXACT")
        best, best_move = (-INF if maximizing else INF), -1
        if depth == 0:
            self.stats[1] += 1
            best = evaluation  # Stand pat: an explicit option in this toy q-game.
            if (maximizing and best >= beta) or (not maximizing and best <= alpha):
                self.stats[2] += 1
                return self.save(key, best, -1, "LOWER" if maximizing else "UPPER")
            if maximizing:
                alpha = max(alpha, best)
            else:
                beta = min(beta, best)
        order = [i for i, (_, tactical) in enumerate(moves) if depth > 0 or tactical]
        if self.ordering:
            order.sort(key=lambda i: (i != self.hint[state],
                       -self.game[moves[i][0]][1] if maximizing else self.game[moves[i][0]][1], i))
        for i in order:
            child = moves[i][0]
            self.path.append(child)  # Apply this move to the active state path.
            try:
                value, _ = self.search(child, max(0, depth - 1), qleft if depth > 0 else qleft - 1, alpha, beta)
            finally:
                self.path.pop()  # Undo also runs during cancellation.
            if (maximizing and value > best) or (not maximizing and value < best):
                best, best_move = value, i
            if maximizing:
                alpha = max(alpha, best)
            else:
                beta = min(beta, best)
            if alpha >= beta:
                self.stats[2] += 1
                break
        flag = "UPPER" if best <= alpha0 else "LOWER" if best >= beta0 else "EXACT"
        return self.save(key, best, best_move, flag)

    def run(self, start, max_depth, qlimit=0, node_budget=1_000_000, use_tt=True, ordering=True):
        if (type(start) is not int or not 0 <= start < len(self.game) or
                type(max_depth) is not int or not 1 <= max_depth <= 12 or
                type(qlimit) is not int or not 0 <= qlimit <= 6 or
                type(node_budget) is not int or not 1 <= node_budget <= 1_000_000 or
                type(use_tt) is not bool or type(ordering) is not bool):
            raise ValueError("invalid search parameters")
        self.use_tt, self.ordering, self.budget = use_tt, ordering, node_budget
        self.tt, self.path, self.hint = {}, [], [-1] * len(self.game)
        self.stats, history = [0] * 6, []
        completed, committed_value, committed_move = 0, 0, -1
        for depth in range(1, max_depth + 1):
            before = self.stats[:5]
            code, value, move = "DONE", 0, -1
            self.path.append(start)
            try:
                value, move = self.search(start, depth, qlimit, -INF, INF)
            except Stopped:
                code = "ABORT"
            finally:
                self.path.pop()
            if self.path:
                raise RuntimeError("undo failed")
            delta = [a - b for a, b in zip(self.stats[:5], before)]
            history.append((depth, code, value, move, delta))
            if code == "ABORT":
                status = "PARTIAL" if completed else "NO_COMPLETED_DEPTH"
                return status, completed, committed_value, committed_move, self.stats.copy(), history
            completed, committed_value, committed_move = depth, value, move
        return "COMPLETE", completed, committed_value, committed_move, self.stats.copy(), history


def show(name, game, depth, qlimit=0, budget=1_000_000, tt=True, ordering=False):
    result = GameSearch(game).run(0, depth, qlimit, budget, tt, ordering)
    status, done, score, move, stats, history = result
    print(f"{name}: {status}, depth={done}, score={score}, move={move}")
    labels = ("nodes", "evals", "cutoffs", "tt_hits", "qnodes", "peak")
    print(", ".join(f"{k}={v}" for k, v in zip(labels, stats)) + ", restored=YES")
    print("passes=[" + ",".join(f"{d}:{c}:{v}:{m}:{s[0]}" for d, c, v, m, s in history) + "]")


def main():
    tree = [(True, 0, [(1, False), (2, False), (3, False)]),
            (False, 3, [(4, False), (5, False)]), (False, 2, [(6, False), (7, False)]),
            (False, 4, [(8, False), (9, False)]),
            (True, 3, []), (True, 5, []), (True, 2, []), (True, 9, []), (True, 0, []), (True, 7, [])]
    shared = [(True, 0, [(1, False), (2, False)]),
              (False, 4, [(3, False), (4, False)]), (False, 3, [(3, False), (5, False)]),
              (True, 5, [(6, False), (7, False)]), (True, 4, []), (True, 3, []),
              (False, 5, []), (False, 6, [])]
    tactical = [(True, 0, [(1, False), (2, False)]),
                (False, 8, [(3, True)]), (False, 3, [(4, True)]), (True, -5, []), (True, 2, [])]
    show("worked", tree, 2)
    show("ordered", tree, 2, ordering=True)
    show("transposition", shared, 3)
    show("static horizon", tactical, 1)
    show("quiescence", tactical, 1, qlimit=1)
    show("interrupted", tree, 3, budget=7)
    show("no completed pass", tree, 2, budget=1)
    show("terminal root", [(True, -7, [])], 2)
    print("checks = PASS")


if __name__ == "__main__":
    main()

#include <algorithm>
#include <iostream>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
const int INF=1000000;
struct Stopped {};
struct Edge { int child; bool tactical; };
struct Node { bool maximizing; int evaluation; vector<Edge> moves; };
struct Entry { int value,move; string flag; };
struct Pass { int depth; string code; int value,move; vector<long long> counts; };
struct Result { string status; int depth,value,move; vector<long long> stats; vector<Pass> history; };
struct PathGuard {
    vector<int>& path;
    PathGuard(vector<int>& p,int child):path(p) { path.push_back(child); }
    ~PathGuard() { path.pop_back(); }
    PathGuard(const PathGuard&)=delete;
    PathGuard& operator=(const PathGuard&)=delete;
};
class GameSearch {
public:
    vector<Node> game;
    unordered_map<int,Entry> tt;
    vector<int> path,hint;
    vector<long long> stats;
    long long budget;
    bool use_tt,ordering;
    explicit GameSearch(const vector<Node>& input):game(input) {
        if(game.empty() || game.size()>64) throw invalid_argument("invalid state count");
        size_t total=0;
        for(size_t s=0;s<game.size();++s) {
            const Node& n=game[s];
            if(n.evaluation < -1000 || n.evaluation>1000) throw invalid_argument("invalid score");
            total+=n.moves.size();
            for(const Edge& e:n.moves)
                if(e.child<=static_cast<int>(s) || e.child>=static_cast<int>(game.size()) || game[e.child].maximizing==n.maximizing)
                    throw invalid_argument("edges must go forward and alternate players");
        }
        if(total>4096) throw invalid_argument("too many moves");
    }
    pair<int,int> save(int state,int key,int value,int move,const string& flag) {
        if(use_tt) tt[key]={value,move,flag};
        if(move>=0) hint[state]=move;
        return {value,move};
    }
    pair<int,int> search(int state,int depth,int qleft,int alpha,int beta) {
        if(stats[0]>=budget) throw Stopped();
        ++stats[0]; stats[5]=max(stats[5],static_cast<long long>(path.size())-1);
        if(depth==0) ++stats[4];
        int key=(state*13+depth)*7+qleft,alpha0=alpha,beta0=beta;
        auto it=tt.find(key);
        if(use_tt && it!=tt.end()) {
            const Entry& e=it->second;
            if(e.flag=="EXACT" || (e.flag=="LOWER" && e.value>=beta) || (e.flag=="UPPER" && e.value<=alpha)) {
                ++stats[3]; return {e.value,e.move};
            }
        }
        const Node& n=game[state];
        if(n.moves.empty() || (depth==0 && qleft==0)) {
            ++stats[1]; return save(state,key,n.evaluation,-1,"EXACT");
        }
        int best=n.maximizing ? -INF : INF,best_move=-1;
        if(depth==0) {
            ++stats[1]; best=n.evaluation; // Stand pat in the toy q-game.
            if((n.maximizing && best>=beta) || (!n.maximizing && best<=alpha)) {
                ++stats[2]; return save(state,key,best,-1,n.maximizing ? "LOWER" : "UPPER");
            }
            if(n.maximizing) alpha=max(alpha,best); else beta=min(beta,best);
        }
        vector<int> order;
        for(size_t i=0;i<n.moves.size();++i) if(depth>0 || n.moves[i].tactical) order.push_back(static_cast<int>(i));
        if(ordering) sort(order.begin(),order.end(),[&](int a,int b) {
            bool ah=a==hint[state],bh=b==hint[state];
            if(ah!=bh) return ah;
            int av=game[n.moves[a].child].evaluation,bv=game[n.moves[b].child].evaluation;
            if(av!=bv) return n.maximizing ? av>bv : av<bv;
            return a<b;
        });
        for(int i:order) {
            pair<int,int> child_result;
            {
                PathGuard move(path,n.moves[i].child);
                child_result=search(n.moves[i].child,max(0,depth-1),depth>0 ? qleft : qleft-1,alpha,beta);
            } // Undo also runs when Stopped is thrown.
            int value=child_result.first;
            if((n.maximizing && value>best) || (!n.maximizing && value<best)) { best=value; best_move=i; }
            if(n.maximizing) alpha=max(alpha,best); else beta=min(beta,best);
            if(alpha>=beta) { ++stats[2]; break; }
        }
        string flag=best<=alpha0 ? "UPPER" : best>=beta0 ? "LOWER" : "EXACT";
        return save(state,key,best,best_move,flag);
    }
    Result run(int start,int max_depth,int qlimit=0,long long node_budget=1000000,bool enable_tt=true,bool enable_ordering=true) {
        if(start<0 || start>=static_cast<int>(game.size()) || max_depth<1 || max_depth>12 || qlimit<0 || qlimit>6 || node_budget<1 || node_budget>1000000)
            throw invalid_argument("invalid search parameters");
        use_tt=enable_tt; ordering=enable_ordering; budget=node_budget;
        tt.clear(); path.clear(); hint.assign(game.size(),-1); stats.assign(6,0);
        vector<Pass> history; int completed=0,committed_value=0,committed_move=-1;
        for(int depth=1;depth<=max_depth;++depth) {
            vector<long long> before(stats.begin(),stats.begin()+5);
            string code="DONE"; int value=0,move=-1;
            try {
                PathGuard root(path,start);
                auto result=search(start,depth,qlimit,-INF,INF);
                value=result.first; move=result.second;
            } catch(const Stopped&) { code="ABORT"; }
            if(!path.empty()) throw logic_error("undo failed");
            vector<long long> delta(5);
            for(size_t i=0;i<5;++i) delta[i]=stats[i]-before[i];
            history.push_back({depth,code,value,move,delta});
            if(code=="ABORT") return {completed ? "PARTIAL" : "NO_COMPLETED_DEPTH",completed,committed_value,committed_move,stats,history};
            completed=depth; committed_value=value; committed_move=move;
        }
        return {"COMPLETE",completed,committed_value,committed_move,stats,history};
    }
};
void show(const string& name,const vector<Node>& game,int depth,int qlimit=0,long long budget=1000000,bool tt=true,bool ordering=false) {
    Result r=GameSearch(game).run(0,depth,qlimit,budget,tt,ordering);
    cout<<name<<": "<<r.status<<", depth="<<r.depth<<", score="<<r.value<<", move="<<r.move<<'\n';
    vector<string> labels={"nodes","evals","cutoffs","tt_hits","qnodes","peak"};
    for(size_t i=0;i<labels.size();++i) { if(i) cout<<", "; cout<<labels[i]<<'='<<r.stats[i]; }
    cout<<", restored=YES\npasses=[";
    for(size_t i=0;i<r.history.size();++i) {
        if(i) cout<<',';
        const Pass& p=r.history[i]; cout<<p.depth<<':'<<p.code<<':'<<p.value<<':'<<p.move<<':'<<p.counts[0];
    }
    cout<<"]\n";
}
int main() {
    vector<Node> tree={
        {true,0,{ {1,false},{2,false},{3,false} } },
        {false,3,{ {4,false},{5,false} } }, {false,2,{ {6,false},{7,false} } }, {false,4,{ {8,false},{9,false} } },
        {true,3,{} }, {true,5,{} }, {true,2,{} }, {true,9,{} }, {true,0,{} }, {true,7,{} } };
    vector<Node> shared={
        {true,0,{ {1,false},{2,false} } }, {false,4,{ {3,false},{4,false} } }, {false,3,{ {3,false},{5,false} } },
        {true,5,{ {6,false},{7,false} } }, {true,4,{} }, {true,3,{} }, {false,5,{} }, {false,6,{} } };
    vector<Node> tactical={
        {true,0,{ {1,false},{2,false} } }, {false,8,{ {3,true} } }, {false,3,{ {4,true} } }, {true,-5,{} }, {true,2,{} } };
    show("worked",tree,2);
    show("ordered",tree,2,0,1000000,true,true);
    show("transposition",shared,3);
    show("static horizon",tactical,1);
    show("quiescence",tactical,1,1);
    show("interrupted",tree,3,0,7);
    show("no completed pass",tree,2,0,1);
    show("terminal root",{ {true,-7,{} } },2);
    cout<<"checks = PASS\n";
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
    static final int INF=1_000_000;
    static final class Stopped extends RuntimeException { private static final long serialVersionUID=1L; }
    static final class Edge {
        final int child; final boolean tactical;
        Edge(int child,boolean tactical) { this.child=child; this.tactical=tactical; }
    }
    static final class Node {
        final boolean maximizing; final int evaluation; final Edge[] moves;
        Node(boolean maximizing,int evaluation,Edge... moves) { this.maximizing=maximizing; this.evaluation=evaluation; this.moves=moves.clone(); }
    }
    static final class Val {
        final int value,move;
        Val(int value,int move) { this.value=value; this.move=move; }
    }
    static final class Entry {
        final int value,move; final String flag;
        Entry(int value,int move,String flag) { this.value=value; this.move=move; this.flag=flag; }
    }
    static final class Pass {
        final int depth,value,move; final String code; final long[] counts;
        Pass(int depth,String code,int value,int move,long[] counts) { this.depth=depth; this.code=code; this.value=value; this.move=move; this.counts=counts.clone(); }
    }
    static final class Result {
        final String status; final int depth,value,move; final long[] stats; final List<Pass> history;
        Result(String status,int depth,int value,int move,long[] stats,List<Pass> history) {
            this.status=status; this.depth=depth; this.value=value; this.move=move; this.stats=stats.clone(); this.history=new ArrayList<>(history);
        }
    }
    static final class GameSearch {
        final Node[] game;
        final Map<Integer,Entry> tt=new HashMap<>();
        final List<Integer> path=new ArrayList<>();
        int[] hint; long[] stats; long budget; boolean useTT,ordering;
        GameSearch(Node[] input) {
            if(input.length<1 || input.length>64) throw new IllegalArgumentException("invalid state count");
            game=new Node[input.length]; long total=0;
            for(int s=0;s<input.length;++s) {
                Node n=input[s];
                if(n.evaluation < -1000 || n.evaluation>1000) throw new IllegalArgumentException("invalid score");
                total+=n.moves.length;
                for(Edge e:n.moves)
                    if(e.child<=s || e.child>=input.length || input[e.child].maximizing==n.maximizing)
                        throw new IllegalArgumentException("edges must go forward and alternate players");
                game[s]=new Node(n.maximizing,n.evaluation,n.moves);
            }
            if(total>4096) throw new IllegalArgumentException("too many moves");
        }
        Val save(int state,int key,int value,int move,String flag) {
            if(useTT) tt.put(key,new Entry(value,move,flag));
            if(move>=0) hint[state]=move;
            return new Val(value,move);
        }
        Val search(int state,int depth,int qleft,int alpha,int beta) {
            if(stats[0]>=budget) throw new Stopped();
            ++stats[0]; stats[5]=Math.max(stats[5],path.size()-1);
            if(depth==0) ++stats[4];
            int key=(state*13+depth)*7+qleft,alpha0=alpha,beta0=beta;
            Entry entry=tt.get(key);
            if(useTT && entry!=null && (entry.flag.equals("EXACT") || (entry.flag.equals("LOWER") && entry.value>=beta) || (entry.flag.equals("UPPER") && entry.value<=alpha))) {
                ++stats[3]; return new Val(entry.value,entry.move);
            }
            Node n=game[state];
            if(n.moves.length==0 || (depth==0 && qleft==0)) {
                ++stats[1]; return save(state,key,n.evaluation,-1,"EXACT");
            }
            int best=n.maximizing ? -INF : INF,bestMove=-1;
            if(depth==0) {
                ++stats[1]; best=n.evaluation; // Stand pat in the toy q-game.
                if((n.maximizing && best>=beta) || (!n.maximizing && best<=alpha)) {
                    ++stats[2]; return save(state,key,best,-1,n.maximizing ? "LOWER" : "UPPER");
                }
                if(n.maximizing) alpha=Math.max(alpha,best); else beta=Math.min(beta,best);
            }
            List<Integer> order=new ArrayList<>();
            for(int i=0;i<n.moves.length;++i) if(depth>0 || n.moves[i].tactical) order.add(i);
            if(ordering) order.sort((a,b)-> {
                boolean ah=a==hint[state],bh=b==hint[state];
                if(ah!=bh) return ah ? -1 : 1;
                int av=game[n.moves[a].child].evaluation,bv=game[n.moves[b].child].evaluation;
                if(av!=bv) return n.maximizing ? Integer.compare(bv,av) : Integer.compare(av,bv);
                return Integer.compare(a,b);
            });
            for(int i:order) {
                path.add(n.moves[i].child);
                Val child;
                try { child=search(n.moves[i].child,Math.max(0,depth-1),depth>0 ? qleft : qleft-1,alpha,beta); }
                finally { path.remove(path.size()-1); }
                int value=child.value;
                if((n.maximizing && value>best) || (!n.maximizing && value<best)) { best=value; bestMove=i; }
                if(n.maximizing) alpha=Math.max(alpha,best); else beta=Math.min(beta,best);
                if(alpha>=beta) { ++stats[2]; break; }
            }
            String flag=best<=alpha0 ? "UPPER" : best>=beta0 ? "LOWER" : "EXACT";
            return save(state,key,best,bestMove,flag);
        }
        Result run(int start,int maxDepth,int qlimit,long nodeBudget,boolean enableTT,boolean enableOrdering) {
            if(start<0 || start>=game.length || maxDepth<1 || maxDepth>12 || qlimit<0 || qlimit>6 || nodeBudget<1 || nodeBudget>1_000_000)
                throw new IllegalArgumentException("invalid search parameters");
            useTT=enableTT; ordering=enableOrdering; budget=nodeBudget;
            tt.clear(); path.clear(); hint=new int[game.length]; Arrays.fill(hint,-1); stats=new long[6];
            List<Pass> history=new ArrayList<>(); int completed=0,committedValue=0,committedMove=-1;
            for(int depth=1;depth<=maxDepth;++depth) {
                long[] before=Arrays.copyOf(stats,5); String code="DONE"; int value=0,move=-1;
                path.add(start);
                try { Val found=search(start,depth,qlimit,-INF,INF); value=found.value; move=found.move; }
                catch(Stopped e) { code="ABORT"; }
                finally { path.remove(path.size()-1); }
                if(!path.isEmpty()) throw new IllegalStateException("undo failed");
                long[] delta=new long[5]; for(int i=0;i<5;++i) delta[i]=stats[i]-before[i];
                history.add(new Pass(depth,code,value,move,delta));
                if(code.equals("ABORT")) return new Result(completed>0 ? "PARTIAL" : "NO_COMPLETED_DEPTH",completed,committedValue,committedMove,stats,history);
                completed=depth; committedValue=value; committedMove=move;
            }
            return new Result("COMPLETE",completed,committedValue,committedMove,stats,history);
        }
    }
    static Edge e(int child,boolean tactical) { return new Edge(child,tactical); }
    static Node n(boolean maximizing,int score,Edge... moves) { return new Node(maximizing,score,moves); }
    static void show(String name,Node[] game,int depth,int qlimit,long budget,boolean tt,boolean ordering) {
        Result r=new GameSearch(game).run(0,depth,qlimit,budget,tt,ordering);
        System.out.println(name+": "+r.status+", depth="+r.depth+", score="+r.value+", move="+r.move);
        String[] labels={"nodes","evals","cutoffs","tt_hits","qnodes","peak"}; StringBuilder out=new StringBuilder();
        for(int i=0;i<labels.length;++i) { if(i>0) out.append(", "); out.append(labels[i]).append('=').append(r.stats[i]); }
        out.append(", restored=YES\npasses=[");
        for(int i=0;i<r.history.size();++i) {
            if(i>0) out.append(','); Pass p=r.history.get(i);
            out.append(p.depth).append(':').append(p.code).append(':').append(p.value).append(':').append(p.move).append(':').append(p.counts[0]);
        }
        System.out.println(out.append(']'));
    }
    public static void main(String[] args) {
        Node[] tree={n(true,0,e(1,false),e(2,false),e(3,false)),n(false,3,e(4,false),e(5,false)),n(false,2,e(6,false),e(7,false)),
                     n(false,4,e(8,false),e(9,false)),n(true,3),n(true,5),n(true,2),n(true,9),n(true,0),n(true,7)};
        Node[] shared={n(true,0,e(1,false),e(2,false)),n(false,4,e(3,false),e(4,false)),n(false,3,e(3,false),e(5,false)),
                       n(true,5,e(6,false),e(7,false)),n(true,4),n(true,3),n(false,5),n(false,6)};
        Node[] tactical={n(true,0,e(1,false),e(2,false)),n(false,8,e(3,true)),n(false,3,e(4,true)),n(true,-5),n(true,2)};
        show("worked",tree,2,0,1_000_000,true,false);
        show("ordered",tree,2,0,1_000_000,true,true);
        show("transposition",shared,3,0,1_000_000,true,false);
        show("static horizon",tactical,1,0,1_000_000,true,false);
        show("quiescence",tactical,1,1,1_000_000,true,false);
        show("interrupted",tree,3,0,7,true,false);
        show("no completed pass",tree,2,0,1,true,false);
        show("terminal root",new Node[]{n(true,-7)},2,0,1_000_000,true,false);
        System.out.println("checks = PASS");
    }
}

Expected standard output, identical in all three languages:

• worked: COMPLETE, depth=2, score=3, move=0
• nodes=12, evals=7, cutoffs=2, tt_hits=0, qnodes=7, peak=2, restored=YES
• passes=[1:DONE:4:2:4,2:DONE:3:0:8]
• ordered: COMPLETE, depth=2, score=3, move=0
• nodes=13, evals=8, cutoffs=1, tt_hits=0, qnodes=8, peak=2, restored=YES
• passes=[1:DONE:4:2:4,2:DONE:3:0:9]
• transposition: COMPLETE, depth=3, score=4, move=0
• nodes=19, evals=9, cutoffs=2, tt_hits=2, qnodes=8, peak=3, restored=YES
• passes=[1:DONE:4:0:3,2:DONE:4:0:7,3:DONE:4:0:9]
• static horizon: COMPLETE, depth=1, score=8, move=0
• nodes=3, evals=2, cutoffs=0, tt_hits=0, qnodes=2, peak=1, restored=YES
• passes=[1:DONE:8:0:3]
• quiescence: COMPLETE, depth=1, score=2, move=1
• nodes=5, evals=4, cutoffs=0, tt_hits=0, qnodes=4, peak=2, restored=YES
• passes=[1:DONE:2:1:5]
• interrupted: PARTIAL, depth=1, score=4, move=2
• nodes=7, evals=4, cutoffs=0, tt_hits=0, qnodes=4, peak=2, restored=YES
• passes=[1:DONE:4:2:4,2:ABORT:0:-1:3]
• no completed pass: NO_COMPLETED_DEPTH, depth=0, score=0, move=-1
• nodes=1, evals=0, cutoffs=0, tt_hits=0, qnodes=0, peak=0, restored=YES
• passes=[1:ABORT:0:-1:1]
• terminal root: COMPLETE, depth=2, score=-7, move=-1
• nodes=2, evals=2, cutoffs=0, tt_hits=0, qnodes=0, peak=0, restored=YES
• passes=[1:DONE:-7:-1:1,2:DONE:-7:-1:1]
• checks = PASS

Complexity, Correctness, and Invariants

Let $b$ be maximum branching, $d$ a fixed normal depth, $Q$ the tactical cap, and $H=d+Q$ the maximum active horizon. First ignore transpositions, sorting cost, and quiescence. Full minimax visits a tree of $O(b^d)$ nodes for constant $b\gt1$. Alpha-beta has the same worst-case bound with unfavorable move order. On a uniform depth-$d$ tree with perfect ordering, the minimum leaf count is

$$b^{\lceil d/2\rceil}+b^{\lfloor d/2\rfloor}-1,$$

giving the familiar $O(b^{d/2})$ best-order scale for fixed $b$. This is a regular-tree search bound, not a guarantee on every game or evaluator. An actual terminal root takes one call in a single search. The provided driver still runs all $D$ requested iterations, so a terminal root uses $D$ admitted calls and $D$ utility reads if the budget suffices.

With bounded quiescence, a conservative full-tree bound is $O(b^{d+Q})$ for $b\gt1$, though tactical branching is often much smaller. Iterative deepening repeats depths $1$ through $D$. For geometrically growing regular trees their total full-width work remains $O(b^{D+Q})$; a single chain with no quiescence instead costs $1+2+\cdots+(D+1)-1=\Theta(D^2)$ calls when every normal pass reaches its boundary. Move ordering and cache reuse can change each pass's work substantially. There is no distribution-free average-case bound: branching, evaluation quality, tactical density, transpositions, and move order all matter.

For the actual programs, let $N$ be admitted calls, $T$ stored cache entries, and, for each expanded non-base call $v$, let $g_v$ be its outgoing degree and $k_v$ its candidate count after tactical filtering. Assuming expected constant-time hash operations, construction plus a run costs

$$O\left(V+E+D+N+\sum_v\left(g_v+k_v\log(k_v+1)\right)\right)$$

with ordering enabled; remove sorting work when ordering is disabled. The node budget bounds $N$, not move-list scanning, sorting, allocation, or elapsed time. The run initializes $O(V)$ hints, records $O(D)$ history, and can store at most $V(D+1)(Q+1)$ distinct horizon keys. Each stack frame materializes candidate indices, so auxiliary space is $O(V+T+D+bH)$, excluding the copied input graph of size $O(V+E)$. A lazy move iterator without full sorting can reduce active traversal storage toward $O(H)$ plus the table and other state. A transposition table has a real memory cost; it does not preserve a pure depth-only space bound.

Correctness of minimax and pruning. Terminal/base cases equal the specified evaluation model. At a normal node, induction over remaining depth makes max/min backup its minimax value; the same induction over $q$ handles the stand-pat-plus-tactical quiescence model. At a MAX node, an already established score at least beta makes remaining children irrelevant to an ancestor MIN alternative. At a MIN node, a score at most alpha similarly makes its remaining replies irrelevant to an ancestor MAX alternative. A cutoff can therefore return a directional bound without knowing the exact subtree value.

Every table entry preserves that proof: LOWER is at most the true value, UPPER is at least the true value, and EXACT equals it for the same state and horizon. Returning a compatible entry is then as safe as the corresponding completed search or cutoff. Matching horizons and fixed evaluation policy are essential. Full-window root searches cannot fail outside the score range, so a completed root result is exact for its model. Strict-improvement updates select an optimal root action, though tied choices can change with ordering.

Finally, each child call restores its parent's active path even while cancellation propagates. No interrupted ancestor stores an incomplete result; a root iteration is committed only after normal return. Thus a partial search preserves a previously proven depth-limited result. This proves the implementation's evaluation-tree result, not that the heuristic predicts the eventual winner or that the latest score must improve monotonically with depth.

Variants, Pitfalls, and Optimizations

A bound is not an exact score. Suppose a MIN node is searched with alpha $6$. Its first reply is worth $5$, so it cuts off before another reply worth $3$. The returned $5$ proves only an upper bound; the true value is $3$. Later, if a MAX root already has alternative $4$, reusing EXACT 5 would incorrectly prefer this branch. A correct UPPER 5 entry cannot cut at alpha $4$, so the node is searched again. The diagram makes that failure visible.

Horizon and state identity matter. A board arrangement alone may omit side to move, castling/en-passant rights, repetition history, or progress counters. A transposition key must distinguish everything that can change legal moves, utility, or evaluation. The toy DAG excludes repetition; adding a generic visited set would not implement draw rules. If an engine uses Zobrist hashes, apply/undo must restore the hash as well as the board, and collision checks or another explicit collision policy are required. Root-relative mate-distance scores may also need normalization when stored and retrieved at different plies; this example uses position-only bounded scores.

Use depth information carefully. A cached shallow score cannot answer a deeper search. Engines often use entries searched to at least a requested depth under their practical search policy, but that should not be confused with equality of two fixed heuristic horizons: $V_1(s)$ can differ from $V_2(s)$. The code deliberately requires exact $(d,q)$ equality for value reuse. It retains move hints across horizons, verifies candidate legality by generating the current list, and never treats the stored move of a bound as an exact continuation.

Quiescence reduces some errors and introduces its own policy. In the tactical fixture, move $0$ has static value $8$ but allows a tactical reply producing $-5$; move $1$ has static value $3$ but its tactical reply yields $2$. At normal depth $1$, no extension chooses move $0$ with score $8$. With one quiescence ply, MIN backs up $\min(8,-5)=-5$ and $\min(3,2)=2$, so MAX chooses move $1$ with score $2$. A hard tactical cap can still hide longer combinations, and a poor tactical filter can omit a decisive threat. Stand pat is not a legal substitute for an evasion when in check; a chess adapter must generate all required evasions and handle terminal/draw rules before static evaluation.

Negamax is a score-convention rewrite. In a zero-sum alternating game, side-to-move scores permit $N(s,d)=\max_a(-N(\operatorname{result}(s,a),d-1))$, with child window $(-\beta,-\alpha)$. These programs instead use MAX-oriented scores with explicit MAX and MIN nodes. Negating scores or windows halfway through that convention is a bug. Games with extra turns require the correct player transition, and chance or hidden-information games require different models rather than pretending every node is a fully observed MIN turn.

Advanced pruning needs separate reasoning. Killer/history heuristics, a previous principal variation, and transposition moves can improve ordering. Aspiration windows search around an earlier estimate but must widen and re-search on fail-low or fail-high before committing an exact root result. Principal variation search similarly relies on re-search rules. Null-move pruning, late-move reductions, and other selective techniques can change the searched model or require recovery searches; they do not follow automatically from the sound alpha-beta cutoff proof. Measure performance on varied positions: the sample's ordering heuristic increases work from $12$ to $13$ nodes.

Cancellation is not a score. Do not return $0$ as though a timed-out subtree were a draw. Propagate interruption separately, restore every applied move, retain only valid finished descendant entries, and return the last completed iteration. COMPLETE here means the requested depth budget was completed; it does not mean the whole underlying game was solved. A real clock limit also needs time checks, because admission count alone does not bound elapsed time.

Practice Problems and Real-World Use

Begin with the worked tree and verify that exhaustive minimax and alpha-beta return score $3$. Then independently compute values for every state and horizon on a small acyclic graph using reverse-topological dynamic programming. This makes a useful oracle because it uses neither search windows nor move-order pruning. Test selected root moves for optimality, rather than demanding one fixed index among equal-valued alternatives across different orderings.

The supplied implementations were checked on 14,841 inputs per language: $13{,}624$ valid iterative searches with both cache and ordering independently on/off, $1{,}200$ warm-cache probe sequences containing $8{,}400$ narrow/full-window queries, and $17$ invalid inputs. The corpus includes exhaustive four-state graph/score combinations, randomized trees and transposition graphs, negative and tied scores, duplicate moves, tactical extensions, maximum bounds, and interrupted passes. An independent dynamic-programming oracle checked values, optimal root choices, and every audited directional bound. There were $302{,}380$ stored-entry bound checks, $342{,}022$ return-window checks, and $350{,}560$ path-restoration checks. C++ and Java matched Python's statuses, scores, moves, counters, histories, and cache digests; repeated runs agreed, and the C++ corpus passed address/undefined-behavior instrumentation.

For primary background, consult the AIMA authors' adversarial-search chapter. For a production implementation to study separately, see Stockfish's search source, including its quiescence and bound-handling logic. Its additional rules and selective techniques go well beyond this demonstration; the recurrence, exact horizon keys, resource contract, trace, and validation here are specified directly in the lesson.