TIC TAC TOE GAME

DATA STRUCTURE AND ALGORITHM

PROJECT REPORT

Submittedby

J.NOMITH UJJWAL (RA2311030020181)

B.KRUSHIK VARDHAN (RA2311030020182)

S.RATHAN SIMHA REDDY (RA2311030020176)

Under the guidance of

Dr. G.Deena
(Associate Professor, Department of Computer Science and Engineering)

in partial fulfilment for the award of the degree

of

BACHELOR OF TECHNOLOGY
in

COMPUTER SCIENCE AND ENGINEERING

SRM INSTITUTE OF SCIENCE AND TECHNOLOGY

RAMAPURAM, CHENNAI

(Deemed to be University U/S3 of UGCAct ,1956)

 BONAFIDE CERTIFICATE
Certified that this project report titled TIC TAC TOE GAME is the bonafide
work of J.NOMITH UJJWAL (RA2311030020181)who carried out the project
work under my supervision. Certified further, that to the bestof my knowledge
the work reported herein does not form any other project report ordissertation on
the basis of which a degree or award was conferred on an occasion onthis or
anyothercandidate.

SIGNATURE SIGNATURE

Dr. G. DEENA, Dr. K. RAJA, M.E.,Ph.D.,

Associate Professor Professor and Head
Computer Science and Engineering, Computer Science and Engineering
SRM Institute of Science and Technology, SRM Institute of Science and Technology
Ramapuram, Chennai. Ramapuram, Chennai

Submitted for the project viva-voce held on___________ at SRM Institute of Science and
Technology, Ramapuram, Chennai.
 DECLARATION

We hereby declare that the entire work contained in this project report titled IC
TAC TOE GAME has been carried out by J.NOMITH UJJWAL
(RA2311030020181) at SRM Institute of Science and Technology, Ramapuram,
Chennai, under the guidance of Dr.G.Deena , Associate professor, Department of
Computer Science and Engineering.

Place: Chennai MEERA ELDHO

Date: M.N.SWASTHIKA SAHANA
 INTERDUCTION
Games played on three-in-a-row boards can be traced back to Egypt where such
game boards have been found on roofing tiles dating from around 1300 BC. An early variation
of tic-tac-toe was played in the Roman empire Around the first century BC. It was called Terni
lipalli (Three pebbles at a time) and instead of having any number of pieces, each player had
only three; thus, they had to move them around to empty spaces to keep playing.[7] The
game's grid

markings have been found chalked all over Rome. Another closely related ancient game is
Three men morris which is also played on a simple grid and requires three pieces in a row to
finish, and Picaria, a game of the Puebloans.The different names of the game are more recent.

The first print reference to noughts and crosses" (nought being an alternative word for 'zero'),
the British name, appeared in 1858, in an issue of Notes and Queries The first print
reference to a game called "tick-tack-toe" occurred in 1884, but referred to "a children's game
played on a slate, consisting of trying with the eyes shut to bring the pencil down on one of the
numbers of a set, the number hit being scored. "Tic-tac-toe" may also derive from "tick-tack",
the name of an old version of backgammon first described in 1558. The US renaming of
"noughts and crosses" to "tic-tac-toe" occurred in the 20th century.

The first player, who shall be designated "X", has three possible strategically distinct
positions to mark during the first turn. Superficially, it might seem that there are nine possible
positions, corresponding to the nine squares in the grid. However, by rotating the board, we
will find that, in the first turn, every corner mark is strategically equivalent to every other
corner mark. The same is true of

every edge (side middle) mark. From a strategic point of view, there therefore only three
possible first marks: corner, edge, or Centre.

Player X can win or force a draw from any of these starting marks; however, playing the
corner gives the opponent the smallest choice of squares which must be played to avoid losing.
This might suggest that the corner is the best opening move for X, however if another study
shows that if the players are not perfect, an opening move in the Centre is best for X The
second player, who shall be designated "O", must be to respond to X's opening mark in such a
way as to avoid the forced win. Player O must always respond to a corner opening with a
Centre mark, and to a Centre opening with a corner mark. An edge opening must be answered
either with a centre mark, a corner mark next to the X, or an edge mark opposite the X. Any
other responses will allow X to force the win. Once the opening is completed, O's task is to
follow the above list of priorities in order to force the draw, or else to gain a win if X makes a
weak play.
 SCOPE

This project will cover:

•Game Design: The game will be designed to run in a terminal or

command-line interface where two players alternate their turns.

•Data Structures: We will use a 2D array (matrix) to represent the

