Games & SimulationsProblem 4 of 11

Games & SimulationsStarter

Tic Tac Toe

State PatternStrategy PatternObserver Pattern

O(1) win detection using row/column/diagonal counters instead of scanning the board. Works for any NxN size.

Key Abstractions

Game

Orchestrator that manages turns and delegates to board and win checker

Board

Grid state with placement validation and cell ownership

Player

Participant with a symbol (X/O) and an optional move strategy

WinChecker

O(1) win detection using row/col/diagonal accumulators

MoveStrategy

Strategy for AI players: random, minimax, or human input

GameState

Enum tracking IN_PROGRESS, X_WINS, O_WINS, DRAW

Class Diagram

The Key Insight

First instinct is to scan the board after every move. Check all rows, all columns, both diagonals. That's O(n^2) per move on an NxN board. But you already know which row, column, and diagonals were affected by the last move. You only need to check those.

Better yet, you don't even need to "check" them. Maintain running counters. Increment for X, decrement for O. When any counter hits +n or -n, that player wins. O(1) per move, no board scanning, and it works for any board size without changes.

Requirements

Functional

NxN board (default 3x3) with two players
Players alternate turns placing X and O
Detect win (row, column, or diagonal) and draw conditions
Support both human and AI players via pluggable move strategies
Reject out-of-bounds and occupied cell moves

Non-Functional

O(1) win detection per move
Game state transitions should be explicit and testable
Board size should be configurable without code changes

Design Decisions

Why separate WinChecker from Board?

Board manages cell state. WinChecker manages win detection logic. If you merge them, testing win detection means setting up actual board state first. Keeping them separate lets you unit-test the counter logic on its own. It also makes it straightforward to swap in different win conditions, like "connect 4 in a row on a 6x6 board."

Why accumulators instead of a bitmask?

Bitmasks work well for 3x3 and are common in competitive programming. They don't generalize to NxN without extra bit-packing complexity. Accumulators are equally O(1) and scale to any board size with zero additional work. Clarity wins here.

Why Strategy for player moves?

Without it, adding AI means if/else chains inside the game loop: "if human, read input; if random, pick random; if minimax, run minimax." With Strategy, the game loop doesn't know or care what kind of player it's talking to. Adding a new AI is a new class, not a modification to existing code.

Interview Follow-ups

"How would you implement minimax AI?" New MinimaxStrategy implementing MoveStrategy. It recursively evaluates all possible game states and picks the optimal move. Alpha-beta pruning cuts the search space significantly.
"How would you extend to Connect Four?" Larger board, gravity (pieces fall to the bottom), and the win condition changes to "4 in a row." The WinChecker needs to track more diagonals, but the counter approach still works.
"How would you add an undo feature?" Command pattern. Each move is a MoveCommand with execute() and undo(). A stack of commands gives you full undo history.
"How would you support multiplayer over a network?" Extract the game loop into a GameServer. Players send moves via websockets. The server validates, updates state, and broadcasts to all clients.

