Attempt to implement the minimax algorithm

This is a discussion on Attempt to implement the minimax algorithm within the C++ Programming forums, part of the General Programming Boards category; Hi, Sorry if it doesn't belong here (it's not really c++, not entirely c and I think it's not general ...

  1. #1
    Registered User gavra's Avatar
    Join Date
    Jun 2008
    Posts
    265

    Attempt to implement the minimax algorithm

    Hi,
    Sorry if it doesn't belong here (it's not really c++, not entirely c and I think it's not general enough for the general AI programming category). Appreciate moving it if needed.

    So I bumped into an attempt to implement the simple minimax algorithm in a Tic Tac Toe game:
    Code:
    bool CheckWin(char board[3][3], int i, int j, char player)
    {
        board[i][j] = player;
        if (CheckWin(board, i, j))
        {
           board[i][j] = 0;
           return true;
        }
        board[i][j] = 0;
        return false;
    }
    
    int CountWinAndLose(char board[3][3], char player)
    {
        int count = 0;
        for (int i=0;i<3;i++)
            for (int j=0;j<3;j++)
                if (board[i][j] == 0)
                {
                   if (CheckWin(board, i, j, player))
                      count++;
                   if (CheckWin(board, i, j, player == 'X' ? 'O' : 'X'))
                      count--;
                }
        return count;
    }
    
    int MiniMax(char board[3][3], char player, int depth, int max, int* maxij, int torns)
    {
        int count;
        
        if (depth == 0)
           return max;
        
        if (torns == 10)
           return 0;
        
        for (int k=0;k<3;k++)
            for (int l=0;l<3;l++)
                if (board[k][l] == 0)
                {
                    count = 0;
                    board[k][l] = player;
                    count = CountWinAndLose(board, player)
                          + MiniMax(board, player == 'X' ? 'O' : 'X', depth - 1, max, maxij, torns + 1);
                    if (count > max)
                    {
                       max = count;
                       *maxij = k * 3 + l;
                    }
                    board[k][l] = 0;
                }
        return max;
    }
    Yep it doesn't work.. any ideas?

    Thanks (:
    gavra.

  2. #2
    Registered User
    Join Date
    Sep 2009
    Posts
    48
    This code appears to be riddled with issues, but you haven't specified the exact problem you're having (do you get any compiler/linker errors?) and you haven't posted all the code, so there could be more issues elsewhere. For example, are there multiple overloaded CheckWin(...) functions, or is the call to CheckWin(char[3][3], int, int) within the CheckWin(char[3][3], int, int, char) erroneously missing the fourth argument?
    Last edited by Ushakal; 08-17-2011 at 03:08 PM.

  3. #3
    Registered User gavra's Avatar
    Join Date
    Jun 2008
    Posts
    265
    The problem is that it doesn't really calculate the best next move. It does the same moves all the time depending if the cell is available.
    No errors.
    I was asking more about the algorithm itself, but it seems that there might be something else. I will upload the relevant code you mentioned later.
    Thanks.

    Edit:
    The part where I use the calculated next move:
    Code:
                           {
                                result = MiniMax(board, 'X', 5, -1, &step, 0);
                                i = step / 3;
                                j = step % 3;
                                board[i][j] = 'X';
                           }
    Overload of CheckWin:
    Code:
    bool CheckWin(char board[3][3], int i, int j)
    {
         if (board[i][j] == board[i][(j + 1) % 3] && board[i][j] == board[i][(j + 2) % 3])
            return true;
         
         if (board[i][j] == board[(i + 1) % 3][j] && board[i][j] == board[(i + 2) % 3][j])
            return true;
         
         if (board[i][j] == board[0][0] && board[i][j] == board[1][1] && board[i][j] == board[2][2])
            return true;
            
         if (board[i][j] == board[0][2] && board[i][j] == board[1][1] && board[i][j] == board[2][0])
            return true;
            
         return false;
    }
    I think that is the relevant parts of code, the rest will only confuse you.
    Last edited by gavra; 08-18-2011 at 10:00 AM.
    gavra.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 1
    Last Post: 04-05-2011, 04:15 AM
  2. Tic Tac Toe Minimax Algorithm Problem
    By hello.world in forum Game Programming
    Replies: 3
    Last Post: 10-24-2010, 05:47 AM
  3. help me implement Dijkstra's Algorithm
    By iamnew in forum C++ Programming
    Replies: 4
    Last Post: 05-07-2010, 07:02 PM
  4. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 01:30 AM
  5. Replies: 9
    Last Post: 11-12-2007, 02:29 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21