Блог

Главная - Вопросы по программированию - 3×3 Крестики-нолики в C с использованием минимакса

3×3 Крестики-нолики в C с использованием минимакса

#c #tic-tac-toe #minimax

#c #крестики-нолики #минимакс

Вопрос:

Примечание # 1 — Есть аналогичный вопрос, но это на Python, и я не могу разобраться в этом на C.

Примечание # 2 — это человек против Игра с искусственным интеллектом, и я буду называть ИИ как «процессор». Символом процессора является «O», а человеческим символом всегда является «X».

Примечание # 3 — Я хочу спроектировать игру так, чтобы процессор никогда не проигрывал (ни в выигрыше, ни вничью).

Я хочу, чтобы пользователь пошел первым и выбрал любой из 9 квадратов. Итак, по сути, я хочу, чтобы процессор методом перебора вычислял результат каждого возможного хода игры и на основе этого присваивал «баллы» его возможным ходам (8 оставшихся вариантов).). Таким образом, он возвращается и знает, в какую сторону идти, чтобы не проиграть.

Также я хочу сделать это с использованием минимаксного алгоритма и на C.

Моя проблема — я думаю, что мне не хватает функции, которая на самом деле использует возвращаемые «оценки». Мне не нужен код, но я был бы признателен, если бы мог получить представление о том, как реализовать эту функцию. Также меня смущает функция nextMove(), я хочу, чтобы она проверяла, нет ли незаполненного поля, затем заполняла его буквой «О», а затем наступала очередь игрока. Но поскольку он будет вызван снова при рекурсии, он может работать некорректно. Есть какие-нибудь предложения?

Редактировать — Вознаграждение идет к ответу, который поможет мне понять, как реализовать эту игру, используя минимаксный алгоритм, как описано здесь: https://en.wikipedia.org/wiki/Minimax#Pseudocode

 #include <stdio.h>
#define FALSE 0
#define TRUE 1
#define NEGINF -10000
#define POSINF  10000


struct node { // each node is like a snapshot of the game at that point in time
    char board[9]; // the 3x3 square is implemented as an array of 9 chars 
    int value; // the value of that snapshot ( 1 if cpu wins, -1 if cpu loses, 0 for draw)
    int position; // 0 to 8 inclusive with 0 being [0][0] and 8 being [2][2] (row major fashion) and indicates position where the next 'X' or 'O' would be assigned
};



int max(int value, int returnedValue) {
    return value > returnedValue ?  value :  returnedValue;
}

int min(int value, int returnedValue) {
    return value < returnedValue ?  value :  returnedValue;
}

