Во-первых, я прошу прощения за немного неправильный заголовок, я просто не хотел, чтобы он состоял из 30 слов. Сокращение альфа/бета, которое я реализовал, значительно уменьшило количество оценок, когда я применил его к своей игре TicTacToe, убедитесь сами ниже.
Каждая пара значений оценки измеряется с тем же состоянием игры, что и ввод.
Проблема возникает, когда я хочу реализовать обрезку шашек, играющих в нейронную сеть, над которой я работал. Что было целью всего этого с самого начала, я просто на скорую руку запустил игру TicTacToe, чтобы поэкспериментировать с MiniMax + Alpha/Beta, поскольку я никогда раньше не имел дело с этими алгоритмами.
Вот такой же эксперимент с NN.
Теперь о коде (один из шашек, дайте мне знать, если вы хотите взглянуть на версию TicTacToe, хотя они почти идентичны).
Я вставлю только один раз начало обоих методов, так как они абсолютно идентичны, покажу обе подписи, так как они немного отличаются.
Небольшое примечание, чтобы сделать код более понятным.
Доска — это объект, который отслеживает фигуры, доступные ходы, какой сейчас ход, была ли игра выиграна/ничья и т. д.
Move — это объект, который содержит всю информацию, относящуюся к ходам. Когда я создаю клон в качестве первой строки метода, я просто создаю клон данной доски, и конструктор применяет к ней заданный ход.
private double miniMax(Board b, Move m, int depth) {
и
private double alphaBeta(Board b, Move m, int depth, double alpha, double beta) {
начало обоих методов:
Testboard clone = new Testboard(b, m);
// Making a clone of the board in order to
// avoid making changes to the original one
if (clone.isGameOver()) {
if (clone.getLoser() == null)
// It's a draw, evaluation = 0
return 0;
if (clone.getLoser() == Color.BLACK)
// White (Max) won, evaluation = 1
return 1;
// Black (Min) won, evaluation = -1
return -1;
}
if (depth == 0)
// Reached the end of the search, returning current Evaluation of the board
return getEvaluation(clone);
Очередное продолжение MiniMax:
// If it's not game over
if (clone.getTurn() == Color.WHITE) {
// It's white's turn (Maxing player)
double max = -1;
for (Move move : clone.getMoves()) {
// For each children node (available moves)
// Their minimax value is calculated
double score = miniMax(clone, move, depth-1);
// Only the highest score is stored
if (score > max)
max = score;
}
// And is returned
return max;
}
// It's black's turn (Min player)
double min = 1;
for (Move move : clone.getMoves()) {
// For each children node (available moves)
// Their minimax value is calculated
double score = miniMax(clone, move, depth-1);
// Only the lowest score is stored
if (score < min)
min = score;
}
// And is returned
return min;
}
MiniMax с продолжением обрезки Alpha/Beta:
// If it's not game over
if (clone.getTurn() == Color.WHITE) {
// It's white's turn (Maxing player)
for (Move move : clone.getMoves()) {
// For each children node (available moves)
// Their minimax value is calculated
double score = alphaBeta(clone, move, depth-1, alpha, beta);
if (score > alpha)
// If this score is greater than alpha
// It is assigned to alpha as the new highest score
alpha = score;
if (alpha >= beta)
// The cycle is interrupted early if the value of alpha equals or is greater than beta
break;
}
// The alpha value is returned
return alpha;
}
// It's black's turn (Min player)
for (Move move : clone.getMoves()) {
// For each children node (available moves)
// Their minimax value is calculated
double score = alphaBeta(clone, move, depth-1, alpha, beta);
if (score < beta)
// If this score is lower than beta
// It is assigned to beta as the new lowest score
beta = score;
if (alpha >= beta)
// The cycle is interrupted early if the value of alpha equals or is greater than beta
break;
}
// The beta value is returned
return beta;
}
Я честно застрял, и я не уверен, что я мог бы сделать, чтобы попытаться выяснить, что происходит. Я пробовал MiniMax+A/B на нескольких разных, даже случайно сгенерированных нейронных сетях, но я никогда не видел улучшения, когда дело доходит до количества сделанных оценок. Я надеюсь, что кто-то здесь сможет пролить свет на эту ситуацию, спасибо!