un

guest
1 / ?
back to lessons

Branching Factor & Node Count

A game tree models every possible sequence of moves from a starting position. Each node represents a board state. Each edge represents one legal move. The tree's structure determines whether search remains feasible.

Key Parameters

Branching factor b: number of legal moves available at a typical position.

Depth d: number of plies (half-moves) to search ahead.

Node count at depth d: b^d

Total nodes across all depths: 1 + b + b² + ... + b^d = (b^(d+1) − 1) / (b − 1)

For large b and d, the total ≈ b^d (dominated by the leaf level).

4×4×4 Tic-Tac-Toe

The full game tree: b ≈ 64 (legal squares), d = 64 (total moves). Full node count ≈ 64^64 ≈ 10^115. The observable universe contains roughly 10^80 atoms. Brute-force search is physically impossible.

Game Tree & Alpha-Beta Pruning

Computing Tree Size

Chess provides more realistic numbers. Average branching factor b ≈ 35. A 6-ply search (3 moves each side) requires approximately 35^6 nodes.

Compute the number of leaf nodes for a chess search of depth d = 6 plies with branching factor b = 35. Then compute the same for d = 10 plies. Show both calculations explicitly.

Alpha-Beta Pruning: Reducing the Exponent

Alpha-beta pruning eliminates subtrees that cannot affect the minimax result. The key insight: if you already know one branch gives value V, you can prune any sibling branch whose value provably falls below V (for the maximizing player) or above V (for the minimizing player).

Best-Case Geometry

Under optimal move ordering (best moves searched first), alpha-beta reduces the effective branching factor from b to √b. Search depth effectively doubles for the same node budget:

Full search: b^d nodes

Alpha-beta best case: b^(d/2) nodes

Example: b=35, d=6. Full: 35^6 ≈ 1.84 × 10^9. Alpha-beta: 35^3 = 42,875. Reduction factor: ~43,000.

In practice, move ordering is imperfect. Typical reduction: b^(d×0.75) — equivalent branching factor ≈ b^0.75.

For a chess engine with b = 35 and d = 8 plies, compute the node count under: (1) full minimax search, (2) perfect alpha-beta pruning (best case). What is the reduction factor? Show all calculations.

Center-Corner Duality

Hamming notes a geometric duality in the 4×4×4 cube: there exists an inversion sending the 8 corner positions to the 8 center positions (the inner 2×2×2 cube) & vice versa, while preserving all 76 winning lines.

Counting Lines Through a Position

In a 4×4×4 cube, positions differ in how many winning lines pass through them:

Corner positions: 7 lines each (4 face diagonals, 2 edge lines, 1 space diagonal)

Edge-center positions: 4 lines each

Face-center positions: 6 lines each

Body-center positions (inner 2×2×2): 7 lines each

The duality maps corners (7 lines) to body-centers (7 lines). Both sets form 'hot spots.'

Why Hot Spots Matter Geometrically

A player controlling more high-line-count positions controls more potential winning lines. This is a direct geometric argument: line coverage maximization guides move selection without any search.

The 4×4×4 cube has 76 total winning lines and 64 positions. The 8 corners each lie on 7 lines, the 8 body-center positions each lie on 7 lines, the 24 face-center positions each lie on 6 lines, and the 24 edge positions each lie on 4 lines. Verify: do these counts add up consistently? Compute the total count of (position, line) incidences from both sides: by summing over positions, and separately by counting 4 endpoints per line. Do the two totals agree?

Evaluation Functions

Every game-playing program needs an evaluation function: a function mapping board states to numeric values (positive = good for the maximizing player, negative = good for the minimizing player). The evaluation function provides the boundary condition at the leaves of the search tree.

Linear Evaluation Functions

A linear evaluation function assigns a weight w_i to each feature f_i of the position:

E(position) = w_1 × f_1 + w_2 × f_2 + ... + w_n × f_n

For 4×4×4 tic-tac-toe: features might include open lines controlled, positions in high-line-count squares, forks threatened. For chess: material count, center control, king safety, pawn structure.

This is a linear function in feature space — a hyperplane in ℝ^n. Two positions with the same feature values get the same evaluation regardless of all other differences. The geometry of the evaluation function determines what the program 'sees.'

Samuel's checker program improved by adjusting the weight vector w — gradient descent in the space of linear evaluation functions.

A simple 4×4×4 tic-tac-toe evaluation function uses two features: (1) f_1 = number of your open lines (lines where you have pieces and opponent has none), (2) f_2 = number of opponent's open lines. The evaluation: E = w_1 × f_1 − w_2 × f_2. If w_1 = 2 and w_2 = 3, compute E for a position where you have 12 open lines and your opponent has 8. Then: if E > 0 means the position favors you, what does this result say about the position?

Geometry & the Boundary of Formalization

The game tree has a clean geometric structure: exponential growth at depth d, reducible to b^(d/2) by alpha-beta, further reducible by restricting to high-value positions (hot spots reduce effective b). The evaluation function defines a hyperplane in feature space.

All of this is clean, precise, formally complete. It describes the center of the game-playing problem — the region where mathematical structure provides clear guidance.

The boundary — where to switch from rule-application to exploration, when to trade positional advantage for tactical opportunity, how to recognize emergent patterns beyond the evaluation function — resists this formalization. Hamming's tacit knowledge lives at that boundary.

The geometry lets you compute how much search you can afford. It does not tell you what to look for.

Reflect on the geometry covered in this lesson. The game tree formalism (b^d nodes, alpha-beta reduction to b^(d/2), linear evaluation functions) provides a precise description of the *tractable* parts of game playing. Where does the geometry break down — and what property of game-playing intelligence lies beyond the geometric model? Give a specific answer, not a general observation.