Minimax Algorithm: Tic-Tac-Toe

                   In this blog, we are going to learn about the new algorithm which is 'minimax algorithm' and will have a look at it's pseudo code....

                  Mini-max algorithm is a recursive or backtracking algorithm which is used in decision-making and game theory. It provides an optimal move for the player assuming that opponent is also playing optimally.

                  In this algorithm two players play the game, one is called MAX and other is called MIN.Both the players fight it as the opponent player gets the minimum benefit while they get the maximum benefit.Both Players of the game are opponent of each other, where MAX will select the maximized value and MIN will select the minimized value.The minimax algorithm performs a depth-first search algorithm for the exploration of the complete game tree.The minimax algorithm proceeds all the way down to the terminal node of the tree, then backtrack the tree as the recursion.


Let's have a look on Pseudo-code for MinMax Algorithm:

function minimax(node, depth, maximizingPlayer) is

if depth ==0 or node is a terminal node then

return static evaluation of node


if MaximizingPlayer then      // for Maximizer Player

maxEva= -infinity         

 for each child of node do

 eva= minimax(child, depth-1, false)

maxEva= max(maxEva,eva)        //gives Maximum of the values

return maxEva


else                         // for Minimizer player

 minEva= +infinity 

 for each child of node do

 eva= minimax(child, depth-1, true)

 minEva= min(minEva, eva)         //gives minimum of the values

 return minEva


Following are the properties of Mini-Max algorithm we have seen above:

1.Complete- Min-Max algorithm is Complete. It will definitely find a solution (if exist), in the finite search tree.
2.Optimal- Min-Max algorithm is optimal if both opponents are playing optimally.
3.Time complexity- As it performs DFS for the game-tree, so the time
4.complexity of Min-Max algorithm is O(bm), where b is branching factor of the game-tree, and m is the maximum depth of the tree.
5.Space Complexity- Space complexity of Mini-max algorithm is also similar to DFS which is O(bm).

                    I hope all of this discussion has helped you further understand the minimax algorithm, and perhaps how to dominate at a game of tic tac toe. If you have further questions or anything is confusing, leave some comments and I we'll try to improve the article.

Beginner's Project: Tic-Tac-Toe

                              Now as you all are known with the rules about how to play the game, let's design code based on these rules:

Secret Strategies to win Tic-tac-toe:

1)Tic-tac-toe is a very mindful game. You have to be aware of every move of your opponent and even figure out which move you will make next.
2)To beat your opponent, be it a person or a computer even, you need to plan out a strategy.
3)You first need to figure out how you can make those three X’s in a row and stop your opponent from winning as well.
4)Watch your opponent’s every move. For example, if they put two O’s in a row, then you MUST put an X in the next square to those consecutive O’s or you’ll lose.
5)In short, you must be very vigilant while making your moves. This is the only way you’ll never lose a game of tic-tac-toe. If you’ll not win then at least you will have a tie

                              Here’s a beginner project: Tic Tac Toe. The code below contains the solution needed to create a tic tac toe game.
Code:
#include <iostream>
using namespace std;
char square[10] = {‘o’,’1′,’2′,’3′,’4′,’5′,’6′,’7′,’8′,’9′};

int checkwin();
void board();

int main()
{
int player = 1,i,choice;
char mark;
do
{
board();
player=(player%2)?1:2;

cout << “Player ” << player << “, enter a number: “;
cin >> choice;

mark=(player == 1) ? ‘X’ : ‘O’;

if (choice == 1 && square[1] == ‘1’)
square[1] = mark;
else if (choice == 2 && square[2] == ‘2’)

square[2] = mark;
else if (choice == 3 && square[3] == ‘3’)

square[3] = mark;
else if (choice == 4 && square[4] == ‘4’)

square[4] = mark;
else if (choice == 5 && square[5] == ‘5’)
square[5] = mark;
else if (choice == 6 && square[6] == ‘6’)

square[6] = mark;
else if (choice == 7 && square[7] == ‘7’)

square[7] = mark;
else if (choice == 8 && square[8] == ‘8’)

square[8] = mark;
else if (choice == 9 && square[9] == ‘9’)

square[9] = mark;
else
{
cout<<“Invalid move “;

player–;
cin.ignore();
cin.get();
}
i=checkwin();

player++;
}while(i==-1);
board();
if(i==1)
cout<<“==>aPlayer “<<–player<<” win “;
else
cout<<“==>aGame draw”;

cin.ignore();
cin.get();
return 0;
}

