Thread: Minimax algorithm not behaving properly

  1. #1
    Registered User
    Join Date
    Jul 2022
    Posts
    2

    Post Minimax algorithm not behaving properly

    I have been learning to program for a couple months now and decided to take a shot at tic-tac-toe and an AI to accompany it. From what I've seen elsewhere, everything in the ai() and minimax() functions should be working properly, however I have noted that the AI tends to miss wins and assume it is a draw in won positions.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    char board[3][3] = {{' ',' ',' '},{' ',' ',' '},{' ',' ',' '}};
    int drawBoard();
    int turn();
    int turns();
    int winner();
    int ai(char current[3][3]);
    int minimax(char test[3][3], int player);
    
    int main()
    {
        int players;
        
        printf("How many players? (1 - 2): ");
        scanf("%d", &players);
        
        if(players == 1)
        {
            do
            {
                 system("clear");
                drawBoard();
                turn();
                if(winner(board) != 0 && winner(board) != 1 && winner(board) != -1)
                {
                ai(board);
                }
            }
            while(winner(board) != 1 && winner(board) != -1 && winner(board) != 0);
        }
        else if(players == 2)
        {
            do
            {
                system("clear");
                drawBoard();
                turns();
            }
            while(winner(board) != 1 && winner(board) != -1 && winner(board) != 0);
        }
        
        system("clear");
        drawBoard();
        if(winner(board) != 0)
        {
        printf("Game Over!\nWinner is player %d\n", (winner(board)+3)/2);
        }
        else
        {
        printf("It is a draw!\n");
        }
        return 0;
    }
    
    int drawBoard()
    {
        for (int i = 1; i < 12; i++)
        {
            if(i % 4 == 0)
            {
                printf("---------------------\n");
            }
            else if(i % 2 == 0)
            {
                printf("  %c   |   %c   |   %c  \n", board[(i-2)/4][0], board [(i-2)/4][1],                  
                board[(i-2)/4][2]);
            }
            else
            {
                printf("      |       |      \n");
            }
        }
    }
    
    int turn()
    {
        int row, col;
        
        printf("Select a row: ");
        scanf("%d", &row);
        printf("Select a column: ");
        scanf("%d", &col);
    
        if(board[row-1][col-1] != ' ')
        {
            printf("Please try again!\n");
            turn();
            return 0;
        }
    
        board[row-1][col-1] = 'X';
    }
    
    int turns()
    {
        static int player = 1;
        int row, col;
        
        printf("Player %d select a row: ", player);
        scanf("%d", &row);
        printf("Player %d select a column: ", player);
        scanf("%d", &col);
    
        if(board[row-1][col-1] != ' ')
        {
            printf("Please try again!\n");
            turns();
            return 0;
        }
    
        if(player == 1)
        {
            board[row-1][col-1] = 'X';
            player = 2;
        }
        else
        {
            board[row-1][col-1] = 'O';
            player = 1;
        }
    }
    
    signed int winner(char check[3][3])
    {
        int i, j, temp, total = 0;
    
        for(i = 0; i < 3; i++)
        {
            
            if(check[i][0] == check[i][1] && check[i][0] == check[i][2] && check[i][0] != ' ')
            {
                temp = (int)check[i][0];
                if(temp == 88)
                {
                    return -1;
                }
                else
                {
                    return 1;
                }
            }
            if(check[0][i] == check[1][i] && check[0][i] == check[2][i] && check[0][i] != ' ')
            {
                temp = (int)check[0][i];
                if(temp == 88)
                {
                    return -1;
                }
                else
                {
                    return 1;
                }
            }
        }
        if(check[0][0] == check[1][1] && check[0][0] == check[2][2] && check[0][0] != ' ')
        {
            temp = (int)check[0][0];
            if(temp == 88)
            {
                return -1;
            }
            else
            {
                return 1;
            }
        }
        if(check[2][0] == check[1][1] && check[2][0] == check[0][2] && check[2][0] != ' ')
        {
            temp = (int)check[2][0];
            if(temp == 88)
            {
                return -1;
            }
            else
            {
                return 1;
            }
        }
        
        for(i = 0; i < 3; i++){
        for(j = 0; j < 3; j++){
        temp = (int)check[i][j];
        if(check[i][j] != 32)
        {
            total += 1;
        }}}
        if(total == 9)
        {
        return 0;
        }
    }
    
    int ai(char current[3][3])
    {
        signed int score, bestScore = -1000;
        int bestMove[2];
    
        for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            if((int)current[i][j] == 32)
            {
                current[i][j] = 'O';
                score = minimax(current, 1);
                current[i][j] = ' ';
                if(score > bestScore)
                {
                    bestScore = score;
                    bestMove[0] = i;
                    bestMove[1] = j;
                }
            }
        }
        }
        board[bestMove[0]][bestMove[1]] = 'O';
    }
    
    int minimax(char test[3][3], int player)
    {
        int i, j, score;
        
        if(winner(test) == 0 || winner(test) == 1 || winner(test) == -1)
        {
            return winner(test);
        }
        if(player == 2)
        {
            signed int bestScore = -1000;
            for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                if((int)test[i][j] == 32)
                {
                    test[i][j] = 'O';
                    drawBoard();
                    score = minimax(test, 1);
                    test[i][j] = ' ';
                
                    if(score > bestScore)
                    {
                        bestScore = score;
                    }
                }
            }}
            return bestScore;
        }
        else
        {
            signed int bestScore = 1000;
            for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                if((int)test[i][j] == 32)
                {
                    test[i][j] = 'X';
                    drawBoard();
                    score = minimax(test, 2);
                    test[i][j] = ' ';
                
                    if(score < bestScore)
                    {
                        bestScore = score;
                    }
                }
            }}
            return bestScore;
        }
    }
    I have looked through this so many times and can not for the life of me find an error. Thanks in advance!

  2. #2
    Registered User
    Join Date
    Jul 2022
    Posts
    2
    It is worth noting that the algorithm will never lose. When X is placed in the centre of the board, it will always pick a corner (whether or not that is thanks to the minimax is debatable), and it will always pick the centre if any other move is played. It just seems to ignore wins for some reason...

  3. #3
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    Code:
    int winner();
    1. Fix the prototype for winner.
    2. Stop using so many magic numbers

    Magic number (programming) - Wikipedia

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  4. #4
    Registered User
    Join Date
    Dec 2017
    Posts
    1,633
    Your winner function doesn't have a return value for NOTHING, i.e., not a win for X or O and not a draw. In that case it just "falls off the end" of the function and returns an arbitrary value. Try:
    Code:
    int winner(char check[3][3])
    {
        for (int i = 0; i < 3; i++)
        {
            if (check[i][0] == check[i][1] &&
                check[i][0] == check[i][2] &&
                check[i][0] != ' ')
            {
                return check[i][0] == 'X' ? -1 : 1;
            }
            if (check[0][i] == check[1][i] &&
                check[0][i] == check[2][i] &&
                check[0][i] != ' ')
            {
                return check[0][i] == 'X' ? -1 : 1;
            }
        }
     
        if (check[0][0] == check[1][1] &&
            check[0][0] == check[2][2] &&
            check[0][0] != ' ')
        {
            return check[0][0] == 'X' ? -1 : 1;
        }
     
        if (check[2][0] == check[1][1] &&
            check[2][0] == check[0][2] &&
            check[2][0] != ' ')
        {
            return check[2][0] == 'X' ? -1 : 1;
        }
     
        int total = 0;
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                if (check[i][j] != ' ')
                    ++total;
     
        return total == 9 ? : 0 : 2;
    }
    A little inaccuracy saves tons of explanation. - H.H. Munro

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need assistance with the minimax tree algorithm implementation.
    By KonoDioDa22 in forum C++ Programming
    Replies: 4
    Last Post: 10-28-2017, 05:46 PM
  2. Function not behaving properly
    By Moksha in forum C Programming
    Replies: 9
    Last Post: 01-19-2017, 01:50 PM
  3. Attempt to implement the minimax algorithm
    By gavra in forum C++ Programming
    Replies: 2
    Last Post: 08-17-2011, 11:27 PM
  4. Tic Tac Toe Minimax Algorithm Problem
    By hello.world in forum Game Programming
    Replies: 3
    Last Post: 10-24-2010, 05:47 AM
  5. while loop not behaving properly.
    By Dreamerv3 in forum C++ Programming
    Replies: 20
    Last Post: 01-08-2002, 05:51 PM

Tags for this Thread