Почему ИИ, который сделан с помощью минимакс алгоритма, иногда проигрывает в человека ? с++

378
11 июля 2017, 21:36

Я сделал небольшую игру крестики-нолики, для ИИ использован минимакс алгоритм. Но определенными комбинациями его легко обыграть.

Код:

#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Move
{
public:
    int score;
    int index;
};
static vector<string> origBoard = { "0", "1", "2", "3", "4", "5", "6", "7", "8", };
static string huPlayer = "o";
static string aiPlayer = "x";
void emptyIndices(vector<string>& board, vector<int>& emptyIndicesList)
{
    for (size_t i = 0; i < 9; i++)
    {
        if (board[i] != "x" && board[i] != "o")
        {
            emptyIndicesList.push_back(i);
        }
    }
}
bool winning(vector<string> board, string player)
{
    if (
        (board[0] == player && board[1] == player && board[2] == player) ||
        (board[3] == player && board[4] == player && board[5] == player) ||
        (board[6] == player && board[7] == player && board[8] == player) ||
        (board[0] == player && board[3] == player && board[6] == player) ||
        (board[1] == player && board[4] == player && board[7] == player) ||
        (board[2] == player && board[5] == player && board[8] == player) ||
        (board[0] == player && board[4] == player && board[8] == player) ||
        (board[2] == player && board[4] == player && board[6] == player)
        )
    {
        return true;
    }
    return false;
}
bool isDraw(vector<string> board)
{
    size_t result = 0;
    for (size_t i = 0; i < board.size(); i++)
    {
        if (board[i] != aiPlayer && board[i] != huPlayer)
        {
            result++;
        }
    }
    return (result == 0);
}
void printCell(string cell)
{
    cout << "[";
    if (!atoi(cell.c_str()) && cell != "0")
    {
        cout << cell;
    }
    else
    {
        cout << " ";
    }
    cout << "]";
}
void printBoard(vector<string> board)
{
    size_t i = 0;
    while (i != 9)
    {
        printCell(board[i]);
        printCell(board[i + 1]);
        printCell(board[i + 2]);
        cout << endl;
        i += 3;
    }
    cout << endl;
}
bool cellIsEmpty(string cell)
{
    if (cell == aiPlayer || cell == huPlayer)
    {
        return false;
    }
    return true;
}
int minimax(vector<string> newBoard, string player)
{
    vector<int> availSpots;
    emptyIndices(newBoard, availSpots);
    if (winning(newBoard, huPlayer))
    {
        return -10;
    }
    else if (winning(newBoard, aiPlayer))
    {
        return 10;
    }
    else if (availSpots.size() == 0)
    {
        return 0;
    }
    vector<Move> moves;
    for (size_t i = 0; i < availSpots.size(); i++)
    {
        Move move;
        move.index = stoi(newBoard[availSpots[i]]);
        newBoard[availSpots[i]] = player;
        if (player == aiPlayer)
        {
            int result = minimax(newBoard, huPlayer);
            move.score = result;
        }
        else
        {
            int result = minimax(newBoard, aiPlayer);
            move.score = result;
        }
        newBoard[availSpots[i]] = to_string(move.index);
        moves.push_back(move);
    }
    int bestMove;
    if (player == aiPlayer)
    {
        int bestScore = -10000;
        for (size_t i = 0; i < moves.size(); i++)
        {
            if (moves[i].score > bestScore)
            {
                bestScore = moves[i].score;
                bestMove = i;
            }
        }
    }
    else
    {
        int bestScore = 10000;
        for (size_t i = 0; i < moves.size(); i++)
        {
            if (moves[i].score < bestScore)
            {
                bestScore = moves[i].score;
                bestMove = i;
            }
        }
    }
    return moves[bestMove].index;
}
int humanMove(vector<string>& board)
{
    int huMove;
    do
    {
        cout << " Move > ";
        cin >> huMove;
    } while (!cellIsEmpty(origBoard[huMove - 1]) && huMove < 1 && huMove > 9);
    origBoard[huMove - 1] = huPlayer;
    system("cls");
    printBoard(origBoard);
    cout << "\n";
    if (isDraw(origBoard))
    {
        cout << " Draw!\n\n";
        return 1;
    }
    if (winning(origBoard, huPlayer))
    {
        cout << " You win!\n\n";
        return 1;
    }
    return 0;
}
int aiMove(vector<string>& board)
{
    cout << " Waiting for AI move...";
    int moveAi = minimax(origBoard, huPlayer);
    origBoard[moveAi] = aiPlayer;
    system("cls");
    printBoard(origBoard);
    cout << "\n";
    if (isDraw(origBoard))
    {
        cout << " Draw!\n\n";
        return 1;
    }
    if (winning(origBoard, aiPlayer))
    {
        cout << " You lose!\n\n";
        return 1;
    }
    return 0;
}
void main()
{
    printBoard(origBoard);
    cout << "\n";
    while (true)
    {
        if (humanMove(origBoard) == 1)
        {
            break;
        }
        if (aiMove(origBoard) == 1)
        {
            break;
        }
    }
    system("pause");
}

Кто-то может подсказать, что я сделал не так в самом алгоритме ?

READ ALSO
Бесконечный цикл перед PeekMessage

Бесконечный цикл перед PeekMessage

Всем доброй ночиВсе-таки не успокоюсь, пока не решу окончательно одну проблему

260
Наиболее точный вариант таймера для MFC C++

Наиболее точный вариант таймера для MFC C++

Уважаемые коллеги! В моем приложении MFC должна выводится некоторая строка в list control через некоторый промежуток времени от 50 до 1000 миллисекунд

245
Какие методы и операторы необходимы для использования типа в качестве параметра стандартного шаблонного контейнера?

Какие методы и операторы необходимы для использования типа в качестве параметра стандартного шаблонного контейнера?

Какие методы и операторы необходимы для использования типа в качестве параметра стандартного шаблонного контейнера?

188
Ошибка event.js:160 throw er // unhandled &#39;error&#39; event gulp

Ошибка event.js:160 throw er // unhandled 'error' event gulp

Ошибка появилась после использования mmenu и hamburgers css

394