int someoneHasWon(struct node someNode) {
    if(someNode.board[0] == someNode.board[3] amp;amp; someNode.board[3] == someNode.board[6] amp;amp; someNode.board[6] == 'X')
        return TRUE;        
    
    if(someNode.board[0] == someNode.board[3] amp;amp; someNode.board[3] == someNode.board[6] amp;amp; someNode.board[6] == 'O')
        return TRUE;    
        //someNode.value = -1;
    if(someNode.board[1] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[7] amp;amp; someNode.board[7] == 'X')
        return TRUE;    
        //someNode.value = 1;//return 1;
    if(someNode.board[1] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[7] amp;amp; someNode.board[7] == 'O')
        return TRUE;    
        //someNode.value = -1;//return -1;
    if(someNode.board[2] == someNode.board[5] amp;amp; someNode.board[5] == someNode.board[8] amp;amp; someNode.board[8] == 'X')
        return TRUE;
            //someNode.value = 1;//return 1;
    if(someNode.board[2] == someNode.board[5] amp;amp; someNode.board[5] == someNode.board[8] amp;amp; someNode.board[8] == 'O')
        return TRUE;    
        //someNode.value = -1;//return -1;
    if(someNode.board[0] == someNode.board[1] amp;amp; someNode.board[1] == someNode.board[2] amp;amp; someNode.board[2] == 'X')
        return TRUE;    
        ////someNode.value = 1;//return 1;
    if(someNode.board[0] == someNode.board[1] amp;amp; someNode.board[1] == someNode.board[2] amp;amp; someNode.board[2] == 'O')
        return TRUE;    
        //someNode.value = -1;//return -1;
    if(someNode.board[3] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[5] amp;amp; someNode.board[5] == 'X')
        return TRUE;    
        //someNode.value = 1;//return 1;
    if(someNode.board[3] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[5] amp;amp; someNode.board[5] == 'O')
        return TRUE;    
        //someNode.value = -1;//return -1;
    if(someNode.board[6] == someNode.board[7] amp;amp; someNode.board[7] == someNode.board[8] amp;amp; someNode.board[8] == 'X')
        return TRUE;    
        //someNode.value = 1;//return 1;
    if(someNode.board[6] == someNode.board[7] amp;amp; someNode.board[7] == someNode.board[8] amp;amp; someNode.board[8] == 'O')
        return TRUE;    
        //someNode.value = -1;//return -1;
    if(someNode.board[0] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[8] amp;amp; someNode.board[8] == 'X')
        return TRUE;    
        //someNode.value = 1;//return 1;
    if(someNode.board[0] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[8] amp;amp; someNode.board[8] == 'O')
        return TRUE;    
        //someNode.value = -1;//return -1;
    if(someNode.board[6] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[2] amp;amp; someNode.board[2] == 'X')
        return TRUE;    
        //someNode.value = 1;//return 1;
    if(someNode.board[6] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[2] amp;amp; someNode.board[2] == 'O')
        return TRUE;

    return FALSE;
}

int isTerminal(struct node someNode) {
    for(int i = 0; i < 9; i  )
        if(someNode.board[i] == ' ') // if square left to fill then game is yet incomplete
            return FALSE;
    if(someoneHasWon(someNode) == TRUE) // if any player has won earlier with squares left
        return TRUE;
    return TRUE; // if it's a draw with no squares left to fill

}