Code Implementation

  1  from __future__ import annotations
  2  from enum import Enum
  3  from abc import ABC, abstractmethod
  4  from dataclasses import dataclass
  5  import random
  6  
  7  
  8  class Symbol(Enum):
  9      EMPTY = "."
 10      X = "X"
 11      O = "O"
 12  
 13      def value_for_counter(self) -> int:
 14          """X adds +1, O adds -1 to accumulators."""
 15          return 1 if self == Symbol.X else -1
 16  
 17  class GameState(Enum):
 18      IN_PROGRESS = "in_progress"
 19      X_WINS = "x_wins"
 20      O_WINS = "o_wins"
 21      DRAW = "draw"
 22  
 23  
 24  class Board:
 25      def __init__(self, size: int = 3):
 26          self.size = size
 27          self._grid = [[Symbol.EMPTY] * size for _ in range(size)]
 28          self._moves_left = size * size
 29  
 30      def place(self, row: int, col: int, symbol: Symbol) -> bool:
 31          if not (0 <= row < self.size and 0 <= col < self.size):
 32              return False
 33          if self._grid[row][col] != Symbol.EMPTY:
 34              return False
 35          self._grid[row][col] = symbol
 36          self._moves_left -= 1
 37          return True
 38  
 39      def get_cell(self, row: int, col: int) -> Symbol:
 40          return self._grid[row][col]
 41  
 42      def is_full(self) -> bool:
 43          return self._moves_left == 0
 44  
 45      def available_moves(self) -> list[tuple[int, int]]:
 46          return [
 47              (r, c)
 48              for r in range(self.size)
 49              for c in range(self.size)
 50              if self._grid[r][c] == Symbol.EMPTY
 51          ]
 52  
 53      def __str__(self) -> str:
 54          return "\n".join(" ".join(cell.value for cell in row) for row in self._grid)
 55  
 56  
 57  class WinChecker:
 58      """
 59      Maintain accumulators instead of scanning:
 60      - rows[i]: sum of values in row i
 61      - cols[j]: sum of values in column j
 62      - diag: main diagonal sum
 63      - anti_diag: anti-diagonal sum
 64  
 65      X contributes +1, O contributes -1.
 66      When any accumulator reaches +n or -n, that player wins.
 67      """
 68  
 69      def __init__(self, size: int):
 70          self._size = size
 71          self._rows = [0] * size
 72          self._cols = [0] * size
 73          self._diag = 0
 74          self._anti_diag = 0
 75  
 76      def record_move(self, row: int, col: int, symbol: Symbol) -> bool:
 77          val = symbol.value_for_counter()
 78          self._rows[row] += val
 79          self._cols[col] += val
 80          if row == col:
 81              self._diag += val
 82          if row + col == self._size - 1:
 83              self._anti_diag += val
 84  
 85          target = self._size * val  # +n for X, -n for O
 86          return (
 87              self._rows[row] == target
 88              or self._cols[col] == target
 89              or self._diag == target
 90              or self._anti_diag == target
 91          )
 92  
 93  
 94  @dataclass(frozen=True)
 95  class Move:
 96      row: int
 97      col: int
 98  
 99  class MoveStrategy(ABC):
100      @abstractmethod
101      def next_move(self, board: Board, symbol: Symbol) -> Move: ...
102  
103  class HumanStrategy(MoveStrategy):
104      def next_move(self, board: Board, symbol: Symbol) -> Move:
105          while True:
106              raw = input(f"Player {symbol.value}, enter row col: ")
107              parts = raw.strip().split()
108              if len(parts) == 2 and all(p.isdigit() for p in parts):
109                  return Move(int(parts[0]), int(parts[1]))
110              print("Invalid input. Try again.")
111  
112  class RandomStrategy(MoveStrategy):
113      def next_move(self, board: Board, symbol: Symbol) -> Move:
114          moves = board.available_moves()
115          r, c = random.choice(moves)
116          return Move(r, c)
117  
118  
119  @dataclass
120  class Player:
121      name: str
122      symbol: Symbol
123      strategy: MoveStrategy
124  
125      def get_move(self, board: Board) -> Move:
126          return self.strategy.next_move(board, self.symbol)
127  
128  
129  class Game:
130      def __init__(self, size: int = 3, players: list[Player] | None = None):
131          self._board = Board(size)
132          self._checker = WinChecker(size)
133          self._players = players or [
134              Player("Player 1", Symbol.X, HumanStrategy()),
135              Player("Player 2", Symbol.O, HumanStrategy()),
136          ]
137          self._current_turn = 0
138          self._state = GameState.IN_PROGRESS
139  
140      @property
141      def state(self) -> GameState:
142          return self._state
143  
144      def make_move(self, row: int, col: int) -> GameState:
145          if self._state != GameState.IN_PROGRESS:
146              raise RuntimeError("Game is over")
147  
148          player = self._players[self._current_turn]
149          if not self._board.place(row, col, player.symbol):
150              raise ValueError(f"Invalid move: ({row}, {col})")
151  
152          if self._checker.record_move(row, col, player.symbol):
153              self._state = (
154                  GameState.X_WINS if player.symbol == Symbol.X else GameState.O_WINS
155              )
156          elif self._board.is_full():
157              self._state = GameState.DRAW
158          else:
159              self._current_turn = (self._current_turn + 1) % len(self._players)
160  
161          return self._state
162  
163      def play(self) -> GameState:
164          """Auto-play loop using each player's strategy."""
165          while self._state == GameState.IN_PROGRESS:
166              player = self._players[self._current_turn]
167              move = player.get_move(self._board)
168              print(f"{player.name} ({player.symbol.value}) -> ({move.row}, {move.col})")
169              self.make_move(move.row, move.col)
170              print(self._board)
171              print()
172          return self._state
173  
174  
175  if __name__ == "__main__":
176      game = Game(
177          size=3,
178          players=[
179              Player("Alice", Symbol.X, RandomStrategy()),
180              Player("Bob", Symbol.O, RandomStrategy()),
181          ],
182      )
183      result = game.play()
184      print(f"Result: {result.value}")

