Notes
Requirements
Fix the scope first. The board is N by N, three by default. Two players, X and O, take turns marking one empty cell. You win with a full row, a full column or a full diagonal of your mark. If the board fills up with no winner, it is a draw. A player can be a human or a computer, and we can undo the last move. Graphics, rankings and chat are out of scope.
Ask the questions that change the code. Does a win need the whole line, or K in a row on a big board? The whole line for now; K in a row is a follow-up. More than two players? Allow it, each with their own mark. How far back can undo go? All the way. An invalid move is rejected and the same player tries again. And the bot is simple: win if it can, block if it must, otherwise take the centre.
- board of N x N, default 3
- two players, X and O, in turns
- a move marks one empty cell
- win: a full row, column or
- diagonal of your mark
- draw: board full, no winner
- players: human or computer
- undo the last move
- out of scope: graphics,
- rankings, chat
- win needs the full line?
- yes; K in a row is a follow-up
- more than two players?
- allowed, each with a mark
- undo how far back?
- any number of moves
- invalid move?
- reject, same player again
- how smart is the bot?
- win, else block, else centre
Entities
Underline the nouns: game, board, cell, player, move. The game owns the board, the list of players, whose turn it is and the status. One idea makes the design flexible: a player is just a name and a mark, and how that player decides where to move is a separate object, a move strategy. Moves are pushed on a stack so we can undo them.
Class diagram
In code the small things are records: a cell is a row and a column, a move is a player and a cell, a player is a name, a mark and a strategy. The status is an enum with three values: in progress, won and draw. The game class holds the board, the players, the index of whose turn it is, the status and a deque of past moves.
enum Status { IN_PROGRESS, WON, DRAW }
record Cell(int row, int col)
record Move(Player player, Cell cell)
record Player(String name, char mark,
MoveStrategy strategy)
class TicTacToe {
Board board; List<Player> players;
int turn; Status status;
Deque<Move> history; } The naive win check
The first idea most people write is to scan the whole board after each move: every row, every column and both diagonals. On three by three that is fine. On a hundred by a hundred it is ten thousand reads for every move. The key observation is that one move can only change four lines: its own row, its own column, and at most the two diagonals. So we only need to look at those.
for each row: all cells == mark? for each column: all cells == mark? main diagonal, anti diagonal 3 x 3: 9 reads, nobody cares 100 x 100: 10,000 reads per move but only 4 lines can change: this row, this column, and maybe the 2 diagonals
O(1) win check
Keep counters instead. For each player, count how many of their marks are in each row and each column, plus one counter for the main diagonal and one for the anti diagonal. Placing a mark adds one to its row and column, and to a diagonal if the cell is on it. If any of those counts reaches N, that player has just won. Four additions and four comparisons: constant time per move, whatever the board size.
Walk one example. X already has the corner and the centre, and now plays the bottom right corner, row two and column two counting from zero. Its row count and column count go from zero to one. Row equals column, so the cell is on the main diagonal, and that count goes from two to three. Row plus column is four, not two, so the anti diagonal is untouched. Three equals N, so X wins. The memory cost is just two N plus two numbers per player.
int[][] rows, cols; // [player][i]
int[] diag, anti; // [player]
rows[p][r]++; cols[p][c]++;
if (r == c) diag[p]++;
if (r + c == n - 1) anti[p]++;
return rows[p][r] == n
|| cols[p][c] == n
|| diag[p] == n || anti[p] == n; - before: X at (0,0) and (1,1)
- rows[X][2]: 0 to 1
- cols[X][2]: 0 to 1
- row equals col: diag[X] 2 to 3
- row + col = 4, not 2: no anti
- diag[X] equals 3: X wins
- memory: 2N + 2 ints per player
Strategy: players
How a player picks a cell is the Strategy pattern. The interface has one method, choose, which gets a view of the board and the two marks and returns a cell. A human strategy returns the next click from the user interface. A bot strategy computes a move. Later you can add a perfect minimax bot or a remote player over the network, and the game class does not change at all.
interface MoveStrategy {
Cell choose(BoardView b,
char me, char opponent);
}
HumanInput: next click from the UI
SimpleBot: win, block, centre,
corner, anything
MinimaxBot, RemotePlayer:
new classes, game unchanged Strategy: the bot
The simple bot follows four rules in order. If one move completes a line for me, take it. If one move would complete a line for the opponent, block it. Otherwise take the centre, then a random free corner, then any empty cell. The random generator is passed in, so a test can seed it and get the same game every time. Two of these bots playing each other draw every game in the demo.
for (Cell c : empty) if (completesLine(b, c, me)) return c; for (Cell c : empty) if (completesLine(b, c, opp)) return c; if centre is free: return centre free corner: pick one at random else: any empty cell Random is injected: seeded in tests
Read-only view
What does a strategy receive? Not the real board, because then a buggy or cheating bot could place marks itself. It receives a board view: an interface with only read methods, size, the mark at a cell and the list of empty cells. The board implements it, but placing and removing marks are not part of the view. This is interface segregation used as a safety rail.
interface BoardView {
int size();
char at(int row, int col);
List<Cell> emptyCells();
}
class Board implements BoardView
place() and remove() are not in
the interface: a bot cannot cheat Flow: one move
Walk one move. The user interface calls play turn. The game asks the current player's strategy for a cell. It rejects the move if the game is over, if it is not this player's turn, or if the cell is taken or off the board. Then the board places the mark and reports a win in constant time. The move goes on the history stack, the status is updated, the turn passes on, and listeners hear about it.
if status != IN_PROGRESS: throw if player != current(): throw if cell not empty or outside: throw won = board.place(cell, turn, mark) history.push(new Move(player, cell)) if won: WON, winner = player else if board full: DRAW else turn = (turn + 1) % players notify listeners, return the Move
Game state
The game has three states. In progress allows moves. Won is set the moment the counters report a full line. Draw is set when the board is full and the last move did not win; the board keeps a simple filled counter, so this check is constant time too. Once the game is won or drawn, play throws, so a late click cannot add a mark. Undo is the only way back to in progress.
- IN_PROGRESS: moves allowed
- WON: set by the counters
- DRAW: filled == N x N
- and no win on the last move
- WON or DRAW: play() throws
- undo: back to IN_PROGRESS
- a filled counter makes the
- draw check O(1) too
Undo
Undo is easy because every move carries enough information to reverse itself. Pop the last move from the stack, clear its cell, and run the same counter update with minus one instead of plus one. Give the turn back to that player and set the status to in progress, because the move we removed might have been the winning one. No board snapshots, so undo is constant time and memory stays small.
Move m = history.pop(); int p = players.indexOf(m.player()); board.remove(m.cell(), p); // same counters, minus one turn = p; status = IN_PROGRESS; winner = null; each Move is enough to reverse itself: no board snapshots
Observer
The game itself should never print or draw. It publishes each move and the new status to listeners: the Observer pattern. A console view, a graphical board, a replay recorder and a statistics counter all subscribe the same way. In tests you subscribe a list and assert the exact sequence of moves, which is much cleaner than reading printed output.
Concurrency
On one device there is no concurrency, so say that. Online, two requests can reach the same game at once, or one player double clicks. Make play and undo synchronized on the game, and do the whose-turn check and the empty-cell check inside the same lock, so the second request sees the updated state and is rejected. Different games have different locks and never wait on each other.
- play() and undo() synchronized
- on the game object
- turn check + empty-cell check
- inside the same lock
- double click: second is rejected
- games never block each other
- or: one actor per game,
- moves in a queue
Extensibility
Interviewers will change the rules. K in a row on a large board, like five in a row on fifteen by fifteen, breaks the full-line counters, so instead walk the four directions out from the last move and count matching marks, which is order K per move. A perfect player is a minimax strategy. Three players already work, since counters are kept per player. A redo button is a second stack that undo pushes onto.
- K in a row on a big board:
- walk 4 directions from the
- last move, O(K) per move
- perfect bot: MinimaxBot
- three players: already works
- move timer: a clock per player
- replay: listener records moves
- redo: a second stack
Testing
The full code is below the player. Two scripted humans play until X wins on the diagonal, then undo reopens the game. Out-of-turn and taken-cell moves are rejected. Three hundred seeded games between two simple bots all end in a draw. Finally, five hundred random games with three players on a five by five board compare the counters against a slow full scan after every single move, and they always agree.
Home plays (0,0) -> IN_PROGRESS Home plays (2,2) -> WON Winner: Home Undo (2,2): status IN_PROGRESS Rejected: not Away's turn Rejected: cell (1,1) is taken 300 bot games: X 0, O 0, draws 300 O(1) win check matched a full scan on 12421 moves
Follow-ups
Expect follow-ups. Why counters? Constant time per move instead of N squared. A neat two-player trick uses one counter per line, where X adds one and O subtracts one, and a value of plus or minus N is a win. K in a row means counting outward from the last move. Perfect play is minimax with memoised board states. And a saved game is simply its list of moves, replayed onto an empty board.
- why counters, not a scan?
- two players only: one counter
- per line, X adds 1, O adds -1
- K in a row? check from the move
- perfect play? minimax, memo
- on the board state
- save a game? the move list
- million games online?
- state in a store by game id
Say it like this
Here is the short version to say out loud. The board keeps per-player counts for every row, every column and both diagonals, so checking a win is constant time. Each player holds a move strategy and only sees a read-only board view. Moves go on a stack, so undo just runs the counters backwards. Moves are published to observers, and play checks the turn under a per-game lock.
- "A Board keeps per-player counts
- for each row, column and both
- diagonals, so a win is O(1).
- Players hold a MoveStrategy and
- see a read-only BoardView. Moves
- go on a stack for undo, go to
- observers, and play() checks the
- turn under a per-game lock."