Tic-Tac-Toe

Problem statement (interviewer prompt)

Design the classes for a tic-tac-toe game playable by two humans or one human vs a bot. Cover move validation, win/draw detection, and extending to N×N or three-player variants.

classDiagram
  class Game {
    -board : Board
    -players : List~Player~
    -current : int
    -state : GameState
    +makeMove(row, col)
    -checkWinOrDraw()
  }
  class Board {
    -size : int
    -cells : Symbol[][]
    +placeAt(row, col, sym)
    +isFull() boolean
    +hasWinningLine(sym) boolean
  }
  class Player {
    <<abstract>>
    +name : String
    +symbol : Symbol
    +nextMove(board) Move
  }
  class HumanPlayer
  class BotPlayer {
    -strategy : Strategy
    +nextMove(board)
  }
  class Strategy {
    <<interface>>
    +chooseMove(board, sym) Move
  }
  class RandomStrategy
  class MinimaxStrategy
  Game *-- Board
  Game *-- "2" Player
  Player <|-- HumanPlayer
  Player <|-- BotPlayer
  BotPlayer --> Strategy
  Strategy <|.. RandomStrategy
  Strategy <|.. MinimaxStrategy

Strategy pattern keeps bot logic swappable. Win-line detection is one method; supports N×N if you parameterise board size.

A small but instructive design. The interview signal is how you structure for change (board size, player count, bot difficulty) without overengineering.

Class diagram

classDiagram
  class Game {
    -board : Board
    -players : List~Player~
    -current : int
    -state : GameState
    +start()
    +makeMove(row, col)
    -checkWinOrDraw()
  }
  class Board {
    -size : int
    -cells : Symbol[][]
    -rowCount : Map
    -colCount : Map
    -diag : Map
    -antidiag : Map
    +placeAt(row, col, sym) WinResult
    +isFull() boolean
  }
  class Symbol {
    <<enumeration>>
    X
    O
    EMPTY
  }
  class GameState {
    <<enumeration>>
    IN_PROGRESS
    WIN
    DRAW
  }
  class Player {
    <<abstract>>
    +symbol
    +nextMove(board) Move
  }
  class HumanPlayer
  class BotPlayer {
    -strategy : Strategy
  }
  class Strategy {
    <<interface>>
    +choose(board, sym) Move
  }
  class MinimaxStrategy {
    -depth : int
  }
  Game *-- Board
  Game *-- "2..N" Player
  Player <|-- HumanPlayer
  Player <|-- BotPlayer
  BotPlayer --> Strategy
  Strategy <|.. MinimaxStrategy

O(1) win detection

Instead of scanning the board after every move, maintain running counts:

class Board {
    final int n;
    final int[][] cells;
    final Map<Symbol, int[]> rowCount;  // [sym][row] = #cells
    final Map<Symbol, int[]> colCount;
    final Map<Symbol, Integer> diag;
    final Map<Symbol, Integer> antidiag;

    WinResult placeAt(int r, int c, Symbol s) {
        cells[r][c] = s;
        if (++rowCount.get(s)[r] == n) return WinResult.WIN;
        if (++colCount.get(s)[c] == n) return WinResult.WIN;
        if (r == c && ++diag.get(s) == n) return WinResult.WIN;
        if (r + c == n - 1 && ++antidiag.get(s) == n) return WinResult.WIN;
        return WinResult.NONE;
    }
}

O(1) per move, O(n) memory.

State machine

stateDiagram-v2
  [*] --> IN_PROGRESS : start
  IN_PROGRESS --> IN_PROGRESS : valid move
  IN_PROGRESS --> WIN : winning move
  IN_PROGRESS --> DRAW : board full
  WIN --> [*]
  DRAW --> [*]

Minimax bot

