Алгоритм минимакса не работает должным образом (реализован на C)

У меня возникла проблема с реализацией минимаксного алгоритма в 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;
    } }

Добро пожаловать! Пожалуйста, опубликуйте код как полный, компилируемый Минимально воспроизводимый пример. Вы разместили фрагменты, которые читатели должны будут собрать воедино.

Weather Vane 08.04.2023 21:12
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
1
75
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Проблема в том, что вы пробовали какие-то альтернативы; здесь:

    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;

Другие вопросы по теме