Games and Adversarial Search

A game search starts with a state: enough information to determine what can happen next. In tic-tac-toe, that means the board and the player to move. The board alone is incomplete because the next mark changes with the turn.

Define the six parts

A game model supplies:

• An initial state, $S_0$.
• A function, $\text{To-Move}(s)$, naming the player who acts in state $s$.
• The legal moves, $\text{Actions}(s)$.
• A transition model, $\text{Result}(s,a)$, giving the state after action $a$.
• A terminal test, $\text{Is-Terminal}(s)$, detecting the end of play.
• A utility function, $\text{Utility}(s,p)$, giving player $p$ a numeric payoff in a terminal state.

For tic-tac-toe, start with an empty 3-by-3 board and X to move. An action chooses an empty square. The transition places the current player's mark and changes the turn. Play ends as soon as someone makes a row, column, or diagonal of three, or the full board gives a draw. From X's view, score a win as +1, a draw as 0, and a loss as −1. The terminal test must run before another mark is placed: play does not continue after a win.

Classify the game along separate axes

These axes are independent. Dice make backgammon stochastic even though its board is visible. Hidden cards concern information, not whether an action itself is random. In a hidden-information game, a player reasons about the possible states consistent with its observations, called a belief state.

Keep the payoff viewpoint fixed

In a two-player zero-sum game, one player's gain is the other's loss. Constant-sum scores behave the same way: win 1, loss 0, and draw ½ each always total 1. One number is enough to express the opposition. Call the player who wants it larger MAX, and the player who wants it smaller MIN. These are roles; MAX need not always be White or X.

An ordinary search can choose every action along a path. A game-playing agent must respond to moves it does not control. Its solution is a strategy, specifying what to do in each situation it might face. A plan that works only if the opponent makes a helpful reply is not enough.

A game tree starts at the current state. Each outgoing edge represents one legal move, and its child is the resulting state. Label each nonterminal node with the player who acts there. In a two-player alternating game, MAX and MIN levels alternate.

Count individual turns

One ply is one move by one player. In chess, a full move usually includes one turn by White and one by Black, so it spans two plies. A depth-4 search from White's turn reaches positions after White, Black, White, and Black have acted. Count edges from the root, whose depth is zero.

Let $b$ be the branching factor and $m$ the maximum depth. A uniform tree has $b^d$ nodes at depth $d$ and $b^m$ leaves. Its total number of nodes is:

For $b>1$, the deepest levels dominate, giving exponential growth. With four moves per position, depth 3 has 64 leaves; depth 4 has 256. One extra ply multiplies the leaf count by four, not by one.

Separate games from positions

Tic-tac-toe has at most $9!=\mathrm{362,880}$ orders for filling the board. Many orders would continue after an earlier win and are not complete legal games. Stopping immediately at wins gives 255,168 complete games: 131,184 X wins, 77,904 O wins, and 46,080 draws. Across legal play there are only 5,478 distinct board positions, including the empty board.

The gap comes partly from transpositions: different move orders reaching the same state. X can play one corner, O the center, and X the opposite corner, or X can play those two corners in the reverse order. Both paths end at the same board and turn. A tree keeps both paths; a game graph can store their shared state once. Reusing work requires identifying complete states, not just visually similar boards.

See why full search breaks down

Chess is often modeled with about 35 legal moves per position and a 100-ply game, or 50 moves by each player. This gives the rough scale:

Real branches end at different depths and have different numbers of moves, but this estimate already explains why enumerating an entire chess game tree is impractical. On an empty 19-by-19 Go board, the first stone alone has 361 possible points.

The search tree is what an algorithm actually generates. Plain minimax generates the full game tree below the state for a finite game it searches to completion. Pruning, depth limits, and selective simulation generate less. A cutoff leaf can therefore be an unfinished position, even though a full game-tree leaf is terminal.

Picture a strategy inside the tree

