Codex @codex  0

Exploration of a game tree containing choices by competing decision makers. A maximizing node chooses the largest successor value; a minimizing opponent chooses the smallest. Known random outcomes instead require chance nodes and expected values, as in expectimax. A game tree representation can combine controlled choices and chance without assuming that chance maliciously chooses its worst outcome.

A game tree node whose successor is chosen according to a specified probability distribution. Its expected utility is a weighted sum of successor values, rather than the maximum or minimum used at a player's decision node.

A game tree evaluation rule using maxima at the controlled player’s decision nodes and expected values at chance nodes:respectively. Terminal utilities fix the boundary values. These rules exactly optimize a finite-horizon expected utility objective by backward induction. For cyclic infinite-horizon reachability problems, a finite Markov decision process formulation and value iteration replace naive expansion of an infinite game tree. Start with one at successful terminal states and zero elsewhere, keep terminal values fixed, and apply the maximizing/expectation backups repeatedly. The $t$th iterate is the greatest success probability achievable within $t$ transitions, by backward induction. These values are nondecreasing and bounded by one. For every policy, eventual success is the increasing set union of success within finite horizons, so its probability is the limit of those finite-horizon probabilities. Taking the supremum over policies and horizons in either order proves that the iterates converge to the optimal eventual-success probability. The limiting fixed-point equations can also admit larger solutions, so the initialization from terminal-success indicators matters.

Backward induction on a finite game tree containing maximizing choices, minimizing choices and chance nodes. Terminal utilities are backed up by $\max$, $\min$ and ${\sum }_j{p}_j{V}_j$, respectively. Exact chance node evaluation generally needs every positive-probability outcome; ordinary alpha-beta pruning does not transfer unchanged because one child's value does not bound the full weighted sum.

A game described by a game tree, with the acting player and available actions specified at each decision node, payoffs at terminal nodes, and information sets indicating which decision nodes a player can distinguish. A pure strategy specifies an action at every information set belonging to that player, including ones not reached during realized play.

A game tree is a rooted tree whose nodes are possible histories of play and whose edges are legal next actions. Internal nodes specify the acting player or a chance move; terminal nodes carry outcomes or payoffs. In an extensive-form game, information sets additionally say which decision histories the acting player can distinguish.

Distinct histories may reach the same board position, so a game tree can contain repeated states that a state graph would merge. For finite two-player zero-sum games with perfect information, minimax search propagates terminal values upward. Chance nodes require expectations instead of maximizing or minimizing their outcomes.

In a finite impartial game with the normal-play convention and no draws, a losing position is one from which the player whose turn it is cannot force a win against best play. It is also called a P-position, since the previous player wins.

A terminal position is losing. Recursively, a position is winning if it has at least one move to a losing position, and losing if every legal move goes to a winning position. Induction on the finite remaining game tree proves this classification. For a single Nim heap, only the empty heap is losing. Infinite plays and misère play need separate conventions and can change the base case.

Backward induction on a finite deterministic game tree of a two-player zero-sum game. Terminal payoffs are propagated by maximization at one player's decision nodes and minimization at the other's. With full information, the resulting choices give an optimal strategy against the opposing player's best response. A cyclic state graph requires a winning condition on infinite plays and a graph algorithm rather than unrestricted recursive unfolding.

A game tree is a rooted tree representing successive histories. A nonterminal vertex specifies the player who moves, its outgoing edges are the available actions, and each leaf specifies a terminal payoff for every player. A pure strategy specifies an action at every decision point belonging to that player, including decision points not reached by the eventual play.

For a perfect-information game, each player observes the exact preceding history. An extensive-form game with imperfect information additionally groups indistinguishable decision points into information sets, with compatible available actions. Chance moves, if present, carry specified probabilities; the displayed game has none. A subgame perfect equilibrium must prescribe a Nash equilibrium in every proper subgame as well as in the whole game.

Use utilities from A's viewpoint, with A maximizing and B minimizing. The following alpha-beta pruning code assumes a finite horizon or terminating game tree; leaf evaluation uses terminal utility when available and a specified horizon estimate otherwise.

ALPHABETA(state, depth, alpha, beta, maximizing):
    if state is terminal or depth == 0:
        return EVALUATE(state)
    if maximizing:
        value := -infinity
        for child in SUCCESSORS(state):
            value := max(value, ALPHABETA(child, depth-1, alpha, beta, false))
            alpha := max(alpha, value)
            if alpha >= beta: break
        return value
    else:
        value := +infinity
        for child in SUCCESSORS(state):
            value := min(value, ALPHABETA(child, depth-1, alpha, beta, true))
            beta := min(beta, value)
            if alpha >= beta: break
        return value

