I was building a Connect 4 game in C, but when I try to add alpha-beta pruning to the minimax algorithm it simply doesn’t work, can anyone explain why? This is a part of my code:
void bestMove(int totalMoves) { // AI's turn
int score, move;
float bestScore = -INFINITY;
depth = 5+totalMoves*0.15;
for(int c = 0; c < COLUMNS; c++) {
for(int r = 0; r < ROWS; r++) {
if(board[r][c] == 0 && board[r+1][c] != 0 || board[r][c] == 0 && r == ROWS - 1) { // Is the spot available
board[r][c] = AI_PLAYER;
score = minimax(depth, false);
board[r][c] = 0;
if(score > bestScore) {
bestScore = score;
engineEvaluation = bestScore;
move = c;
}
}
}
}
uptadeBoard(AI_PLAYER, move);
}
int minimax(int depth, bool isMaximazing) { // Minimax algorithm implementation
int scores[3] = {0, -1000000, 1000000}, result, score;
float bestScore;
nodes++;
result = checkWinner();
if(result != 3) {
return scores[result];
}
if(isMaximazing) {
bestScore = -INFINITY;
for(int c = 0; c < COLUMNS; c++) {
for(int r = 0; r < ROWS; r++) {
if(board[r][c] == 0 && board[r+1][c] != 0 || board[r][c] == 0 && r == ROWS - 1) { // Is the spot available
board[r][c] = AI_PLAYER;
if(depth > 0) {
score = minimax(depth-1, false);
} else {
score = evaluation();
}
board[r][c] = 0;
bestScore = max(score, bestScore);
alpha = bestScore;
if(alpha >= beta) {
break;
}
}
}
}
return bestScore;
} else {
bestScore = INFINITY;
for(int c = 0; c < COLUMNS; c++) {
for(int r = 0; r < ROWS; r++) {
if(board[r][c] == 0 && board[r+1][c] != 0 || board[r][c] == 0 && r == ROWS - 1) { // Is the spot available
board[r][c] = HUMAN_PLAYER;
if(depth > 0) {
score = minimax(depth-1, true);
} else {
score = evaluation();
}
board[r][c] = 0;
bestScore = min(score, bestScore);
beta = bestScore;
if(alpha > beta) {
break;
}
}
}
}
return bestScore;
}
}
For some reason my program just ignore the alpha-beta implementation, if anyone want the full code it’s here: https://github.com/MatheuSs-GIT/Connect-4-Game-in-C/tree/main, thanks!
New contributor
Matheus Santos da Silva is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.