A strategy subtree for MAX keeps one selected edge at each MAX node and every legal edge at each MIN node. MAX chooses its own action but must retain a response to any opponent move. A single root-to-leaf path describes only one possible play. It cannot show that the chosen plan survives the other replies.

Minimax chooses the best result MAX can secure against optimal opposition. Every leaf utility is measured for MAX. A large number favors MAX even when the node being evaluated belongs to MIN.

Work from the leaves toward the root

At a terminal node, return its utility. At a MAX node, return the largest child value. At a MIN node, return the smallest. Continue until the root receives a value:

A child value already summarizes optimal continuation from that child. This is why a parent compares the returned values instead of reopening every leaf below them. The recursion works through any number of alternating levels.

Trace a two-ply decision

MAX has three moves, each leading to a MIN node:

First take the minimum within each row. MIN can make A worth 4, B worth 2, and C worth 5. Then MAX takes the maximum of those three results:

The minimax value is 5. The minimax decision is the move to C. One is a number describing the position; the other is an action the program can play.

The largest leaf, 15, lies under B, but MAX does not control the reply that reaches it. MIN would select 2. Averaging B's leaves gives 10, which also looks attractive, but averaging models a random choice with suitable probabilities. Optimal opposition calls for a minimum.

Read the principal variation

The principal variation is the line followed when the players choose optimal moves. Here MAX plays C and MIN chooses its leaf worth 5. In a deeper tree, follow the chosen maximum or minimum at each level. The terminal utility on that line matches the root value. If several moves tie, more than one optimal line can exist.

Understand the guarantee

For a finite deterministic two-player zero-sum game with perfect information, following the minimax strategy guarantees at least the root value. An optimal opponent holds MAX to that value. An opponent's mistake can allow a better result, so 5 is a floor, not a prediction that every game must end at exactly 5.

A program can exploit weakness while preserving that floor. If two moves both have minimax value 5, it can prefer the one with more opportunities for the opponent to make a mistake. Choosing a move with minimax value 2 because it contains a tempting 15 abandons the guarantee of 5. The difference is whether the move preserves the best worst-case value.

The minimax definition is already a recursive program. A value function takes a state and returns a number. A search function compares the possible first moves and returns the action to play.

Separate move choice from value calculation

The following pseudocode assumes MAX acts at the root and turns alternate:

MINIMAX-SEARCH(s):
    if Is-Terminal(s): return no action
    bestMove = no action
    bestValue = -infinity
    for a in Actions(s):
        value = MIN-VALUE(Result(s, a))
        if value > bestValue:
            bestValue = value
            bestMove = a
    return bestMove

MAX-VALUE(s):
    if Is-Terminal(s): return Utility(s, MAX)
    v = -infinity
    for a in Actions(s):
        v = max(v, MIN-VALUE(Result(s, a)))
    return v

MIN-VALUE(s):
    if Is-Terminal(s): return Utility(s, MAX)
    v = +infinity
    for a in Actions(s):
        v = min(v, MAX-VALUE(Result(s, a)))
    return v

Initialize MAX with negative infinity so that any child improves it; initialize MIN with positive infinity. Test termination before generating successors. A full tic-tac-toe board with no winning line is a draw, not a nonterminal position whose best move must be selected from an empty list.

Trace what recursion discovers

Consider this tic-tac-toe board, with X to move and a period for an empty square:

X O X
. O .
. . .

O threatens the middle column. If X plays anywhere except bottom-middle, O can win next turn. Those moves have value −1 for X. Playing bottom-middle blocks the immediate win and allows a draw with best play, giving value 0. The root returns bottom-middle. The algorithm needs no separate instruction naming this threat: the terminal outcomes determine the values.

Budget time and memory

Depth-first minimax examines $O(b^m)$ nodes for branching factor $b$ and maximum depth $m$. Storing all generated siblings at each active level needs $O(bm)$ memory. Generating successors one at a time reduces the active search storage to $O(m)$, apart from the state representation. Exponential time, not the recursion stack, is usually the main obstacle.