game board, where each element in the array corresponds to a position in
the grid.

•Algorithmic Implementation: Efficient algorithms will be

developed to:

•Check for victory conditions after each player’s turn.

• Handle invalid moves (e.g., a player trying to play in an

occupied cell).

• Declare the winner or identify a draw.

•Time Complexity: The project will focus on optimizing time

complexity, particularly in checking for wins, which will involve constant-
time checks of rows, columns, and diagonals.

6
 OBJECTIVES
The primary objective of this project is to:

• Design and implement the game of Tic Tac Toe using basic
data structures.

• Ensure efficient handling of player turns, input validation, and

game state updates.

• Use algorithms to check for the game’s completion, either by

a win or a draw, as efficiently as possible.

• Provide a command-line interface where two players can play

the game interactively.

By completing this project, we aim to:

1. Develop a clear understanding of how to use arrays and lists to represent the
game board.

2. Implement algorithms to check the status of the game after each turn,
detecting winning conditions and draws.

3. Provide a platform that seamlessly manages the interaction between the

players and the game system, including error handling and ensuring the validity of moves.

7
 PROBLEM STATEMENT
The problem requires building a Tic Tac Toe game that:

1. Manages Player Turns: The game should alternate turns

between two players and validate the inputs to ensure that players can
only mark unoccupied spaces.

2. Detects Win Conditions: After each move, the game must

check whether the current player has won by forming a line of three
symbols in any row, column, or diagonal.

3. Handles Draws: If all cells on the grid are filled and no

player has won, the game must declare a draw.

4. Validates Moves: Players can only place their mark in an

empty cell. The game must reject moves where the cell is already
occupied or if the input is out of bounds.

5. Provides an Interface: The game should be implemented in

a way that allows two players to interact easily (in this case, via a
command-line interface).

6. Ends Correctly: The game should stop once a player wins or

a draw occurs, and should announce the result before ending.

8
 PROBLEM DESCRIPTION
The Tic Tac Toe game is a two-player, zero-sum, turn-based game
played on a 3x3 grid. The game is simple in design yet requires efficient
handling of game mechanics to ensure the rules are followed, and the
game progresses smoothly. In this project, the Tic Tac Toe game will be
implemented using basic data structures and algorithms, focusing on
managing the game’s state, checking for winning conditions, and
validating user input.

3.1 Game Rules

1. Players:

• There are two players in the game:

• Player 1: Uses the symbol ‘X’.

• Player 2: Uses the symbol ‘O’.

• The game alternates between Player 1 and Player 2, with

each player marking one empty cell during their turn.

2. Game Board:

• The game is played on a 3x3 grid (a matrix of 9 cells).

9
 • The grid starts empty, and players take turns marking a single
cell with their respective symbols (‘X’ or ‘O’).

3. Winning Condition:

• A player wins the game if they can place three of their

symbols consecutively in a straight line (either horizontally, vertically, or
diagonally).

• There are 8 possible winning combinations:

• 3 rows, 3 columns, and 2 diagonals.

4. Draw Condition:

• If all cells are filled and no player has formed a line of three
consecutive symbols, the game ends in a draw.

5. Move Validation:

• A player can only mark an empty cell. If a player tries to mark

a cell that has already been occupied or selects a cell outside the grid’s
boundaries, the move is considered invalid, and the player will be
prompted to select another cell.

6. Game Termination:

• The game terminates when:

• One of the players achieves a winning condition.

• All cells are filled without a winner, resulting in a draw.

• Once the game ends, the result is displayed (either “Player 1

wins”, “Player 2 wins”, or “It’s a draw”), and the game stops accepting
further input.

10
 IMPLEMENTATION AND CODE
#include <stdbool.h>

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#define COMPUTER 1

#define HUMAN 2

#define SIDE 3

#define COMPUTERMOVE 'O'

#define HUMANMOVE 'X'

// ---------------- Intelligent Moves start

11
struct Move {

int row, col;

};

char player = 'x', opponent = 'o';

// This function returns true if there are moves

// remaining on the board. It returns false if

// there are no moves left to play.

bool isMovesLeft(char board[3][3])

for (int i = 0; i < 3; i++)

for (int j = 0; j < 3; j++)

if (board[i][j] == '_')

return true;

return false;

// This is the evaluation function

int evaluate(char b[3][3])

