Блог

Главная - Вопросы по программированию - непревзойденные крестики-нолики

непревзойденные крестики-нолики

#c #algorithm

#c #алгоритм

Вопрос:

я пытаюсь создать непревзойденный tic tac toe для стороннего проекта, и я не могу сделать это правильно (на самом деле, я могу превзойти это по иронии судьбы). На самом деле это реализация минимаксного алгоритма; я пришел с этим кодом

 #include <iostream>
#include <string>

using namespace std;
struct Move
{
    int line, columns;
};
//Return the number of remainings turn based on the number of lest boxes
int remainingsTurns(char grid[3][3])
{
    int remainingTurn = 0;
    for (int k = 0; k < 3; k  )
    {
        for (int i = 0; i < 3; i  )
        {
            if (grid[k][i] == ' ')
            {
                remainingTurn  ;
            }
        }
    }
    return remainingTurn;
}
//Print the grid on screen
void printGrid(char grid[3][3])
{
    for (int k = 0; k < 3; k  )
    {
        for (int i = 0; i < 3; i  )
        {
            cout << "| " << grid[k][i] << " ";
        }

        cout << "|" << endl;
    }

}
//Give a value to the board
int evaluateBoard(char grid[3][3])
{
    //Check the board for lines
    for (int k = 0; k < 3; k  )
    {
        if (grid[k][0] == grid[k][1] amp;amp; grid[k][1] == grid[k][2])
        {
            if (grid[k][0] == 'x')
            {
                return  10;
            }
            else if (grid[k][0] == 'o')
            {
                return -10;
            }
        }
    }

    //Check the board for columns
    for (int k = 0; k < 3; k  )
    {
        if (grid[0][k] == grid[1][k] amp;amp; grid[1][k] == grid[2][k])
        {
            if (grid[0][k] == 'x')
            {
                return  10;
            }
            else if (grid[0][k] == 'o')
            {
                return -10;
            }
        }
    }

    //Check the board for diagonals
    if (grid[0][0] == grid[1][1] amp;amp; grid[0][0] == grid[2][2])
    {
        if (grid[0][0] == 'x')
        {
            return  10;
        }
        else if (grid[0][0] == 'o')
        {
            return -10;
        }
    }
    if (grid[0][2] == grid[1][1] amp;amp; grid[0][2] == grid[2][0])
    {
        if (grid[0][0] == 'x')
        {
            return  10;
        }
        else if (grid[0][0] == 'o')
        {
            return -10;
        }
    }
    //if no ictory return 0
    return 0;
}
// MiniMax algorithm
int miniMax(char grid[3][3], int turn, bool maxMove)
{
    int score = evaluateBoard(grid);
    
    if (score == 10)
    {
        return score;
    }
    if (score == -10)
    {
        return score;
    }
    //Check if the game is a tie
    if (remainingsTurns(grid) == 0)
    {
        return 0;
    }
    if (maxMove)
    {
        int best = -1000;
        for (int k = 0; k < 3; k  )
        {
            for (int i = 0; i < 3; i  )
            {
                if (grid[k][i] == ' ')
                {
                    grid[k][i] = 'x';
                    best = max(best, miniMax(grid, turn   1, !maxMove));
                    grid[k][i] = ' ';

                }
            }
        }
        return best;
    }
    else
    {
        int best = 1000;
        for (int k = 0; k < 3; k  )
        {
            for (int i = 0; i < 3; i  )
            {
                if (grid[k][i] == ' ')
                {
                    grid[k][i] = 'o';
                    best = min(best, miniMax(grid, turn   1, !maxMove));
                    grid[k][i] = ' ';
                }
            }
        }
        return best;
    }
}

Move playerMov(char grid[3][3])
{
    Move playerMove;
    int input = -1;
    cout << "Enter the column you want to play (1, 2 or 3)" << endl;
    cin >> input;
    if (input == 1 || input == 2 || input == 3)
    {
        playerMove.columns = input-1;
        input = -1;
    }
    else
    {
        cout << "Error, enter a valid number!" << endl;
        playerMov(grid);

    }
    cout << "Enter the line you want to play (1, 2 or 3)" << endl;
    cin >> input;
    if (input == 1 || input == 2 || input == 3)
    {
        playerMove.line = input-1;
        input = -1;
    }
    else
    {
        cout << "Error, enter a valid number!" << endl;
        playerMov(grid);

    }
    return playerMove;

}
//return the best move using the MiniMax
Move findMove(char grid[3][3])
{
    int best = -1000;
   
    Move move;
    move.line = -1;
    move.columns = -1;
    //Check all move to find if this move is the best possible move
    for (int k = 0; k < 3; k  )
    {
        for (int i = 0; i < 3; i  )
        {
            if (grid[k][i] == ' ')
            {
                grid[k][i] = 'x';
                int moveValue = miniMax(grid, 0, false);
                grid[k][i] = ' ';
                if (moveValue > best)
                {
                    move.line = k;
                    move.columns = i;
                }
            }
        }
    }
    return move;
}
int main()
{
    char grid[3][3];
    int turn = 0;
    Move playerMove, algoMove;
    for (int k = 0; k < 3; k  )
    {
        for (int i = 0; i < 3; i  )
        {
            grid[k][i] = ' ';
        }
    }

    cout << "Welcome to the unbeatable Tic Tac Toe !" << endl;
    do
    {
        printGrid(grid);
        playerMove = playerMov(grid);
        grid[playerMove.line][playerMove.columns] = 'o';
        Move computerMove = findMove(grid);
        grid[computerMove.line][computerMove.columns] = 'x';

    } while (remainingsTurns(grid) > 0);

    cout << endl;
}

но движения алгоритма не кажутся правильными, он всегда выбирает нижний правый угол, и я не понимаю почему…
Эта реализация в значительной степени вдохновлена этой статьей от Geek for Geek, где я пытался украсть алгоритм, но я не могу сделать это правильно, чтобы сделать его пригодным для одиночной игры.
Чего мне не хватает?

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

1. Почему вы проверяете grid[0][0] в grid[0][2] == grid[1][1] amp;amp; grid[0][2] == grid[2][0] случае?

2. Также playerMov(grid); в playerMov функции должно быть return playerMov(grid);

3. потому что это плохой тест с моей стороны …». Спасибо, что заметили это

4. Не связано: чтобы сделать его больше похожим на C (вместо C), вы могли бы создать свой собственный Board класс и поместить свободные функции в качестве функций-членов в этот класс. class Board { char grid[3][3]; public: int evaluate(); }; и так далее.

5. нет, playerMov(grid) вызовите функцию еще раз, чтобы заставить пользователя перезапустить свой ввод в случае ввода вне сетки (если игрок попытается ввести другое число вместо 1, 2 или 3)

Ответ №1:

В вашем коде множество ошибок:

  • Вы проверяете значение grid[0][0] в grid[0][2] == grid[1][1] amp;amp; grid[0][2] == grid[2][0] случае функции evaluateBoard . Так и должно быть grid[0][2] .
  • playerMov(grid); в функции playerMov должно быть return playerMov(grid); . В противном случае повторно введенные «правильные» значения будут удалены и (частично) будут возвращены неинициализированные playerMov .
  • Вы должны обновиться best до moveValue того, moveValue > best когда findMove запустите функцию «». (это должно быть причиной проблемы в вашем вопросе)