Game playing through search, self-play, and learned evaluation

Why this subject matters now

For four decades the state of the art in game playing was a handcrafted evaluation function driving alpha-beta search. Deep Blue beat Kasparov in 1997 that way, with an evaluation tuned by grandmasters and a search that reached a dozen plies. That paradigm had a ceiling. Writing an evaluation function is writing down, by hand, what a good position looks like, and for Go nobody could. The board is nineteen by nineteen, the branching factor is around 250 near the opening, and the value of a stone depends on global configurations that resist any short list of features. The breakthrough of 2016 to 2018 was not a faster search. It was replacing the two handcrafted pieces, the move-ordering policy and the position evaluation, with a single neural network trained by self-play, and letting Monte Carlo tree search use that network as a prior. AlphaGo beat Lee Sedol, AlphaGo Zero discarded human games entirely, and AlphaZero collapsed the whole method into one algorithm that reached superhuman play in Go, chess, and shogi from nothing but the rules and self-play.

The reason a practitioner is expected to know this stack today, and was not five years ago, is that it stopped being about board games. MuZero removed the assumption that the agent even knows the rules, learning a model of the environment good enough to plan in. The same algorithm set records on Atari. The self-play loop, in which a policy generates its own ever-harder training data and search turns a weak policy into a stronger target, is now the mental model for a large slice of reasoning research. The search-then-distill pattern in AlphaZero is the same shape as generating candidate solutions, scoring them, and training on the good ones. And the imperfect-information branch, which the board-game work never touched, produced the first superhuman poker agents, Libratus and Pluribus, from a completely different idea, counterfactual regret minimization, that a strong applied researcher should be able to derive. This page owns the self-play-plus-learned-evaluation stack and the imperfect-information theory. The basics of minimax, alpha-beta, and uninformed search are derived in the companion page on search and classical AI, and the policy-gradient and value-function machinery that AlphaZero and MuZero rest on is derived in deep reinforcement learning. This page recaps only what it needs and then goes past both.

Game trees and the general-game-playing problem

The formal object

A finite, deterministic, perfect-information, two-player, zero-sum game is a tuple \( (\mathcal{S}, s_0, \mathcal{A}, \tau, \rho, u) \). It consists of a set of states \( \mathcal{S} \), an initial state \( s_0 \), legal-action sets \( \mathcal{A}(s) \), a transition \( \tau(s,a) \) giving the successor, a mover function \( \rho(s) \in \{\text{MAX}, \text{MIN}\} \) saying whose turn it is, and a utility \( u(s) \in \R \) defined at terminal states, with MAX seeking to maximize it and MIN to minimize it. Zero-sum means the two players' payoffs sum to a constant, so one number \( u \) describes both. The game tree is the unrolling of this system from \( s_0 \). The root is \( s_0 \), the children of a node \( s \) are \( \{\tau(s,a) : a \in \mathcal{A}(s)\} \), and the leaves are terminal states. It is a tree rather than a graph only if we distinguish states by the path that reached them. The same board position reached two ways gives two nodes unless we deduplicate, which is exactly what transposition tables do below.

