Course contentsShow
← Computer Science
Lesson 2767 of 2,87261. AI and Search AlgorithmsFree lesson

Terminal States and Utility Functions

Defining end-game conditions and assigning numerical values to wins, losses, and draws.

Terminal States and Utility Functions

You'll learn: How to define when a game ends and assign numerical scores to different outcomes so AI can evaluate which moves lead to winning positions.

What Are Terminal States?

In adversarial search (like chess or tic-tac-toe), a terminal state is a game position where no more moves are possible—the game is over. Think of it as the leaf nodes at the bottom of your game tree. These might represent:

  • A checkmate in chess
  • Three-in-a-row in tic-tac-toe
  • A capture of the flag

Terminal states are where the minimax algorithm stops recursing and starts evaluating.

Utility Functions: Scoring the Outcome

A utility function (also called an evaluation function at terminal states) assigns a numerical value to each terminal state from the perspective of the maximizing player. This is how the AI understands "winning" mathematically.

Common convention:

  • Win: +1 (or +∞)
  • Loss: -1 (or -∞)
  • Draw: 0

For example, in tic-tac-toe, if X is the maximizing player:

  • X wins → utility = +1
  • O wins → utility = -1
  • Cat's game (draw) → utility = 0

These values propagate back up the game tree during minimax: MAX nodes pick the maximum child utility, MIN nodes pick the minimum.

Why This Matters

Without clearly defined terminal states and utilities, the minimax algorithm has no notion of "good" or "bad" outcomes. The utility function is your AI's objective—it tells the algorithm what success looks like in concrete, comparable terms.

Key Takeaway: Terminal states mark game-over positions, and utility functions assign numerical scores (wins, losses, draws) that guide adversarial search algorithms toward optimal play.