I've been having an issue implementing the minimax algorithm in C, for a tic-tac-toe game, here is the code for the minimax() function:
int minimax(char(*board)[3], int isMax, char var)
{
int score;
char oppVar;
int maxScore = -1000;
int minScore = 1000;
if (var == 'X')
oppVar = 'O';
else
oppVar = 'X';
if (checkWnr(board, var))
return 1;
else if (var == 'O' && checkWnr(board, oppVar)) //the condition without which the program doesn't run properly
return -1; //details lower in the post
else if (!emptyCells(board))
return 0;
if(isMax)
{
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (board[i][j] == ' ')
{
board[i][j] = var;
score = minimax(board, 0, oppVar);
maxScore = max(maxScore, score);
board[i][j] = ' ';
}
return maxScore;
}
else
{
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (board[i][j] == ' ')
{
board[i][j] = var;
score = minimax(board, 1, oppVar);
minScore = min(minScore, score);
board[i][j] = ' ';
}
return minScore;
}
The function that calls it and actually makes the move on the board:
void bestMove(int dum1, int dum2, char(*board)[3], char var)
{
int score;
MOVES move;
move.grade = -1000;
char oppVar;
if (var == 'X')
oppVar = 'O';
else
oppVar = 'X';
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (board[i][j] == ' ')
{
board[i][j] = var;
score = minimax(board, 0, oppVar);
if (score > move.grade)
{
move.grade = score;
move.line = i;
move.column = j;
}
board[i][j] = ' ';
}
board[move.line][move.column] = var;
}
as well as the MOVES struct and checkWnr(), emptyCells() functions used above:
typedef struct {
int line;
int column;
int grade;
}MOVES;
int checkWnr(char(*board)[3], char var)
{
if (board[0][0] == var && board[1][1] == var && board[2][2] == var)
return 1;
else if (board[0][2] == var && board[1][1] == var && board[2][0] == var)
return 1;
for (int i = 0; i < 3; i++)
if (board[i][0] == var && board[i][1] == var && board[i][2] == var)
return 1;
else if (board[0][i] == var && board[1][i] == var && board[2][i] == var)
return 1;
return 0;
}
int emptyCells(char(*board)[3])
{
int nr = 0;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (board[i][j] == ' ')
nr++;
return nr;
}
Basically the algorithm works as intended only when the following condition is met, (to return -1, for a loss):
else if (var == 'O' && checkWnr(board, oppVar)) return -1;
if I, for example, remove the var == 'O' condition or add another one, similar for 'X', like:
else if (var == 'X' && checkWnr(board, oppVar)) return -1;
all while KEEPING the other one in place, the program will still start placing values on the board from left to right, disregarding the scores obtained.
I have no idea why this is happening, any help would be appreciated, thanks in advance!
Compilable code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <windows.h>
#define PLAYR 1
#define COMPR 2
typedef struct {
int line;
int column;
int grade; }MOVES;
void clearBoard(char(*board)[3]); void showBoard(char(*board)[3]); int valid(int line, int col, char(*board)[3]); void usrMove(int line, int col, char(*board)[3], char var); int checkWnr(char(*board)[3], char var); int winner(char(*board)[3], char p1var, char p2var); int emptyCells(char(*board)[3]); void getInput(int* line, int* col, char(*board)[3]); void bestMove(int dum1, int dum2, char(*board)[3], char var); int minimax(char(*board)[3], int isMax, char var);
int main() {
char board[3][3], input[10], p1var, p2var;
int line, col;
while (1)
{
do
{
printf("\n(P1) X or O? ");
fseek(stdin, 0, SEEK_END);
fgets(input, 10, stdin);
input[strcspn(input, "\n")] = 0;
input[0] = toupper(input[0]);
} while (strcmp(input, "X") && strcmp(input, "O"));
if (!strcmp(input, "X"))
{
p1var = 'X';
p2var = 'O';
}
else
{
p1var = 'O';
p2var = 'X';
}
clearBoard(board);
system("cls");
while (!winner(board, p1var, p2var) && emptyCells(board))
{
showBoard(board);
getInput(&line, &col, board);
line--; col--;
usrMove(line, col, board, p1var);
if (!emptyCells(board) || winner(board, p1var, p2var))
{
system("cls");
break;
}
bestMove(line, col, board, p2var);
system("cls");
}
showBoard(board);
if (winner(board, p1var, p2var) == PLAYR)
printf("\nYou won!");
else if (winner(board, p1var, p2var) == COMPR)
printf("\nYou lost!");
else if (!emptyCells(board))
printf("\nTie!");
}
return 0; }
int valid(int line, int col, char(*board)[3]) {
if (line > 3 || line < 1 || col > 3 || col < 1 || board[line - 1][col - 1] != ' ')
return 0;
return 1; }
void getInput(int* line, int* col, char(*board)[3]) {
do
{
printf("\nEnter line, column: ");
fseek(stdin, 0, SEEK_END);
scanf_s("%d %d", line, col);
if (!valid((*line), (*col), board))
{
printf("\nInvalid input, please try again!");
(*line) = -1;
(*col) = -1;
}
} while (!valid((*line), (*col), board)); }
int winner(char(*board)[3], char p1var, char p2var) {
if (checkWnr(board, p1var))
return PLAYR;
else if (checkWnr(board, p2var))
return COMPR;
return 0; }
void usrMove(int line, int col, char(*board)[3], char var) {
board[line][col] = var;
return 0; }
void clearBoard(char(*board)[3]) {
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
*(*(board + i) + j) = ' '; }
void showBoard(char(*board)[3]) {
printf("\n|---|---|---|\n");
printf("| %c | %c | %c |\n", board[0][0], board[0][1], board[0][2]);
printf("|---|---|---|\n");
printf("| %c | %c | %c |\n", board[1][0], board[1][1], board[1][2]);
printf("|---|---|---|\n");
printf("| %c | %c | %c |\n", board[2][0], board[2][1], board[2][2]);
printf("|---|---|---|\n"); }
int checkWnr(char(*board)[3], char var) {
if (board[0][0] == var && board[1][1] == var && board[2][2] == var)
return 1;
else if (board[0][2] == var && board[1][1] == var && board[2][0] == var)
return 1;
for (int i = 0; i < 3; i++)
if (board[i][0] == var && board[i][1] == var && board[i][2] == var)
return 1;
else if (board[0][i] == var && board[1][i] == var && board[2][i] == var)
return 1;
return 0; }
int emptyCells(char(*board)[3]) {
int nr = 0;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (board[i][j] == ' ')
nr++;
return nr; }
void bestMove(int dum1, int dum2, char(*board)[3], char var) {
int score;
MOVES move;
move.grade = -1000;
char oppVar;
if (var == 'X')
oppVar = 'O';
else
oppVar = 'X';
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (board[i][j] == ' ')
{
board[i][j] = var;
score = minimax(board, 0, oppVar);
if (score > move.grade)
{
move.grade = score;
move.line = i;
move.column = j;
}
board[i][j] = ' ';
}
board[move.line][move.column] = var; }
int minimax(char(*board)[3], int isMax, char var) {
int score;
char oppVar;
int maxScore = -1000;
int minScore = 1000;
if (var == 'X')
oppVar = 'O';
else
oppVar = 'X';
if (checkWnr(board, var))
return 1;
else if (var == 'O' && checkWnr(board, oppVar))
return -1;
else if (!emptyCells(board))
return 0;
if (isMax)
{
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (board[i][j] == ' ')
{
board[i][j] = var;
score = minimax(board, 0, oppVar);
maxScore = max(maxScore, score);
board[i][j] = ' ';
}
return maxScore;
}
else
{
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (board[i][j] == ' ')
{
board[i][j] = var;
score = minimax(board, 1, oppVar);
minScore = min(minScore, score);
board[i][j] = ' ';
}
return minScore;
} }
The problem is where you have tried some alternatives; here:
if (checkWnr(board, var))
return 1;
else if (var == 'O' && checkWnr(board, oppVar))
return -1;
The condition checkWnr(board, var) is wrong, because var is the player who's turn it is in the minimax search. So if the game was won, it must have been won by the opponent in their previous move.
Secondly, when oppVar has won, you need to check whether the current player is the maximising player or not. If maximising, then return -1, else 1. This way you indicate that this is a bad situation (the opponent won).
So change that block of code to this:
if (checkWnr(board, oppVar))
return isMax ? -1 : 1;