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.