S
S
sttie2020-02-29 21:19:37
C++ / C#
sttie, 2020-02-29 21:19:37

How to fix the minimax algorithm implementation?

I am writing a tic-tac-toe bot (minimax algorithm, without alpha-beta clipping yet). The algorithm is:

// turn = -1, если сейчас ход бота, и turn = 1 иначе

// анализ хода бота начинается в этой функции
int analyseMove(vector<char>* field, int turn)
{
    // доступные ходы
    vector<int> moves = freeCells(field);

    // если бот ходит первым, то по умолчанию идем в центр
    if (moves.size() == 9)
        return 5;

    // изначально оценка у бота минимальна
    int best_move, best_score = -11;

    for (int i = 0; i < moves.size(); i++)
    {
        // деталь реализации, в вопросе не имеет значение
        int move = moves[i];

        makeMove(turn, move, field);
        // начинаем считать для каждого возможного хода
        // глубина равна количеству возможных шагов
        int score = getEvaluation(moves.size(), field, -turn);
        undoMove(move, field);

        if (score > best_score)
        {
            best_score = score;
            best_move = moves[i];
        }
    }

    return best_move;
}


int getEvaluation(int depth, vector<char>* field, int turn)
{
    // проверяем, есть ли победные комбинации.
    // result = 10, если победил бот, -10 - если победил человек, 0 - если ничья
    int result = checkWinner(*field);

    // если ничья (= достигли максимального уровня рекурсии) или кто-то победил, 
    // возвращаем оценку (-10, 0, или 10)
    if (depth == 0 || result != 0)
        return result;

    vector<int> moves = freeCells(field);
    // если ход бота, то best_score будет минимальным (т.к. turn = -1)
    // и аналогично с человеком
    int best_score = 11 * turn;

    for (int i = 0; i < moves.size(); i++)
    {
        // деталь реализации, в вопросе не имеет значение
        int move = moves[i];

        makeMove(turn, move, field);
        // идем глубже
        int score = getEvaluation(depth - 1, field, -turn);
        undoMove(move, field);

        if (turn == -1)
            best_score = max(best_score, score);
        else
            best_score = min(best_score, score);
    }

    return best_score;
}


As a result, the bot simply goes to the first free cell that comes across. First I wrote it myself, then I looked at the implementation of other people - everything is about the same, but my version does not work. What error am I missing?

Answer the question

In order to leave comments, you need to log in

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question