📌 1. Problem Statement

Design a Tic Tac Toe game that:

• Supports configurable board size (N × N)

• Supports 2 players

• Validates moves

• Detects win efficiently

• Detects draw

• Logs moves

• Is extensible (AI, multiplayer, new win strategies)

• Uses proper design patterns

• Is written in C++ (single-threaded)

📌 2. Functional Requirements

Core Features

• Create game with size N

• Add 2 players

• Players make alternate moves

• Validate moves

• Detect winner

• Detect draw

• Display result

• Log game events

• Allow restart (extensible)

📌 3. Non-Functional Requirements

• Clean architecture

• O(1) win detection

• Extensible strategy

• Easy to add AI

• Maintainable code

• Testable components

📌 4. High-Level Architecture

Game
 ├── Board
 │     └── Cell
 ├── Player
 ├── WinningStrategy
 ├── Logger
 └── GameState

📌 5. Design Patterns Used (With Clear Reasoning)

Pattern	Where Used	Why Used
Strategy	Winning algorithm	Switch win logic easily
Factory Method	Player creation	Encapsulate object creation
Singleton	Logger	One global logger
Observer	Logging system	Notify events
Decorator	AI Player	Add behavior dynamically
Builder	Game construction	Clean configuration
Command	Move execution	Encapsulate actions
State	Game lifecycle	Manage transitions
Template Method	Winning base class	Standard win-check structure

📌 6. Algorithms Used

🟢 1. O(1) Winning Algorithm (Optimized)

Instead of scanning entire board after every move (O(n²)):

We maintain:

rowCount[n]
colCount[n]
diag
antiDiag

For Player X → +1 For Player O → -1

If:

abs(rowCount[i]) == n
OR abs(colCount[i]) == n
OR abs(diag) == n
OR abs(antiDiag) == n

→ Winner found

Complexity:

• Move: O(1)

• Win check: O(1)

🟢 2. Move Validation

• Check bounds

• Check if cell empty

Complexity: O(1)

🟢 3. Draw Detection

if totalMoves == n*n

📌 7. Complete C++ Implementation

🔹 ENUMS

enum class Symbol { X = 1, O = -1 };
enum class GameStatus { IN_PROGRESS, DRAW, WIN };

🔹 Observer Pattern

class Observer {
public:
    virtual void update(string message) = 0;
    virtual ~Observer() {}
};

🔹 Singleton Logger

class Logger : public Observer {
private:
    Logger() {}
public:
    static Logger& getInstance() {
        static Logger instance;
        return instance;
    }

    void update(string message) override {
        cout << "[LOG] " << message << endl;
    }
};

🔹 Cell Class

class Cell {
public:
    int row, col;
    Symbol* symbol;

    Cell(int r, int c) : row(r), col(c), symbol(nullptr) {}

    bool isEmpty() {
        return symbol == nullptr;
    }

    void setSymbol(Symbol* s) {
        symbol = s;
    }
};

🔹 Board Class

class Board {
private:
    int size;
    vector<vector<Cell>> grid;

public:
    Board(int n) : size(n) {
        for(int i=0;i<n;i++) {
            vector<Cell> row;
            for(int j=0;j<n;j++)
                row.emplace_back(i,j);
            grid.push_back(row);
        }
    }

    int getSize() { return size; }

    bool placeMove(int r, int c, Symbol* s) {
        if(r<0 || c<0 || r>=size || c>=size)
            return false;
        if(!grid[r][c].isEmpty())
            return false;

        grid[r][c].setSymbol(s);
        return true;
    }
};

🔹 Strategy Pattern – Winning Strategy Base

class BaseWinningStrategy {
protected:
    int size;
public:
    BaseWinningStrategy(int n): size(n){}
    virtual bool checkWin(int row, int col, Symbol sym)=0;
    virtual ~BaseWinningStrategy(){}
};

🔹 Efficient Winning Strategy (O(1))

class EfficientWinningStrategy : public BaseWinningStrategy {
private:
    vector<int> rowCount;
    vector<int> colCount;
    int diag=0, antiDiag=0;

public:
    EfficientWinningStrategy(int n)
        : BaseWinningStrategy(n),
          rowCount(n,0), colCount(n,0) {}

    bool checkWin(int row, int col, Symbol sym) override {
        int val = (int)sym;

        rowCount[row]+=val;
        colCount[col]+=val;

        if(row==col) diag+=val;
        if(row+col==size-1) antiDiag+=val;

        if(abs(rowCount[row])==size ||
           abs(colCount[col])==size ||
           abs(diag)==size ||
           abs(antiDiag)==size)
            return true;

        return false;
    }
};