/*******************************************************************
FUNCTION TO DRAW BOARD OF TIC TAC TOE WITH PLAYERS MARK
********************************************************************/

void board()
{
system(“cls”);
cout << “nntTic Tac Toenn”;

cout << “Player 1 (X) – Player 2 (O)” << endl << endl;
cout << endl;

cout << ” | | ” << endl;
cout << ” ” << square[1] << ” | ” << square[2] << ” | ” << square[3] << endl;

cout << “_____|_____|_____” << endl;
cout << ” | | ” << endl;

cout << ” ” << square[4] << ” | ” << square[5] << ” | ” << square[6] << endl;

cout << “_____|_____|_____” << endl;
cout << ” | | ” << endl;

cout << ” ” << square[7] << ” | ” << square[8] << ” | ” << square[9] << endl;

cout << ” | | ” << endl << endl;
}

let's look for different algorithms of implementation of this game in further blogs....
THANK YOU!!!

Techniques

The techniques for tic tac toe making can be:

1.C

2.CPP

3.Java

4.Python

5.With AI without AI

Before starting the game ...its crucial to know the steps like how it  is being played?.. basically, here are some rules ,then their is pseudo code , algorithm and then comes code.

so lets proceed then.....

How to play?
Now that we are aware of the game and its history , lets get to the rules and regulations considered while playing this game.

Now that we are aware of the game and its history, let’s get to the rules and regulations considered while playing this game.

You might already know to play tic-tac-toe since you think it’s a very easy and simple game, right? Well, that’s where  most people are wrong. If you really get your mind around the game, you will find out that it is not a simple as you thought it would be.

Let’s take a look at the rules for tic-tac-toe:

        The game is played on a 3 by 3 square grid.

        It’s a 2 player game.

        One player picks the ‘X’ mark and the other is ‘O’ mark.

        You only get one turn for one mark to put in empty squares.

        Whichever player gets 3 of their marks in a row, wins.

        The marks can be made diagonally, vertically or horizontally.

        When all of the 9 squares are filled up, the game is over.

        If neither of the two players is successful in having 3 marks in a row, the game ends in a tie.

Let's look further what more interesting comes!!!1!

More about Tic Tac Toe

                 Tic-tac-toe (also known as noughts and crosses or Xs and Os) is a paper and pencil game  for two players, X and O, who take turns marking the spaces in a 3×3 grid. The player who succeeds in placing three of their marks in a horizontal, vertical, or diagonal row wins the game.

             In order to solve Tic-Tac-Toe, we need to go deeper than just to think about it as a game where two players place X’s and O’s on the board. Formally speaking, Tic-Tac-Toe is a zero-sum and perfect information game. It means that each participant’s gain is equal to the other participants’ losses and we know everything about the current game state.

History behind tic-tac-toe

Around the 1st century B.C, this game was first introduced during the Roman Empire. It didn’t go by its current name but rather was called “three pebbles at a time”. If you search over the internet, you will even find images of the game’s grid which were found drawn on many Roman ruins. Not only Roman but Egyptian ruins also bear witness to such chalking.

The game was first called ‘tic-tac-toe’ in 1884 but was considered as a children’s game.

Secret Strategies to win Tic-tac-toe

Tic-tac-toe is a very mindful game. You have to be aware of every move of your opponent and even figure out which move you will make next.

To beat your opponent, be it a person or a computer even, you need to plan out a strategy.

You first need to figure out how you can make those three X’s in a row and stop your opponent from winning as well.

Watch your opponent’s every move. For example, if they put two O’s in a row, then you MUST put an X in the next square to those consecutive O’s or you’ll lose.

In short, you must be very vigilant while making your moves. This is the only way you’ll never lose a game of tic-tac-toe. If you’ll not win then at least you will have a tie. 

GOOD LUCK