A mathematical game specifies participants, available choices, information and consequences of combined choices. A normal-form game records complete strategies and payoffs; an extensive-form game records the sequence of decisions and what each player knows at them.
For example, matching pennies gives each player two actions and opposing payoffs depending on whether their choices agree. Its equilibrium requires mixed strategies. A puzzle with one decision maker is often called a game informally, but strategic interaction and game theory enter when outcomes depend on several decision makers' choices. The rules determine the mathematical object; a physical board alone does not.
Peg solitaire is a one-player finite board puzzle in which a peg jumps over an adjacent peg into an empty hole, and the jumped peg is removed. In a standard orthogonal version, the three holes must lie consecutively in one row or column. Board shape, initial occupied holes and the desired final configuration are part of the problem specification.
Every move decreases the number of pegs by exactly one, so a play starting with pegs has at most moves if at least one peg remains. A solution reducing to a single peg must have exactly moves. This is a counting necessity, not a guarantee of solvability.
The puzzle illustrates state-space search: a position is a subset of occupied holes, and directed edges are legal jumps. Backtracking explores possible continuations, while board symmetries can identify equivalent states. Algebraic invariants and monotone weight functions can prove some target configurations unreachable without enumerating every play.
A two-player game on nine positions arranged in a three-by-three grid. Players alternate marking empty positions and stop when one has a full row, column or diagonal, or when the board is full. A game search must stop at the first win. Distinct move histories can reach the same position; canonical occupancy sets or bitboards make that equality available to memoization. Quotienting by board symmetry changes the requested output unless distinct oriented positions are subsequently restored.
