Low Level Design : Tic-Tac-Toe

If you’re venturing into the domain of low level design, tic-tac-toe might be the first question that you might find yourself standing against. In this article we’ll discuss how to approach a low level design question, and get our tic-tac-toe game up and running.

What is tic-tac-toe?

Before approaching any low level design question, it’s important that we understand the functionalities that needs to be implemented as part of it. Though most of us are familiar with what Tic-Tac-Toe is, and what the rules for the games are. In case someone isn’t, this https://en.wikipedia.org/wiki/Tic-tac-toe would be great guide to get started.

Functionality

Now that we have a basic understanding of what Tic-tac-Toe is, let’s list down the basic functionalities that we need to implement as part of the design.

1. The game should have two players with each having a sign as either O or X.
2. The tic-tac-toe is usually of size 3x3, but we’ll generalise and take the board size as N.
3. If case a winning condition is achieve, we return the winner
4. In case the board is filled, the game is declared as drawn.

Deciding the Winner

The main hurdles that haunts us in the entire design is how to decide the winner of the game? Let’s look at the most basic approach with which we can decide the winner of the game. After a player makes a move, we check the entire board for any winning condition. If you remember, the player wins a game if they have marked all the cells of a row, column or diagonal with their sign. Let’s look at the code for that.

# We are storing the count of elements in the row and column in a dict of dict
# of row/column and player's sign (i.e O or X)
# We are iterating through the entire board after a players move to check
# if a row, column or diagonal has been filled by the player
for row in range(board.size):
  for col in range(board.size):
    if board[row][col] == player.sign:
      rowCount[row][player.sign] = rowCount[row][player.sign] + 1
      colCount[col][player.sign] = colCount[col][player.sign] + 1
      if row == col:
        diagonal[0][player.sign] = diagonal[0][player.sign] + 1
      if row + col == board.size:
        diagonal[1][player.sign] = diagonal[1][player.sign] + 1

for count in rowCount:
  if count == board.size:
    return True

for count in colCount:
  if count == board.size:
    return True

if diagonal[0][player.sign] == board.size:
  return True

if diagonal[1][player.sign] == board.size:
  return True

This implementation would result in O(n2) time complexity after every players move. Though this complexity is something that can be forgone for simpler cases when the board size is of conventional nature as in 3x3, but since we don’t want to design a specific tic-tac-toe board, but a generic board where the size of the board can be decided by the users, the value of n could extend to larger numbers. In case of large number, this would not be a ideal approach to go forward with.

How can we further optimize our search here? Instead of searching the entire board after every move of player, does it makes sense to search only the row, column or diagonal they have affected in the move? If that’s the case, we can drastically reduce our search space after every move, and bring down the time complexity from O(N2) to O(N)

# We are storing the count of elements in the row and column in a dict of dict
# of row/column and player's sign (i.e O or X)
# We are iterating through the entire board after a players move to check
# if a row, column or diagonal has been filled by the player
for col in range(board.size):
    if board[row][col] == player.sign
      rowCount[row][player.sign] = rowCount[row][player.sign] + 1
    if row == col:
      diagonal[0][player.sign] = diagonal[0][player.sign] + 1
    if row + col == board.size:
      diagonal[1][player.sign] = diagonal[1][player.sign] + 1

for row in range(board.size):
    if board[row][col] == player.sign
      rowCount[row][player.sign] = rowCount[row][player.sign] + 1
    if row == col:
      diagonal[0][player.sign] = diagonal[0][player.sign] + 1
    if row + col == board.size:
      diagonal[1][player.sign] = diagonal[1][player.sign] + 1

if rowCount[row][player.sign] == board.size:
  return True

if colCount[col][player.sign] == board.size:
  return True

if diagonal[0][player.sign] == board.size:
  return True

if diagonal[1][player.sign] == board.size:
  return True

That’s a great improvement, but can we further improve the time complexity and bring it to a constant time. we’ve been using hashmaps to store the count of marks in a row, column and diagonal already, do we really need to iterate through the board again to check if the winning condition has been achieved or not, can we simply not check if for a particular row, column or diagonal the players’ sign count is equal to the size of the board or not. There we go, we’ve reached a constant time complexity this way.

self.rows[row] = self.rows.get(row, {})
self.rows[row][sign] = self.rows[row].get(sign,0) + 1

if self.rows[row][sign] == self.size:
  return True

self.cols[col] = self.cols.get(col, {})
self.cols[col][sign] = self.cols[col].get(sign,0) + 1

if self.cols[col][sign] == self.size:
  return True

if row == col:
  self.diagonals["forward"] = self.diagonals.get("forward", {})
  self.diagonals["forward"][sign] = self.diagonals["forward"].get(sign,0) + 1
  if self.diagonals["forward"][sign] == self.size:
    return True

if row + col == self.size - 1:
  self.diagonals["backward"] = self.diagonals.get("backward", {})
  self.diagonals["backward"][sign] = self.diagonals["backward"].get(sign,0) + 1
  if self.diagonals["backward"][sign] == self.size:
    return True

There we go, we have a running logic of deciding the winner of the game, and that too in constant time complexity.
The other functionalities can be implemented on top of our logic to get the game running. Try to code out a working solution.

You can refer to my code here if required: https://github.com/archi14/Tic-Tac-Toe

Hope you found this helpful. Feel free to comment any suggestions/questions.