Two size parameters govern everything. The branching factor \( b \) is the average number of legal moves, and the depth \( d \) is the number of plies to a terminal state (one ply is one player's move). The number of leaves is on the order of \( b^d \), and the numbers are hopeless to enumerate. Tic-tac-toe has about \( 10^5 \) game sequences, checkers about \( 10^{20} \), chess a game-tree complexity around \( 10^{123} \), and Go around \( 10^{360} \). No algorithm visits that tree. Every method in this page is a way of computing, or approximating, the value of the root while touching a vanishingly small fraction of the leaves.

General game playing takes the rules as input

Classical game AI bakes the rules into the program. A chess engine's move generator is chess-specific code. General game playing, introduced by Genesereth, Love, and Pell (2005) as an annual AAAI competition, poses a harder problem. The agent is given the rules of a game it has never seen, written in a declarative Game Description Language (GDL), and must play well with no game-specific engineering. GDL is a logic-programming notation. It declares the initial state, the legal moves as a function of the current state, the state-update relation, the terminal condition, and the goal values, all as logical rules over ground terms. A general game player parses these rules into an internal reasoner, then must supply its own search and its own evaluation, because it was given neither. This is why general game playing became the proving ground for domain-independent methods. An agent cannot lean on a handcrafted evaluation function it does not have, so it must either derive features from the rule structure or, more successfully, use a method that needs no evaluation function at all. That method was Monte Carlo tree search, and general game playing is where it first dominated, several years before AlphaGo, because MCTS estimates a position's value by random rollouts to the end of the game and so requires nothing but a simulator of the rules, which GDL provides for free.

The declarative framing matters beyond the competition. When the rules are data rather than code, the same planner must work across games, which forces the algorithm designer to separate the game-independent search from the game-specific model. That separation is exactly what MuZero later pushed to its limit by learning the model instead of parsing it, and it is the reason the general-game-playing literature and the model-based reinforcement learning literature converge on the same questions.

Minimax and alpha-beta, and the pruning result derived

Minimax, recapped

The minimax value of a state is defined by backward induction from the leaves,

This is the value MAX secures against a perfectly adversarial MIN, a security level, because playing the arg-max at every MAX node guarantees at least \( V(s_0) \) no matter what MIN does. The companion page on classical AI proves that property and works a small minimax tree. Here the recap exists only to set up pruning. Exact minimax evaluates every leaf, \( \Theta(b^d) \), so it is never run on a large game directly. Two ideas rescue it, pruning subtrees that cannot change the root value (alpha-beta), and replacing the exact leaf value with a heuristic evaluation at a fixed depth. The second is where handcrafted-evaluation engines lived. The derivation of the first is below.

Alpha-beta pruning

Alpha-beta carries two bounds down the tree. Let \( \alpha \) be the best (largest) value MAX can already guarantee along the path to the current node, and \( \beta \) the best (smallest) value MIN can already guarantee. At a MAX node we scan children, updating a running value \( v \) upward. The moment \( v \ge \beta \), we stop, because MIN, who moves above this node, already has an option worth \( \beta \) and will never let the game reach a node worth \( v \ge \beta \). This is a beta cutoff. Symmetrically at a MIN node, once \( v \le \alpha \) we stop with an alpha cutoff. The pruned subtrees are exactly those that provably cannot affect the root value, so alpha-beta returns the identical minimax value. It is an exact algorithm, not an approximation. Knuth and Moore (1975) gave the definitive analysis and proved the algorithm correct, including the subtle point that a pruned node's value may be computed only approximately (bounded, not exact) yet the root is still exact.

Deriving the best-case node count

The value of alpha-beta is entirely a function of move ordering. In the worst order it prunes nothing and evaluates all \( b^d \) leaves. In the best order it evaluates far fewer, and the classic result quantifies exactly how few. Consider a uniform tree with branching factor \( b \) and depth \( d \), and suppose that at every node the best move is searched first. Define \( T(d) \) as the number of leaves alpha-beta evaluates on such a tree. The argument distinguishes two kinds of node.

At a node where the mover is about to establish the value (call it a PV node, for principal variation), we cannot know which child is best without examining it, and the ordering assumption only tells us the best child is first. The first child must be searched in full as a PV node. Every subsequent child, however, only needs to be refuted. We need to show it is no better than the value the first child already returned, and with perfect ordering the refutation succeeds after examining just one of its children, because that grandchild's value already crosses the cutoff bound. So a PV node at depth counted-from-leaves \( k \) spawns one PV child at level \( k-1 \) and \( b-1 \) cut nodes, and a cut node needs only one child examined, itself a PV node one level down. Writing \( P(k) \) for leaves under a PV node and \( C(k) \) for leaves under a cut node with \( k \) levels remaining,

with \( P(0) = C(0) = 1 \). Substituting the second equation into the first,

Rather than solve the recurrence in closed form, count leaves by level parity, which is cleaner and gives the famous exponent. Unrolling the PV path, at each level the PV node emits \( b-1 \) cut nodes, and a cut node emits \( b-1 \) PV nodes two levels below, so the number of full-width branchings is halved. The tree that is actually evaluated has full branching on every other level and branching one on the alternate levels. A tree with \( d \) levels, branching \( b \) on \( \lceil d/2 \rceil \) of them and branching \( 1 \) on the rest, has

leaves, which is \( \Theta\!\left(b^{d/2}\right) \). This is the Knuth-Moore result. Its meaning is plain. With perfect move ordering, alpha-beta evaluates the square root of the number of leaves minimax would, which is the same as searching twice as deep for the same leaf budget, since \( b^{d/2} \) is the leaf count of a full-width search to depth \( d/2 \). Every ply of extra depth is worth roughly one class of strength in chess, so move ordering is not an optimization detail. It is the difference between a club player and a grandmaster at fixed hardware.

The exponent \( d/2 \) is the best case. The effective branching factor of a real engine sits between \( b^{1/2} \) (perfect ordering) and \( b \) (no ordering). Good engines get within a small factor of the square-root bound, which is why so much engineering goes into ordering.

Move ordering, iterative deepening, and transposition tables

Because the payoff of ordering is quadratic, engines spend heavily to search promising moves first. Three mechanisms dominate. Iterative deepening searches to depth 1, then 2, then 3, and so on, using the best move from depth \( k \) to order the root moves at depth \( k+1 \). The re-search cost is negligible because the tree is geometric (the same argument as for iterative deepening in uninformed search, worked in the classical AI page), and the ordering information it provides more than pays for itself. It also gives an anytime algorithm. Stop whenever the clock runs out and play the best move from the deepest completed iteration.

Transposition tables exploit the fact that the game is really a graph, not a tree. The same position arises through many move orders (a transposition). A hash table keyed on the position stores, for each position seen, its computed value or bound, the depth to which it was searched, and the best move found. When search reaches a position already in the table at sufficient depth, it reuses the stored value instead of re-searching, and even when the stored depth is too shallow to reuse the value, the stored best move seeds the ordering. To key the table cheaply, engines use Zobrist hashing, which assigns an independent random 64-bit key \( z[p][q] \) to every (piece-type \( p \), square \( q \)) pair once at startup and defines the hash of a position as the XOR of the keys of all pieces present, \( H = \bigoplus_{(p,q) \text{ on board}} z[p][q] \). Its decisive property is that it is incremental. Moving a piece from square \( q_1 \) to \( q_2 \) updates the hash by \( H \mathrel{\oplus}= z[p][q_1] \oplus z[p][q_2] \), two XORs, rather than rehashing the whole board, because XOR is its own inverse and is associative and commutative. A move and its undo apply the same XOR, so make and unmake are symmetric. The collision probability for a well-chosen random key set is about \( 2^{-64} \) per pair of distinct positions, negligible for search.

Monte Carlo tree search

Why sample instead of enumerate

Alpha-beta needs an evaluation function to cut off search before the leaves. When no good evaluation function exists, as in Go, a different idea works, estimating a position's value by playing the game out to the end many times with a cheap policy and averaging the outcomes. A single random playout is a noisy, unbiased-enough sample of how good a position is. Average enough of them and the estimate sharpens. Monte Carlo tree search (Coulom 2006, Kocsis and Szepesvari 2006) makes this precise by growing an asymmetric tree that spends its samples where they matter, deep along promising lines and shallow elsewhere, rather than uniformly. It needs only a simulator of the rules, which is why it took over general game playing and computer Go before any neural network entered the picture.

The four phases

MCTS repeats a four-phase iteration, each iteration adding one node to a search tree that starts as just the root.

   SELECTION            EXPANSION           SIMULATION          BACKPROPAGATION
   descend the tree     add one child       random rollout      update stats up
   by a tree policy     for an untried      from the new node   the path: N += 1,
   (UCT) until a node   move                to a terminal       W += outcome for
   with untried moves                       state, get outcome  the mover at each node

        root                root                root                root  (N,W updated)
        /  \                /  \                /  \                /  \
      ...  node           ...  node           ...  node          ...  node (updated)
                              |                   |                   |
                            new                 new                 new  (updated)
                                                 :
                                              rollout ~~~~> z

Selection walks from the root down through nodes that are fully expanded (all children present), at each step choosing a child by a tree policy that balances exploiting high-value children against exploring under-sampled ones. Expansion reaches a node with at least one untried move, plays one such move, and adds the resulting child to the tree. Simulation (rollout) plays from that new node to a terminal state using a fast default policy, often uniform random, and reads off the outcome \( z \). Backpropagation walks back up the path just traversed, incrementing each node's visit count \( N \) and adding the outcome to its value total \( W \), taking care to add the outcome from the perspective of the player who moved into that node, since the tree alternates movers. After a budget of iterations, the move played is usually the root child with the most visits, not the highest mean value, because the visit count is the more robust statistic. A child gets visited a lot precisely when it keeps looking good under repeated scrutiny.

Deriving the UCT selection rule from UCB1

The tree policy is the heart of MCTS. Kocsis and Szepesvari's insight was that choosing a child at a node is a multi-armed bandit problem. Each child is an arm, pulling it means running one simulation through it, and the reward is the simulation outcome. The regret-optimal solution to the stochastic bandit is the UCB1 rule of Auer, Cesa-Bianchi, and Fischer (2002). UCB1 is derived from a concentration inequality. Suppose arm \( i \) has true mean reward \( \mu_i \in [0,1] \), has been pulled \( n_i \) times, and has empirical mean \( \bar{x}_i \). Hoeffding's inequality bounds the chance the empirical mean is far below the truth,

We want a confidence radius \( \varepsilon \) that shrinks as we pull more, but slowly enough that the total probability of ever being wrong stays bounded as the number of total pulls \( N \) grows. Setting the right-hand side to \( N^{-4} \) and solving,

The union bound over all arms and all time steps then keeps the total failure probability finite (the series \( \sum_N N \cdot N^{-4} \) converges), which is what makes the resulting regret grow only logarithmically. UCB1 acts optimistically. It plays the arm maximizing the upper confidence bound, empirical mean plus confidence radius,

UCT (Upper Confidence bounds applied to Trees) is UCB1 run at every internal node of the MCTS tree, with \( \bar{x}_i = W_i / N_i \) the mean simulation outcome through child \( i \), \( n_i = N_i \) its visit count, and \( N \) the parent's visit count,

The first term exploits and the second explores. A child that has been visited rarely has a large \( \ln N / N_i \) and so is pulled up, while a child visited often relies on its mean. Kocsis and Szepesvari proved that with this rule the probability of selecting a suboptimal move at the root converges to zero, so in the limit of infinite simulations UCT's value estimates converge to the minimax values. The constant \( c \) trades exploration against exploitation. The Hoeffding derivation gives \( c = \sqrt{2} \approx 1.41 \) for rewards in \( [0,1] \), but in practice \( c \) is tuned per domain, because rollout outcomes are far from independent and the theoretical constant is rarely optimal. Values from roughly \( 0.4 \) to \( 2 \) are common depending on the reward scale.

RAVE and the all-moves-as-first heuristic

Early in a search each child has few visits and its UCT mean is very noisy. The RAVE heuristic (Rapid Action Value Estimation), developed by Gelly and Silver (2011) for computer Go, shares statistics across the tree to reduce that variance. The underlying idea is AMAF, all-moves-as-first. A move that appears anywhere in a simulation, not only as the immediate child, is credited with that simulation's outcome, on the reasoning that in many games the value of playing a move is roughly independent of exactly when it is played. RAVE keeps, alongside the true visit count and value, an AMAF count and value for each move, and blends them,

where the tilde quantities are the AMAF statistics and \( \beta \) starts near one (trust the plentiful AMAF data) and decays to zero as the true visit count grows (trust the unbiased data). RAVE was a large part of what made pre-neural Go programs strong, and it illustrates the general MCTS move of introducing a cheap, biased estimator to guide early exploration, then letting the unbiased estimator take over. AlphaGo's neural prior later played exactly this role, more powerfully.

Progressive widening for large branching

When the branching factor is very large, or the action space continuous, a node may have more legal moves than the simulation budget can ever visit even once, and plain UCT wastes the budget expanding a node's children before it has enough visits to tell them apart. Progressive widening (also called progressive unpruning) caps the number of children considered at a node as a slowly growing function of its visit count. Only \( \lceil C N^{\alpha} \rceil \) children are allowed, with \( \alpha \in (0,1) \), so a node with \( N \) visits considers \( O(N^\alpha) \) moves and adds a new one only when its visit count crosses the next threshold. Moves are added in order of some prior (a heuristic, or a policy network), so the most promising moves are the ones actually explored. This is how MCTS is applied to games and planning problems with hundreds or thousands of moves per state, and it is the mechanism that lets the same search operate on continuous control after a discretization or a sampled action set.

AlphaGo, AlphaGo Zero, and AlphaZero

The policy-value network

AlphaGo (Silver et al., 2016) kept MCTS but replaced its two weakest parts, the uniform rollout policy and the absent evaluation function, with neural networks. The original system used several networks, a policy network trained by supervised learning on human expert moves, a second policy network refined by policy-gradient self-play, a fast rollout policy, and a value network predicting the game outcome. AlphaGo Zero (Silver et al., 2017) simplified this to a single network trained entirely from self-play with no human data, and AlphaZero (Silver et al., 2018) generalized that one algorithm to chess and shogi as well as Go. The unified network is a function \( f_\theta(s) = (\boldsymbol{p}, v) \) from a board state to a policy vector \( \boldsymbol{p} \) over legal moves (a probability for each move) and a scalar value \( v \in [-1, 1] \) predicting the game's eventual result from the current player's perspective. Architecturally it is a deep residual convolutional tower over a stack of board-plane features, splitting into a policy head and a value head. The exact forward pass is implemented below in PyTorch and JAX.

PUCT, the network prior inside the search

AlphaZero's tree policy is not UCT. It replaces the \( \ln N \) exploration term with one weighted by the network's prior probability \( P(s,a) \) for each move, a variant of the PUCT rule (predictor + UCB applied to trees). At a node \( s \) with children indexed by action \( a \), each edge stores a visit count \( N(s,a) \), an action-value \( Q(s,a) \) (the mean of the network value estimates backed up through that edge), and the fixed prior \( P(s,a) \) from the policy head. Selection chooses

Read the exploration term \( U \) piece by piece. The prior \( P(s,a) \) puts the exploration budget on moves the network already likes, so a strong prior focuses search the way a strong player's intuition prunes candidate moves. The numerator \( \sqrt{\sum_b N(s,b)} \) grows with total visits to the parent, so all children keep getting some exploration pressure as the node is visited more. The denominator \( 1 + N(s,a) \) shrinks the term for children already visited a lot, handing the budget to their less-visited siblings. Early on, when every \( N(s,a) = 0 \), the \( Q \) terms are all equal (initialized to zero) and selection follows the prior exactly. As visits accumulate, the empirical \( Q \) values take over and the search can overrule the prior. That is the whole point. The network provides a fast, differentiable guess, and the search corrects it with lookahead. The constant \( c_{\text{puct}} \) sets how long the prior dominates before the values do. AlphaZero used a value that also grows slowly with the parent visit count.

The key difference from plain MCTS is that AlphaZero does no rollouts at all. When expansion reaches a new leaf \( s' \), it does not play the game out. It evaluates \( f_\theta(s') = (\boldsymbol{p}, v) \) once, uses \( \boldsymbol{p} \) as the priors for \( s' \)'s edges, and backs up the scalar \( v \) as the leaf's value. A single network evaluation replaces a full random playout, which is both far less noisy and far more informed, and it is why AlphaZero needs only hundreds of simulations per move where classical MCTS needed tens of thousands.

The self-play training loop

Training is a closed loop with no external data. The current network plays games against itself. In each position, MCTS is run for a fixed simulation budget, and the move actually played is sampled from the search's visit distribution \( \boldsymbol{\pi}(s) \propto N(s,\cdot)^{1/T} \) (with temperature \( T \) annealed toward zero as the game proceeds, so early moves are exploratory and late moves greedy). Each self-play game yields, for every position \( s \) visited, a training triple \( (s, \boldsymbol{\pi}(s), z) \), where \( \boldsymbol{\pi}(s) \) is the MCTS visit distribution and \( z \in \{-1,0,1\} \) is the game's final outcome from \( s \)'s player's perspective. The network is then trained to make its policy head match the search distribution and its value head match the outcome, minimizing

a squared-error value loss plus a cross-entropy policy loss plus weight decay. The improved network replaces the old one and the loop repeats. Notice that the targets are generated by the system itself. The policy target is the output of search applied to the current network, and search is stronger than the raw network, so the network is always chasing a target better than itself.

MCTS as a policy-improvement operator

The reason the loop converges to strong play, rather than drifting, is a precise analogy to policy iteration in reinforcement learning. Policy iteration alternates policy evaluation (compute the value of the current policy) with policy improvement (act greedily with respect to that value to get a better policy), and the policy-improvement theorem guarantees each step is no worse. In AlphaZero, the raw network policy \( \boldsymbol{p}_\theta \) is the current policy, and MCTS is the improvement operator. Running search from the network's priors produces a visit distribution \( \boldsymbol{\pi} \) that is a strictly better policy than \( \boldsymbol{p}_\theta \), because lookahead corrects the prior's errors. The value head, meanwhile, performs policy evaluation, learning the value of the searched policy. Training the network on \( (\boldsymbol{\pi}, z) \) distills the improved policy back into the network, so the next iteration's prior is stronger, and search improves upon that in turn. The loop is approximate policy iteration in which the improvement step is a tree search rather than a one-step greedy max, and the evaluation step is a regression. This is the most transferable idea on the page. Search is a way to turn any policy into a better one, and training on the searched policy makes the improvement permanent.

Why self-play is a curriculum

Self-play solves the exploration and data problems at once. The opponent is always exactly matched in strength, because it is the same network, so games are decided by fine margins and every game is informative. A fixed strong opponent would beat a weak learner every time and provide no gradient, and a fixed weak opponent would teach nothing once surpassed. As the network improves, the opponent improves in lockstep, so the difficulty of the training distribution rises automatically to track the agent's competence, which is the defining property of a curriculum. Nobody designs the sequence of positions. It emerges from two copies of an improving policy playing each other. This automatic difficulty scaling is why self-play reaches superhuman strength from random initialization, and it is the property that reasoning-model researchers try to reproduce when they train a model on problems generated and filtered by earlier versions of itself.

MuZero, planning in a learned model

Dropping the known-rules assumption

AlphaZero still needs a perfect simulator. To expand a node it must apply the real rules to get the next state. MuZero (Schrittwieser et al., 2020) removes that requirement, which is what lets it play Atari, where the agent sees only pixels and rewards and is never told the dynamics. Instead of a given transition function, MuZero learns three functions jointly. A representation function \( h_\theta \) maps the observed history to an initial latent state \( s^0 = h_\theta(o_{1:t}) \). A dynamics function \( g_\theta \) maps a latent state and an action to a next latent state and a predicted reward, \( (s^{k+1}, r^{k+1}) = g_\theta(s^k, a^{k+1}) \). And a prediction function \( f_\theta \) maps a latent state to a policy and value, \( (\boldsymbol{p}^k, v^k) = f_\theta(s^k) \), exactly like AlphaZero's head. MCTS then runs entirely in the latent space. The tree's nodes are latent states, edges apply the learned dynamics, and leaves are evaluated by the learned prediction function. The agent plans inside a model it invented, never reconstructing the real state.

The value-equivalence principle

The subtle and important point is what the learned model is trained to get right. It is not trained to predict future observations. MuZero never reconstructs the pixels of the next frame. It is trained only so that the quantities that matter for planning, the predicted policy, value, and reward along real trajectories, match what actually happened. Concretely, unrolling the model for \( K \) steps from a real state and feeding in the actions actually taken, the losses are the predicted reward at each step against the observed reward, the predicted value against an \( n \)-step bootstrapped return target, and the predicted policy against the MCTS visit distribution that was computed at that step. Nothing forces the latent state to resemble the true state in any other respect. This is the value-equivalence principle. A model is good enough if it produces the same values and optimal actions as the real environment under the planning algorithm, even if it is wildly wrong about everything the planner does not consult. It frees the model from wasting capacity on visually complex but decision-irrelevant detail, and it is the conceptual bridge from game engines to model-based RL. You do not need to simulate the world, only the part of it that changes your decision. The same principle shows up in the general-game-playing framing, where the declared rules are exactly the decision-relevant dynamics and nothing else.

Imperfect-information games

Why minimax fails

Everything above assumes perfect information, in which both players see the full state. Poker breaks that assumption, and the break is fundamental, not a technicality. In a perfect-information game an optimal strategy can be deterministic, and minimax computes it by treating the opponent as worst-case at each node. In an imperfect-information game, a player cannot see the opponent's private cards, so many distinct states look identical from the player's viewpoint. The player must choose one action for all of them, without knowing which they are in. Two consequences follow. First, deterministic play is exploitable. If you always bet your strong hands and check your weak ones, an opponent reads your action and plays perfectly against it, so an optimal strategy must be randomized, mixing actions to stay unpredictable. Bluffing is not a psychological trick. It is a mathematical necessity of hiding information. Second, the value of a decision depends on the probability distribution over which hidden state you are actually in, which depends on both players' strategies, so the tree cannot be solved bottom-up by independent max and min operations. The subtrees are coupled through shared information. Minimax has no place to put the randomization or the belief, and it simply does not apply.

Extensive-form games and information sets

The right formalism is the extensive-form game. It is a tree whose nodes are decision points, whose edges are actions, and whose leaves carry payoffs, with one addition, chance nodes (the deal of the cards) with fixed probabilities and, crucially, a partition of each player's decision nodes into information sets. An information set \( I \) is a set of nodes that the player to move cannot distinguish, because they differ only in information hidden from that player. The player must choose the same action distribution at every node in \( I \). A behavioral strategy \( \sigma_i \) for player \( i \) assigns to each of that player's information sets \( I \) a probability distribution \( \sigma_i(I, \cdot) \) over the legal actions there. A strategy profile \( \sigma = (\sigma_1, \sigma_2, \dots) \) is a Nash equilibrium if no player can raise their expected payoff by unilaterally changing their strategy. In a two-player zero-sum game a Nash equilibrium is exactly an unexploitable (minimax-optimal) strategy, and its value is the game value. The goal in two-player zero-sum imperfect-information games is to compute, or closely approximate, such an equilibrium.

Regret matching

Counterfactual regret minimization is built out of a simple online-learning primitive, regret matching, so derive that first. Consider a single decision with action set \( \mathcal{A} \), repeated over rounds \( t = 1, \dots, T \). On round \( t \) you choose a distribution \( \sigma^t \) over actions, then a payoff vector \( \boldsymbol{v}^t \) is revealed, giving the value \( v^t(a) \) each action would have earned. Your realized value is \( \langle \sigma^t, \boldsymbol{v}^t \rangle \). The regret for action \( a \) is how much better you would have done by always playing \( a \),

Regret matching sets the next distribution proportional to positive accumulated regret,

falling back to the uniform distribution when all regrets are non-positive. The intuition is to shift probability toward actions you wish you had played more. The guarantee is that regret matching is a no-regret algorithm. The average positive regret vanishes, \( \max_a R^T_+(a) / T \le \Delta \sqrt{|\mathcal{A}|} / \sqrt{T} \to 0 \), where \( \Delta \) is the payoff range. The proof bounds the growth of \( \sum_a R^T_+(a)^2 \) by a Blackwell approachability argument. The constant is not important here, only that the average regret falls like \( 1/\sqrt{T} \).

Counterfactual regret and the CFR decomposition

The problem with applying regret matching directly to a whole game is that the regret at one information set depends on the strategy everywhere else, so the single-decision analysis does not transfer. Zinkevich, Johanson, Bowling, and Piccione (2007) solved this by defining a per-information-set surrogate, the counterfactual value, whose regret decomposes across the tree. Fix a strategy profile \( \sigma \). For information set \( I \) belonging to player \( i \), let \( \pi^\sigma(h) \) be the probability that the game reaches node \( h \) under \( \sigma \), and factor it as \( \pi^\sigma(h) = \pi^\sigma_i(h)\, \pi^\sigma_{-i}(h) \), the product of the player's own action probabilities along the path and everyone else's (including chance). The counterfactual value of \( I \) is

the expected payoff summed over the terminal states \( z \) reachable from \( I \), weighted by the probability of reaching each node of \( I \) if the player had tried to reach \( I \) (their own reach probability replaced by 1, which is what the \( \pi_{-i} \) weighting encodes). The word "counterfactual" names exactly this. The value is computed as if the player had played to get to \( I \), stripping out their own probability of avoiding it, so that regrets at different information sets are on a common footing. Let \( v_i(\sigma_{I \to a}, I) \) be the same quantity when the player is forced to play action \( a \) at \( I \). The immediate counterfactual regret of not playing \( a \) at \( I \), accumulated over iterations, is

and CFR runs regret matching independently at every information set using these counterfactual regrets, \( \sigma^{T+1}(I, a) = R^T_+(I,a) / \sum_{a'} R^T_+(I,a') \).

Why the average strategy converges to Nash

The decisive theorem of Zinkevich et al. is that the total regret of the whole game is bounded by the sum of the immediate counterfactual regrets over information sets,

Each term on the right is minimized by regret matching at that information set, so each grows like \( \sqrt{T} \), and with \( |\mathcal{I}_i| \) information sets the full-game regret grows like \( |\mathcal{I}_i| \sqrt{T} \), giving average regret \( R^T_i / T = O(1/\sqrt{T}) \to 0 \). The bridge to Nash is a classical result from online learning. In a two-player zero-sum game, if both players use no-regret algorithms, then the pair of their time-averaged strategies converges to a Nash equilibrium, and the gap from equilibrium (exploitability) is bounded by the sum of the two average regrets. The reason it is the average strategy, not the current one, is essential. The current strategy \( \sigma^T \) keeps oscillating as the players chase each other's regrets and need never converge, but the running average \( \bar{\sigma}^T(I,a) \propto \sum_t \pi^{\sigma^t}_i(I)\, \sigma^t(I,a) \) (weighting each iterate by the player's own reach probability that iteration) smooths out the oscillation and provably approaches equilibrium. In practice one runs CFR for many iterations, accumulating both the regret sums and the reach-weighted strategy sums, and reports the normalized average strategy as the equilibrium approximation.