struct node nextMove(struct node someNode) {
    for(int i = 0; i < 9; i  )
        if(someNode.board[i] == ' ') {
            someNode.board[i] = 'O';
            break;
        }
        return someNode;
    }

    int minimax(struct node someNode, int depth, int maximizingPlayer) {

        if(depth == 0 || isTerminal(someNode) == TRUE) {
            if(someNode.board[0] == someNode.board[3] amp;amp; someNode.board[3] == someNode.board[6] amp;amp; someNode.board[6] == 'X')
                someNode.value = 1;
            if(someNode.board[0] == someNode.board[3] amp;amp; someNode.board[3] == someNode.board[6] amp;amp; someNode.board[6] == 'O')
                someNode.value = -1;
            if(someNode.board[1] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[7] amp;amp; someNode.board[7] == 'X')
                someNode.value = 1;//return 1;
            if(someNode.board[1] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[7] amp;amp; someNode.board[7] == 'O')
                someNode.value = -1;//return -1;
            if(someNode.board[2] == someNode.board[5] amp;amp; someNode.board[5] == someNode.board[8] amp;amp; someNode.board[8] == 'X')
                someNode.value = 1;//return 1;
            if(someNode.board[2] == someNode.board[5] amp;amp; someNode.board[5] == someNode.board[8] amp;amp; someNode.board[8] == 'O')
                someNode.value = -1;//return -1;
            if(someNode.board[0] == someNode.board[1] amp;amp; someNode.board[1] == someNode.board[2] amp;amp; someNode.board[2] == 'X')
                someNode.value = 1;//return 1;
            if(someNode.board[0] == someNode.board[1] amp;amp; someNode.board[1] == someNode.board[2] amp;amp; someNode.board[2] == 'O')
                someNode.value = -1;//return -1;
            if(someNode.board[3] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[5] amp;amp; someNode.board[5] == 'X')
                someNode.value = 1;//return 1;
            if(someNode.board[3] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[5] amp;amp; someNode.board[5] == 'O')
                someNode.value = -1;//return -1;
            if(someNode.board[6] == someNode.board[7] amp;amp; someNode.board[7] == someNode.board[8] amp;amp; someNode.board[8] == 'X')
                someNode.value = 1;//return 1;
            if(someNode.board[6] == someNode.board[7] amp;amp; someNode.board[7] == someNode.board[8] amp;amp; someNode.board[8] == 'O')
                someNode.value = -1;//return -1;
            if(someNode.board[0] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[8] amp;amp; someNode.board[8] == 'X')
                someNode.value = 1;//return 1;
            if(someNode.board[0] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[8] amp;amp; someNode.board[8] == 'O')
                someNode.value = -1;//return -1;
            if(someNode.board[6] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[2] amp;amp; someNode.board[2] == 'X')
                someNode.value = 1;//return 1;
            if(someNode.board[6] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[2] amp;amp; someNode.board[2] == 'O')
                someNode.value = -1;//return -1;
            someNode.value = 0;//return 0;
        }
        if(maximizingPlayer == TRUE) { //maximizing player is cpu i.e. 'O'
        
            someNode.value = NEGINF;
            while(isTerminal(someNode) != TRUE)
                someNode.value = max(someNode.value, minimax(nextMove(someNode), depth - 1, FALSE));
            return someNode.value;
    }
    else { //minimizing player is me i.e. 'X'
        int boxNumber = 0;
        scanf("%d", amp;boxNumber);
        someNode.position = boxNumber;
        someNode.board[someNode.position] = 'X';
        someNode.value = POSINF;
        while(isTerminal(someNode) != TRUE)
            someNode.value = min(someNode.value, minimax(nextMove(someNode), depth - 1, TRUE));
        return someNode.value;
    }
}

int main() {
    int boxNumber = 0;
    printf("Assume you're X and cpu is O nInput any box number you like n(0 to 8 both inclusive) n...you'll be defeated anyways lol :n");
    scanf("%d", amp;boxNumber);
    struct node origin;
    for(int i = 0; i < 9; i  )
        origin.board[i] = ' ';
    origin.position = boxNumber;
    origin.board[origin.position] = 'X';
    origin.value = 0;
    minimax(origin, 8, TRUE);
}

Версия кода №2 —

 #include <stdio.h>
#define FALSE 0
#define TRUE 1
#define NEGINF -10000
#define POSINF  10000

struct node
{
    char board[9];
    int value;
    int position;
};

//char someNode.board[9] = {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '};

int max(int value, int returnedValue)
{
    return value > returnedValue ? value : returnedValue;
}

int min(int value, int returnedValue)
{
    return value < returnedValue ? value : returnedValue;
}

