AI Glossary / Graphs and symbolic AI / Beginner
Terminal test
Definition
A terminal test is a procedure that decides whether a state is a genuine ending of a modeled game, task, or episode. It returns an answer such as true or false according to the task's rules. In game search, the test determines when further play should stop and the final utility should be used. It is separate from both scoring the outcome and deciding to stop search early.
What it means
The test answers “Is this over?” It does not necessarily answer “Who won?” or “How good is this position?” A separate utility function evaluates terminal outcomes.
The state representation must contain enough information to apply the rules. A visible board may be sufficient for a simple game, while another game may require turn information, repetition history, or a move counter.
How it works
List every condition that ends the task and implement a precise check for each. Combine them according to the rules, and ensure that an ending is recognized before ordinary successor generation continues.
In a basic minimax procedure, a true terminal test returns the state's utility immediately. Otherwise, the algorithm examines successor states and combines their values according to whose turn it is. A practical search may also use a cutoff test for depth or time limits. If a cutoff occurs in a nonterminal state, a heuristic evaluation is needed instead of pretending that the game has ended.
Validate the test on reachable examples, boundary cases, and different ending reasons. If callers can provide malformed states, specify whether a separate validator rejects them.
Three practical examples
1. Tic-tac-toe: the test checks whether either player has completed a winning line or whether the board is full without a winner.
2. A finite task simulation: the test identifies completion of the objective or a defined failure condition, while recording which condition occurred.
3. Game-tree search: the test distinguishes a genuinely finished position from a promising but unfinished position encountered at the search's maximum depth.
Think of it this way
Think of the official checking whether a match has ended under the rules. The official first determines that play is over; the result can then be recorded as a win, loss, or draw.
The analogy is limited because a computational test must encode the actual conditions and available state. A timer stopping an analyst's examination is not automatically a rule ending the match. Separate the game's boundaries from the computation's boundaries.
Worked example
For ordinary three-by-three tic-tac-toe, represent empty cells with a dot. Use the terminal rule “a winning row, column, or diagonal exists, or the board has no empty cells.” Assume the input is a reachable valid position and play stops on a win.
Board A has rows “X X X”, “O O .”, and “. . .”. The first row contains three X marks, so the terminal test is true even though four cells are empty. A test that checks only whether the board is full would incorrectly continue play.
Board B has rows “X X .”, “O O .”, and “. X .”. No row, column, or diagonal contains three matching nonempty marks, and empty cells remain. The terminal test is false. Reaching a depth limit while analyzing Board B does not change that answer.
Board C has rows “X O X”, “X O O”, and “O X X”. Every cell is occupied and no winning line exists, so the test is true and the outcome is a draw. If utility is +1 for an X win, −1 for an O win, and 0 for a draw, Board A has utility +1 and Board C has utility 0.
The Boolean terminal answer is true for both A and C. Their different utilities demonstrate why ending detection and outcome evaluation should not be confused. The examples have been checked by inspecting all rows, columns, and diagonals, not by executing a game engine.
Illustrative case study
Fictional case: BoardLab builds a small teaching game. Its search code stops only when no empty squares remain, so it generates moves after an earlier winning line. A second shortcut treats every depth-limited leaf as a draw.
The team implements the complete terminal rule and keeps the computational cutoff separate. It adds examples of early wins, full-board draws, and unfinished cutoff positions. Reviewers confirm that final utility is used only for genuine endings.
Common misconceptions and mistakes
Do not equate terminal with winning. Draws and losses are endings too.
Checking for zero legal moves is not a universal terminal test. Some games require a pass or define special handling when a player cannot move.
A cutoff test is not a substitute for the game's terminal test. It answers whether the search should stop expanding, which can happen before the game ends.
Do not assume one terminal rule works across variants. Changed victory conditions, repetition rules, or scoring conventions can require a different test. Also avoid using final utility before confirming that the state lies within that function's intended domain.
Business use
Terminal tests are small components with large consequences for search and learning systems. An incorrect ending condition can produce impossible continuations, wrong targets, or misleading evaluation scores.
Write down the ending conditions in language domain reviewers can understand, then map them to precise state checks. Record ending reasons where useful and ensure simulations agree with deployed rules. Review boundary cases when rules change.
People also ask
Does the test return the winner?
It need not. Its core role is to identify an ending; outcome information can be supplied separately or alongside that answer.
Can a state be terminal before the board is full?
Yes. Many games end as soon as a victory condition is achieved.
Should a depth limit make terminal true?
No, unless that limit is genuinely part of the task rules. An ordinary search depth limit belongs to a cutoff test.
Check your understanding
Why is Board C terminal even though neither player has a winning line?
Answer: The board is full, which is a draw-ending condition under the stated rules. Terminal status does not require a winner.
Related terms
- Terminal states
- Cutoff test
- Utility function
- Evaluation function
- Minimax
- Terminal state
- game rules
- state validation
- search depth
Learn next
Study cutoff tests and heuristic evaluation next. For each worked board, record terminal status, ending reason, and whether exact terminal utility is applicable. Then imagine stopping search at Board B and explain why a heuristic estimate is needed instead of an invented final result.
More in Graphs and symbolic AI
- Temporal logic - Temporal logic is a family of formal languages for expressing how statements hold across time or sequences of states.
- Temporal-projection - Temporal-projection is the reasoning task of determining what will hold after specified actions or events, given an initial description and a model of change.
- Term - In first-order logic, a term is an expression that denotes an object in the domain under an interpretation and, when variables occur, a variable assignment.
- Ternary search tree - A ternary search tree is a data structure for storing and finding strings one character at a time.
- Theta* - Theta* is a path-planning algorithm that searches a grid while allowing the resulting route to contain straight segments at arbitrary angles.
- Thought vector - A thought vector is an informal name for a learned numerical representation of the content of a sentence or other input.
Sources
Primary reference: Russell and Norvig, AIMA game-playing slides, https://aima.cs.berkeley.edu/slides-pdf/chapter06.pdf, minimax and resource-limit sections. The algorithm's terminal/utility and cutoff/evaluation distinction was read directly. The board states, inspections, and fictional case are original teaching material under explicitly stated game rules.
Previous: Terminal symbol Next: Termination condition