def minimax(board, sym, depth, alpha, beta):
    if board.is_terminal():
        return board.score(sym)
    if maximising:
        v = -inf
        for move in board.legal_moves():
            board.apply(move)
            v = max(v, minimax(board, opp(sym), depth+1, alpha, beta))
            board.undo(move)
            alpha = max(alpha, v)
            if alpha >= beta: break
        return v
    ...

For 3×3 it's instant (9! = 362,880 max nodes). For 4×4 use alpha-beta pruning + depth limit.

Extensions

Variation	Change
N×N	Parameterise board size; win condition = N-in-a-row
K-in-a-row	Win condition = K; scan windows
Three players	Add Symbol.Z; turn rotation
Networked	Add Session and Move event over WebSocket
Replay	Persist List<Move>; replay applies in order

Common interview signal

• Did you separate Game (turn order, state) from Board (cell state)?
• Did you avoid checking the whole board on every move?
• Did you use a strategy interface so bots are pluggable?
• Did you handle invalid moves (occupied cell, out of bounds, wrong turn)?

Where Tic-Tac-Toe fits

flowchart TB
  TTT((Tic-Tac-Toe))
  BPL[Behavioral patterns<br/>Strategy + State]
  SM[State machines<br/>game state]
  OOP[OOP pillars<br/>player inheritance]
  CHESS[Chess engine<br/>deeper sibling]
  BPL --> TTT
  SM --> TTT
  OOP --> TTT
  TTT -. shape .- CHESS

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class TTT service;
    class BPL,SM,OOP,CHESS datastore;

Glossary & fundamentals

Tag	Concept	What it is	Page
LLD	Behavioral patterns	Strategy + State	behavioral-patterns
LLD	State machines	the game's state model	state-machines
LLD	OOP pillars	inheritance for player types	oop-pillars
LLD	Chess engine	similar shape, deeper rules	chess-engine

Quick reference

Classes

• Game (turn, state, history)
• Board (cells, win check)
• Player (abstract; Human or Bot)
• Strategy (Random, Minimax)

Move flow

1. Read row, col from current player.
2. Validate (in bounds, empty, current turn).
3. Place symbol; check win/draw via running counts.
4. Switch player or end game.

O(1) win check

Maintain per-symbol row count, col count, diag, antidiag. Increment on placement; if any reaches N, win.

Minimax bot

• Recursive evaluate to terminal
• Alpha-beta prune for deeper boards
• Cap depth on big N

Extensions

• N×N or K-in-a-row
• 3+ players
• Network (WebSocket)
• Replay (List)

Interview signal

• Separation of Game vs Board
• Pluggable Player (Strategy)
• Move validation completeness
• State machine clarity

Refs

• AIMA - Game Playing chapter

FAQ

How is win detection done in O(1) per move?

Keep row, column, and diagonal counters per player. Each move increments the four counters touched; if any reaches N, that player wins. No board scan needed.

How do you support human vs bot play?

Use the Strategy pattern: a Player interface with HumanPlayer (prompts UI) and BotPlayer (runs minimax or alpha-beta). Game asks the current player for their next move.

How is the game extended to N by N?

Replace the 3 by 3 grid with an N-sized Board and pass N to the win-detection counters. The same move loop and Player interface work unchanged.

How does minimax solve tic-tac-toe?

Recursively evaluate all moves, alternating max and min, with terminal scores of plus or minus 1 for win and 0 for draw. Tic-tac-toe is fully solved: optimal play always draws.

What states make up the game?

WaitingForMove, GameOver with a winner enum (X, O, Draw), and optionally Paused. Each move triggers a transition based on win detection and remaining empty cells.

Related Topics

• Chess Engine: same shape, much deeper rules
• State Machines: the IN_PROGRESS/WIN/DRAW transitions
• Behavioral Patterns: Strategy for bot interchangeability

Further reading

• Book - Russell & Norvig - AIMA (game playing)
• Blog - Sebastian Lague - Minimax algorithm explained

Video walkthrough

Tic-Tac-Toe: Complete System Design & Low Level Design : via LLD Walkthrough