Answer the question
In order to leave comments, you need to log in
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;
}
Answer the question
In order to leave comments, you need to log in
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question