CODEWITHSUNDEEP
c++algorithmminimax
adn.911
adn.911

Reputation: 1314

Implementing minimax algorithm for tic-tac-toe

I am trying to implement the minimax algorithm for a tic-tac-toe game where both the players are human and each time computer suggests an optimal move using the minimax algorithm. But it is not giving the right suggestion every time. For example: it does not gives the right suggestion for the following scenario: player X : 1 player O : 2 player X : 5. Here is my code: 

#include <stdio.h>
#include <algorithm>  
#include <string>
using namespace std;

#define inf 1<<20
int posmax, posmin;
char board[15];

void print_board()
{
    int i;
    for (i = 1; i <= 9; i++)
    {   
        printf("%c ",board[i]);
        if (i % 3 == 0)
            printf("\n");
    }
    printf("\n");
}

int check_win(char board[])
{
    if ((board[1] == 'X' && board[2] == 'X' && board[3] == 'X') ||
        (board[4] == 'X' && board[5] == 'X' && board[6] == 'X') ||
        (board[7] == 'X' && board[8] == 'X' && board[9] == 'X') ||
        (board[1] == 'X' && board[4] == 'X' && board[7] == 'X') ||
        (board[2] == 'X' && board[5] == 'X' && board[8] == 'X') ||
        (board[3] == 'X' && board[6] == 'X' && board[9] == 'X') ||
        (board[1] == 'X' && board[5] == 'X' && board[9] == 'X') ||
        (board[3] == 'X' && board[5] == 'X' && board[7] == 'X'))
    {
        return 1;
    }
    else if((board[1] == 'O' && board[2] == 'O' && board[3] == 'O') ||
            (board[4] == 'O' && board[5] == 'O' && board[6] == 'O') ||
            (board[7] == 'O' && board[8] == 'O' && board[9] == 'O') ||
            (board[1] == 'O' && board[4] == 'O' && board[7] == 'O') ||
            (board[2] == 'O' && board[5] == 'O' && board[8] == 'O') ||
            (board[3] == 'O' && board[6] == 'O' && board[9] == 'O') ||
            (board[1] == 'O' && board[5] == 'O' && board[9] == 'O') ||
            (board[3] == 'O' && board[5] == 'O' && board[7] == 'O'))
    {
        return -1;
    }
    else return 0;
}

int check_draw(char board[])
{
    if ((check_win(board) == 0) && (board[1] != '_') && (board[2] != '_') &&
        (board[3] != '_') && (board[4] != '_') && (board[5] != '_') &&
        (board[6] != '_') && (board[7] != '_') && (board[8] != '_') &&
        (board[9] != '_'))
    {
        return 1;
    }
    else return 0;
}

int minimax(int player, char board[], int n)
{
    int i, res, j;

    int max = -inf;
    int min = inf;

    int chk = check_win(board);
    if (chk == 1)
        return 1;
    else if (chk == (-1))
        return -1;
    else if (chk = check_draw(board))
        return 0;

    for (i = 1; i <= 9; i++)
    {
        if(board[i] == '_')
        {
            if(player == 2)  
            {
                board[i] = 'O';
                res = minimax(1, board, n + 1);

                board[i] = '_';
                if(res < min)
                {
                    min = res;
                    if (n == 0)
                        posmin = i;
                }
            }
            else if (player == 1)
            {
                board[i] = 'X';
                res = minimax(2, board, n + 1);
                board[i] = '_';
                if (res > max)
                {
                    max = res;
                    if (n == 0)
                        posmax = i;
                }
            }
        }
    }

    if (player == 1)
        return max;
    else return min;    
}


// 1 is X, 2 is O
int main()
{
    int i, j, input, opt;

    for(i = 1; i <= 9; i++)
        board[i] = '_';

    printf("Board:\n");
    print_board();

    for(i = 1; i <= 9; i++)
    {
        if (i % 2 == 0)
            printf("Player O give input:\n");
        else 
            printf("Player X give input:\n");

        scanf("%d", &input);
        if (i % 2 != 0)
            board[input] = 'X';
        else
            board[input] = 'O';

        printf("Board:\n");
        print_board();

        int chk = check_win(board);
        if (chk == 1)
        {
            printf("Player X wins!\n");
            break;
        }
        else if (chk == -1)
        {
            printf("Player O wins!\n");
            break;
        }
        else if ((chk == 0) && (i != 9))
        {
            posmax = -1;
            posmin = -1;
            if(i % 2 == 0)
            {
                opt = minimax(1, board, 0);
                printf("Optimal move for player X is %d\n", posmax);
            }
            else 
            {
            opt = minimax(2, board, 0);
            printf("Optimal move for player O is %d\n", posmin);
            }
        }
        else 
            printf("The game is tied!\n");
    }
    return 0;
}

Upvotes: 1

Views: 19118

Answers (4)

Christian Ammer
Christian Ammer

Reputation: 7542

In my opinion your program does not give wrong suggestions. Minimax calculates the score of a move if both players are playing optimal. The score in your case can be +1, -1 and 0, therefore if a game e.g. is inevitable lost, it does not make a difference at which depth it is lost. Given the following gamestate

X O _
X _ _
_ _ _

and optimal play of player X, it does not matter where player O makes his move (he loses in either case):

  • After O plays 7, X plays 5, O plays 6, X plays 8 --> X wins
  • After O plays 3, X plays 7 --> X wins

Player X wins. Move 7 gives the same score as move 3 and all other playable moves. If you like to make your algorithm give the move suggestion 7 for this example, you have to include the game-depth into your evaluation function. You can do this by changing the return values of your function to following:

int chk = check_win(board);
if (chk == 1)
    return (10 - n);
else if (chk == (-1))
    return -(10 - n);
else if (chk = check_draw(board))
    return 0;

Upvotes: 2

lacungus
lacungus

Reputation: 77

Replace printf("Optimal move for player X is %d %d\n", posmax); with printf("Optimal move for player X is %d\n", posmax);

and

printf("Optimal move for player O is %d %d\n", posmin); with printf("Optimal move for player O is %d\n", posmin);

Everything else seems to be correct, though it doesn't always print the fastest victory (if victory exists).

Upvotes: 0

maniek
maniek

Reputation: 7307

This (although inefficiently coded) is, I think ,correct. If not, please give a move sequence where You think the program is wrong.

It is not giving the shortest move sequence, which might be what You are after. then, You should refactor it to return the move which gives the shortest move sequence (if winning) or the longest one(when losing).

Upvotes: 0

Dennis Meng
Dennis Meng

Reputation: 5187

Unless I'm reading main() wrong, you're only letting 8 of the squares be filled before declaring it a draw. It's probably not the bug you're looking for, but it's a start.

Upvotes: 0

Related Questions