Continuing our series, we will now design one of the games mentioned at https://igotanoffer.com/blogs/tech/system-design-interviews section 2.

Another topic that comes up frequently is designing a classic game. The exact game you’ll be asked about varies, but here are some of the most common ones we’ve seen:

Tic-tac-toe

Chess

Boggle

Minesweeper

Cards/poker

In the first round, we will take a look what they all have in common in terms of requirements and then go into more detail afterwards.

Requirement Gathering - Fundamentals

Let's gather our requirements once more.

Requirements

All of the games are played in rounds. Some by a single player (minesweeper), most by two players (Tic-Tac-Toe) and others by N players (cards, Poker, Boggle).
After a player makes a move, the state of the game needs to be updated and shown to the players.
Stop the game if one of the player wins or there is a draw.
Allow moves according to game rules
Calculate winner after each move according to game rules.

The non-functional requirements are simple

Non-functional requirements

Make user-interaction seamless and pleasant
No further non-functional requirements for now

As the non-functional requirements are kept simple, we will not try to overengineer the solution either. Sure, the stateholders will ask for additional functional and non functional requirements such as scoring boards, how to join a game, chat within a game or the ability to run thousand of games in parallel. Obviously then there will be asks for monetization, authentication, authorization, in-game purchases and the like but we will focus on the core domain.

Let's choose TicTacToe as our special case and continue from there.

The rules are (summarized by ChatGPT):

Game Board: Tic-Tac-Toe is played on a 3x3 grid, which can be drawn on paper or played on a computer or mobile app.
Players: There are two players in the game. One player uses 'X' and the other uses 'O'.
Objective: The main objective is to be the first player to get three of their marks in a row - horizontally, vertically, or diagonally.
Game Play:
- Players take turns placing their mark (X or O) in an empty square on the grid.
- The first player is usually the 'X' and the second player is the 'O'.
Winning the Game: A player wins if they manage to place three of their marks in a row, column, or diagonal.
Draw: If all 9 squares are filled and neither player has 3 marks in a row, the game is considered a draw.

Let's start with the architecture and design.

Architecture and Design

Similar to my previous post https://hashnode.com/edit/clr5yzlkh000b09lc77rq5l45, we will choose an appropriate architectural style before we design the specifics.

Both a layered traditional application and a monolithic architecture could be sensible choices, depending on the use-case. For a web-based application it's almost impossible to actually make it completelty monolithic if the two players are on different computers. So some layering (client + server) will automatically be involved.

A Micro-Service or Service-Oriented-Architecture just does not have any benefits in this use-case. There is a single set of rules and those most likely would be kept in a single micro-service. You cannot really consider the presentation layer to be a micro-service either. It just does not apply here, really.

We also know that a Data Centric architectural style is not benefitial as we did not even have any benefits about persistence. This does not, however, mean that you cannot be successful by modelling the game logic through OOP and the relationship of the objects that model our domain.

The specific domain of our game can be transformed into an implementation with OOP and functional programming, either way.

This particular exercise is an example where pseudo-code or real interfaces with missing implementation are a good way to start quickly and iterate on the design. Diagrams are inferiour in my opinion in this particular exercise.

Object Oriented Programming Approach

Let's start with the traditional approach of sketching out this game in OOP. We will try to do this in the most traditional approach for OOP.

class Player {
    // constructor missing
    symbol: string;
    name: string;
}  
class Board {
    // constructor missing
    grid: string[][];
}
class TicTacToeGame {
    // constructor missing
    board: Board;
    player1: Player;
    player2: Player;
    currentPlayer: Player;
    move(row: number, col: number): boolean;
    checkWin(): true;
    checkDraw(): boolean;
    switchPlayer(): void;
}

const game = // init class for TicTacToe;
let gameIsRunning = true;
// displayBoard(game.board);
while (gameIsRunning) {
    // obtain moveParams
    const moveSuccessful = game.move(moveParams);
    // displayBoard(game.board); display the changed board after a move
    if (moveSuccessful) {
        if (game.checkWin()) {
            gameIsRunning = false;
        } else if (game.checkDraw()) {
            gameIsRunning = false;
        } else {
            game.switchPlayer();
        }
    }

}

The first class is to define what a Player is. A minimum requirement would be that each player has a symbol and a name associated to it.

Now we define the Board class with its data structure as simply a two dimensional array of string. This is obviously awful and we could improve on it later with an enum or a more specific Field class. In traditional OOP one probably would choose a Field class.

But the more interesting aspect is the class TicTacToeGame . The board and the two players have to be initialized. The currentPlayer switches through the switchPlayer method. move is called with some parameters obtained from user input. In the game loop we end the game on a draw or a win and show the board if a move has been made.

While this works, this must be improved. From this starting point we would now

Add validation that the two players have not choosen the same symbol while narrowing down the symbol through a class or enum. This adds further complexity. This validation logic would need to be implemented on the class TicTacToeGame .
Express what parts of the classes are private and what parts are public
Lock the properties player1 and player2 as they cannot be modified after the game started.