CFR+, deep CFR, and the poker results

Plain CFR converges but slowly, and two lines of work sped it up. CFR+ (Tammelin, 2014) makes two changes. It clamps accumulated regrets at zero after every iteration rather than letting negative regret build up (so an action that became good is tried again immediately, not after its regret climbs back from deeply negative), and it weights later iterations more heavily in the average. Empirically CFR+ converges roughly an order of magnitude faster and was the engine behind the essentially-solved heads-up limit Hold'em result of Bowling, Burch, Johanson, and Tammelin (2015). The scaling problem is memory. Tabular CFR stores a regret and strategy entry for every information set, and large games have far too many. Deep CFR (Brown, Lerer, Gross, and Sandholm, 2019) replaces the tables with neural networks that generalize across information sets, training a network to predict the accumulated regrets from features of the information set, and so approximates CFR without enumerating the game.

These methods produced the first superhuman poker agents in the hardest common benchmark. Libratus (Brown and Sandholm, 2018) beat top human professionals at heads-up no-limit Texas Hold'em, combining a blueprint strategy computed by a CFR variant with real-time nested subgame solving that recomputed a finer strategy for the actual situation during play, plus a self-improvement module that patched holes the opponents found. Pluribus (Brown and Sandholm, 2019) went further to the far harder six-player no-limit game, where the two-player zero-sum equilibrium theory does not even strictly apply, and still beat elite professionals, using a cheaper depth-limited search and abstraction. A complementary line, Neural Fictitious Self-Play (Heinrich and Silver, 2016), reaches approximate equilibria in imperfect-information games by combining reinforcement learning against the average opponent with supervised learning of one's own average strategy, a different route to the same no-regret destination.