Common Mistakes

✗Scanning the entire board after each move to check for a win. O(n^2) when O(1) is right there.
✗Using strings for player symbols instead of enums. Typo bugs like 'x' vs 'X' will bite you.
✗Hardcoding 3x3. A general NxN solution is barely more code and shows design maturity.
✗Putting game logic inside the Board class. Board should only manage cell state, not turns or wins.

Key Points

✓O(1) win detection by incrementing counters per row, column, and diagonal instead of scanning the board
✓State pattern manages game lifecycle with clean transitions between IN_PROGRESS, WIN, and DRAW
✓Strategy pattern for player moves. Same interface for human input and AI algorithms.
✓Board is decoupled from win logic so you can swap win conditions without touching placement code

Related Designs

The Key Insight

Requirements

Functional

NxN board (default 3x3) with two players

Players alternate turns placing X and O

Detect win (row, column, or diagonal) and draw conditions

Support both human and AI players via pluggable move strategies

Reject out-of-bounds and occupied cell moves

Non-Functional

O(1) win detection per move

Game state transitions should be explicit and testable

Board size should be configurable without code changes

Design Decisions

Why separate WinChecker from Board?

Why accumulators instead of a bitmask?

Why Strategy for player moves?

Interview Follow-ups

"How would you implement minimax AI?" New MinimaxStrategy implementing MoveStrategy. It recursively evaluates all possible game states and picks the optimal move. Alpha-beta pruning cuts the search space significantly.

"How would you extend to Connect Four?" Larger board, gravity (pieces fall to the bottom), and the win condition changes to "4 in a row." The WinChecker needs to track more diagonals, but the counter approach still works.

"How would you add an undo feature?" Command pattern. Each move is a MoveCommand with execute() and undo(). A stack of commands gives you full undo history.

"How would you support multiplayer over a network?" Extract the game loop into a GameServer. Players send moves via websockets. The server validates, updates state, and broadcasts to all clients.

