Connect Four

1. Minimax with Alpha-Beta Pruning

Connect Four has ~4 trillion possible positions. Minimax explores the game tree up to depth 6, choosing moves that maximize AI score while minimizing yours. Alpha-Beta Pruning cuts branches that can't affect the result, reducing search nodes by up to 50%.

function minimax(board, depth, alpha, beta, isMaximizing, startTime) {
  if (Date.now() - startTime > 2000)
    return { score: evaluateBoard(board, 2), col: -1 };
  const winner = checkWinner(board);
  if (winner?.winner === 2) return { score: 100_000, col: -1 };
  if (winner?.winner === 1) return { score: -100_000, col: -1 };
  const validCols = getValidCols(board);
  if (validCols.length === 0 || depth === 0)
    return { score: evaluateBoard(board, 2), col: -1 };
  validCols.sort((a, b) => Math.abs(a - 3) - Math.abs(b - 3));
  if (isMaximizing) {
    let best = { score: -Infinity, col: validCols[0] };
    for (const col of validCols) {
      const newBoard = board.map(row => [...row]);
      dropDisc(newBoard, col, 2);
      const result = minimax(newBoard, depth-1, alpha, beta, false, startTime);
      if (result.score > best.score) best = { score: result.score, col };
      alpha = Math.max(alpha, best.score);
      if (beta <= alpha) break;
    }
    return best;
  }
  // ... minimizing player
}

2. Heuristic Evaluation — Window Scoring

We score every consecutive window of 4 cells in all directions. 3-in-a-row with an empty space scores +5. 2-in-a-row scores +2. Opponent 3-in-a-row scores -4. Center column positions get a +3 bonus — statistically the most valuable.

function scoreWindow(window: Cell[], player: 1|2): number {
  const opp = player === 1 ? 2 : 1;
  const playerCount = window.filter(c => c === player).length;
  const emptyCount = window.filter(c => c === 0).length;
  const oppCount = window.filter(c => c === opp).length;
  if (playerCount === 4) return 100;
  if (playerCount === 3 && emptyCount === 1) return 5;
  if (playerCount === 2 && emptyCount === 2) return 2;
  if (oppCount === 3 && emptyCount === 1) return -4;
  return 0;
}

3. Move Ordering

Alpha-Beta Pruning works best when strong moves are evaluated first. We sort candidate columns by proximity to the center (column 3), since center moves statistically lead to more winning positions.

// Sort columns: center first → better pruning
validCols.sort((a, b) =>
  Math.abs(a - 3) - Math.abs(b - 3)
);

4. Physics-based Drop Animation

Discs fall with simulated gravity and bounce on landing. velocity increases each frame (gravity = 0.8), and reverses with a damping factor (0.3) on impact.

// Each animation frame:
velocity += 0.8;           // gravity
currentY += velocity;      // move down

if (currentY >= targetY) {
  currentY = targetY;
  velocity = -velocity * 0.3;  // bounce
  if (Math.abs(velocity) < 0.5) {
    // animation complete
  }
}