What transfers to real decision problems, and what does not

The transferable core is threefold. First, search as a policy-improvement operator is general. Whenever a fast policy can be evaluated by lookahead against a model or a scorer, the searched result is a better policy that can be distilled back, and this holds for tool-use agents and reasoning models as much as for board games. Second, self-play as an automatic curriculum transfers wherever an adversary or a difficulty can scale with the learner. Third, the value-equivalence principle, model only what changes the decision, is a design rule for any model-based system. What does not transfer is more important to state clearly. Games are closed worlds with known, cheap, perfect simulators (or, for MuZero, learnable ones from abundant self-play data), a clean scalar reward, and unlimited free experience. Real decision problems usually have none of these. There is no simulator of a customer, a market, or a human conversation to roll out against. Reward is ambiguous and gamed the moment it is optimized against, and self-play has no meaning when there is no symmetric adversary. The self-play result is a proof that a curriculum plus search plus distillation can reach superhuman skill from scratch when a perfect cheap simulator exists, and the central open problem in applying it elsewhere is precisely the absence of that simulator. The zero-sum assumption is also load-bearing. The Nash-convergence guarantees of CFR hold in two-player zero-sum games and degrade in general-sum or many-player settings, where equilibria multiply and are not interchangeable, which is why Pluribus's six-player success is an empirical result rather than a theorem.

