Minimax Algorithm
Links which have explained minimax algo:
- Minimax Introduction
- Minimax: GeeksForGeeks
- How to make a unbeatable tic tac toe using Minimax algorithm: Medium
- Minimax Algorithm Video
- Minimax PDF Compiled by Manmeet Sir ;)
Additional Resources
- AlphaBeta Pruning PDF
- Minimax, and Alpha-Beta: MIT OpenCourseWare
- Alpha-Beta pruning: HackerEarth
- UCLA CS 161 Notes On Alpha-Beta pruning
- Northwestern Universitry Notes On Alpha-Beta pruning
- 2048 Game AI bot using Minimax and Alpha Beta
- Stick Picking game AI bot
Hackerrank problem of Tic Tac Toe. We strongly recommend you to make a Tic Tac Toe bot and submit it there to see how well it works. This will give you a strong idea of how to make an AI bot and will prepare you for developing high level bots.
To run our code and view the code of previous year’s problem statement you can clone the repo: Clash Of Pawns AI
PseudoCode for Minimax Without Depth
(score, move) maxTurn(game):
if game is in terminal state:
return (score(game), none)
max = (none, none)
foreach emptySpace in game:
game[emptySpace] = X
currentMove = minTurn(game)
if currentMove.score > max.score:
max = (currentMove.score, emptySpace)
game[emptySpace] = none // reverting change
return max
(score, move) minTurn(game):
if game is in terminal state:
return (score(game), none)
min = (none, none)
foreach emptySpace in game:
game[emptySpace] = O
currentMove = maxTurn(game)
if currentMove.score < min.score:
min = (currentMove.score, emptySpace)
game[emptySpace] = none // reverting change
return min
PseudoCode for Minimax Algorithm With Depth
(score, move) maxTurn(game, depth):
if game is in terminal state:
return (score(game, depth), none)
max = (none, none)
foreach emptySpace in game:
game[emptySpace] = X
currentMove = minTurn(game, depth + 1)
if currentMove.score > max.score:
max = (currentMove.score, emptySpace)
game[emptySpace] = none // reverting change
return max
(score, move) minTurn(game, depth):
if game is in terminal state:
return (score(game, depth), none)
min = (none, none)
foreach emptySpace in game:
game[emptySpace] = O
currentMove = maxTurn(game, depth + 1)
if currentMove.score < min.score:
min = (currentMove.score, emptySpace)
game[emptySpace] = none // reverting change
return min
int score(game, depth):
if X has won:
return 10 - depth
else if O has won:
return depth - 10
return 0
Code for Tic-Tac-Toe
wget this url for raw cpp file.
#include<bits/stdc++.h>
using namespace std;
struct chaal{
int row,column;
};
char b[4][4];
char player,comp; //player is you and comp is your bot
int evaluate(int depth) //This function calculates the score of board at given time
{
int i;
//Check if there are three consecutive O's or X's in rows
for(i=1;i<=3;i++)
{
if(b[i][1]==b[i][2]&&b[i][2]==b[i][3])
{
if(b[i][1]==comp)
{return 20-depth;}
else if(b[i][1]==player)
{return -20+depth;}
}
}
//Check if there are three consecutive O's or X's in Columns
for(i=1;i<=3;i++)
{
if(b[1][i]==b[2][i]&&b[2][i]==b[3][i])
{
if(b[1][i]==comp)
{return 20-depth;}
else if(b[1][i]==player)
{return -20+depth;}
}
}
//Check if there are three consecutive O's or X's in Diagonals
if(b[1][1]==b[2][2]&&b[2][2]==b[3][3])
{
if(b[1][1]==comp)
{return 20-depth;}
else if(b[1][1]==player)
{return -20+depth;}
}
if(b[1][3]==b[2][2]&&b[2][2]==b[3][1])
{
if(b[1][3]==comp)
{return 20-depth;}
else if(b[1][3]==player)
{return -20+depth;}
}
return 0;
}
//Checks if there is any move left on the board
bool moveleft()
{
int i,j;
for(i=1;i<=3;i++)
for(j=1;j<=3;j++)
if(b[i][j]=='_')
return true;
return false;
}
int minimax(int depth,bool ismaxturn)
{
int i,j,val;
int score=evaluate(depth);
if(score==20-depth)
return score;
if(score==-20+depth)
return score;
if(moveleft()==false)
return 0;
if(ismaxturn)
{
int best=-10000;
// Iterate over all 9 positions
for(i=1;i<=3;i++)
{
for(j=1;j<=3;j++)
{
if(b[i][j]=='_') //If the position is blank
{
b[i][j]=comp;
best=max(minimax(depth+1,!ismaxturn),best); //Updates the best value
b[i][j]='_';
}
if(alpha>beta) return best;
}
}
return best;
}
else
{
int best=10000;
// Iterate over all 9 positions
for(i=1;i<=3;i++)
{
for(j=1;j<=3;j++)
{
if(b[i][j]=='_') //If the position is blank
{
b[i][j]=player; //set step
best=min(minimax(depth+1,!ismaxturn),best); //Updates the best value
b[i][j]='_'; //Unset step...changes board back to its original form
}
}
}
return best;
}
}
//This function returns the best possible move to the main function
chaal findbestmove(int depth,bool ismaxturn)
{
int i,j,val;
struct chaal bestmove;
//Initialization steps
int bestval=-10000;
bestmove.row=-1;
bestmove.column=-1;
for(i=1;i<=3;i++)
{
for(j=1;j<=3;j++)
{
if(b[i][j]=='_')
{
b[i][j]=comp;
val=minimax(depth,!ismaxturn);
// If we found a better move ,just update bestmove with that move
if(val>bestval)
{
bestval=val;
bestmove.row=i;
bestmove.column=j;
}
b[i][j]='_';
}
}
}
return bestmove;
}
void print()
{
printf("\n\n");
printf("\t\t\t %c | %c | %c \n", b[1][1],b[1][2], b[1][3]);
printf("\t\t\t--------------\n");
printf("\t\t\t %c | %c | %c \n", b[2][1],b[2][2], b[2][3]);
printf("\t\t\t--------------\n");
printf("\t\t\t %c | %c | %c \n\n", b[3][1],b[3][2], b[3][3]);
}
int main()
{
int p,i,j,r,c;
const int INF=10000000;
struct chaal cur_move;
for(i=1;i<=3;i++)
for(j=1;j<=3;j++)
b[i][j]='_';
printf("WELCOME TO THE GAME OF TIC-TAC-TOE\n");
printf("PRESS 1 FOR TAKING O AND 2 FOR TAKING X\n");
scanf("%d",&p);
if(p==1)
{player='O';comp='X';}
else
{player='X';comp='O';}
printf("I GIVE YOU THE CHANCE OF MAKING FIRST TURN \n");
int depth=1;
while(moveleft())
{
printf("ENTER THE ROW AND COLUMN OF YOUR INPUT\n");
cin>>r>>c;
b[r][c]=player;
int x=evaluate(depth);
depth++;
print();
printf("\n\n");
if(x==-20+depth) // You have won the game
{
printf("CONGRATULATIONS\n");
return 0;
}
cur_move=findbestmove(depth,true);
b[cur_move.row][cur_move.column]=comp;
print();
x=evaluate(depth);
printf("\n\n");
if(x==20-depth)
{
printf("SORRY TO SAY BUT YOU NEED A LOT OF PRACTICE\n");
return 0;
}
}
printf("IT IS A DRAW\n");
return 0;
}