Worked system design solution

Design Tic Tac Toe with Minimax AI

Tic Tac Toe extended with a computer opponent: the classic minimax algorithm for perfect play, alpha-beta pruning for ~10x speedup, depth-limited search with a heuristic for larger boards, configurable difficulty (random / medium / unbeatable), and an Iterative Deepening wrapper that respects time budgets. Implemented in TypeScript, Java, and C++.

LLDMedium22 min readgameminimaxalpha-beta-pruningairecursion

Clarify Requirements

Rules, AI difficulty levels, performance budget

Functional requirements

Board — 3×3 grid. Each cell empty, X, or O.
Two players — X always moves first; players alternate.
Win condition — three of the same symbol in any row, column, or diagonal.
Draw — board full with no winner.
makeMove(player, row, col) — places the symbol if legal, mutates board, switches turn.
AI opponent with three difficulty levels:
- Easy — picks a random empty cell.
- Medium — depth-limited minimax (depth 2-3) — sometimes loses to perfect play.
- Hard — full minimax with alpha-beta — never loses, wins when human errs.
aiMove() — computes the AI's best response. Time budget: 50 ms (3×3 is trivially in budget).
Generalisable to N×N — same algorithm scales to 4×4 (with depth-limit + heuristic) but performance degrades sharply.

Non-functional requirements

Hard difficulty must explore the full 3×3 tree in < 5 ms thanks to alpha-beta pruning.
The minimax function must be pure — given a board state, return the best score; never mutate.
AI behaviour should be deterministic for a given board (helps unit tests). Tie-break by first explored move.

Out of scope (v1)

Item	Reason
Networked multiplayer	Out of scope
Animated UI	Rendering layer
Opening book / endgame tablebase	3×3 doesn't need it
Monte Carlo Tree Search	Overkill for 3×3
Reinforcement-learning agent	Different problem

Key edge cases

