The Logic Behind Tic-Tac-Toe game
Tags: javascript, computerscience, algorithms
Published: 2022-10-02 05:40:13

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.

![The algorithm in flow chart](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9x3ve20u1k0q7jf3s6pt.png)

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

```js
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.

```html
<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>
```

```js
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.

1. Win/Loss
A player will win a game if he can place three of his characters in a horizontal row, vertical column, or diagonal. 

2. 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.

```js
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.

```js
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!