The mechanism
A policy selects an action. Search evaluates possible continuations before that selection, using a transition model and a value estimate at the explored boundary. In this rule-defined tic-tac-toe specimen, legal moves change a nine-cell board, players alternate, X maximizes and O minimizes a score. Terminal wins receive exact ±100 and draws receive zero. At a truncated leaf, an explicitly authored open-line heuristic supplies a provisional value. Deeper search may replace that guess with a different consequence, at a cost in visited nodes. The heuristic is not learned. Research systems such as AlphaZero combine learned value/policy functions with search; their training and search results are not reproduced by this small example.
- Read the board, infer the next player from legal move counts and enumerate legal actions.
- Apply each action to a separate board and alternate the maximizing/minimizing player.
- Use exact terminal outcomes when available; at the selected depth, use the declared heuristic instead.
- Choose the action under the resulting values and count the visited states. Preserve the original board for comparison.
Science and assumptions
Search, value estimates and selected actions
Use terminal utility, or a boundary heuristic when depth is zero, otherwise alternate maximizing and minimizing over legal transitions.
Symbols and units
- s,a
- Board state and legal action
discrete state / action
- d
- Remaining lookahead depth
plies
- T
- Rule-defined transition
function
- u,h,V
- Terminal utility, authored heuristic and search value
score
The displayed position has X at opposite corners and O in the center, so O moves next. Compare lookahead depths 1 through 5 and inspect each legal action’s value and visited-node count. A separate exact test uses an immediate X winning row and verifies that the winning move has value +100 regardless of the nonterminal heuristic.
Assumptions Finite deterministic perfect-information game, alternating players and a declared fixed heuristic. This is minimax teaching search, not AlphaZero or a learned planning system.
Engineering example
The displayed position has X at opposite corners and O in the center, so O moves next. Compare lookahead depths 1 through 5 and inspect each legal action’s value and visited-node count. A separate exact test uses an immediate X winning row and verifies that the winning move has value +100 regardless of the nonterminal heuristic.
Distinctions and tradeoffs
Searching at inference time is not the same operation as updating learned parameters. An authored heuristic must not be presented as a trained value function.
More search can improve a decision when the transition/value assumptions are useful, but consumes time and can amplify a wrong model. More visited nodes are not evidence of better real-world reasoning.
Inference-time selection, planning and tool policies can involve additional computation beyond one forward pass. Their benefits require task-specific verification and explicit environmental semantics.
Specifications and interfaces
- Teaching specimen
- Search and value
The displayed position has X at opposite corners and O in the center, so O moves next. Compare lookahead depths 1 through 5 and inspect each legal action’s value and visited-node count. A separate exact test uses an immediate X winning row and verifies that the winning move has value +100 regardless of the nonterminal heuristic.
- Evidence boundary
- Explicit computed example
Finite deterministic perfect-information game, alternating players and a declared fixed heuristic. This is minimax teaching search, not AlphaZero or a learned planning system.
Interfaces
- Inputs and convention Input
- Read the board, infer the next player from legal move counts and enumerate legal actions.
- Computed result and scope Output
- Trace legal game actions through a bounded alternating-player search and distinguish terminal evidence from a truncated heuristic.
Check your understanding
What changes when lookahead depth increases in this specimen?
- The evaluated continuation tree and computation spent selecting an action
- The fixed heuristic is automatically trained
- The rules of the environment change
Answer and reasoning
The evaluated continuation tree and computation spent selecting an action
The evaluated continuation tree and computation spent selecting an action. Finite deterministic perfect-information game, alternating players and a declared fixed heuristic. This is minimax teaching search, not AlphaZero or a learned planning system.
Evidence and scope
The workbench executes the declared small mechanism. Numeric examples are authored and independently checked, not measurements from the cited research. Finite deterministic perfect-information game, alternating players and a declared fixed heuristic. This is minimax teaching search, not AlphaZero or a learned planning system.
Open Mathematical foundations for the bounded executable mechanism and its record. General numerical labs are an additional reference library.