Как исправить реализацию алгоритма минимакс?

Question

sttie @sttie

C++

Как исправить реализацию алгоритма минимакс?

Пишу бота для крестиков-ноликов (алгоритм минимакс, пока без альфа-бета отсечений). Алгоритм таков:

// 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;
}

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