Worked problems

Implementation

The first block is a complete MCTS with UCT selection, run on tic-tac-toe as a concrete game interface. It has all four phases, selection by UCT, expansion of one untried move, a uniform-random rollout to a terminal state, and backpropagation that credits each node from the perspective of the player who moved into it. Run from the empty board it returns the center as the opening move, the correct optimal choice, after about 1200 visits to that child out of 4000 simulations. The code is plain Python so the algorithm is visible with no library in the way.

import math, random
random.seed(1)

# ---- game interface: tic-tac-toe. state = (board tuple of 9, player in {+1,-1})
def start():           return ((0,) * 9, 1)
def legal(s):          b, _ = s; return [i for i in range(9) if b[i] == 0]
def step(s, a):        b, p = s; nb = list(b); nb[a] = p; return (tuple(nb), -p)
LINES = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)]
def winner(s):
    b, _ = s
    for x, y, z in LINES:
        if b[x] != 0 and b[x] == b[y] == b[z]:
            return b[x]                       # +1 or -1
    return 0 if all(v != 0 for v in b) else None   # 0 draw, None ongoing

class Node:
    __slots__ = ("s", "parent", "a", "N", "W", "children", "untried")
    def __init__(self, s, parent=None, a=None):
        self.s, self.parent, self.a = s, parent, a
        self.N, self.W = 0, 0.0
        self.children = {}
        self.untried = legal(s)

def uct_child(node, c=1.4142135623730951):
    logN = math.log(node.N)
    # UCT(i) = W_i/N_i + c * sqrt(ln N_parent / N_i)
    return max(node.children.values(),
               key=lambda ch: ch.W / ch.N + c * math.sqrt(logN / ch.N))

