Connect-4

Medium Algorithms: Minimax, Alpha-Beta Pruning, Transposition Tables

Connect-4

Medium Algorithms: Minimax, Alpha-Beta Pruning, Transposition Tables

Overview

Connect-4 is a solved game—we know the first player can force a win with perfect play. With ~4.2 × 10^13 possible positions, transposition tables become essential for avoiding redundant computation.

Rules

Two players alternate dropping colored discs into a 7-column, 6-row grid. Discs fall to the lowest available row. The first player to align four discs horizontally, vertically, or diagonally wins.

Transposition Tables

A transposition occurs when different move sequences lead to the same position. Without a transposition table, the algorithm evaluates the same position multiple times.

// Hash the current position
hash = computeHash(position)

if hash in transpositionTable:
  return transpositionTable[hash]  // Cache hit!

// Evaluate normally
value = alphaBeta(position, depth, alpha, beta, isMaximizing)

// Store result
transpositionTable[hash] = value
return value

Key Properties

  • Branching Factor: ~7 legal moves per position (fewer as game progresses)
  • Avg Game Length: ~42 moves
  • Search Depth: 8-12 plies with effective pruning
  • Memory: Hash table stores ~1-10 million positions

Move Ordering

The order in which we explore moves dramatically affects alpha-beta pruning efficiency. Connect-4 strategies:

  1. Center-Bias Ordering: Evaluate center columns first (strongest positions)
  2. Threat Assessment: Prioritize moves that block opponent wins
  3. Winning Moves: Check for immediate winning moves first

Interactive Demo

Play Connect-4 against the AI:

Connect-4 Game

Click a column to drop your disc (red). The AI plays yellow.

Heuristic Evaluation

Since Connect-4 can be computationally expensive, we use evaluation heuristics:

evaluate(position):
  score = 0
  
  // Count aligned pieces
  score += countAlignedPieces(position, player) * 10
  score -= countAlignedPieces(position, opponent) * 10
  
  // Bonus for center control
  score += centerBonus(position)
  
  return score

Implementation Notes

  • Zobrist Hashing: Use fast bitwise hashing for transposition lookups
  • Iterative Deepening: Search progressively deeper until time runs out
  • Killer Moves: Track moves that caused cutoffs at the same depth
  • Position Database: Pre-computed perfect play data available

Code on GitHub

See the complete Connect-4 solver with endgame databases and opening books.

Next Steps

Ready for non-deterministic games? Explore Catan where Monte Carlo Tree Search handles hidden information and probabilistic elements.