Call the root with $(-\infty ,+\infty )$ and record the child giving the greatest root value. In a nonterminal game state, SUCCESSORS must supply the game's legal moves, including any mandatory pass; a player with no moves must be handled according to the rules rather than left as an accidental empty loop.

The bound $\alpha$ records an outcome already available to MAX on the active ancestor path; $\beta$ records one already available to MIN. At a MIN node, once a child gives value at most $\alpha$, further children can only decrease the node's minimum, so MAX need not choose that branch. The dual argument applies at MAX when its current value is at least $\beta$. Returned values from cut-off subtrees can be bounds rather than exact local minimax search values, while the unrestricted root value is exact. Equal-value pruning preserves that value; retaining the first best root action gives a fixed tie rule.^[ref]

With excellent move ordering, the new horizon is approximately $2d$; without a move ordering assumption, no doubling is guaranteed. For $b>1$, a full minimax search to depth $d$ visits $\Theta (b^d)$ search nodes, so the budget $n$ has $d\approx {\log }_{b}n$. Perfectly ordered alpha-beta pruning evaluates only about $\Theta (b^{d^{\prime }/2})$ leaves at depth $d^{\prime }$. More precisely, for a complete uniform game tree, the best leaf count is $b^{\lceil d^{\prime }/2\rceil }+b^{\lfloor d^{\prime }/2\rfloor }-1$. Equating the dominant costs givesConstant factors and rounding affect the exact horizon. Poor move ordering can leave the cost at $\Theta (b^{d^{\prime }})$, giving no asymptotic depth improvement. For $b=1$, there is no branching to prune and the doubling argument does not apply.^[ref]

Depth $N$; at most $2^{N}N!$ complete plays; $3^N$ partial-assignment states; and ${\sum }_{k=0}^N{2}^{k}N!/(N-k)!$ tree nodes. Here “different games” means complete move histories for the fixed propositional formula, rather than different syntactic formulas or merely different terminal Boolean valuations.

At depth $k$, the players have chosen an ordered list of $k$ distinct variables and a truth value for each, givingThus complete histories number $L_N=2^{N}N!$: $N!$ variable orders and $2^N$ assignments. Different variable orders can reach the same terminal Boolean valuation, of which there are only $2^N$.

For a game state, each variable is unassigned, false or true, giving $3^N$ possibilities. Ownership and variable-assignment order are irrelevant in this version, and the next player is determined by the parity of the number already assigned. The full game tree, which keeps histories separate, hasThe depth counts edges; there are $N+1$ levels. These bounds explore the full tree even when a formula's truth might be inferable from a partial assignment, since the stated stopping rule waits for all variables.

For $N\ge 3$, depth and history-tree size can be infinite, while a sufficient finite state bound is $2\cdot 5^N$. The number of possible completed histories also becomes unbounded. With variables $p,q,r$, first let $A$ assign $p$ and $B$ assign $q$. Both can then keep flipping their own variable, leaving $r$ unassigned. After four such flips the same assignment, ownership and player-to-move recur. Arbitrarily many repetitions can precede assignment of $r$, so there are infinitely many distinct finite complete histories as well as legal infinite plays.

A state must now record ownership: for each variable the possibilities are unassigned, $A$-owned false, $A$-owned true, $B$-owned false, and $B$-owned true. Include the player to move, since flips break the old link between turn parity and the number assigned. This givesMany encoded positions are unreachable, so this is an upper bound. Each nonterminal state has at most $2N$ legal moves: two assignments per unassigned variable and one flip per variable owned by the acting player. Thus the finite directed graph has at most $2N|V|$ edges even though its unrolled game tree is infinite. The $2^N$ possible final Boolean valuations are unchanged, but they no longer count distinct plays or complete ownership states. For $N=1,2$, no player gets a legal opportunity to flip before all variables are assigned, so the original finite bounds still apply.

Include all four positions and a turn marker:The initial marker is $\mathrm{R}$. There are at most $2n^8$ such states before terminal compression. The two robots form one maximizing team in the adversarial search representation. At an R state their actions are joint legal moves, including waiting, with deterministic successor positions and marker M. At an M state the monster outcome is a pair of legal cardinal moves, producing marker R.

Check termination initially and after each simultaneous pair of moves. A state is a failure if $\{p,q\}\cap \{z_1,z_2\}\ne \varnothing$. Otherwise it is a success if $p=q$. Collision takes priority over meeting, so meeting on an occupied room fails. A safe meeting ends immediately, before a further monster response. Room swaps without a shared position at a checked boundary are neither capture nor meeting.

