Tic-tac-toe

A two-player game played on a 3×3 grid, where players alternate marks and try to place three in a row. With optimal play, every game ends in a draw.

Game tree: A branching representation of possible game states and the moves connecting them. Each legal mark creates a branch, and every complete path represents one game.
Three-in-a-row: A line of three matching marks in a row, column, or diagonal on a 3×3 grid. Completing this pattern is the game's winning condition.
Minimax algorithm: A search algorithm that selects a move by maximizing a player's outcome while minimizing the opponent's. Its small game tree lets the algorithm examine every possible continuation.
Noughts and crosses: The common British name for the same 3×3 mark-placement game called tic-tac-toe in North America. The name differs by region, but the rules and objective are the same.
Minimax: A decision rule that chooses moves by assuming an opponent will respond optimally. It identifies moves that prevent a perfect opponent from winning.
Winning condition: A rule that specifies which game state counts as a victory. The winning condition is exactly three marks aligned in one of eight possible lines.
Alpha–beta pruning: A technique that skips game-tree branches that cannot affect a minimax decision. It demonstrates how search can avoid examining irrelevant moves, even when exhaustive search is feasible.
Gomoku: A two-player alignment game usually played on a larger grid, with five marks in a row needed to win. Its longer winning line and larger board create a much deeper search problem.
Combinatorial game theory: The mathematical study of games whose positions and moves can be analyzed formally. Tic-tac-toe is a small example of a game with precisely defined positions and moves.
Draw (game): A game result in which neither player wins under the rules. A full board without a three-mark line ends in a draw.

Linked from 4 pages

Hales–Jewett theoremRelated: The theorem explains why sufficiently high-dimensional tic-tac-toe variants have unavoidable monochromatic winning lines.