implementing negamax algorithm with alpha beta pruning for connect four in C

114 Views Asked by At

I am currently writing a connect four game in C, and I have already made a working minimax algorithm to find the best move (with a depth of only 12). I recently remembered about negamax, and how it might be faster to run, but when I tried to implement it, the move found was never good.

So far I have tried looking around on the internet and everytime I rewrite the code, I end up rewriting the same function as before, but I really don't understand why it is wrong... Everything apart for the negamax function works, as it worked perfectly using minimax.

It's also important to note that PLAYER_X is 0 and PLAYER_O is 1. The getScore(PLAYER) function simply returns a heuristic score for a player.

Here is the minimax function that works fine:

int minimax(int depth, int alpha, int beta, int maximizingPlayer) {

    //Only the maximizing player can possibly win, because he played last
    if(isWin(maximizingPlayer))
    {
        return (1-maximizingPlayer)*10000 - maximizingPlayer*10000;
    }

    if(isDraw())
    {
        return 0;
    }
    if (depth == 0)
    {
        return getScore(maximizingPlayer) - getScore(1-maximizingPlayer);
    }

    int bestValue = 999999;
    if(maximizingPlayer)
    {
        bestValue = -999999;
    }

    for (int col = 0; col < WIDTH; col++)
    {
        if (isValidMove(col))
        {

            makeMove(col, 1-maximizingPlayer);
            //1-maximizingPlayer inverts who the maximizingPlayer is
            int eval = minimax(depth - 1, alpha, beta, 1-maximizingPlayer);
            undoMove(col, 1-maximizingPlayer);

            if (maximizingPlayer)
            {
                bestValue = (eval > bestValue) ? eval : bestValue;
                alpha = (alpha > eval) ? alpha : eval;
            }
            else
            {
                bestValue = (eval < bestValue) ? eval : bestValue;
                beta = (beta < eval) ? beta : eval;
            }
            if (alpha >= beta)
            { //Pruning
                break;
            }
        }
    }

    return bestValue;
}

Here is the incorrect negamax function:

int negamax(int depth, int alpha, int beta, int maximizingPlayer) {

    if(isWin(maximizingPlayer))
    {
        return 10000;
    }
    if(isWin(1-maximizingPlayer))
    {
        return -10000;
    }

    if(isDraw())
    {
        return 0;
    }
    if (depth == 0)
    {
        return getScore(maximizingPlayer) - getScore(1-maximizingPlayer);
    }

    int bestScore = -999999;

    for (int col = 0; col < WIDTH; col++)
    {
        if (isValidMove(col))
        {

            makeMove(col, maximizingPlayer);
            int score = -negamax(depth - 1, -beta, -alpha, 1 - maximizingPlayer);
            undoMove(col, maximizingPlayer);

            if(score > bestScore)
            {
                bestScore = score;
            }
            
            if(score > alpha)
            {
                alpha = score;
            }
            //Alpha beta pruning
            if (alpha >= beta)
            {
                break;
            }
        }
    }

    return bestScore;
}

I'm very new to algorithms such as negamax... so any help will be appreciated!

The full code is here

An example of it failing is to just play the following sequence: 3, 2, 4 and immediately win.

Another example is to simply play the column 3 four times in a row. It is never blocked, so the player immediately wins.

0

There are 0 best solutions below