Preserve the scoring convention

In MAX/MIN code, every call returns MAX's utility. Do not flip its sign simply because MIN acts next. Negamax uses a different convention: each value is from the current player's viewpoint, so a child value is negated before the parent maximizes it:

For a game ending in fewer than 100 plies, timing can be included by scoring a MAX win at depth $d$ as $100-d$, a loss as $-100+d$, and a draw as 0. Faster wins then score higher and delayed losses are less negative. The strict depth limit keeps every win positive and every loss negative.

For example, wins at plies 3 and 7 score 97 and 93, so the faster win is preferred. Losses at those depths score −97 and −93, making the later loss preferable while both remain worse than a draw.

A single MAX utility works when two players' interests are strictly opposed. With several players or overlapping interests, keep a utility vector. For players A, B, and C, the vector (1, 2, 6) gives their payoffs in that order.

Select by the active player's entry

At a node where C acts, compare the third entries of the child vectors. Return the entire vector of C's preferred child. At a B node, compare the second entries of those returned vectors; at an A node, compare the first.

Do not independently maximize each entry. If the available outcomes are (1, 2, 6) and (4, 2, 3), C chooses (1, 2, 6). The combination (4, 2, 6) is not an available outcome and cannot be backed up.

Work backward through three players

A moves first, then B, then C. Under A's left move, B chooses between two C nodes:

• The first has leaves (1, 2, 6) and (4, 2, 3). C chooses (1, 2, 6).
• The second has leaves (6, 1, 2) and (7, 4, 1). C chooses (6, 1, 2).

B compares second entries 2 and 1, so the left branch returns (1, 2, 6).

Under A's right move:

• C chooses (5, 4, 5) over (2, 5, 4), because 5 exceeds 4 in the third entry.
• C chooses (5, 2, 4) over (7, 7, 1), because 4 exceeds 1 in the third entry.

B compares second entries 4 and 2, so the right branch returns (5, 4, 5). Finally, A compares first entries 1 and 5 and chooses right. The root receives the whole vector (5, 4, 5).

State how ties are resolved

If C can choose (2, 3, 4) or (6, 1, 4), both give C 4. A's eventual payoff could be 2 or 6. A prediction needs a tie-breaking rule or a model of C's choice. Another player's indifference need not be harmless to the root player.

If two pursuers both want MAX caught, a round has one MAX layer and a MIN layer for each pursuer. With two pursuers, one round is three plies. This model is different from three independent players pursuing their own rewards.

Allow interests to overlap

In a general-sum game, both players may prefer (100, 100) to lower joint payoffs. Players can also temporarily benefit from attacking a common leader. Such alliance-like behavior can follow from their own preferences and change when the position changes.

Ordinary alpha-beta cutoffs rely on opposed interests and do not transfer directly to utility vectors. The paranoid model restores a two-player opposition, permitting alpha-beta search, but can predict coordinated hostility that the other players would not actually choose.

Alpha-beta pruning gives the same root value as minimax on the same tree with the same leaf values. It saves work by proving that some branches cannot improve the choice. Tied optimal moves may be returned in a different order.

Pass a search window down the path

Two bounds describe choices available above the current node:

• $\alpha$ is MAX's best available value along the path: MAX can already obtain at least this much.
• $\beta$ is MIN's best available value along the path: MIN can already hold MAX to at most this much.

Start the root with negative and positive infinity. Each recursive child receives the current bounds. They are local arguments, not global numbers shared across unrelated sibling searches.

At a MAX node, keep the largest child value seen. Stop when it reaches or exceeds beta: MIN above already has an alternative no larger than beta. Otherwise raise alpha when MAX finds an improvement. At a MIN node, keep the smallest child value seen. Stop when it reaches or falls below alpha: MAX above already has an alternative at least as good. Otherwise lower beta.