int someoneHasWon(struct node someNode)
{
    if (someNode.board[0] == someNode.board[3] amp;amp; someNode.board[3] == someNode.board[6] amp;amp; someNode.board[6] == 'x')
        return TRUE;

    if (someNode.board[0] == someNode.board[3] amp;amp; someNode.board[3] == someNode.board[6] amp;amp; someNode.board[6] == 'o')
        return TRUE;
    //someNode.value = -1;
    if (someNode.board[1] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[7] amp;amp; someNode.board[7] == 'x')
        return TRUE;
    //someNode.value = 1;//return 1;
    if (someNode.board[1] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[7] amp;amp; someNode.board[7] == 'o')
        return TRUE;
    //someNode.value = -1;//return -1;
    if (someNode.board[2] == someNode.board[5] amp;amp; someNode.board[5] == someNode.board[8] amp;amp; someNode.board[8] == 'x')
        return TRUE;
    //someNode.value = 1;//return 1;
    if (someNode.board[2] == someNode.board[5] amp;amp; someNode.board[5] == someNode.board[8] amp;amp; someNode.board[8] == 'o')
        return TRUE;
    //someNode.value = -1;//return -1;
    if (someNode.board[0] == someNode.board[1] amp;amp; someNode.board[1] == someNode.board[2] amp;amp; someNode.board[2] == 'x')
        return TRUE;
    ////someNode.value = 1;//return 1;
    if (someNode.board[0] == someNode.board[1] amp;amp; someNode.board[1] == someNode.board[2] amp;amp; someNode.board[2] == 'o')
        return TRUE;
    //someNode.value = -1;//return -1;
    if (someNode.board[3] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[5] amp;amp; someNode.board[5] == 'x')
        return TRUE;
    //someNode.value = 1;//return 1;
    if (someNode.board[3] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[5] amp;amp; someNode.board[5] == 'o')
        return TRUE;
    //someNode.value = -1;//return -1;
    if (someNode.board[6] == someNode.board[7] amp;amp; someNode.board[7] == someNode.board[8] amp;amp; someNode.board[8] == 'x')
        return TRUE;
    //someNode.value = 1;//return 1;
    if (someNode.board[6] == someNode.board[7] amp;amp; someNode.board[7] == someNode.board[8] amp;amp; someNode.board[8] == 'o')
        return TRUE;
    //someNode.value = -1;//return -1;
    if (someNode.board[0] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[8] amp;amp; someNode.board[8] == 'x')
        return TRUE;
    //someNode.value = 1;//return 1;
    if (someNode.board[0] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[8] amp;amp; someNode.board[8] == 'o')
        return TRUE;
    //someNode.value = -1;//return -1;
    if (someNode.board[6] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[2] amp;amp; someNode.board[2] == 'x')
        return TRUE;
    //someNode.value = 1;//return 1;
    if (someNode.board[6] == someNode.board[4] amp;amp; someNode.board[4] 

== someNode.board[2] amp;amp; someNode.board[2] == 'o')
            return TRUE;
    
        return FALSE;
    }
    
    int isTerminal(struct node someNode)
    {
        for (int i = 0; i < 9; i  )
            if (someNode.board[i] == ' ') // if square left to fill then game is yet incomplete
                return FALSE;
        if (someoneHasWon(someNode) == TRUE) // if any player has won earlier with squares left
            return TRUE;
        return TRUE; // if it's a draw with no squares left to fill
    }
    
    struct node nextMove(struct node someNode)
    {
        for (int i = 0; i < 9; i  )
            if (someNode.board[i] == ' ')
            {
                someNode.board[i] = 'o';
                break;
            }
        return someNode;
    }
    
    int minimax(struct node someNode, int depth, int maximizingPlayer)
    {
    
        if (depth == 8 || isTerminal(someNode) == TRUE)
        {
            if (someNode.board[0] == someNode.board[3] amp;amp; someNode.board[3] == someNode.board[6] amp;amp; someNode.board[6] == 'x')
                someNode.value = 1;
            if (someNode.board[0] == someNode.board[3] amp;amp; someNode.board[3] == someNode.board[6] amp;amp; someNode.board[6] == 'o')
                someNode.value = -1;
            if (someNode.board[1] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[7] amp;amp; someNode.board[7] == 'x')
                someNode.value = 1; //return 1;
            if (someNode.board[1] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[7] amp;amp; someNode.board[7] == 'o')
                someNode.value = -1; //return -1;
            if (someNode.board[2] == someNode.board[5] amp;amp; someNode.board[5] == someNode.board[8] amp;amp; someNode.board[8] == 'x')
                someNode.value = 1; //return 1;
            if (someNode.board[2] == someNode.board[5] amp;amp; someNode.board[5] == someNode.board[8] amp;amp; someNode.board[8] == 'o')
                someNode.value = -1; //return -1;
            if (someNode.board[0] == someNode.board[1] amp;amp; someNode.board[1] == someNode.board[2] amp;amp; someNode.board[2] == 'x')
                someNode.value = 1; //return 1;
            if (someNode.board[0] == someNode.board[1] amp;amp; someNode.board[1] == someNode.board[2] amp;amp; someNode.board[2] == 'o')
                someNode.value = -1; //return -1;
            if (someNode.board[3] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[5] amp;amp; someNode.board[5] == 'x')
                someNode.value = 1; //return 1;
            if (someNode.board[3] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[5] amp;amp; someNode.board[5] == 'o')
                someNode.value = -1; //return -1;
            if (someNode.board[6] == someNode.board[7] amp;amp; someNode.board[7] == someNode.board[8] amp;amp; someNode.board[8] == 'x')
                someNode.value = 1; //return 1;
            if (someNode.board[6] == someNode.board[7] amp;amp; someNode.board[7] == someNode.board[8] amp;amp; someNode.board[8] == 'o')
                someNode.value = -1; //return -1;
            if (someNode.board[0] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[8] amp;amp; someNode.board[8] == 'x')
                someNode.value = 1; //return 1;
            if (someNode.board[0] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[8] amp;amp; someNode.board[8] == 'o')
       

         someNode.value = -1; //return -1;
        if (someNode.board[6] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[2] amp;amp; someNode.board[2] == 'x')
            someNode.value = 1; //return 1;
        if (someNode.board[6] == someNode.board[4] amp;amp; someNode.board[4] == someNode.board[2] amp;amp; someNode.board[2] == 'o')
            someNode.value = -1; //return -1;
        someNode.value = 0;      //return 0;
    }
    if (maximizingPlayer == TRUE)
    { //maximizing player is cpu i.e. 'o'

        someNode.value = NEGINF;
        while (isTerminal(someNode) != TRUE)
            someNode.value = max(someNode.value, minimax(nextMove(someNode), depth   1, FALSE));
        if (someNode.value == -1) {
            printf("o %d n", someNode.value);
            return someNode.value;
        }
    }
    else
    { //minimizing player is me i.e. 'x'
        int boxNumber = 0;
        printf("Enter your move :n");
        scanf("%d", amp;boxNumber);
        someNode.position = boxNumber;
        someNode.board[someNode.position] = 'x';
        someNode.value = POSINF;
        while (isTerminal(someNode) != TRUE)
            someNode.value = min(someNode.value, minimax(nextMove(someNode), depth   1, TRUE));
        if (someNode.value == 1)
            return someNode.value;
    }
}