🔹 Factory Method – Player Creation

class Player {
protected:
    string name;
    Symbol symbol;

public:
    Player(string n, Symbol s): name(n), symbol(s){}
    virtual pair<int,int> makeMove()=0;
    Symbol getSymbol(){ return symbol; }
    string getName(){ return name; }
    virtual ~Player(){}
};

class HumanPlayer : public Player {
public:
    HumanPlayer(string n, Symbol s)
        : Player(n,s){}

    pair<int,int> makeMove() override {
        int r,c;
        cout<<"Enter row and col: ";
        cin>>r>>c;
        return {r,c};
    }
};

class PlayerFactory {
public:
    static shared_ptr<Player> createPlayer(
        string type, string name, Symbol s) {
        if(type=="HUMAN")
            return make_shared<HumanPlayer>(name,s);
        return nullptr;
    }
};

🔹 Decorator Pattern – AI Extension

class PlayerDecorator : public Player {
protected:
    shared_ptr<Player> player;
public:
    PlayerDecorator(shared_ptr<Player> p)
        : Player(p->getName(), p->getSymbol()),
          player(p) {}
};

class AIPlayerDecorator : public PlayerDecorator {
public:
    AIPlayerDecorator(shared_ptr<Player> p)
        : PlayerDecorator(p){}

    pair<int,int> makeMove() override {
        cout<<"AI making move...\n";
        return {0,0}; 
    }
};

🔹 Game Class

class Game {
private:
    Board board;
    shared_ptr<Player> p1;
    shared_ptr<Player> p2;
    shared_ptr<Player> current;
    unique_ptr<BaseWinningStrategy> strategy;
    GameStatus status;
    int moves=0;

public:
    Game(int n,
         shared_ptr<Player> pl1,
         shared_ptr<Player> pl2)
        : board(n), p1(pl1), p2(pl2),
          current(pl1),
          strategy(make_unique<EfficientWinningStrategy>(n)),
          status(GameStatus::IN_PROGRESS) {}

    void play() {

        while(status==GameStatus::IN_PROGRESS) {

            auto move=current->makeMove();
            bool placed=board.placeMove(
                move.first, move.second,
                &current->getSymbol());

            if(!placed){
                cout<<"Invalid Move\n";
                continue;
            }

            Logger::getInstance().update(
                current->getName()+" moved");

            moves++;

            if(strategy->checkWin(
                move.first, move.second,
                current->getSymbol())) {

                status=GameStatus::WIN;
                cout<<current->getName()<<" Wins!\n";
                break;
            }

            if(moves==board.getSize()*board.getSize()){
                status=GameStatus::DRAW;
                cout<<"Game Draw\n";
                break;
            }

            current=(current==p1? p2:p1);
        }
    }
};

🔹 Builder Pattern – Game Builder

class GameBuilder {
private:
    int size;
    shared_ptr<Player> p1;
    shared_ptr<Player> p2;

public:
    GameBuilder& setSize(int n){
        size=n;
        return *this;
    }

    GameBuilder& setPlayer1(shared_ptr<Player> pl){
        p1=pl;
        return *this;
    }

    GameBuilder& setPlayer2(shared_ptr<Player> pl){
        p2=pl;
        return *this;
    }

    unique_ptr<Game> build(){
        return make_unique<Game>(size,p1,p2);
    }
};

🔹 Main Function

int main(){

    auto player1=PlayerFactory::createPlayer(
        "HUMAN","Alice",Symbol::X);

    auto player2=PlayerFactory::createPlayer(
        "HUMAN","Bob",Symbol::O);

    auto game=GameBuilder()
                .setSize(3)
                .setPlayer1(player1)
                .setPlayer2(player2)
                .build();

    game->play();

    return 0;
}

📌 Complexity Analysis

Operation	Complexity
Move Placement	O(1)
Win Check	O(1)
Draw Check	O(1)
Space	O(n²)

🧵 Multithreading Problems in the Tic Tac Toe Implementation

Our current implementation is single-threaded and assumes:

• Only one thread calls game->play()

• Only one thread makes moves

• No external UI thread

• No AI thread

• No logging concurrency

If we allow:

• Multiple threads (UI thread + AI thread)

• Network multiplayer

• Async logging

• Spectator updates

👉 The current design becomes unsafe.

Below is a complete breakdown of every multithreading issue and its proper fix.

🚨 PROBLEM 1: Race Condition on Board State

Where?

bool placeMove(int r, int c, Symbol* s)

Two threads:

Thread A: places move at (0,0) Thread B: places move at (0,0)

Both check:

if(!grid[r][c].isEmpty())

Both see empty Both write Result: corrupted state ❌