MAX-VALUE(s, alpha, beta):
    if Is-Terminal(s): return Utility(s, MAX)
    v = -infinity
    for a in Actions(s):
        v = max(v, MIN-VALUE(Result(s, a), alpha, beta))
        if v >= beta: return v
        alpha = max(alpha, v)
    return v

MIN-VALUE(s, alpha, beta):
    if Is-Terminal(s): return Utility(s, MAX)
    v = +infinity
    for a in Actions(s):
        v = min(v, MAX-VALUE(Result(s, a), alpha, beta))
        if v <= alpha: return v
        beta = min(beta, v)
    return v

The root compares actions and retains alpha between them:

ALPHA-BETA-SEARCH(s):
    if Is-Terminal(s): return no action
    alpha = -infinity
    beta = +infinity
    bestMove = no action
    for a in Actions(s):
        v = MIN-VALUE(Result(s, a), alpha, beta)
        if v > alpha:
            alpha = v
            bestMove = a
    return bestMove

Trace a MIN cutoff

Search the MIN branches A = (4, 9, 6), B = (2, 15, 13), and C = (5, 8, 10), left to right. A must examine all three leaves and returns 4. The root now has alpha 4. B's first leaf is 2. Its final minimum can only stay at 2 or fall, so B cannot beat A. Skip B's two remaining leaves. C examines all three leaves and returns 5. The root chooses C after examining seven of nine leaves.

Trace a MAX cutoff

Suppose a MIN parent already has a child worth 3, setting beta to 3. Its next MAX child finds a leaf worth 6. That child's value is at least 6, so MIN will prefer its existing 3. Skip the remaining children of that MAX node. The cutoff reasoning uses MIN's alternative, even though the current node is MAX.

A pruned MIN node can return an upper bound; a pruned MAX node can return a lower bound. Their exact values remain unknown. The completed root value is exact for the searched tree. Equality also permits a cutoff because a branch that can only tie cannot improve the current best value.

Alpha-beta saves the most work when strong moves are searched early. The values do not change with move order; the point at which the search can prove a cutoff does.

Compare two orders

For the three MIN branches A = (4, 9, 6), B = (2, 15, 13), and C = (5, 8, 10), starting with A examines seven leaves. Start with C instead. Its three leaves establish alpha 5. A then finds 4 immediately and cuts off; B finds 2 immediately and cuts off. Only five leaves are evaluated, and the answer remains C with value 5.

For a uniform tree with perfect ordering, the leaf count is:

This is about $O(b^{m\mathrm{/}2})$ instead of minimax's $O(b^m)$. The effective branching factor falls to about $\sqrt{b}$, allowing roughly twice the depth for a comparable budget. With $b=35$, perfect-ordering depth 8 evaluates 3,001,249 leaves; ordinary depth-4 minimax has 1,500,625 leaves. The comparison concerns scale, not identical runtime.

In the worst order alpha-beta can examine every minimax leaf. Its extra bound checks add overhead even when they save no leaves.

Use inexpensive ordering clues

The exact best move is unknown before search. Programs use quick estimates. In chess they may try captures, then threats, then quiet moves. A killer move caused a cutoff elsewhere at the same search depth and is tried early in another position. These clues affect efficiency; they do not justify discarding the other legal moves.

Iterative deepening searches to depth 1, then 2, then 3, and so on. A strong move from the previous iteration becomes an early candidate in the next. The deepest completed result is also ready if time expires.

The repeated work has different costs depending on pruning. For unpruned uniform search with branching factor 35, all shallower iterations add about $1\mathrm{/}(35-1)\approx 2.9\mathrm{\%}$ to the final search. For perfect-ordering alpha-beta, depths 1 through 7 together evaluate 1,677,159 leaves, about 56% of the depth-8 count. Better ordering can still make the overall process worthwhile.

Cache positions with their meaning