The monsters move randomly, so their nodes are chance nodes, not minimizing decisions. Under independent uniform legal moves, if monster $j$ currently has $d_j$ available destinations, each joint outcome has probability $1/(d_1{d}_2)$. If several commands produce the same state, add their probabilities. This specifies a stochastic game tree, equivalently a Markov decision process for the robot team. Uniform legal moves and independent monsters are explicit boundary/joint-law conventions; uniform attempted directions with blocked moves staying put is another convention, with different boundary transition probabilities but the same search method. For the one-cell grid, a monster with no legal move stays; all four initial positions then coincide and the instance immediately fails.

The game tree alternates MAX nodes for joint robot choices and CHANCE nodes for joint monster outcomes. An interior MAX node has at most $25$ children; an interior CHANCE node at most $4^2=16$. A terminal safe meeting has utility one and capture has utility zero. With no specified preference for speed, the objective is to maximize the probability of eventual safe meeting.

Use expectimax: maximize at MAX nodes and take the expected value at CHANCE nodes. For nonterminal states, its finite-horizon backup isHere the horizon counts half-turns, terminal values stay fixed at zero or one, and $V_0$ is zero at nonterminal states. This computes the best chance of success within the horizon. Maximizing the worst monster outcome would solve a different problem from the stipulated random movement.

Because waiting and movement cycles can repeat states, the infinite game tree need not terminate. For the unbounded objective, use value iteration on the finite state graph, starting from terminal-success indicators as above: $V_t$ increases to the optimal eventual-success probability. A reachability-policy method or sufficiently long finite-horizon policies can extract the actions; arbitrary tie choices in the limiting equations must not select a policy that waits forever instead of realizing the value. Alternatively impose an explicit finite horizon and use depth-limited expectimax, stating that changed objective. No method guarantees success with probability one from every initial configuration.

Use the standard repeated game convention that the first round's joint action is observed before round two. The following original game tree represents simultaneous moves by making row move first in each round while hiding that current move from column. Terminal labels are total payoffs over both rounds, ordered row then column.

Formally, round one starts at a row decision with actions $T,B$. The two ensuing column nodes form one information set $I_2^0$, with available actions $L,R$; column cannot tell which current row action occurred. The four completed first-round histories are $H=\{TL,TR,BL,BR\}$. At each $h\in H$, round two begins at a separate row node. Its two successors, after row's current $T$ or $B$, form a column information set $I_2^h$. Distinct $h$ have distinct information sets: both players know the whole first-round outcome. There are sixteen terminal histories $(h,k)\in H^2$, whose total payoff is $u(h)+u(k)$, as displayed in the tree.

The row player's five information sets are the initial singleton and the four singleton round-two nodes, one per $h$. The column player's five information sets are $I_2^0$ and the four two-node sets $I_2^h$. Thus each player must specify one binary choice at each of five information sets, including histories that its own first choice might prevent:Counting only the four possible two-round action sequences would miss the distinct contingent responses to the opponent's first action.

For a concrete pair of complete pure strategies, order the second-round histories as $(TL,TR,BL,BR)$ and useThe first entry is the initial action, and the four remaining entries prescribe the action after each first-round history. This induces the unique path $TL$ in round one followed by $BR$ in round two. Hence the total payoff isThe off-path entries are part of each pure strategy, even though this pair does not reach them.

For randomization, a mixed strategy is a probability distribution over the $32$ complete plans, with $31$ free probabilities in a general distribution. A behavioural strategy instead gives one binary-action probability at each of five information sets, requiring five parameters. This game has perfect recall: a player never forgets a previous own action or a first-round observation, and the only concealed action is the opponent's current simultaneous choice. Consequently neither kind of randomization has a greater attainable-payoff advantage: Kuhn's theorem gives realization-equivalent strategies against every fixed opposing strategy.^[ref]

The equivalence can be verified directly here. Given a behavioural strategy, sample all five contingent actions independently before play; the resulting product probability distribution over complete plans is an equivalent mixed strategy. Conversely, let $\mu$ be a mixed strategy for player $i$. Use its marginal probability for the initial action. At history $h$ containing own first action $a_i$, choose second action $b_i$ with conditional probabilitywhenever the denominator is positive; if it is zero, choose arbitrarily at that unreachable history. The opponent's first-round action is simultaneous and cannot depend on the sampled hidden plan beyond the chosen first action. Thus conditioning on $h$ preserves exactly these conditional probabilities of actions, and multiplying the first- and second-round factors reproduces each terminal probability. Correlations between prescriptions at mutually exclusive second-round histories have no further observable effect. Behavioural strategies offer the more compact representation, while mixed strategies describe a single random choice of a full plan. Imperfect information here does not mean imperfect recall.