12
{

// Checking for Rows for X or O victory.

for (int row = 0; row < 3; row++) {

if (b[row][0] == b[row][1]

&& b[row][1] == b[row][2]) {

if (b[row][0] == player)

return +10;

else if (b[row][0] == opponent)

return -10;

// Checking for Columns for X or O victory.

for (int col = 0; col < 3; col++) {

if (b[0][col] == b[1][col]

&& b[1][col] == b[2][col]) {

if (b[0][col] == player)

return +10;

else if (b[0][col] == opponent)

return -10;

13
 }

// Checking for Diagonals for X or O victory.

if (b[0][0] == b[1][1] && b[1][1] == b[2][2]) {

if (b[0][0] == player)

return +10;

else if (b[0][0] == opponent)

return -10;

if (b[0][2] == b[1][1] && b[1][1] == b[2][0]) {

if (b[0][2] == player)

return +10;

else if (b[0][2] == opponent)

return -10;

// Else if none of them have won then return 0

return 0;

14
// This is the minimax function. It considers all

// the possible ways the game can go and returns

// the value of the board

int minimax(char board[3][3], int depth, bool isMax)

int score = evaluate(board);

// If Maximizer has won the game return his/her

// evaluated score

if (score == 10)

return score;

// If Minimizer has won the game return his/her

// evaluated score

if (score == -10)

return score;

// If there are no more moves and no winner then

// it is a tie

if (isMovesLeft(board) == false)

15
 return 0;

// If this maximizer's move

if (isMax) {

int best = -1000;

// Traverse all cells

for (int i = 0; i < 3; i++) {

for (int j = 0; j < 3; j++) {

// Check if cell is empty

if (board[i][j] == '_') {

// Make the move

board[i][j] = player;

int val

= minimax(board, depth + 1, !isMax);

if (val > best) {

best = val;

// Undo the move

board[i][j] = '_';

16
 }

return best;

// If this minimizer's move

else {

int best = 1000;

// Traverse all cells

for (int i = 0; i < 3; i++) {

for (int j = 0; j < 3; j++) {

// Check if cell is empty

if (board[i][j] == '_') {

// Make the move

board[i][j] = opponent;

// Call minimax recursively and choose

int val

= minimax(board, depth + 1, !isMax);

17
 if (val < best) {

best = val;

// Undo the move

board[i][j] = '_';

return best;

// This will return the best possible move for the player

struct Move findBestMove(char board[3][3])

int bestVal = -1000;

struct Move bestMove;

bestMove.row = -1;

bestMove.col = -1;

// Traverse all cells, evaluate minimax function for

18
// all empty cells. And return the cell with optimal

// value.

for (int i = 0; i < 3; i++) {

for (int j = 0; j < 3; j++) {

// Check if cell is empty

if (board[i][j] == '_') {

// Make the move

board[i][j] = player;

// compute evaluation function for this

// move.

int moveVal = minimax(board, 0, false);

// Undo the move

board[i][j] = '_';

// If the value of the current move is

// more than the best value, then update

// best/

if (moveVal > bestVal) {

bestMove.row = i;

19
 bestMove.col = j;

bestVal = moveVal;

// printf("The value of the best Move is : %d\n\n",

// bestVal);

return bestMove;

// -----------------------------------Intelligent Moves end

// Function to display the game board

void showBoard(char board[][SIDE])

printf("\n\n");

printf("\t\t\t %c | %c | %c \n", board[0][0],

board[0][1], board[0][2]);

20
 printf("\t\t\t--------------\n");

printf("\t\t\t %c | %c | %c \n", board[1][0],

board[1][1], board[1][2]);

printf("\t\t\t--------------\n");

printf("\t\t\t %c | %c | %c \n\n", board[2][0],

board[2][1], board[2][2]);

// Function to show the instructions

void showInstructions()

printf("\t\t\t Tic-Tac-Toe\n\n");

printf("Choose a cell numbered from 1 to 9 as below "

"and play\n\n");

printf("\t\t\t 1 | 2 | 3 \n");

printf("\t\t\t--------------\n");

printf("\t\t\t 4 | 5 | 6 \n");

printf("\t\t\t--------------\n");

printf("\t\t\t 7 | 8 | 9 \n\n");

21
 printf("-\t-\t-\t-\t-\t-\t-\t-\t-\t-\n\n");

// Function to initialise the game

void initialise(char board[][SIDE], int moves[])

srand(time(NULL));

// Initially, the board is empty

for (int i = 0; i < SIDE; i++) {

for (int j = 0; j < SIDE; j++)

board[i][j] = ' ';

// Fill the moves with numbers

for (int i = 0; i < SIDE * SIDE; i++)

moves[i] = i;

// Randomize the moves

for (int i = 0; i < SIDE * SIDE; i++) {

int randIndex = rand() % (SIDE * SIDE);

22
 int temp = moves[i];

moves[i] = moves[randIndex];

moves[randIndex] = temp;

// Function to declare the winner of the game

void declareWinner(int whoseTurn)

if (whoseTurn == COMPUTER)

printf("COMPUTER has won\n");

else

printf("HUMAN has won\n");

// Function to check if any row is crossed with the same

// player's move

int rowCrossed(char board[][SIDE])

for (int i = 0; i < SIDE; i++) {

if (board[i][0] == board[i][1]

23
 && board[i][1] == board[i][2]

&& board[i][0] != ' ')

return 1;

return 0;

// Function to check if any column is crossed with the same

// player's move

int columnCrossed(char board[][SIDE])

for (int i = 0; i < SIDE; i++) {

if (board[0][i] == board[1][i]

&& board[1][i] == board[2][i]

&& board[0][i] != ' ')

return 1;

return 0;

// Function to check if any diagonal is crossed with the

24
// same player's move

int diagonalCrossed(char board[][SIDE])

if ((board[0][0] == board[1][1]

&&board[1][1] == board[2][2]

&&board[0][0] != ' ')

|| (board[0][2] == board[1][1]

&&board[1][1] == board[2][0]

&&board[0][2] != ' '))

return 1;

return 0;

// Function to check if the game is over

int gameOver(char board[][SIDE])

return (rowCrossed(board) || columnCrossed(board)

|| diagonalCrossed(board));

25
// Function to play Tic-Tac-Toe

void playTicTacToe(int whoseTurn)

// A 3*3 Tic-Tac-Toe board for playing

char board[SIDE][SIDE];

int moves[SIDE * SIDE];

// Initialise the game

initialise(board, moves);

// Show the instructions before playing

showInstructions();

int moveIndex = 0, x, y;

// Keep playing until the game is over or it is a draw

while (!gameOver(board) && moveIndex != SIDE * SIDE) {

if (whoseTurn == COMPUTER) {

char tempBoard[3][3];

for (int i = 0; i < 3; i++) {

26
 for (int j = 0; j < 3; j++) {

if (board[i][j] == 'X') {

tempBoard[i][j] = 'x';

else if (board[i][j] == 'O') {

tempBoard[i][j] = 'o';

else {

tempBoard[i][j] = '_';

struct Move thisMove = findBestMove(tempBoard);

x = thisMove.row;

y = thisMove.col;

board[x][y] = COMPUTERMOVE;

printf("COMPUTER has put a %c in cell %d %d\n",

COMPUTERMOVE, x, y);

showBoard(board);

moveIndex++;

whoseTurn = HUMAN;

27
}

else if (whoseTurn == HUMAN) {

int move;

printf("Enter your move (1-9): ");

scanf("%d", &move);

if (move < 1 || move > 9) {

printf("Invalid input! Please enter a "

"number between 1 and 9.\n");

continue;

x = (move - 1) / SIDE;

y = (move - 1) % SIDE;

if (board[x][y] == ' ') {

board[x][y] = HUMANMOVE;

showBoard(board);

moveIndex++;

if (gameOver(board)) {

declareWinner(HUMAN);

return;

whoseTurn = COMPUTER;

28
 }

else {

printf("Cell %d is already occupied. Try "

"again.\n",

move);

// If the game has drawn

if (!gameOver(board) && moveIndex == SIDE * SIDE)

printf("It's a draw\n");

else {

// Toggling the user to declare the actual winner

if (whoseTurn == COMPUTER)

whoseTurn = HUMAN;

else if (whoseTurn == HUMAN)

whoseTurn = COMPUTER;

// Declare the winner

declareWinner(whoseTurn);

29
}

// Driver program

int main()

// Let us play the game with COMPUTER starting first

playTicTacToe(COMPUTER);

return 0;

OUTPUT

30
 CONCLUSION
The Tic Tac Toe Game Project successfully demonstrates the
application of fundamental data structures and algorithms in developing
an interactive and engaging game. By representing the game board as a
2D array and employing simple yet efficient algorithms to validate moves,
check win conditions, and handle game states, this project highlights how
basic DSA concepts can be applied to solve real-world problems.
In conclusion, the Tic Tac Toe game serves as an excellent exercise in
applying DSA concepts to a problem involving decision-making, user
interaction, and state management. It lays the groundwork for more
complex applications in game development and interactive systems while
emphasizing the importance of efficiency and correctness in algorithm
design.

31