A transposition table stores results indexed by complete game state. If another move order reaches that state, the program can reuse a suitable entry. Store the searched depth and whether the result is exact, a lower bound, or an upper bound. A shallow entry does not replace a deeper search's required information. A bound may tighten a window or justify a cutoff, but must not be treated as an exact value.

An evaluation function estimates how favorable an unfinished position is for MAX. It makes depth-limited search possible: the frontier receives estimated values that can be backed up by minimax or alpha-beta.

Make scores useful to search

A good evaluator is fast, agrees with the ordering of real terminal outcomes, and correlates with success from nonterminal positions. Terminal states themselves should receive their exact utility. A MAX win must score above every nonterminal estimate, so that collecting pieces cannot become more attractive than winning.

One view of evaluation is to group positions by shared features. If such a group produces 72% wins, 8% draws, and 20% losses, with utilities 1, ½, and 0, its average utility is:

This interpretation depends on how positions and continuations were sampled. It is an estimate of outcome quality, not a proof of a forced win.

Add weighted features

A common design is a weighted sum:

Each feature $f_i(s)$ measures a property of the position; each weight $w_i$ says how much it contributes. Differences between the sides keep the viewpoint clear. A positive material difference means MAX has more material.

Traditional chess values are pawn 1, knight 3, bishop 3, rook 5, and queen 9. The king is not assigned a capturable material value. Suppose MAX is White. White has a queen, two rooks, a bishop, and six pawns:

Black has two rooks, two knights, a bishop, and seven pawns:

The material feature is therefore $28-26=2$. If White has 30 legal moves and Black 24, the mobility difference is 6. With material weight 1 and mobility weight 0.1:

That 2.6 is a feature score, not a 260% win probability. The weights define its scale.

Account for features that interact

A simple linear sum gives each feature a fixed contribution independent of the others. Real game value can depend on combinations: a pair of bishops can be worth more than the sum of their separate effects, and a pawn's importance can change in an endgame. Combined features, stage-dependent weights, or nonlinear evaluators can capture these effects. Weights may be selected by judgment or fitted to outcomes from recorded games.

More features also cost time. An elaborate evaluator that prevents an extra useful search ply can hurt the decision even if its individual estimates improve.

Match the scale to the backup rule

In deterministic minimax, consistent strictly increasing transformations preserve the ordering through maxima and minima. Squaring only positive scores, for example, keeps their order. Squaring arbitrary signed scores does not. At chance nodes, actual distances between utilities matter because the values are averaged. A score designed only to rank positions needs calibration before it can represent expected utility.

Heuristic minimax stops before the game ends. Its answer is optimal for the searched tree with its assigned frontier scores. It can still choose a losing move in the real game when those estimates miss what happens next.

Distinguish terminal states from cutoffs

A terminal state has a known outcome. A depth cutoff leaves play unfinished and needs an estimate. Test them in that order:

H-MINIMAX(s, d):
    if Is-Terminal(s): return Utility(s, MAX)
    if Is-Cutoff(s, d): return Eval(s)
    if To-Move(s) == MAX:
        return max over a of H-MINIMAX(Result(s, a), d + 1)
    return min over a of H-MINIMAX(Result(s, a), d + 1)

The cutoff commonly tests whether the depth has reached a limit. Alpha-beta can prune this same heuristic tree. Its pruning remains exact relative to those frontier values; it does not turn estimates into true game outcomes.

Under a time limit, iterative deepening retains the action from the deepest completed iteration. A partially searched deeper root can favor the first branch simply because its competitors have not been evaluated yet.

Finish a tactical exchange

A quiescent position is quiet enough that a short forced continuation is unlikely to swing its evaluation sharply. Quiescence search continues beyond the normal depth in unsettled positions, usually following captures until the exchange settles.

Suppose White's queen captures a pawn exactly at the depth limit. The material score improves by 1. But Black can recapture that queen on the next ply. The net material change is:

