Возврат рекурсии по альфа-бета-обрезке Java Minimax
Я пытаюсь реализовать минимакс с альфа-бета-отсечкой для игры в шашки на Java. Мой минимаксный алгоритм работает отлично. Мой код работает с альфа-бета-кодом на месте. К сожалению, когда я играю 1000 игр против стандартного минимаксного алгоритма, алгоритм альфа-бета всегда отстает на 50 игр или около того.
Поскольку альфа-бета-обрезка не должна снижать качество ходов, просто время, необходимое для их достижения, должно быть что-то не так. Однако я вынул ручку и бумагу и нарисовал значения гипотетических листовых узлов и использовал свой алгоритм, чтобы предсказать, будет ли он вычислять правильное наилучшее движение, и логических ошибок, похоже, нет. Я использовал дерево из этого видео: альфа-бета-обрезка, чтобы проследить мой алгоритм. По логике он должен делать все те же выборы и, следовательно, быть работающей реализацией.
Я также поместил операторы print в код (они были удалены, чтобы уменьшить беспорядок), и значения возвращаются правильно, это появляется, и сокращение действительно происходит. Несмотря на все мои усилия, я не смог найти, где лежит логическая ошибка. Это моя третья попытка реализовать это, и у всех них была одна и та же проблема.
Я не могу опубликовать полный код здесь, он слишком длинный, поэтому я включил методы, имеющие отношение к ошибке. Я не уверен, но я подозреваю, что проблема, вероятно, заключается в нерекурсивном методе move(), хотя я не могу найти в нем логической ошибки, так что я просто буду больше в нем разбираться, возможно, делая вещи хуже, а не лучше без рифмы или причины.
Есть ли хитрость для восстановления нескольких целочисленных значений из рекурсивных вызовов в цикле for? Он отлично работает как с моими минимаксными, так и с негамаксическими реализациями, но альфа-бета-обрезание, кажется, дает странные результаты.
@Override
public GameState move(GameState state)
{
int alpha = -INFINITY;
int beta = INFINITY;
int bestScore = -Integer.MAX_VALUE;
GameTreeNode gameTreeRoot = new GameTreeNode(state);
GameState bestMove = null;
for(GameTreeNode child: gameTreeRoot.getChildren())
{
if(bestMove == null)
{
bestMove = child.getState();
}
alpha = Math.max(alpha, miniMax(child, plyDepth - 1, alpha, beta));
if(alpha > bestScore)
{
bestMove = child.getState();
bestScore = alpha;
}
}
return bestMove;
}
private int miniMax(GameTreeNode currentNode, int depth, int alpha, int beta)
{
if(depth <= 0 || terminalNode(currentNode.getState()))
{
return getHeuristic(currentNode.getState());
}
if(currentNode.getState().getCurrentPlayer().equals(selfColor))
{
for(GameTreeNode child: currentNode.getChildren())
{
alpha = Math.max(alpha, miniMax(child, depth - 1, alpha, beta));
if(alpha >= beta)
{
return beta;
}
}
return alpha;
}
else
{
for(GameTreeNode child: currentNode.getChildren())
{
beta = Math.min(beta, miniMax(child, depth - 1, alpha, beta));
if(alpha >= beta)
{
return alpha;
}
}
return beta;
}
}
//Checks to see if the node is terminal
private boolean terminalNode(GameState state)
{
if(state.getStatus().equals(win) || state.getStatus().equals(lose) || state.getStatus().equals(draw))
{
return true;
}
else
{
return false;
}
}
5 ответов
Я заметил, что вы сказали, что нашли проблему, но разве минимамакс
if it is MAX's turn to move
for child in children
result = alphaBetaMinimax(child, alpha, beta)
if result > alpha
alpha = result
if node is root
bestMove = operator of child
if alpha >= beta
return alpha
return alpha
if it is MIN's turn to move
for child in children
result = alphaBetaMinimax(child, alpha, beta)
if result < beta
beta = result
if node is root
bestMove = operator of child
if beta <= alpha
return beta
return beta
вы написали:
if alpha >= beta
return beta
return alpha
16 марта 2013 года sage88 спросил:
Есть ли хитрость для восстановления нескольких целочисленных значений из рекурсивных вызовов в цикле for? Он отлично работает как с моими минимаксными, так и с негамаксическими реализациями, но отсечение альфа-бета, кажется, дает некоторые странные результаты.
В сокращении альфа-бета единственное интересующее выходное значение представляет собой оценку узла: конечное значение беты в минимальном узле рассматривается для альфа-значения его родительского максимального узла; аналогично, конечное значение альфа в максимальном узле рассматривается как бета-значение его родительского минимального узла. Следовательно:
Ответ на ваш вопрос - сам алгоритм, так как это наиболее актуальная уловка.
Тем не менее, в вашей реализации есть две ошибки: 1) Как первоначально указал Адриан Блэкберн, он неправильно возвращает альфа из минимального узла и наоборот, таким образом искажая его точность; 2) Он отказывается от возможности сокращения, преждевременно рассматривая родительскую альфа или бета в значении текущего узла. Эта версия исправляет возвращаемые значения и максимизирует сокращение:
private int miniMax(GameTreeNode currentNode, int depth, int alpha, int beta) {
if (depth <= 0 || terminalNode(currentNode.getState())) {
return getHeuristic(currentNode.getState());
}
if (currentNode.getState().getCurrentPlayer().equals(selfColor)) {
int currentAlpha = -INFINITY;
for (GameTreeNode child : currentNode.getChildren()) {
currentAlpha = Math.max(currentAlpha, miniMax(child, depth - 1, alpha, beta));
alpha = Math.max(alpha, currentAlpha);
if (alpha >= beta) {
return alpha;
}
}
return currentAlpha;
}
int currentBeta = INFINITY;
for (GameTreeNode child : currentNode.getChildren()) {
currentBeta = Math.min(currentBeta, miniMax(child, depth - 1, alpha, beta));
beta = Math.min(beta, currentBeta);
if (beta <= alpha) {
return beta;
}
}
return currentBeta;
}
Спасибо за интересный и интересный вопрос:)
Для большего удовольствия, вот разъяснение вашего move() метод, удаляющий избыточный вызов Math.max():
@Override
public GameState move(GameState state) {
GameState bestMove = null;
int bestScore = -INFINITY;
GameTreeNode gameTreeRoot = new GameTreeNode(state);
for (GameTreeNode child : gameTreeRoot.getChildren()) {
int alpha = miniMax(child, plyDepth - 1, bestScore, INFINITY);
if (alpha > bestScore || bestMove == null) {
bestMove = child.getState();
bestScore = alpha;
}
}
return bestMove;
}
Наконец (еще веселее), просто предложение, изменение имени метода, чтобы уточнить цель terminalNode()хотя я бы переместил это в GameState поэтому он может быть вызван без параметров:
private boolean isTerminal(GameState state) {
//return Is.any(state.getStatus(), win, lose, draw);
return state.getStatus().equals(win)
|| state.getStatus().equals(lose)
|| state.getStatus().equals(draw);
}
Просто чтобы ответить на ваш вопрос
Есть ли хитрость для восстановления нескольких целочисленных значений из рекурсивных вызовов в цикле for?
Да, в Java вам нужно будет передать объект в рекурсивный вызов функции, а затем изменить содержимое этого объекта. После того, как функция вернется, вы сможете получить доступ к измененным значениям.
Например.
class ToBeReturned {
int returnValue1;
int returnValue2;
int returnValue3;
}
Вы уже исправили свою проблему, но проблема, с которой вы столкнулись, довольно распространена. Поэтому всякий раз, когда вы строите часть алгоритма для агента ИИ, вы должны правильно его тестировать. Так что, как только ваш алгоритм минимакса верен, вы можете просто сгенерировать много случайных деревьев и проверить, совпадают ли результаты. Например, в Python вы можете сделать это следующим образом:
class Node():
def __init__(self, data, children):
self.data = data
self.children = children
def generateTree(depth, branching):
total = branching**depth
values = [randint(-100, 100) for _ in xrange(total)]
level = [Node(values[i], []) for i in xrange(total)]
for _ in xrange(depth):
total /= branching
level = [Node(None, level[i * branching: (i+1) * branching]) for i in xrange(total)]
return level[0], values
Теперь вы можете создать дерево с множеством случайных деревьев и сравнить результаты.
tree, values = generateTree(depth, branching)
print negamax(tree, depth, 1) == alpha_beta_negamax(tree, depth, float('-inf'), float('inf'), 1)
Не забывайте, что минимакс и альфа-бета возвращают только лучшее значение, тогда как в реальной игре вас интересует ход. Очень просто изменить их таким образом, чтобы они могли вернуть ход, но разработчик должен решить, как вернуть ход. Это потому, что может быть много ходов, которые приводят к лучшему решению (вы можете вернуть первый, последний или самый распространенный, чтобы найти все ходы и вернуть случайный).
В вашем случае проблема была в случайности возвращаемых значений, поэтому во время тестирования хорошим подходом является исправление случайности.
Для достижения оптимальных результатов ставок вы должны реализовать своего рода порядок ходов. В шахматах это обычно захваты или проверки. Такого рода движения, как правило, больше всего меняют оценку, и поэтому они оказывают большое влияние на сокращение. В шашках это может быть взятие камней оппонентов или продвижение собственных камней 8-го ранга (извините, не знаю используемых терминов).