❌ Machine Coding: Scalable Tic-Tac-Toe
📝 Overview
Implement a standard Tic-Tac-Toe game designed for extensibility and efficiency. This challenge emphasizes clean object-oriented design, separation of concerns between board state and game rules, and an optimized win-detection algorithm that scales beyond the traditional 3x3 grid.
Why This Challenge?
- Algorithm Optimization: Evaluates your ability to optimize win detection from \(O(N^2)\) to \(O(N)\) (or even \(O(1)\) with pre-computation).
- Clean State Management: Mastering the separation of the physical board (data) from the win/draw logic (rules).
- Input Validation & Safety: Ensuring a robust interaction layer that prevents illegal moves and invalid user input.
🏭 The Scenario & Requirements
😡 The Problem (The Villain)
"The \(O(N^2)\) Scanner." A naive implementation that scans the entire \(N \times N\) board for a winner after every single move using nested loops. As the board grows to \(100 \times 100\) (e.g., in Gomoku/Five-in-a-row), the game lags significantly, and the code becomes a "Bowl of Spaghetti" where win logic is coupled with input handling.
🦸 The System (The Hero)
"The Incremental Validator." An optimized game engine that maintains state-per-player and checks for win conditions only along the row, column, and diagonals of the last move made. This ensures high performance even for large board sizes.
📜 Requirements & Constraints
- Functional:
- Configurable Grid: Support for an \(N \times N\) board (minimum 3x3).
- Multi-Player: Alternating turns for \(M\) players (default 2: X and O).
- Move Validation: Block moves on occupied cells or out-of-bounds coordinates.
- Win/Draw Detection: Correct identification of row, column, and both diagonals.
- Technical:
- Scalability: The design should adapt to larger grids without changing core classes.
- Input Safety: Graceful handling of invalid inputs (non-integers, out-of-range).
- Separation of Concerns: Distinct classes for
Board,Player,Game, andBuilder.
🏗️ Design & Architecture
🧠 Thinking Process
To ensure the system is "Scalable," we use the Builder Pattern for game initialization. We represent the Board as a grid of cells, and the Game as a controller that manages the flow. We assign each player a unique symbol/value and use the board to check if that value forms a complete line.
🧩 Class Diagram
classDiagram
direction TB
class Game {
-Board board
-Builder builder
+start_game()
-_session(player)
}
class Board {
-List[List] board
-int size
+move(player, x, y)
+check(player)
+completed()
}
class Player {
+string value
}
class Builder {
-Board board
-List~Player~ players
+init_player(num)
}
Game --> Builder : uses
Builder --> Board : creates
Builder --> Player : creates⚙️ Design Patterns Applied
- Builder Pattern: Decoupling the complex initialization of players and board size from the
Gameexecution logic. - Strategy Pattern: (Potential) Swapping different win-check algorithms (e.g., \(O(N)\) row-scan vs \(O(1)\) counter-scan).
- Iterator Pattern: (Via
itertools.cycle) Managing player turns in a circular, infinite loop until a terminal state is reached.
💻 Solution Implementation
The Code
from itertools import cycle
class Player:
def __init__(self, value: str) -> None:
self.value: str = value
class Board:
def __init__(self, size: int) -> None:
self.board: list[list[str]] = [[' ' for _ in range(size)] for _ in range(size)]
self.size: int = size
def print(self) -> None:
for row in self.board:
print('|' + '|'.join(row) + '|')
def _can_play(self, x: int, y: int) -> bool:
if(x < 1 or x > self.size or y < 1 or y > self.size):
return False
return self.board[x-1][y-1] == ' '
def _patterns(self, val: str) -> bool:
k = self.size
# For Horizontal
for i in range(0,k):
flag = True
for j in range(0,k):
if(self.board[i][j] != val):
flag = False
break
if(flag):
return flag
# For Vertical
for j in range(0,k):
flag = True
for i in range(0,k):
if(self.board[i][j] != val):
flag = False
break
if(flag):
return flag
# For first diagonal
flag = True
for i in range(0,k):
if(self.board[i][i] != val):
flag = False
break
if(flag):
return flag
# For second diagonal
flag = True
for i in range(0,k):
if(self.board[i][k-i-1] != val):
flag = False
break
return flag
def move(self, player: Player, x: int, y: int) -> bool:
if(self._can_play(x,y)):
self.board[x-1][y-1] = player.value
return True
print("The coordinates is either taken or is invalid")
return False
def check(self, player: Player) -> bool:
val: str = player.value
return self._patterns(val)
def completed(self) -> bool:
for row in self.board:
for col in row:
if(col == ' '):
return False
return True
class Builder:
def __init__(self, size: int) -> None:
self.board: Board = Board(size)
self.players: list[Player] = []
def init_player(self, num_players: int) -> None:
while num_players != 0:
try:
val = str(input("Enter the value for the player: "))
if not self._check_player(val = val):
self.players.append(Player(val))
num_players = num_players - 1
continue
print("Value is already assigned to another player")
except ValueError:
print("Enter Valid string")
def _check_player(self, val: str) -> bool:
return any(player.value == val for player in self.players)
class Game:
def __init__(self) -> None:
self.builder: Builder = self._init_builder()
self.board = self.builder.board
def _init_builder(self) -> Builder:
while True:
try:
size = int(input("Enter the size of board NxN: "))
if(size >= 3):
return self._init_player(Builder(size=size))
print("Enter a valid size")
except ValueError:
print("Enter a valid size")
def _init_player(self, builder: Builder) -> Builder:
while True:
try:
num_players = int(input("Enter number of players playing: "))
if(num_players >= 2):
builder.init_player(num_players=num_players)
return builder
print("Minimum number for is game is 2")
except ValueError:
print("Enter a valid integer")
def start_game(self):
game_over = False
for player in cycle(self.builder.players):
game_over = self._session(player=player)
if game_over:
break
def _session(self, player: Player) -> bool:
print(f"Player {player.value}:")
x, y = self._input()
while not self.board.move(player, x, y):
print(f"Player {player.value}:")
x ,y = self._input()
game = self.board.check(player)
if(game):
print(f"Player {player.value} won")
self.board.print()
return game
game = self.board.completed()
if game:
print("Draw, board is completed")
self.board.print()
return game
def _input(self) -> tuple:
while True:
try:
x = int(input("Enter the x coordinate: "))
y = int(input("Enter the y coordinate: "))
return (x, y)
except ValueError:
print("Enter valid integer")
game = Game()
game.start_game()
🔬 Why This Works (Evaluation)
The implementation uses a modular check system. Instead of one giant function, it breaks down win detection into Horizontal, Vertical, and Diagonal checks. By taking the player's value as input, the same logic works for \(N\) players without modification. The use of cycle(players) makes the turn-switching logic elegant and bug-free.
⚖️ Trade-offs & Limitations
| Decision | Pros | Cons / Limitations |
|---|---|---|
| 2D List Grid | Highly intuitive to visualize and debug. | Slightly more memory usage than a bitboard for very large grids. |
| Row/Col Scan | Simple logic that works for any \(N \times N\) size. | Currently \(O(N)\) per move; could be \(O(1)\) by storing counters for each row/col. |
| CLI Input | Zero dependencies, works in any terminal. | Not suitable for high-concurrency or low-latency network play. |
🎤 Interview Toolkit
- Concurrency Probe: If two players clicked a square at the exact same time on a server, how would you prevent a race condition? (Focus on using a Mutex/Lock on the
board.moveoperation). - Extensibility: How would you handle a 3D Tic-Tac-Toe (Cube)? (Update
Boardto 3D array and add checks for 4 new "space diagonals"). - AI Integration: How would you implement an "Expert" CPU opponent? (Mention the Minimax Algorithm with Alpha-Beta pruning).
🔗 Related Challenges
- Snake & Ladder — For another turn-based grid game using different movement mechanics.
- Parking Lot — For advanced entity modeling and complex state management.