Stopping after the first capture reports +1; a short capture extension reveals −8. The issue is evaluating halfway through an exchange, not a failure of minimax's backup rule.

Recognize delayed losses

The horizon effect occurs when a program delays an unavoidable loss until it falls beyond the search depth. A trapped bishop may still be lost after several pawn checks. If search sees the checks but stops before the bishop capture, it may throw away pawns to hide that future loss.

A singular extension searches deeper along a move that stands clearly above its alternatives. Programs also extend forcing checks or recaptures. Extensions spend extra depth on selected lines; they require a budget so that a search can still finish.

Forward pruning, such as retaining only the best few moves, can discard the winning move. Its savings do not carry alpha-beta's guarantee.

Replace search with exact stored knowledge

An opening book supplies studied early moves. Endgame tablebases work backward from known outcomes through retrograde analysis. Seven-piece chess tablebases include the two kings and supply exact results for their covered endgames. A lookup's rules and state information must match the game being played.

A chance node represents a random event. Its branches list possible outcomes and their probabilities, which add up to 1. No player chooses its most favorable branch.

Use the rule belonging to each node

For outcomes $r$, a chance node has value:

Expectiminimax combines all four rules. Expectimax uses MAX and chance when there is no minimizing player. A probability model of a random opponent can supply chance branches even in a game whose move rules are deterministic.

Work backward through both chance and opposition

MAX chooses L or R. Each move leads to a random event, followed by a MIN choice.

After L, a fair coin gives two MIN nodes. Their leaves are (3, 7) and (8, 4). MIN returns 3 and 4. The chance node then gives:

After R, probabilities 0.25 and 0.75 lead to MIN nodes with leaves (10, 1) and (6, 5). Their values are 1 and 5, so:

MAX chooses R because 4 exceeds 3.5. Averaging the raw terminal leaves first would let chance replace MIN's decision. Process each node after its children have been resolved.

Assign the correct probabilities

Two fair dice have 36 equally likely ordered outcomes. Backgammon groups reversed orders, such as 3–5 and 5–3, into the same roll. That gives 21 distinct rolls: six doubles with probability 1/36 each and 15 non-doubles with probability 1/18 each. The check is:

Giving all 21 rolls probability 1/21 would overcount doubles and undercount non-doubles. Equal-looking branches need not have equal probabilities.

If each decision stage has $b$ legal moves and a chance event with $n$ outcomes, searching $m$ such stages costs about $O(b^m{n}^m)$. The depth convention must include how often chance occurs. With roughly 20 legal moves and 21 rolls, backgammon's added chance branches quickly limit exhaustive lookahead.

For example, two stages each containing 21 chance outcomes and 20 actions produce $(21\times 20{)}^2=\mathrm{176,400}$ paths. Count the chance events separately from player plies when estimating that cost.

Prune only when unseen outcomes are bounded

A partial average is not a minimax bound. If utilities lie between 0 and 10 and the first of two equally likely outcomes is worth 2, the whole node lies between 1 and 6. In particular:

If MAX already has another move worth 7, this chance node cannot beat it and the remaining outcome can be skipped. Without a suitable bound on unseen values, an extreme outcome could still change the average enough to reverse the choice.

Minimax asks what result an opponent can enforce. Expectimax asks what average utility follows from a probability model. Their decisions can differ even on the same tree because they represent different behavior.

Compare optimal and random opposition

For MIN branches A = (4, 9, 6), B = (2, 15, 13), and C = (5, 8, 10), minimax chooses C with a guarantee of 5. If the opponent instead chooses each reply uniformly, the expected values are about 6.33, 10, and 7.67. Expectimax chooses B.

This is sensible under the uniform model, but a skilled adversary can answer B with 2. Expectimax is not assuming that the opponent minimizes an average. It is using the specified probabilities. With a correct model it maximizes expected utility; the worst-case protection is weaker than minimax's. It can tie minimax's average performance when both recommend the same move.

