Problem Definition
Connect 4 is a two-player game on a 6×7 grid. Players alternate dropping pieces. First to connect four in a row wins. The AI must decide which column to play.
Minimax Algorithm
Builds a game tree to depth d. Maximizer (AI) picks highest score, minimizer (human) picks lowest. Leaf nodes evaluated by heuristic. Time: O(b^d) where b=7, d=search depth.
Alpha-Beta Pruning
Maintains two bounds: α (best for max) and β (best for min). When α ≥ β, prune remaining branches — they cannot affect the outcome.
Move ordering (centre-first: [3,2,4,1,5,0,6]) dramatically improves pruning by establishing tighter bounds earlier.
Evaluation Heuristic
Scans all 4-cell windows: 4-in-a-row = +1000, 3+1 empty = +5, 2+2 empty = +2. Opponent 3-in-a-row = -4. Centre column bonus = +3 per piece.
Empirical Results
| Depth |
No Pruning |
Alpha-Beta |
Pruning % |
| 2 | 49 | 27 | 44.9% |
| 4 | 2,401 | 440 | 81.7% |
| 6 | 117,649 | 5,217 | 95.6% |
| 8 | 5,764,801 | 45,810 | 99.2% |
Pruning effectiveness increases with depth: from 44.9% at depth 2 to 99.2% at depth 8. The deeper you search, the more you save — making alpha-beta pruning essentially free optimization.