def rollout(s):
    while winner(s) is None:                  # play uniformly at random to the end
        s = step(s, random.choice(legal(s)))
    return winner(s)                          # +1, -1, or 0

def mcts(root_state, iters=4000):
    root = Node(root_state)
    for _ in range(iters):
        node, s = root, root_state
        while not node.untried and node.children:      # SELECTION
            node = uct_child(node); s = node.s
        if node.untried:                               # EXPANSION
            a = node.untried.pop(); s = step(node.s, a)
            node = node.children.setdefault(a, Node(s, node, a))
        z = rollout(s)                                 # SIMULATION
        while node is not None:                         # BACKPROPAGATION
            mover = -node.s[1]                          # player who moved into node.s
            node.N += 1
            node.W += 1.0 if z == mover else (0.5 if z == 0 else 0.0)
            node = node.parent
    a, ch = max(root.children.items(), key=lambda kv: kv[1].N)  # most-visited move
    return a, ch.N

move, visits = mcts(start(), 4000)
print("opening move:", move, "visits:", visits)   # -> 4 (center), ~1261 visits

The second block is a self-contained regret-matching CFR loop for rock-paper-scissors, run as self-play to near-equilibrium. It accumulates regret sums and strategy sums exactly as the derivation prescribes, and the reported average strategy converges to the uniform Nash equilibrium \( (\tfrac13, \tfrac13, \tfrac13) \) within a few thousand iterations. Switching the opponent to a fixed non-uniform strategy instead makes the average converge to the best response, the pure Paper of Problem 4.

import numpy as np

# rock-paper-scissors, row payoff matrix over actions (Rock, Paper, Scissors)
A = np.array([[0, -1, 1],
              [1,  0, -1],
              [-1, 1,  0]], dtype=float)

def regret_match(regret_sum):
    pos = np.maximum(regret_sum, 0.0)
    tot = pos.sum()
    return pos / tot if tot > 0 else np.full(3, 1 / 3)   # uniform fallback

def solve_rps(T=100000):
    r_row = np.zeros(3); s_row = np.zeros(3)   # row regret / strategy accumulators
    r_col = np.zeros(3); s_col = np.zeros(3)   # column player (payoff -A^T)
    for _ in range(T):
        row = regret_match(r_row)
        col = regret_match(r_col)
        s_row += row; s_col += col
        # counterfactual (here just expected) action utilities
        u_row = A @ col                        # value of each row action vs col mix
        r_row += u_row - row @ u_row           # regret = action util - strategy util
        u_col = (-A.T) @ row                   # column payoff is -A^T
        r_col += u_col - col @ u_col
    return s_row / s_row.sum(), s_col / s_col.sum()

row_avg, col_avg = solve_rps()
print("row average strategy:", np.round(row_avg, 4))   # -> [0.3333 0.3333 0.3333]
print("col average strategy:", np.round(col_avg, 4))   # -> [0.3333 0.3333 0.3333]

The third block is the AlphaZero-style policy-value network forward pass and the PUCT selection, given side by side in PyTorch and JAX. The network is a residual convolutional tower with a policy head (logits over the action space) and a value head (a scalar in \( [-1, 1] \) via tanh). The shapes are annotated. Both implementations of PUCT select move d (index 3) on the statistics of Problem 5, matching the hand computation.

import torch
import torch.nn as nn
import torch.nn.functional as F

class ResBlock(nn.Module):
    def __init__(self, ch):
        super().__init__()
        self.c1 = nn.Conv2d(ch, ch, 3, padding=1, bias=False); self.b1 = nn.BatchNorm2d(ch)
        self.c2 = nn.Conv2d(ch, ch, 3, padding=1, bias=False); self.b2 = nn.BatchNorm2d(ch)
    def forward(self, x):
        y = F.relu(self.b1(self.c1(x)))
        y = self.b2(self.c2(y))
        return F.relu(x + y)                       # residual

class PolicyValueNet(nn.Module):
    # in_ch board planes -> (policy logits over n_actions, value in [-1,1])
    def __init__(self, in_ch=17, ch=64, blocks=4, n_actions=362, board=19):
        super().__init__()
        self.stem  = nn.Sequential(nn.Conv2d(in_ch, ch, 3, padding=1, bias=False),
                                   nn.BatchNorm2d(ch), nn.ReLU())
        self.tower = nn.Sequential(*[ResBlock(ch) for _ in range(blocks)])
        self.p_conv = nn.Conv2d(ch, 2, 1, bias=False); self.p_bn = nn.BatchNorm2d(2)
        self.p_fc   = nn.Linear(2 * board * board, n_actions)
        self.v_conv = nn.Conv2d(ch, 1, 1, bias=False); self.v_bn = nn.BatchNorm2d(1)
        self.v_fc1  = nn.Linear(board * board, ch); self.v_fc2 = nn.Linear(ch, 1)
    def forward(self, x):                          # x: (B, in_ch, board, board)
        h = self.tower(self.stem(x))               # (B, ch, board, board)
        p = F.relu(self.p_bn(self.p_conv(h))).flatten(1)
        logits = self.p_fc(p)                      # (B, n_actions)
        v = F.relu(self.v_bn(self.v_conv(h))).flatten(1)
        v = torch.tanh(self.v_fc2(F.relu(self.v_fc1(v)))).squeeze(-1)  # (B,)
        return logits, v

net = PolicyValueNet().eval()
with torch.no_grad():
    logits, value = net(torch.zeros(2, 17, 19, 19))
print(logits.shape, value.shape)                   # (2, 362) (2,)

def puct_select(P, N, Q, c_puct=1.5):
    # a* = argmax_a [ Q + c_puct * P * sqrt(sum N) / (1 + N) ]
    U = c_puct * P * torch.sqrt(N.sum()) / (1.0 + N)
    return int(torch.argmax(Q + U))

P = torch.tensor([0.50, 0.30, 0.15, 0.05])
N = torch.tensor([60.0, 20.0, 15.0, 5.0])
Q = torch.tensor([0.20, 0.10, -0.05, 0.40])
print("PUCT selects index", puct_select(P, N, Q))  # -> 3  (move d)

import jax, jax.numpy as jnp
import flax.linen as fnn

class ResBlock(fnn.Module):
    ch: int
    @fnn.compact
    def __call__(self, x, train=False):
        y = fnn.Conv(self.ch, (3, 3), padding="SAME", use_bias=False)(x)
        y = fnn.relu(fnn.BatchNorm(use_running_average=not train)(y))
        y = fnn.Conv(self.ch, (3, 3), padding="SAME", use_bias=False)(y)
        y = fnn.BatchNorm(use_running_average=not train)(y)
        return fnn.relu(x + y)                     # residual