A tree can mix models. A hostile agent's node takes a minimum, while a random agent's node takes a weighted average. Use the rule for the agent acting at that node, not one rule for every non-MAX layer.

See why order alone is insufficient

Suppose move A gives 2 with probability 0.6 and 3 with probability 0.4. Move B gives 1 with probability 0.6 and 4 with probability 0.4:

A has the larger expectation. Now cube every terminal value. Their ranking stays the same, but the expectations become:

B now wins the comparison. Averaging transformed outcomes is different from transforming their average. Cubing amplifies the benefit of B's high outcome enough to change the decision.

Preserve decisions with the right transformations

A positive affine transformation multiplies every expectation by the same positive number and adds the same constant. Applying $10x+5$ gives A a value of 29 and B a value of 27, keeping A preferred.

If A and B were MIN nodes, their values would be 2 and 1 before cubing and 8 and 1 afterward. Their ordering would be unchanged. Maxima and minima select a child value; averages combine the sizes of several values.

An evaluator used with chance should therefore estimate the intended expected utility on a consistent scale, such as win probability or a positive affine transformation of it. A nonlinear ranking score may be suitable for deterministic minimax while making the wrong risk trade-offs under chance.

Monte Carlo tree search, or MCTS, estimates moves from simulated games while building a tree that guides future simulations. A simulated continuation to the end is a playout or rollout. Its policy can select random legal moves or use inexpensive knowledge to produce more sensible play.

Store evidence at each node

Keep a visit count $N(n)$ and a cumulative reward $U(n)$. In a two-player win/loss game, use wins for the player who made the move leading into node $n$. A draw commonly adds half a win. Then $U(n)\mathrm{/}N(n)$ estimates that mover's success rate.

The root has no incoming move. Its visits still count every iteration; root wins can be tracked from the root player's viewpoint if needed. Child scores, which drive selection, must consistently use the incoming mover's viewpoint.

Repeat the four phases

1. Selection: From the root, follow a selection policy through existing children until reaching a terminal node or a node with an untried move.
2. Expansion: If nonterminal, add one child for an untried legal move.
3. Simulation: Run a playout from that child to a terminal outcome.
4. Back-propagation: Update visits and rewards for nodes on the selected path.

If selection reaches a terminal node, skip expansion and simulation. Its known outcome can be backed up immediately. A playout's temporary continuation need not be stored as new tree nodes: ordinary expansion adds one child per iteration.

Trace a reward update

White acts at the root. Selection and expansion follow:

• n1, reached by White's move;
• n2, reached by Black's move;
• n3, reached by White's move.

The playout ends in a Black win. Increase visits by one at the root and at n1, n2, and n3. Increase wins at n2 only among these three child nodes, because n2's incoming mover was Black. White's child nodes receive no win increment. Under a root-player convention, the root's own win total also stays unchanged.

A draw would add 0.5 to each child's reward. Counting Black's win as a success at every node would make White select moves that help Black.

Let the tree become uneven

Repeated iterations concentrate simulations on promising or uncertain branches. Strong-looking moves tend to acquire larger subtrees, while poor moves receive less work. The search does not impose one fixed depth on every line. Once a legal move is available, it can stop at a time limit and use its accumulated statistics.

The final action is usually the root child with the most visits. A move with two wins from two simulations has a perfect observed rate but little evidence. A heavily visited move reflects much more of the search's scrutiny.

Pure Monte Carlo search gives root moves independent playouts without growing a decision tree. It can repeatedly miss one strong opponent reply because later play stays governed by the rollout policy. MCTS learns where to branch deeper as it accumulates evidence, though a rare tactical refutation may still take time to discover.

MCTS must decide where another simulation is most useful. Exploitation revisits moves that already look strong. Exploration investigates moves with less evidence that might prove better. Always chasing the largest observed win rate can lock the search onto an early lucky result.