1 from __future__ import annotations 2 from enum import Enum 3 from abc import ABC, abstractmethod 4 from dataclasses import dataclass 5 import random 6 7 8 class Symbol(Enum): 9 EMPTY = "." 10 X = "X" 11 O = "O" 12 13 def value_for_counter(self) -> int: 14 """X adds +1, O adds -1 to accumulators.""" 15 return 1 if self == Symbol.X else -1 16 17 class GameState(Enum): 18 IN_PROGRESS = "in_progress" 19 X_WINS = "x_wins" 20 O_WINS = "o_wins" 21 DRAW = "draw" 22 23 24 class Board: 25 def __init__(self, size: int = 3): 26 self.size = size 27 self._grid = [[Symbol.EMPTY] * size for _ in range(size)] 28 self._moves_left = size * size 29 30 def place(self, row: int, col: int, symbol: Symbol) -> bool: 31 if not (0 <= row < self.size and 0 <= col < self.size): 32 return False 33 if self._grid[row][col] != Symbol.EMPTY: 34 return False 35 self._grid[row][col] = symbol 36 self._moves_left -= 1 37 return True 38 39 def get_cell(self, row: int, col: int) -> Symbol: 40 return self._grid[row][col] 41 42 def is_full(self) -> bool: 43 return self._moves_left == 0 44 45 def available_moves(self) -> list[tuple[int, int]]: 46 return [ 47 (r, c) 48 for r in range(self.size) 49 for c in range(self.size) 50 if self._grid[r][c] == Symbol.EMPTY 51 ] 52 53 def __str__(self) -> str: 54 return "\n".join(" ".join(cell.value for cell in row) for row in self._grid) 55 56 57 class WinChecker: 58 """ 59 Maintain accumulators instead of scanning: 60 - rows[i]: sum of values in row i 61 - cols[j]: sum of values in column j 62 - diag: main diagonal sum 63 - anti_diag: anti-diagonal sum 64 65 X contributes +1, O contributes -1. 66 When any accumulator reaches +n or -n, that player wins. 67 """ 68 69 def __init__(self, size: int): 70 self._size = size 71 self._rows = [0] * size 72 self._cols = [0] * size 73 self._diag = 0 74 self._anti_diag = 0 75 76 def record_move(self, row: int, col: int, symbol: Symbol) -> bool: 77 val = symbol.value_for_counter() 78 self._rows[row] += val 79 self._cols[col] += val 80 if row == col: 81 self._diag += val 82 if row + col == self._size - 1: 83 self._anti_diag += val 84 85 target = self._size * val # +n for X, -n for O 86 return ( 87 self._rows[row] == target 88 or self._cols[col] == target 89 or self._diag == target 90 or self._anti_diag == target 91 ) 92 93 94 @dataclass(frozen=True) 95 class Move: 96 row: int 97 col: int 98 99 class MoveStrategy(ABC): 100 @abstractmethod 101 def next_move(self, board: Board, symbol: Symbol) -> Move: ... 102 103 class HumanStrategy(MoveStrategy): 104 def next_move(self, board: Board, symbol: Symbol) -> Move: 105 while True: 106 raw = input(f"Player {symbol.value}, enter row col: ") 107 parts = raw.strip().split() 108 if len(parts) == 2 and all(p.isdigit() for p in parts): 109 return Move(int(parts[0]), int(parts[1])) 110 print("Invalid input. Try again.") 111 112 class RandomStrategy(MoveStrategy): 113 def next_move(self, board: Board, symbol: Symbol) -> Move: 114 moves = board.available_moves() 115 r, c = random.choice(moves) 116 return Move(r, c) 117 118 119 @dataclass 120 class Player: 121 name: str 122 symbol: Symbol 123 strategy: MoveStrategy 124 125 def get_move(self, board: Board) -> Move: 126 return self.strategy.next_move(board, self.symbol) 127 128 129 class Game: 130 def __init__(self, size: int = 3, players: list[Player] | None = None): 131 self._board = Board(size) 132 self._checker = WinChecker(size) 133 self._players = players or [ 134 Player("Player 1", Symbol.X, HumanStrategy()), 135 Player("Player 2", Symbol.O, HumanStrategy()), 136 ] 137 self._current_turn = 0 138 self._state = GameState.IN_PROGRESS 139 140 @property 141 def state(self) -> GameState: 142 return self._state 143 144 def make_move(self, row: int, col: int) -> GameState: 145 if self._state != GameState.IN_PROGRESS: 146 raise RuntimeError("Game is over") 147 148 player = self._players[self._current_turn] 149 if not self._board.place(row, col, player.symbol): 150 raise ValueError(f"Invalid move: ({row}, {col})") 151 152 if self._checker.record_move(row, col, player.symbol): 153 self._state = ( 154 GameState.X_WINS if player.symbol == Symbol.X else GameState.O_WINS 155 ) 156 elif self._board.is_full(): 157 self._state = GameState.DRAW 158 else: 159 self._current_turn = (self._current_turn + 1) % len(self._players) 160 161 return self._state 162 163 def play(self) -> GameState: 164 """Auto-play loop using each player's strategy.""" 165 while self._state == GameState.IN_PROGRESS: 166 player = self._players[self._current_turn] 167 move = player.get_move(self._board) 168 print(f"{player.name} ({player.symbol.value}) -> ({move.row}, {move.col})") 169 self.make_move(move.row, move.col) 170 print(self._board) 171 print() 172 return self._state 173 174 175 if __name__ == "__main__": 176 game = Game( 177 size=3, 178 players=[ 179 Player("Alice", Symbol.X, RandomStrategy()), 180 Player("Bob", Symbol.O, RandomStrategy()), 181 ], 182 ) 183 result = game.play() 184 print(f"Result: {result.value}")