Skip to content

Latest commit

 

History

History

2018_08_15_CodeWarriors-1

Minimax Algorithm

Links which have explained minimax algo:

Additional Resources

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;
}

{% include disqus.html %}