Edge case	Expected behaviour
AI called on a finished board	Throw / return null
AI is first to move on empty board	Should pick center (best opening)
Two equally-good moves	Pick the first one explored (deterministic)
Human plays at center first	AI must respond at a corner, not edge
Depth-limited minimax cannot reach terminal	Use heuristic eval (#open lines for me - #open lines for opponent)

Minimax complexity

Plain minimax for 3×3: explores ≤ 9! / something but bounded by board size = ~250 k leaves worst case.
With alpha-beta pruning: closer to 5 k leaves, ~50× speedup.
With move ordering (search center first, then corners, then edges): another 2-3×.

Interview: When asked "is minimax practical for 3×3?" the answer is yes (250 k nodes is microseconds). For 4×4 it's borderline. For 5×5 you need either depth-limited heuristic or MCTS.

Core Entities

Board, Player, Move, AI strategy hierarchy

Domain objects

Player

X or O enum. Has other() returning the opponent.

Board

Field	Type	Notes
`grid`	char[3][3]	Empty (.), X, or O
`size`	int	3 by default; supports N
`emptyCount`	int	For fast terminal detection
`isLegal(r, c)`	method	Empty cell in bounds
`place(r, c, sym)`	method	Mutate
`undo(r, c)`	method	Restore (for minimax)
`winner()`	method	Returns `X`, `O`, `DRAW`, or `ONGOING`
`legalMoves()`	method	List of empty (r, c) tuples

Move

A (row, col) pair plus optional score.

AIPlayer (Strategy interface)

Method	Description
`chooseMove(board, symbol)`	Return a `Move`

Concrete strategies

RandomAI — picks a random legal move.
MinimaxAI — full game-tree search with alpha-beta. Symbol passed in so the AI can play either side.
DepthLimitedAI — minimax bounded by depth, using heuristic at leaves.
IterativeDeepeningAI — repeatedly runs minimax with depth 1, 2, 3 … until time budget expires.

Game

Field	Type	Notes
`board`	Board	The state
`current`	Player	Whose turn
`aiX`	AIPlayer?	If X is AI
`aiO`	AIPlayer?	If O is AI
`tick()`	method	Either solicit a move or have the AI move

Minimax intuition

Maximizer is the AI; Minimizer is the opponent.
Recursively evaluate every legal move; return the best score for the maximizer.
Base case: terminal board → return +1 if maximizer won, -1 if minimizer won, 0 for draw.
Adjust score by depth (+1 - depth) to prefer faster wins / slower losses.

Alpha-beta pruning

Maintain alpha (best known for maximizer so far) and beta (best known for minimizer so far). Whenever alpha >= beta, prune the rest of this branch — the opponent will not let us reach it.

function minimax(board, depth, alpha, beta, maximizing):
  if board terminal: return score(board, depth)
  if maximizing:
      v = -INF
      for move in legalMoves:
          place(move, MAX); v = max(v, minimax(board, d+1, alpha, beta, false)); undo(move)
          alpha = max(alpha, v)
          if alpha >= beta: break   // beta cut-off
      return v
  else:
      v = +INF
      for move in legalMoves:
          place(move, MIN); v = min(v, minimax(board, d+1, alpha, beta, true)); undo(move)
          beta = min(beta, v)
          if alpha >= beta: break   // alpha cut-off
      return v

Algorithm: Move ordering multiplies the pruning effect: explore likely-best moves first so cut-offs happen earlier. For tic-tac-toe, order is center, corners, edges.

Classes & Relationships

Game → Board + AIPlayer Strategy hierarchy

Class diagram

classDiagram
    class Player {
        <<enum>>
        X
        O
        EMPTY
        +other() Player
    }

    class Board {
        -grid: char[][]
        -size: int
        -emptyCount: int
        +place(r, c, p) void
        +undo(r, c) void
        +winner() Result
        +legalMoves() Move[]
        +isFull() boolean
    }

    class Move {
        +row: int
        +col: int
        +score: int
    }

    class AIPlayer {
        <<interface>>
        +chooseMove(board, sym) Move
    }

    class RandomAI {
        -rng: Random
        +chooseMove(board, sym) Move
    }

    class MinimaxAI {
        -maxDepth: int
        +chooseMove(board, sym) Move
        -minimax(board, depth, alpha, beta, maximizing, max, min) int
    }

    class IterativeDeepeningAI {
        -timeBudgetMs: int
        +chooseMove(board, sym) Move
    }

    class Game {
        -board: Board
        -current: Player
        -aiX: AIPlayer?
        -aiO: AIPlayer?
        +makeMove(r, c) void
        +tick() void
        +winner() Result
    }

    AIPlayer <|.. RandomAI
    AIPlayer <|.. MinimaxAI
    AIPlayer <|.. IterativeDeepeningAI
    Game "1" o--> "1" Board
    Game ..> AIPlayer
    Board ..> Move
    Board ..> Player

Relationships explained

Game ◇── Board — composition. New game, new board.
Game ──▶ AIPlayer (0..2) — game holds 0, 1, or 2 AI players (human vs human, human vs AI, AI vs AI).
AIPlayer ◀── concrete strategies — open for extension. New difficulty = new class.
Board ↔ Move — Board generates and applies Moves.

Strategy pattern application

Each difficulty is a separate AIPlayer implementation:

RandomAI            // pick random legal move
DepthLimitedAI(2)   // medium difficulty
DepthLimitedAI(4)   // harder
MinimaxAI()         // unbeatable on 3×3
IterativeDeepeningAI(50ms)  // best within time budget for larger boards

The Game does not know or care which strategy is in use. Adding MonteCarloAI later is a 200-line addition that does not touch Game.

Why undo() rather than copy

In recursive minimax we will place + recurse + undo for every move. Copying the board on each call is O(N²) allocation per node. Undoing in place is O(1). For 250 k nodes the difference is profound.

Trade-off: undo cannot run in parallel branches. For tic-tac-toe single-threaded is fine; if you need to parallelise (4×4+), copy the board at the top of each thread.

Iterative Deepening Search (IDS)

For boards larger than 3×3, we don't know in advance how deep we can go in the time budget. IDS:

for d = 1, 2, 3, ...:
    best = minimaxWithDepth(board, d)
    if timeBudget exceeded: break
return best

Surprisingly cheap because each iteration's cost is dominated by the leaf level; previous iterations are negligible. Bonus: if interrupted, we still have the best move from the deepest completed depth.

Interview: Mention IDS even for 3×3 — it shows you understand how to make minimax responsive in real-time settings, which is what production game AI uses.

Code Implementation

Board, MinimaxAI with alpha-beta, plus simpler strategies

TypeScript

// tic-tac-toe.ts
export type Player = 'X' | 'O' | '.';
export type Result = 'X' | 'O' | 'DRAW' | 'ONGOING';
export interface Move { row: number; col: number; score?: number; }

export class Board {
  private grid: Player[][];
  readonly size = 3;

  constructor() {
    this.grid = Array.from({ length: 3 }, () => Array<Player>(3).fill('.'));
  }

  place(r: number, c: number, p: Player): void { this.grid[r][c] = p; }
  undo(r: number, c: number): void { this.grid[r][c] = '.'; }
  cell(r: number, c: number): Player { return this.grid[r][c]; }

  legalMoves(): Move[] {
    const out: Move[] = [];
    // center, corners, edges — better for alpha-beta pruning
    const order: Array<[number, number]> = [
      [1, 1],
      [0, 0], [0, 2], [2, 0], [2, 2],
      [0, 1], [1, 0], [1, 2], [2, 1],
    ];
    for (const [r, c] of order) if (this.grid[r][c] === '.') out.push({ row: r, col: c });
    return out;
  }

  isFull(): boolean {
    for (const row of this.grid) for (const c of row) if (c === '.') return false;
    return true;
  }

  winner(): Result {
    const lines: Array<[Player, Player, Player]> = [];
    const g = this.grid;
    for (let i = 0; i < 3; i++) {
      lines.push([g[i][0], g[i][1], g[i][2]]);
      lines.push([g[0][i], g[1][i], g[2][i]]);
    }
    lines.push([g[0][0], g[1][1], g[2][2]]);
    lines.push([g[0][2], g[1][1], g[2][0]]);
    for (const [a, b, c] of lines) {
      if (a !== '.' && a === b && b === c) return a as Result;
    }
    return this.isFull() ? 'DRAW' : 'ONGOING';
  }
}

export interface AIPlayer {
  chooseMove(board: Board, sym: 'X' | 'O'): Move;
}

export class RandomAI implements AIPlayer {
  chooseMove(board: Board): Move {
    const moves = board.legalMoves();
    return moves[Math.floor(Math.random() * moves.length)];
  }
}

export class MinimaxAI implements AIPlayer {
  chooseMove(board: Board, sym: 'X' | 'O'): Move {
    const opp: 'X' | 'O' = sym === 'X' ? 'O' : 'X';
    let bestScore = -Infinity;
    let bestMove: Move = { row: -1, col: -1 };
    for (const m of board.legalMoves()) {
      board.place(m.row, m.col, sym);
      const score = this.minimax(board, 1, -Infinity, Infinity, false, sym, opp);
      board.undo(m.row, m.col);
      if (score > bestScore) { bestScore = score; bestMove = { ...m, score }; }
    }
    return bestMove;
  }

  private minimax(
    board: Board, depth: number, alpha: number, beta: number,
    maximizing: boolean, max: 'X' | 'O', min: 'X' | 'O',
  ): number {
    const w = board.winner();
    if (w === max) return 10 - depth;
    if (w === min) return depth - 10;
    if (w === 'DRAW') return 0;

    if (maximizing) {
      let v = -Infinity;
      for (const m of board.legalMoves()) {
        board.place(m.row, m.col, max);
        v = Math.max(v, this.minimax(board, depth + 1, alpha, beta, false, max, min));
        board.undo(m.row, m.col);
        alpha = Math.max(alpha, v);
        if (alpha >= beta) break;
      }
      return v;
    } else {
      let v = Infinity;
      for (const m of board.legalMoves()) {
        board.place(m.row, m.col, min);
        v = Math.min(v, this.minimax(board, depth + 1, alpha, beta, true, max, min));
        board.undo(m.row, m.col);
        beta = Math.min(beta, v);
        if (alpha >= beta) break;
      }
      return v;
    }
  }
}

export class IterativeDeepeningAI implements AIPlayer {
  constructor(private timeBudgetMs = 50) {}
  chooseMove(board: Board, sym: 'X' | 'O'): Move {
    const start = Date.now();
    let best: Move = { row: -1, col: -1 };
    const opp: 'X' | 'O' = sym === 'X' ? 'O' : 'X';
    const mm = new MinimaxAI();
    for (let d = 1; d <= 9; d++) {
      // For tic-tac-toe full minimax already terminates fast; this loop is illustrative.
      best = mm.chooseMove(board, sym);
      if (Date.now() - start > this.timeBudgetMs) break;
    }
    return best;
  }
}

Java

import java.util.*;

public class TicTacToe {
    public static class Board {
        private final char[][] g = new char[3][3];
        public Board() { for (char[] r : g) Arrays.fill(r, '.'); }
        public void place(int r, int c, char p) { g[r][c] = p; }
        public void undo(int r, int c) { g[r][c] = '.'; }
        public char cell(int r, int c) { return g[r][c]; }
        public List<int[]> legalMoves() {
            int[][] order = {{1,1},{0,0},{0,2},{2,0},{2,2},{0,1},{1,0},{1,2},{2,1}};
            List<int[]> out = new ArrayList<>();
            for (int[] o : order) if (g[o[0]][o[1]] == '.') out.add(o);
            return out;
        }
        public boolean isFull() {
            for (char[] r : g) for (char c : r) if (c == '.') return false;
            return true;
        }
        public char winner() {
            for (int i = 0; i < 3; i++) {
                if (g[i][0] != '.' && g[i][0] == g[i][1] && g[i][1] == g[i][2]) return g[i][0];
                if (g[0][i] != '.' && g[0][i] == g[1][i] && g[1][i] == g[2][i]) return g[0][i];
            }
            if (g[0][0] != '.' && g[0][0] == g[1][1] && g[1][1] == g[2][2]) return g[0][0];
            if (g[0][2] != '.' && g[0][2] == g[1][1] && g[1][1] == g[2][0]) return g[0][2];
            if (isFull()) return 'D';
            return '.';
        }
    }

    public interface AIPlayer { int[] chooseMove(Board b, char sym); }

    public static class MinimaxAI implements AIPlayer {
        @Override public int[] chooseMove(Board b, char sym) {
            char opp = (sym == 'X') ? 'O' : 'X';
            int best = Integer.MIN_VALUE;
            int[] move = new int[]{-1, -1};
            for (int[] m : b.legalMoves()) {
                b.place(m[0], m[1], sym);
                int s = minimax(b, 1, Integer.MIN_VALUE, Integer.MAX_VALUE, false, sym, opp);
                b.undo(m[0], m[1]);
                if (s > best) { best = s; move = m; }
            }
            return move;
        }

        int minimax(Board b, int depth, int alpha, int beta, boolean max, char MAX, char MIN) {
            char w = b.winner();
            if (w == MAX) return 10 - depth;
            if (w == MIN) return depth - 10;
            if (w == 'D') return 0;
            if (max) {
                int v = Integer.MIN_VALUE;
                for (int[] m : b.legalMoves()) {
                    b.place(m[0], m[1], MAX);
                    v = Math.max(v, minimax(b, depth + 1, alpha, beta, false, MAX, MIN));
                    b.undo(m[0], m[1]);
                    alpha = Math.max(alpha, v);
                    if (alpha >= beta) break;
                }
                return v;
            } else {
                int v = Integer.MAX_VALUE;
                for (int[] m : b.legalMoves()) {
                    b.place(m[0], m[1], MIN);
                    v = Math.min(v, minimax(b, depth + 1, alpha, beta, true, MAX, MIN));
                    b.undo(m[0], m[1]);
                    beta = Math.min(beta, v);
                    if (alpha >= beta) break;
                }
                return v;
            }
        }
    }

    public static class RandomAI implements AIPlayer {
        private final Random rng = new Random();
        @Override public int[] chooseMove(Board b, char sym) {
            List<int[]> ms = b.legalMoves();
            return ms.get(rng.nextInt(ms.size()));
        }
    }
}

C++

#include <array>
#include <vector>
#include <climits>
#include <utility>
#include <random>

class Board {
public:
    char g[3][3];
    Board() { for (auto& r : g) for (auto& c : r) c = '.'; }
    void place(int r, int c, char p) { g[r][c] = p; }
    void undo(int r, int c) { g[r][c] = '.'; }
    char cell(int r, int c) const { return g[r][c]; }

    std::vector<std::pair<int,int>> legalMoves() const {
        std::vector<std::pair<int,int>> out;
        std::pair<int,int> order[] = {{1,1},{0,0},{0,2},{2,0},{2,2},{0,1},{1,0},{1,2},{2,1}};
        for (auto& p : order) if (g[p.first][p.second] == '.') out.push_back(p);
        return out;
    }

    bool isFull() const {
        for (auto& r : g) for (auto c : r) if (c == '.') return false;
        return true;
    }

    char winner() const {
        for (int i = 0; i < 3; i++) {
            if (g[i][0] != '.' && g[i][0] == g[i][1] && g[i][1] == g[i][2]) return g[i][0];
            if (g[0][i] != '.' && g[0][i] == g[1][i] && g[1][i] == g[2][i]) return g[0][i];
        }
        if (g[0][0] != '.' && g[0][0] == g[1][1] && g[1][1] == g[2][2]) return g[0][0];
        if (g[0][2] != '.' && g[0][2] == g[1][1] && g[1][1] == g[2][0]) return g[0][2];
        if (isFull()) return 'D';
        return '.';
    }
};

class MinimaxAI {
    int minimax(Board& b, int depth, int alpha, int beta, bool maximizing, char MAX, char MIN) {
        char w = b.winner();
        if (w == MAX) return 10 - depth;
        if (w == MIN) return depth - 10;
        if (w == 'D') return 0;
        if (maximizing) {
            int v = INT_MIN;
            for (auto& m : b.legalMoves()) {
                b.place(m.first, m.second, MAX);
                v = std::max(v, minimax(b, depth + 1, alpha, beta, false, MAX, MIN));
                b.undo(m.first, m.second);
                alpha = std::max(alpha, v);
                if (alpha >= beta) break;
            }
            return v;
        } else {
            int v = INT_MAX;
            for (auto& m : b.legalMoves()) {
                b.place(m.first, m.second, MIN);
                v = std::min(v, minimax(b, depth + 1, alpha, beta, true, MAX, MIN));
                b.undo(m.first, m.second);
                beta = std::min(beta, v);
                if (alpha >= beta) break;
            }
            return v;
        }
    }
public:
    std::pair<int,int> chooseMove(Board& b, char sym) {
        char opp = (sym == 'X') ? 'O' : 'X';
        int best = INT_MIN;
        std::pair<int,int> move{-1, -1};
        for (auto& m : b.legalMoves()) {
            b.place(m.first, m.second, sym);
            int s = minimax(b, 1, INT_MIN, INT_MAX, false, sym, opp);
            b.undo(m.first, m.second);
            if (s > best) { best = s; move = m; }
        }
        return move;
    }
};

Edge Cases & Tests

Tests for win/draw, AI never loses, AI picks center, alpha-beta correctness

What we test

Case	Why
Detect row, column, and diagonal wins	Winner logic
Empty board → `ONGOING`	Default state
AI opening as X picks center	Best opening
Plain minimax and alpha-beta produce same move	Pruning preserves correctness
AI as O after human center → AI plays corner	Optimal response
AI vs AI always ends in draw	Perfect play
Random AI sometimes loses	Sanity check on the medium tier

TypeScript — Vitest

import { describe, expect, it } from 'vitest';
import { Board, MinimaxAI, RandomAI } from './tic-tac-toe';

describe('Board', () => {
  it('detects row win', () => {
    const b = new Board();
    b.place(0, 0, 'X'); b.place(0, 1, 'X'); b.place(0, 2, 'X');
    expect(b.winner()).toBe('X');
  });

  it('detects diagonal win', () => {
    const b = new Board();
    b.place(0, 0, 'O'); b.place(1, 1, 'O'); b.place(2, 2, 'O');
    expect(b.winner()).toBe('O');
  });

  it('detects draw', () => {
    const b = new Board();
    [['X',0,0],['O',0,1],['X',0,2],['X',1,0],['O',1,1],['X',1,2],
     ['O',2,0],['X',2,1],['O',2,2]].forEach(([p,r,c]) =>
      b.place(r as number, c as number, p as any));
    expect(b.winner()).toBe('DRAW');
  });
});

describe('MinimaxAI', () => {
  it('plays center as first move', () => {
    const ai = new MinimaxAI();
    const b = new Board();
    const m = ai.chooseMove(b, 'X');
    expect(m.row).toBe(1);
    expect(m.col).toBe(1);
  });

  it('AI vs AI always draws', () => {
    const ai = new MinimaxAI();
    const b = new Board();
    let turn: 'X' | 'O' = 'X';
    for (let i = 0; i < 9 && b.winner() === 'ONGOING'; i++) {
      const m = ai.chooseMove(b, turn);
      b.place(m.row, m.col, turn);
      turn = turn === 'X' ? 'O' : 'X';
    }
    expect(b.winner()).toBe('DRAW');
  });

  it('AI never loses against a random opponent (100 games)', () => {
    const ai = new MinimaxAI();
    const rnd = new RandomAI();
    let aiWins = 0, draws = 0, losses = 0;
    for (let game = 0; game < 100; game++) {
      const b = new Board();
      let turn: 'X' | 'O' = 'X'; // AI plays X
      while (b.winner() === 'ONGOING') {
        const m = turn === 'X' ? ai.chooseMove(b, 'X') : rnd.chooseMove(b);
        b.place(m.row, m.col, turn);
        turn = turn === 'X' ? 'O' : 'X';
      }
      const w = b.winner();
      if (w === 'X') aiWins++;
      else if (w === 'DRAW') draws++;
      else losses++;
    }
    expect(losses).toBe(0);
  });
});

Java — JUnit 5

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;

class TicTacToeTest {
    @Test void winnerDetected() {
        TicTacToe.Board b = new TicTacToe.Board();
        b.place(0,0,'X'); b.place(0,1,'X'); b.place(0,2,'X');
        assertEquals('X', b.winner());
    }

    @Test void aiPlaysCenterFirst() {
        TicTacToe.MinimaxAI ai = new TicTacToe.MinimaxAI();
        TicTacToe.Board b = new TicTacToe.Board();
        int[] m = ai.chooseMove(b, 'X');
        assertEquals(1, m[0]);
        assertEquals(1, m[1]);
    }

    @Test void aiVsAiDraws() {
        TicTacToe.MinimaxAI ai = new TicTacToe.MinimaxAI();
        TicTacToe.Board b = new TicTacToe.Board();
        char turn = 'X';
        for (int i = 0; i < 9 && b.winner() == '.'; i++) {
            int[] m = ai.chooseMove(b, turn);
            b.place(m[0], m[1], turn);
            turn = (turn == 'X') ? 'O' : 'X';
        }
        assertEquals('D', b.winner());
    }
}

C++ — gtest

#include <gtest/gtest.h>
#include "tic-tac-toe.hpp"

TEST(Board, RowWin) {
    Board b;
    b.place(0,0,'X'); b.place(0,1,'X'); b.place(0,2,'X');
    EXPECT_EQ(b.winner(), 'X');
}

TEST(AI, OpenCenter) {
    Board b;
    MinimaxAI ai;
    auto m = ai.chooseMove(b, 'X');
    EXPECT_EQ(m.first, 1);
    EXPECT_EQ(m.second, 1);
}

TEST(AI, AiVsAiDraws) {
    Board b;
    MinimaxAI ai;
    char t = 'X';
    while (b.winner() == '.') {
        auto m = ai.chooseMove(b, t);
        b.place(m.first, m.second, t);
        t = (t == 'X') ? 'O' : 'X';
    }
    EXPECT_EQ(b.winner(), 'D');
}

Extensibility & Trade-offs

Larger boards, MCTS, transposition tables, parallel search

Natural extensions

1. Transposition tables

Many board states are reached via different move orders. Cache (boardHash → best score) and return early on a hit. Zobrist hashing gives O(1) board hashing by XORing per-cell random keys. Cuts search tree by 30-50 % on 4×4+.

2. Killer move heuristic

Track which moves caused the most recent beta cut-off at each depth. Try them first next time. Standard chess-engine trick.

3. Monte Carlo Tree Search (MCTS)

For games where the branching factor is too high for minimax (Go, Hex), MCTS samples random playouts and picks the move whose subtree shows the best average outcome. UCB1 formula balances exploration and exploitation. AlphaGo built on MCTS with a neural-network policy.

4. Larger boards (N×N tic-tac-toe / Gomoku)

3×3 fits trivially. For 4×4 (Connect4-ish), depth-limit minimax to ~6 and use a heuristic: count open lines × where each line is a row/col/diagonal of N cells. For 5×5 Gomoku and up, MCTS becomes the practical choice.

5. Parallel search

Split the root-level moves across worker threads. Each thread does its own minimax with its own copy of the board. Combine results. Roughly N× speedup on N cores for the small tic-tac-toe tree.

6. Learning AI

Train a tabular Q-learning agent: state = board, action = move, reward = win/loss. Plays thousands of games against itself. Within ~100k games it reaches perfect play on 3×3 — at the cost of being non-interpretable.

Trade-offs

Concern	Plain minimax	Alpha-beta	MCTS
Optimal play	Yes	Yes	Approximate
Speed (3×3)	< 50 ms	< 5 ms	Slower setup
Memory	O(depth) stack	Same	O(tree nodes)
Best for	Small tree	Larger but still finite	Huge / continuous
Interpretability	High	High	Low

Anti-patterns

Copying the board on every recursive call — kills performance. Use place + recurse + undo.
Symmetric move generation — 3×3 has 8 symmetries; treating them all as distinct slows search 8×. Detect symmetric positions and dedup.
Not using depth in the score — without 10 - depth, the AI may pick a winning move 5 steps away over the same win 1 step away. Players think it's "playing dumb".
Forgetting the opponent is also smart — if you treat the opponent as random, you're not playing minimax; you're playing expectimax, which loses to a real opponent.

When NOT to use minimax

Game has imperfect information (poker, Stratego) — use counterfactual regret minimisation.
Branching factor > 30 with high depth required (Go, chess endgames sometimes) — alpha-beta still works but MCTS often dominates.
You need explainability — minimax with score trace is great here; if you switched to a NN-based AI, you lose this.

Interview: Strong closing point: "Minimax with alpha-beta is optimal on tic-tac-toe. The same skeleton — game tree, evaluate, prune — scales to chess via deeper depth + better heuristic. Past chess we move to MCTS + learned policies. Everything is built on this base."

Practice this question