Tic-tac-toe

1. Minimax Algorithm

Minimax is a decision-making algorithm used in two-player games. The AI simulates all possible future moves and picks the one that maximizes its chance of winning while minimizing yours.

function minimax(
  board: (string | null)[],
  depth: number,
  isMaximizing: boolean,
  alpha: number,
  beta: number
): number {
  const winner = checkWinner(board);
  if (winner === 'O') return 10 - depth;
  if (winner === 'X') return depth - 10;
  if (board.every(cell => cell !== null)) return 0;

  if (isMaximizing) {
    let best = -Infinity;
    for (let i = 0; i < 9; i++) {
      if (!board[i]) {
        board[i] = 'O';
        best = Math.max(best, minimax(board, depth + 1, false, alpha, beta));
        board[i] = null;
        alpha = Math.max(alpha, best);
        if (beta <= alpha) break;
      }
    }
    return best;
  } else {
    let best = Infinity;
    for (let i = 0; i < 9; i++) {
      if (!board[i]) {
        board[i] = 'X';
        best = Math.min(best, minimax(board, depth + 1, true, alpha, beta));
        board[i] = null;
        beta = Math.min(beta, best);
        if (beta <= alpha) break;
      }
    }
    return best;
  }
}

2. Alpha-Beta Pruning

Alpha-Beta Pruning optimizes Minimax by skipping branches that can't possibly affect the final decision. This reduces the number of nodes evaluated from O(b^d) to O(b^(d/2)).

// Alpha: best score maximizer can guarantee
// Beta: best score minimizer can guarantee
// If beta <= alpha, prune remaining branches
if (beta <= alpha) break;

3. Win Detection

All 8 winning combinations are checked after every move.

const WIN_PATTERNS = [
  [0,1,2],[3,4,5],[6,7,8], // rows
  [0,3,6],[1,4,7],[2,5,8], // cols
  [0,4,8],[2,4,6]          // diagonals
];

function checkWinner(board: (string | null)[]): string | null {
  for (const [a,b,c] of WIN_PATTERNS) {
    if (board[a] && board[a] === board[b] && board[a] === board[c]) {
      return board[a];
    }
  }
  return null;
}