int main()
{
    int boxNumber = 0;
    printf("Assume you're x and cpu is O nInput any box number you like n(0 to 8 both inclusive) n...you'll be defeated anyways lol :n");
    scanf("%d", amp;boxNumber);
    struct node origin;
    origin.position = boxNumber;
    origin.board[origin.position] = 'x';
    origin.value = 0;
    printf("%c %d n", origin.board[origin.position], origin.position);
    int val = minimax(origin, 1, TRUE);
    if(val > 0)
        printf("You lose");
    else if(val < 0)
        printf("You win");
    else
        printf("It's a draw");
    return 0;
}

Комментарии:

1. Хотите ли вы реализовать определенным образом (вы действительно много описываете о том, что вы думаете и чего хотите) или вы хотите, чтобы программа была такой, чтобы ИИ никогда не проигрывал? Я спрашиваю, потому что подозреваю, что вы не получаете ответов (несмотря на вознаграждение) из-за возможного конфликта. Т.е. Что заставляет вас думать, что создание никогда не проигрывающего ИИ, как вы описываете, действительно возможно? Подумайте о том, чтобы написать что-то вроде «Я назначу награду за ответ, который обеспечит никогда не проигрывающий ИИ; тот, который ближе всего подходит к моему подходу к разрыву связей». Или «Вознаграждение за лучший ответ (проигрыш) ИИ в соответствии с моим подходом «.

