The Logic Behind Tic-Tac-Toe game

Tic-tac-toe is a paper and pencil game that can be traced back to ancient Egypt, where such game boards were found in roofing tiles dating back to 1300 B.C.

I have recently developed an online multiplayer Tic-tac-toe and today I'm going to explain to you how I designed the algorithm behind the game.

I have been doing competitive programming for quite a while and, I could say this was the first project I had to use my problem-solving skills to solve a real-world problem.

First of all, we can draw a flow chart for the algorithm as follows.

According to the above flow chart, we have to keep track of all the moves on a hypothetical board. For that, we can use a 3x3 nested array where every element is initially an empty string and change it to 'X' or 'O' depending on the player who moves.

When a player makes a move on the board we have to make the same move on the hypothetical board and first check whether the moving square is already occupied or not. For that, we can implement a simple algorithm as follows



let board = [
    ['', '', ''],
    ['', '', ''],
    ['', '', ''],
]
const checkAvailability = (x, y, player) => {
    if (board[x][y] !== '') return alert('Square is already occupied');
    board[x][y] = player
}

Since I developed the game using vanilla.js I had to do some additional work as follows.



<div class="container">
    <div class="row">
    <div class="square" id="1-1"></div>
    <div class="square" id="1-2"></div>
    <div class="square" id="1-3"></div>
    </div>
    <div class="row">
    <div class="square" id="2-1"></div>
    <div class="square" id="2-2"></div>
    <div class="square" id="2-3"></div>
    </div>
    <div class="row">
    <div class="square" id="3-1"></div>
    <div class="square" id="3-2"></div>
    <div class="square" id="3-3"></div>
    </div>
</div>



const btnIds = ['1-1', '1-2', '1-3', '2-1', '2-2', '2-3', '3-1', '3-2', '3-3'];

btnIds.forEach((btn) => {
    const button = document.getElementById(btn);

    //Listen for moves on each square
    button.addEventListener('click', (e) => {
        const coordinate = btn.split('-');
        const y = parseInt(coordinate[0]) - 1;
        const x = parseInt(coordinate[1]) - 1;

        //Check whether the selected button is empty
        if (board[y][x] === '') {
            // Eligible
        } else {
                // Not eligible
        }
    });
});

Now we have checked the eligibility for a move and next, we have to check whether the game is ended or not. There are two scenarios where a Tic-tac-toe game end.

Win/Loss
A player will win a game if he can place three of his characters in a horizontal row, vertical column, or diagonal.
Draw
In a draw scenario, all squares of the board should be occupied by either 'X' or 'O' and there should not be any three consecutive squares in a vertical column, horizontal row, or a diagonal with the same character.

We can implement the algorithm for it as follows.



const checkWinner = (board) => {
    // Checking rows
    for (let i = 0; i < 3; i++) {
        const a = board[i][0];
        const b = board[i][1];
        const c = board[i][2];

        if (a != '' && a === b && b === c) {
            return 'win';
        }
    }

    // Checking columns
    for (let i = 0; i < 3; i++) {
        const a = board[0][i];
        const b = board[1][i];
        const c = board[2][i];

        if (a != '' && a === b && b === c) {
            return 'win';
        }
    }

    // Left Top to Bottom right diagonal
    const a = board[0][0];
    const b = board[1][1];
    const c = board[2][2];

    if (a != '' && a === b && b === c) {
        return 'win';
    }

    // Right Top to Left bottom diagonal
    const d = board[0][2];
    const e = board[1][1];
    const f = board[2][0];

    if (d != '' && d === e && e === f) {
        return 'win';
    }

    // Check for draw
    for (let i = 0; i < 3; i++) {
        for (let j = 0; j < 3; j++) {
            const square = board[i][j];
            if (square === '') return undefined;
        }
    }

    return 'draw';
};

Finally, we can combine all the above functionalities and implement the complete algorithm as follows.



const checkAvailability = (x, y, player) => {
    if (board[x][y] !== '') return alert('Square is already occupied');
    board[x][y] = player

    if (checkWinner(board)) return alert(checkWinner(board));
    const nextPlayer = player === 'X' ? 'O' : 'X';
    alert(`${nextPlayer}s' chance`)
}

Additionally, we can add a few more conditions to implement functionalities such as checking whether the chance is for which player, not allowing the players to move once the game end, etc.

Be creative and implement your solutions for the above scenarios and feel free to ask others whenever you are stuck.

Have a great weekend. Thank You!

Blog

The Logic Behind Tic-Tac-Toe game

Shakya Peiris

Join Our Newsletter. No Spam, Only the good stuff.

Related