Calculate a UCB1 score

The upper confidence bound score for child $n$ is:

The first term is the observed win rate. The second is an exploration bonus. It grows as the parent accumulates visits and shrinks as the child receives more visits. The logarithm is natural. During selection, choose the child with the largest combined score.

Treat an unvisited child as having infinite priority instead of dividing by zero. Every legal move at a node is tried before selection repeatedly favors visited alternatives. MCTS using this selection rule is called UCT, upper confidence bounds applied to trees.

Compare three children

A parent has 50 visits. Its children have win/visit counts 21/30, 7/12, and 3/8. With $C=\sqrt{2}$ and $\ln 50\approx 3.912$:

The second child is selected. Its current win rate is below the first child's, but its uncertainty bonus is larger. The third is even less visited, yet its lower win rate leaves its total slightly below the second's.

With $C=0.5$, the same totals become about 0.881, 0.869, and 0.725. Selection now favors the first child. No outcomes changed; the program changed how strongly it rewards uncertainty.

Interpret the exploration constant

A larger positive $C$ puts more weight on exploration. Setting it to zero removes the bonus and chooses solely by observed mean. The bandit formulation with rewards between 0 and 1 motivates $C=\sqrt{2}$ in this form of the equation; practical game programs tune the constant. Changing the reward scale also changes the balance with the exploration term.

At each parent, its children record wins for the player choosing there. This makes maximizing UCB1 sensible at both players' turns. Storing only White wins throughout the tree while maximizing every score would make Black favor White's success.

Separate search priority from move quality

UCB1 chooses where to spend the next simulation. A large uncertainty bonus can make a weakly sampled move worth investigating. At the end of search, choose the most visited root child, not the highest current UCB1 score. Under the finite-game conditions of UCT and continued exploration, unlimited search converges toward minimax behavior; a finite budget still leaves sampling uncertainty.

A search method fits the size of the move space, the quality of available evaluation, and the kind of uncertainty in the game. The same time budget can produce very different decisions depending on what the method investigates.

Compare tactical coverage and simulation

Alpha-beta can find a single tactical refutation within its search depth. MCTS may initially prefer a move that wins most random playouts but loses to one precise reply. As its tree grows, it can discover that reply, but a short simulation budget may miss it. A high rollout win rate is therefore not a worst-case guarantee.

Connect methods to landmark programs

In 1997 IBM's Deep Blue used alpha-beta search, specialized hardware, and chess evaluation to defeat world champion Garry Kasparov 3½–2½ over six games. Its success showed how much strong search and game-specific evaluation could achieve together.

Go made that combination harder. An empty 19-by-19 board offers 361 stone placements, and judging a position by simple features is difficult. MCTS became a strong approach because it could estimate outcomes through play and grow a selective tree without requiring a hand-written static evaluator.

AlphaGo combined MCTS with neural networks suggesting moves and assessing positions. Its 2016 Nature description preceded its 4–1 victory over Lee Sedol in March 2016. AlphaZero later used neural-network evaluation in place of random playouts and achieved superhuman play in chess, shogi, and Go. These programs show that a search framework can use different sources of position values.

Distinguish strong play from solving a game

A program can beat a champion without proving the value of the initial position. In 2007 Jonathan Schaeffer's team used search and large endgame databases to establish that checkers is a draw with perfect play. Solving the game establishes an outcome against every possible opposing strategy, not just the opponents tested in matches.

Match the method to the model

In a stochastic game, sample random outcomes according to their actual probabilities during tree traversal and rollouts. An event with probability 0.8 should occur about four times as often as one with probability 0.2 over many samples. This estimates the same weighted expectation that explicit chance backup computes.

Every approach still depends on correct rules and state transitions. Depth-limited alpha-beta depends on its evaluator; MCTS depends on its simulation or evaluation policy and finite sample budget. Modeling a hostile opponent as random can be costly whichever search machinery is used to compute that model's answer.