Thread: 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 (:

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?

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.