class PolicyValueNet(fnn.Module):
    ch: int = 64; blocks: int = 4; n_actions: int = 362; board: int = 19
    @fnn.compact
    def __call__(self, x, train=False):            # x: (B, board, board, in_ch) NHWC
        h = fnn.relu(fnn.BatchNorm(use_running_average=not train)(
                fnn.Conv(self.ch, (3, 3), padding="SAME", use_bias=False)(x)))
        for _ in range(self.blocks):
            h = ResBlock(self.ch)(h, train)         # (B, board, board, ch)
        p = fnn.Conv(2, (1, 1), use_bias=False)(h)
        p = fnn.relu(fnn.BatchNorm(use_running_average=not train)(p)).reshape(x.shape[0], -1)
        logits = fnn.Dense(self.n_actions)(p)       # (B, n_actions)
        v = fnn.Conv(1, (1, 1), use_bias=False)(h)
        v = fnn.relu(fnn.BatchNorm(use_running_average=not train)(v)).reshape(x.shape[0], -1)
        v = jnp.tanh(fnn.Dense(1)(fnn.relu(fnn.Dense(self.ch)(v)))).squeeze(-1)  # (B,)
        return logits, v

net = PolicyValueNet()
x = jnp.zeros((2, 19, 19, 17))
params = net.init(jax.random.PRNGKey(0), x)
logits, value = net.apply(params, x)
print(logits.shape, value.shape)                    # (2, 362) (2,)

def puct_select(P, N, Q, c_puct=1.5):
    U = c_puct * P * jnp.sqrt(N.sum()) / (1.0 + N)
    return int(jnp.argmax(Q + U))

P = jnp.array([0.50, 0.30, 0.15, 0.05])
N = jnp.array([60.0, 20.0, 15.0, 5.0])
Q = jnp.array([0.20, 0.10, -0.05, 0.40])
print("PUCT selects index", puct_select(P, N, Q))   # -> 3  (move d)

How it is done in practice

The gap between the derivations and a production system is mostly engineering scale and parallelism. AlphaZero's Go network was a 40-block, 256-channel residual tower, trained on thousands of TPUs generating millions of self-play games. The reported training used 5,000 first-generation TPUs for self-play and 64 second-generation TPUs for training, and reached superhuman Go, chess, and shogi within hours to days. The search at play time is small by comparison, on the order of 800 simulations per move, because each simulation is a single network evaluation rather than a rollout. The dominant cost is therefore batched neural network inference, and the central systems problem is keeping the accelerator busy. A single MCTS descent is inherently sequential (you must evaluate a leaf before you know where to descend next), so implementations use virtual loss, which temporarily pessimizes a node being explored by a pending simulation so that parallel threads descend different paths, and batch the resulting leaf evaluations together. DeepMind's mctx library implements MCTS as pure-JAX batched array operations so an entire batch of games searches in lockstep on a TPU, which is a substantial rewrite of the pointer-chasing tree in the Python above.

The open reproductions show the same shape at community scale. Leela Zero reproduced AlphaGo Zero for Go using games contributed by volunteers over the internet, and Leela Chess Zero (lc0) did the same for chess and is now a top engine, competing with and sometimes surpassing the alpha-beta engine Stockfish, which itself adopted a small neural evaluation (NNUE) that is evaluated incrementally inside a classical alpha-beta search. The two paradigms converged. On the imperfect-information side, the practical systems add abstraction (bucketing similar hands and bet sizes to shrink the game to a solvable size) and real-time subgame solving, because even CFR+ cannot store a table for full no-limit Hold'em's \( 10^{160} \)-ish information sets. Libratus's real-time solver ran on a supercomputer during the match to recompute strategy for the specific situation faced, which is the imperfect-information analogue of AlphaZero's per-move search.

One practical caution the theory hides is that the guarantees are asymptotic. UCT converges to minimax only in the limit of infinite simulations, and with a finite budget it can be led astray by a shallow trap that random rollouts fail to see, which is exactly the failure mode AlphaGo's value network was introduced to fix. CFR converges in the average strategy, so an implementation that accidentally reports the current strategy will look badly non-convergent even when it is correct. And the neural priors can be systematically wrong in ways search cannot fix within its budget if the prior assigns near-zero probability to the only good move, since PUCT's exploration term is proportional to the prior. This is why AlphaZero adds Dirichlet noise to the root priors during self-play, to guarantee every move gets some exploration regardless of what the network thinks.

The current research frontier

Four threads are active. The first is efficiency. EfficientZero (Ye et al., 2021, Tsinghua and collaborators) reached human-level Atari performance with roughly two hours of real-time experience by adding a self-supervised consistency loss to MuZero's learned model and correcting its value targets, attacking the sample inefficiency that makes model-based RL expensive. Sampled MuZero (Hubert et al., 2021, DeepMind) extended the family to large and continuous action spaces by planning over sampled actions, connecting back to progressive widening. Stochastic MuZero handles genuinely stochastic environments by learning chance outcomes.

The second thread is the marriage of search with large language models. The search-as-policy-improvement idea reappears wherever a model generates candidate reasoning steps that are scored and selected, in tree-of-thoughts style search over reasoning traces and, more consequentially, in the training loops of reasoning models such as DeepSeek-R1 (2025) and the OpenAI o-series, which use a policy-gradient loop over verifiable outcomes rather than MCTS but share AlphaZero's structure of generating one's own ever-harder curriculum and training on the parts that verified. Whether explicit tree search or implicit sampling is the better outer loop for language reasoning is an open and actively contested question, with strong results on both sides.

The third thread is imperfect-information at scale beyond poker. ReBeL (Brown, Bakhtin, Lerer, Gong, 2020, Meta AI) unified the perfect- and imperfect-information approaches by doing AlphaZero-style self-play reinforcement learning and search over belief-state value functions, recovering CFR-style guarantees while using a learned network, and reached superhuman heads-up poker with far less domain-specific machinery than Libratus. Player of Games (Schmid et al., 2021, DeepMind) pushed a single algorithm to handle both perfect- and imperfect-information games. And DeepMind's work on Stratego (DeepNash, 2022) and on Diplomacy (Cicero, Meta AI, 2022, which added natural-language negotiation to a search-based planner) shows the imperfect-information and multi-agent frontier moving toward games with enormous action spaces, many players, and communication, where the clean two-player zero-sum theory only partially applies.

The fourth thread is the honest accounting of transfer, pursued across several groups. Work on offline and model-based RL at Berkeley, UT Austin, and elsewhere asks how much of the self-play recipe survives when the cheap perfect simulator is removed, and the general answer so far is that the search-and-distill operator transfers but the free-experience assumption does not, which keeps the practical frontier on problems where a simulator or a verifier can be built.

Open source to read

• google-deepmind/open_spiel is the reference library for research on games, with dozens of perfect- and imperfect-information games behind a common API and clean implementations of CFR, CFR+, MCCFR, MCTS, and NFSP. Start in open_spiel/python/algorithms/cfr.py to see the exact regret and average-strategy accumulation derived above, then mcts.py.
• google-deepmind/mctx is MCTS as batched, JIT-compiled JAX array operations, the production form of the search used in AlphaZero and MuZero. Read mctx/_src/search.py to see how the sequential tree is expressed as vectorized updates for the accelerator.
• leela-zero/leela-zero is a full, readable C++ reimplementation of AlphaGo Zero for Go, trained by a distributed volunteer effort. src/UCTNode.cpp has the PUCT selection and virtual loss in production form.
• LeelaChessZero/lc0 is the chess counterpart and a top-tier engine. The file src/mcts/search.cc is the heavily optimized real-world MCTS, worth reading against the toy Python here to see what production adds.
• suragnair/alpha-zero-general is a compact, well-documented AlphaZero for arbitrary games, the best first read for the whole self-play loop end to end. The files MCTS.py and Coach.py hold the search and the training loop respectively.
• The CFR family in open_spiel (deep CFR in python/algorithms/deep_cfr.py, external-sampling MCCFR, and CFR+) is the cleanest place to study the imperfect-information algorithms end to end against real games like Kuhn and Leduc poker.