The player class could look something like

class Symbol {
    private value: string;

    private constructor(value: string) {
        this.value = value;
    }

    public static readonly X = new Symbol("X");
    public static readonly O = new Symbol("O");
}

This gives us the ability to use X and O directly.

How would we validate that the two players are set correctly.

private validatePlayerSymbols(player1: Player, player2: Player): void {
    const symbol1 = player1.getSymbol();
    const symbol2 = player2.getSymbol();

    if ((symbol1 === Symbol.X && symbol2 === Symbol.O) || (symbol1 === Symbol.O && symbol2 === Symbol.X)) {
        // Symbols are valid
    } else {
        throw new Error("Players must have different symbols: either 'X' or 'O'.");
    }
}

This would solve it for now but we would utterly rely on run-time validation to implement the game rules.

Could we do better? Sure, we could setup the symbol of the second player after choosing the first player chooses the symbol.

But this does not change the fact that the fundamental classes don't actually describe the game rules directly declaratively.

Let's see how this would be done in Functional Programming.

Functional Programming Approach

We use Algebraic Data Types (wiki: ADT) to express the Player as a type.

type PlayerSymbol = 'X' | 'O';

Next we define the Player

type Player<S extends Symbol> = {
    name: string;
    symbol: S;
};

by us not using Symbol but S within the Player type we can then create a utility type

type OppositeSymbol<S extends Symbol> = S extends 'X' ? 'O' : 'X';

and further define

player1: Player<S>;
player2: Player<OppositeSymbol<S>>;

to fully encapsulate that the second player has the opposite symbol at compile time instead of runtime.

type BoardSymbol = PlayerSymbol | '';
type Board = BoardSymbol[][];

we actually don't need to do more than that right now to define any board. In functional programming we prefer to create functions and keep the data structures as simple as possible. However, there are cases where we do embrace OOP and Functional Programming at once. Which is easily possible in TypeScript.

Functions themselves are types indeed and that's why we can just define the overall Move function as a type itself.

type Move = (board: Board, row: number, col: number, 
    symbol: PlayerSymbol) => Board;

As it's not a method anymore, we pass the board into the function as well as getting it as a result. Which is necessary as want to use Board as an immutable value and create a new value every single time a move is made. In functional programming we embrace immutable values. Multi-paradigm languages such as Typescript or Scala can obviously get around this by allowing mutable variables as well as immutable values.

Similar to before, we still need

isGameOver(board: Board): boolean;
function getOppositeSymbol<S extends PlayerSymbol>(symbol: S): OppositeSymbol<S> {
    // ... implementation missing
}
const makeMove: Move = (board: Board, row: number, col: number, 
    symbol: PlayerSymbol) => { // implementation ... }

function ticTacToeGameLoop(board: Board, currentPlayer: PlayerSymbol): void {
    printBoard(board); // this is not a pure function without side-effects
    const moveParams = obtainMoveParams(); // also not a pure function without side-effects
    if (isGameOver(board)) {
        // exit
    }

    const nextBoard = makeMove(board, moveParams);
    // Switch player
    const nextPlayer = getOppositeSymbol(currentPlayer);

    // Recursive call for the next turn
    ticTacToeGameLoop(nextBoard, nextPlayer);
}

// Starting the game
const initialBoard: Board = // ... init the board
ticTacToeGameLoop(initialBoard, 'X'); // just an example where X starts

We define the overall game loop as a recursive function instead of a loop as this gives us the cleanest functional implementation possible.

Displaying the board is a side-effect as we are mutating the outside state. Similarily, obtaining an outside state is considered a side-effect because it violates one of the core principles of the paradigm: function purity. A function is considered pure if it always produces the same output for the same input and does not cause any observable side effects.
However, we completely isolated all side-effects to two functions. The code could easily be modified to abstract all side-effects in a single function as we could combine printBoard and obtainMoveParams.

Some people might prefer to even define the application of the side-effects through a Monad. I am not one of these people.

If we wanted to go further and actually narrow down the function ticTacToeGameLoop I would opt to define it through an effectful framework such as EffectTS which is similar to ZIO in Scala.

// Effect<Requirements, Error, Value> 
type TicTacToeGameLoop = Effect.Effect<Console, never, void>

This really is just a teaser and I hope that I can get into this topic on another part of my blog series.

Summary

We've seen the advantages of using functional programming to define game rules through compile-time safe constructs. This approach significantly enhances the correctness and conciseness of the implementation, surpassing traditional methods like extensive unit testing and runtime validation.

However, transitioning to this style can be challenging. TypeScript, with its flexibility, provides an excellent opportunity to learn functional programming without being overly restrictive.

This design task also underscores the effectiveness of directly writing code, particularly with functional programming patterns. While diagrams and mathematical definitions are alternatives, they may not be as familiar to many developers. TypeScript offers a more accessible and practical approach to exploring these concepts.

Thanks for following.

Systems Design 2 - TicTacToe

An example where Pseudo-Code gets you farther than extensive diagramming.