Возврат рекурсии Java Minimax Alpha-Beta

Ответ 1

Я заметил, что вы сказали, что нашли проблему, но не должны ли минимальная альфа-бета-обрезка быть

if it is MAX 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 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

Ответ 2

Чтобы просто ответить на ваш вопрос

Есть ли уловка для восстановления нескольких целых значений из рекурсивного вызовы в цикле for?

Да, в Java вам нужно передать объект в вызов рекурсивной функции, а затем изменить содержимое этого объекта. После возвращения функции вы сможете получить доступ к измененным значениям.

Eg.

class ToBeReturned {
    int returnValue1;
    int returnValue2;
    int returnValue3;
}

Ответ 3

16 марта 2013 года sage88 спросил:

Есть ли трюк для восстановления нескольких целых значений из рекурсивных вызовов в цикле for? Он отлично работает с моими минимаксными и негамаксными реализациями, но обрезание альфа-бета, похоже, приводит к некоторым странным результатам.

В альфа-бета-обрезке единственное представляющее интерес значение представляет собой оценку node: конечное значение бета в min node рассматривается для альфа-значения его родительского max node; аналогично, последнее значение альфа в max node рассматривается для бета-значения его родительского min node. Поэтому:

Ответ на ваш вопрос - это сам алгоритм, так как это наиболее подходящий трюк.

Тем не менее, в вашей реализации есть две ошибки: 1) Как первоначально указал Адриан Блэкберн, он неправильно возвращает альфа из min node и наоборот, тем самым искажая его точность; 2) Он отказывается от возможностей отсечения, преждевременно рассматривая родительскую альфу или бета в текущем значении node. Эта версия исправляет возвращаемые значения и максимизирует обрезку:

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

Ответ 4

Для достижения выигрышных результатов вы должны реализовать какой-то порядок перемещения. В шахматах это обычно захватывает или проверяет. Такие шаги, как правило, чаще меняют оценку, и поэтому они оказывают большое влияние на приземление. В шашки он может брать камни oponents или продвигать собственные камни на 8-м ранге (извините, не знаю, какие термины используются).

Ответ 5

Вы уже исправили свою проблему, но проблема, с которой вы столкнулись, довольно распространена. Поэтому всякий раз, когда вы создаете часть алгоритма для агента AI, вы должны проверить его правильно. Итак, как только ваш минимаксный алгоритм будет правильным, вы можете просто создать много случайных деревьев и проверить, одинаковы ли результаты. Например, в 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)

Не забывайте, что минимакс и альфа-бета возвращают только лучшее значение, тогда как то, что вас интересует в реальной игре, - это движение. Прямо изменять их таким образом, чтобы они могли возвращать ход, но разработчик должен решить, как будет возвращен этот ход. Это связано с тем, что может быть много ходов, которые приводят к лучшему решению (вы можете вернуть первый, последний или самый общий, чтобы найти все ходы и вернуть случайный).

В вашем случае проблема заключалась в случайности возвращаемых значений, поэтому во время тестирования хороший подход заключается в устранении случайности.