Common misconceptions

"Alpha-beta is an approximation of minimax." It is exact. Alpha-beta prunes only subtrees that provably cannot change the root value and returns the identical minimax value. The approximation in a real engine comes entirely from cutting off search at a fixed depth and using a heuristic evaluation there, not from the pruning.

"MCTS picks the move with the highest average value." Standard MCTS plays the most-visited root child, not the highest-mean one. The visit count is more robust. A child accumulates visits only by repeatedly surviving UCT selection, whereas a high mean from few visits is noise. AlphaZero likewise acts on the visit distribution, and it is that distribution, not the raw values, that trains the policy head.

"AlphaZero's tree search does rollouts like classical MCTS." It does none. Every leaf is evaluated by a single call to the value network, and the policy network supplies the priors. There is no random playout anywhere. This is why it needs hundreds of simulations per move rather than tens of thousands, and why the quality of the network, not the depth of rollouts, sets the strength.

"MuZero learns to predict the next frame." It deliberately does not. Its model is trained only to make the predicted reward, value, and policy match reality along real trajectories, the value-equivalence principle. The latent state need not resemble the true state in any other respect, which is the whole point, because it spends capacity only on what changes decisions.

"You can solve poker with minimax if you search deep enough." You cannot, at any depth. Imperfect information makes optimal play necessarily randomized and couples the tree through information sets, so the bottom-up max-min recursion is not even well defined. Poker needs equilibrium computation (CFR), which is a different algorithm with a different guarantee.

"CFR converges to a Nash equilibrium in its current strategy." The current strategy oscillates and need not converge. It is the reach-weighted average strategy over all iterations that provably approaches equilibrium. An implementation that reports the last iterate will look broken even when it is correct.

"Self-play works for any problem." Self-play as a curriculum needs a symmetric adversary and, for MuZero-style planning, cheap abundant experience from a simulator or a learnable model. Real decision problems that lack a cheap simulator and a clean reward get the search-and-distill operator but not the free automatic curriculum, which is the crux of why the recipe does not simply transfer.

"The exploration constant in UCT is fixed at \( \sqrt{2} \)." \( \sqrt{2} \) is the value the Hoeffding derivation gives for rewards in \( [0,1] \) under the independence assumption, which rollouts violate. In practice \( c \) is tuned per domain and per reward scale. Effective values commonly range from about 0.4 to 2, and AlphaZero's PUCT constant even grows slowly with visit count.

Self-check

References

1. Russell, S. & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th ed.). Pearson. Chapters on adversarial search and games. aima.cs.berkeley.edu
2. Sutton, R. & Barto, A. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press. incompleteideas.net/book
3. Knuth, D. & Moore, R. (1975). An analysis of alpha-beta pruning. Artificial Intelligence 6(4), 293-326. doi:10.1016/0004-3702(75)90019-3
4. Genesereth, M., Love, N. & Pell, B. (2005). General game playing: overview of the AAAI competition. AI Magazine 26(2), 62-72. doi:10.1609/aimag.v26i2.1813
5. Auer, P., Cesa-Bianchi, N. & Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine Learning 47, 235-256. doi:10.1023/A:1013689704352
6. Kocsis, L. & Szepesvari, C. (2006). Bandit based Monte-Carlo planning. ECML. doi:10.1007/11871842_29
7. Coulom, R. (2006). Efficient selectivity and backup operators in Monte-Carlo tree search. Computers and Games. doi:10.1007/978-3-540-75538-8_7
8. Browne, C., Powley, E., Whitehouse, D., Lucas, S., Cowling, P., et al. (2012). A survey of Monte Carlo tree search methods. IEEE Trans. Computational Intelligence and AI in Games 4(1), 1-43. doi:10.1109/TCIAIG.2012.2186810
9. Gelly, S. & Silver, D. (2011). Monte-Carlo tree search and rapid action value estimation in computer Go. Artificial Intelligence 175(11), 1856-1875. doi:10.1016/j.artint.2011.03.007
10. Silver, D., Huang, A., Maddison, C., et al. (2016). Mastering the game of Go with deep neural networks and tree search. Nature 529, 484-489. doi:10.1038/nature16961
11. Silver, D., Schrittwieser, J., Simonyan, K., et al. (2017). Mastering the game of Go without human knowledge. Nature 550, 354-359. doi:10.1038/nature24270
12. Silver, D., Hubert, T., Schrittwieser, J., et al. (2018). A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science 362(6419), 1140-1144. doi:10.1126/science.aar6404
13. Schrittwieser, J., Antonoglou, I., Hubert, T., et al. (2020). Mastering Atari, Go, chess and shogi by planning with a learned model (MuZero). Nature 588, 604-609. doi:10.1038/s41586-020-03051-4
14. Zinkevich, M., Johanson, M., Bowling, M. & Piccione, C. (2007). Regret minimization in games with incomplete information. NeurIPS. papers.nips.cc
15. Tammelin, O. (2014). Solving large imperfect information games using CFR+. arXiv:1407.5042. arxiv.org/abs/1407.5042
16. Bowling, M., Burch, N., Johanson, M. & Tammelin, O. (2015). Heads-up limit hold'em poker is solved. Science 347(6218), 145-149. doi:10.1126/science.1259433
17. Brown, N. & Sandholm, T. (2018). Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science 359(6374), 418-424. doi:10.1126/science.aao1733
18. Brown, N. & Sandholm, T. (2019). Superhuman AI for multiplayer poker (Pluribus). Science 365(6456), 885-890. doi:10.1126/science.aay2400
19. Brown, N., Lerer, A., Gross, S. & Sandholm, T. (2019). Deep counterfactual regret minimization. ICML. arxiv.org/abs/1811.00164
20. Heinrich, J. & Silver, D. (2016). Deep reinforcement learning from self-play in imperfect-information games (NFSP). arXiv:1603.01121. arxiv.org/abs/1603.01121
21. Brown, N., Bakhtin, A., Lerer, A. & Gong, Q. (2020). Combining deep reinforcement learning and search for imperfect-information games (ReBeL). NeurIPS. arxiv.org/abs/2007.13544
22. Ye, W., Liu, S., Kurutach, T., Abbeel, P. & Gao, Y. (2021). Mastering Atari games with limited data (EfficientZero). NeurIPS. arxiv.org/abs/2111.00210
23. Schmid, M., Moravcik, M., Burch, N., et al. (2021). Player of Games. arXiv:2112.03178. arxiv.org/abs/2112.03178