2. Да, я хочу, чтобы ИИ никогда не проигрывал (ни выигрывал, ни играл вничью). Кроме того, я делаю это, чтобы научить себя Минимаксу, как это описано здесь: en.wikipedia.org/wiki/Minimax#Pseudocode

3. geeksforgeeks.org/…

Ответ №1:

Я думаю, что мне не хватает функции, которая фактически использует возвращенные «оценки».

Ну, нет, сама minimax() функция — единственная, которой нужна оценка, которую она (рекурсивно) вычисляет. Проблема в том, что псевдокод, который вы просматриваете в Википедии, очень «псевдо». Это достаточно хорошо иллюстрирует идею алгоритма, но не дает очень хорошей модели для его реальной реализации. В частности, в нем отсутствует ключевой компонент, который требуется для любой практической реализации: в дополнение к вычислению счета minimax() необходимо предоставить хотя бы один ход, который приводит к этому счету. Это ход, который выбирает вызывающий абонент верхнего уровня.

Также меня смущает функция nextMove(), я хочу, чтобы она проверяла, нет ли незаполненного поля, затем заполняла его буквой «О», а затем наступала очередь игрока. Но поскольку он будет вызван снова при рекурсии, он может работать некорректно. Есть предложения?

Существует по крайней мере два возможных общих подхода:

  1. создавайте временные копии платы по мере необходимости, чтобы вы могли изменять их, не меняя оригинал, или
  2. отслеживайте каждую проверенную позицию и очищайте ее после теста.

В любом случае, полезно отделить процесс анализа хода от фактического выбора хода.

Обратите внимание, что вы уже делаете копии, передавая struct node объекты по значению. Само по себе это не обязательно полная или правильная реализация варианта (1), но это определенно то, о чем нужно знать, особенно в отношении моего основного пункта выше.

Кроме того, мне не особенно нравится подход псевдокода к использованию логического ввода minimax() , чтобы указать, следует ли максимизировать или минимизировать. Вместо этого я предпочитаю передавать аргумент, чтобы указать, какой это ход игрока. В симметричной игре, такой как крестики-нолики, minimax() функция затем использует тот факт, что чем лучше результат для одного игрока, тем хуже он для другого. Среди прочего, это имеет тенденцию упрощать код, потому что тогда коду не нужны отдельные регистры вокруг значения этого параметра.

Комментарии:

1. Я понял, что не использую значение, возвращаемое minimax функцией main методу. Я обновил это. Кроме того, я заметил, что псевдокод в википедии использует глубину дерева, как если бы это была его высота (в основном противоположно моему определению высоты). Поэтому я изменил depth - 1 depth 1 на рекурсивный вызов.

2. Тем не менее, код все еще не работает, и любые комментарии / подсказки по моему коду будут оценены.

Ответ №2:

Крестики-нолики — очень простая игра, поэтому в ней не так много игровых состояний. Таким образом, вам не нужно ограничивать AI глубиной.

 function bestMove(board, maximisingPlayer) is
  if tie then
    return {value: 0}
  else if maximising player won then
    return {value: ∞}
  else if minimising player won then
    return {value: -∞}

  if maximisingPlayer then
    value := -∞
    move := 0

    for each child of node do
      tempValue := minimax(child, FALSE).value

      if tempValue > value then
        value := tempValue
        move := child
    
    return {value: value, move: move}
  else 
    value := ∞
    move := 0

    for each child of node do
      tempValue := minimax(child, TRUE).value

      if tempValue < value then
        value := tempValue
        move := child
    
    return {value: value, move: move}

/* Returns best child node after move is made. */
currentBestMove := bestMove(currentBoard, currentPlayer).move

Также в качестве замечания к вашему коду, не помещайте логику win в ту же процедуру, что и минимакс, постарайтесь разбить свой код на более мелкие функции, насколько это возможно. Кроме того, вы можете хранить выигрышные комбинации в массиве.