У меня возникла проблема с реализацией минимаксного алгоритма в C для игры в крестики-нолики, вот код для функции minimax()
:
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;
}
Функция, которая вызывает его и фактически делает ход на доске:
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;
}
а также структуру MOVES и функции checkWnr()
, emptyCells()
, использованные выше:
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;
}
В основном алгоритм работает по назначению только при соблюдении следующего условия (для возврата -1 при убытке):
else if (var == 'O' && checkWnr(board, oppVar)) return -1;
если я, например, удалю условие var == 'O'
или добавлю другое, аналогичное для «X», например:
else if (var == 'X' && checkWnr(board, oppVar)) return -1;
все время, ОСТАВЛЯЯ другой на месте, программа по-прежнему будет размещать значения на доске слева направо, не обращая внимания на полученные баллы.
Я понятия не имею, почему это происходит, любая помощь будет оценена, спасибо заранее!
Компилируемый код:
#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;
} }
Проблема в том, что вы пробовали какие-то альтернативы; здесь:
if (checkWnr(board, var))
return 1;
else if (var == 'O' && checkWnr(board, oppVar))
return -1;
Условие checkWnr(board, var)
неверно, потому что var
— это игрок, чья очередь в минимаксном поиске. Таким образом, если игра была выиграна, она должна быть выиграна противником на предыдущем ходу.
Во-вторых, когда oppVar
выиграл, вам нужно проверить, является ли текущий игрок максимизирующим игроком или нет. Если максимизируете, то верните -1, иначе 1. Таким образом вы указываете, что это плохая ситуация (противник выиграл).
Поэтому измените этот блок кода на этот:
if (checkWnr(board, oppVar))
return isMax ? -1 : 1;
Добро пожаловать! Пожалуйста, опубликуйте код как полный, компилируемый Минимально воспроизводимый пример. Вы разместили фрагменты, которые читатели должны будут собрать воедино.