Is a backed-up value always a maximum?

No. The operator depends on whether the node represents maximization, minimization, chance, or another specified rule.

Only relative to the explored model and the accuracy of its input values.

Can deeper search change it?

Yes, particularly when replacing heuristic frontier estimates with more informative continuations.

AI Glossary / Statistics and probability / Intermediate

Backed-up value

Definition

A backed-up value is a value assigned to an earlier state or search-tree node by combining values from its successors according to a specified decision rule. In minimax game search, values from terminal outcomes or evaluated frontier positions are propagated upward using maximum and minimum operations. The result expresses the value implied by the explored continuations and the assumed behavior of the players.

What it means

A search system looks ahead to possible consequences, evaluates them, and then reasons backward toward the present choice. The number produced at a parent node is its backed-up value. It summarizes later possibilities under the algorithm's rules rather than simply describing the immediate position.

For a maximizing player, the backed-up value is the best available successor value. For an opponent modeled as minimizing that player's utility, it is the worst available successor value from the maximizing player's perspective.

The supplied category is retained, but this term is primarily a search and decision-making concept. It is not a statistical confidence measure, a stored backup copy, or necessarily a probability. Other search and planning algorithms use different backup rules, so the surrounding algorithm matters.

How it works

First define whose utility is being measured and how terminal outcomes are scored. Expand the tree until terminal states or a chosen search frontier is reached. At true terminal states, use the specified utility; at a depth cutoff, use an evaluation function that estimates future desirability.

Process the tree upward. At a MAX node, take the maximum of its child values. At a MIN node, take the minimum. Repeat until the root has a value, and select an action attaining the appropriate optimum.

If the tree instead contains chance nodes, an expectation-based method combines child values using their probabilities. In cost-based planning, immediate costs and successor estimates may be combined under minimization. These operations should not be mixed without specifying the model and the meaning of each node.

For a complete finite deterministic two-player zero-sum game tree, minimax yields the value under optimal adversarial play. With heuristic frontier evaluations, the backed-up result inherits their limitations and the chosen horizon. Alpha-beta pruning can avoid exploring branches that cannot affect the minimax decision while preserving the result under its assumptions; it does not make an inaccurate evaluation function exact.

Three practical examples

A board-game program propagates terminal win, draw, and loss utilities upward to choose a move.
A planning demonstration uses a decision tree to compare choices after accounting for modeled later responses.
A search researcher compares shallow and deeper searches to see how additional explored consequences change the root's backed-up estimate.

Think of it this way

Think of planning several moves ahead in a game and then working backward. At each point you ask which choice the player moving there would make. The value you carry back to the current move reflects that sequence of choices, not the most attractive outcome anywhere in the tree.

Worked example

Consider an original complete two-ply game tree. MAX chooses between Left and Right. After either choice, MIN selects one of two terminal outcomes. All utilities are measured for MAX, with larger values preferred.

Under Left, terminal utilities are 7 and 2. MIN chooses 2, so Left's backed-up value is min(7,2) = 2. Under Right, utilities are 5 and 4. MIN chooses 4, so Right's value is min(5,4) = 4.

At the root, MAX chooses max(2,4) = 4 and therefore selects Right. Choosing Left because it contains a possible payoff of 7 would ignore the opponent's modeled response.

Now consider a different model in which the second step is an equally likely random outcome rather than MIN's choice. Left has expected value (7+2)/2 = 4.5, while Right has expected value (5+4)/2 = 4.5. The choices tie under this chance model. The leaf values stayed the same; changing the backup operator changed the decision problem. These are exact calculations for the stipulated small trees, not estimates of an unspecified real opponent's behavior.

Illustrative case study

Fictional case: Harbor Games develops a teaching game with a small deterministic state space. A prototype initially chooses whichever branch contains the largest leaf score and repeatedly loses to an opponent that selects unfavorable responses.

The team replaces that rule with alternating MAX and MIN backups and displays the intermediate values so learners can inspect the reasoning. For a larger version of the game, it labels cutoff evaluations as estimates and checks how deeper search changes decisions.

The fictional case illustrates a corrected decision rule. It does not claim that minimax is suitable for every business negotiation or that real counterparties always behave as perfectly informed zero-sum opponents.

Common misconceptions and mistakes

Common mistakes include selecting the largest leaf anywhere in the tree, averaging adversarial choices without justification, and switching the utility perspective partway through a calculation.

Another mistake is treating a depth-limited backed-up estimate as a guaranteed final payoff. Its reliability depends on the evaluation function and unexamined continuations. Costs, rewards, and probabilities also have different units and combination rules. Finally, neural-network backpropagation computes gradients, while backing up search values propagates decision evaluations; the shared directional language does not make the procedures identical.

Business use

Understanding backed-up values helps teams inspect AI planning and search decisions. It makes explicit how future outcomes, adversarial responses, and chance assumptions are translated into a present action.

Use a decision model whose operators match the situation. Report the search horizon, utility scale, and whether leaves are exact outcomes or heuristic estimates. In simulations of strategic situations, compare plausible opponent models rather than presenting a minimax value as an unconditional forecast of what will happen.

Check your understanding

Why does MAX choose Right despite the payoff 7 under Left?

Answer: MIN can select Left's alternative payoff of 2, while Right guarantees 4 in the stipulated complete minimax tree.

Related terms

Minimax
Game tree
Evaluation function
Alpha-beta pruning
terminal utility
expectimax
Bellman backup
search horizon

Learn next

trace minimax on larger trees, compare chance and adversarial nodes, and examine how heuristic evaluation affects depth-limited search.

Sources

Sources: Russell and Norvig, Artificial Intelligence: A Modern Approach, author-hosted algorithm collection, minimax and alpha-beta figures, https://aima.eecs.berkeley.edu/algorithms.pdf. The search sense is explicit despite the retained statistics category. The two-ply examples and fictional teaching-game case are original.

Previous: Backdoor Next: Backfitting