Game Evaluation Functions
When the game tree is too big to search to the end — cut off at k-ply, score the board statically, and back up as if it were terminal
The Simplest Explanation
Tic-Tac-Toe is small enough to search to the end. Chess is not — so search only k moves ahead (a k-ply search), then score each leaf position with a static evaluation function , and run Minimax/Alpha-Beta exactly as if those leaves were real endings.
e(n) is static (board → number), continuous in [−1, +1], positive = good for MAX. It replaces true game values at the horizon; everything above it is unchanged minimax machinery.
The Two Standard Components
Shannon's 1950 recipe for chess:
| Component | Examples |
|---|---|
| Material | piece counts weighted by value (queen ≈ 9, rook ≈ 5, …) |
| Positional | center control, pawn structure, mobility, king safety |
This framework underlies essentially every chess engine's leaf scoring.
Tic-Tac-Toe Worked Example
Eval: count open rows/columns/diagonals for MAX, subtract those open for MIN.
Position after MAX takes a corner and MIN takes the center:
- MAX open lines: 4
- MIN open lines: 5
Note: Tic-Tac-Toe's true minimax value with perfect play is 0 (a draw) — the eval is only an estimate at a shallow horizon, and that gap is exactly why deeper search plays better.
How It Plugs Into Search
- Grow the tree to depth k
- At horizon leaves compute
- Back up with min/max (α–β prunes along the way)
- Root's best child = move played; then search again after opponent replies
Deeper k ⇒ more accurate backups but exponential cost — α–β's best case is what buys practical depth.
Properties
| Property | Value |
|---|---|
| Range | typically [−1, +1] in this course |
| Static? | Yes — inspects only the current board |
| Relation to heuristic h | Same idea transplanted to adversarial search |
| Accuracy lever | Search depth k and eval quality trade off |