Java极小化极大算法Alpha-Beta剪枝递归返回

Question

我试图在Java中实现带有Alpha-Beta剪枝的极小化极大算法来玩跳棋游戏。我的极小化极大算法完美地运行。我的代码与已经放置好的alpha-beta代码一起运行。不幸的是，当我玩1000场对标准极小化极大算法的比赛时，alpha-beta算法总是输掉了50场左右。

由于alpha-beta剪枝不应该降低移动的质量，只减少它需要的时间，所以肯定出了什么问题。然而，我拿出笔和纸画了一些假想的叶节点值，并使用我的算法预测它是否会计算出正确的最佳移动，但似乎没有任何逻辑错误。我使用Alpha-Beta Pruning视频中的树来跟踪我的算法。从逻辑上讲，它应该做出所有相同的选择，因此是一个功能实现。

我还将打印语句放入了代码中（为了减少杂乱，已删除），并且返回的值似乎都是正确的，并且确实进行了剪枝。尽管我尽力了，但我无法找到逻辑错误所在。这是我第三次尝试实现这个算法，它们都有同样的问题。

我无法在此处发布完整代码，它太长了，因此我已包含与错误相关的方法。我不确定，但我怀疑问题可能在非递归move()方法中，尽管我找不到其中的逻辑错误，所以我只会在其中打转，可能会使情况变得更糟而没有任何理由。

从for循环的递归调用中恢复多个整数值有什么技巧吗？我的极小化和负极小化实现都可以正常工作，但alpha-beta剪枝似乎产生了一些奇怪的结果。

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

- sage88

---

跳棋有一个标准的起始位置，最小极大化算法和带有Alpha-Beta剪枝的最小极大化算法都是确定性算法，因此除非你在某个地方引入了随机性，否则每局游戏应该完全相同。也许这种随机性导致了结果的分歧。 - Kyle Jones

Minimax和带有Alpha-beta剪枝的Minimax在定义上应该会产生相同的结果，只是Alpha-beta剪枝可以更快地得到结果，这个“更快”取决于您的移动排序启发式算法的优良程度。因此，测试您的Alpha-beta实现的方法是在大量局面下运行带有和不带有Alpha-beta剪枝的Minimax，并验证两个版本产生相同的结果。 - Kyle Jones

我发现问题实际上是由于我的极小化极大算法从最好的相等移动中返回一个随机移动，而我的Alpha-Beta剪枝算法只返回第一个被考虑的最佳移动（因为我的实现方式无法找到相等的移动）。在开始时，棋盘边缘的移动在第3层得分相同，但实际上更差，但它是Alpha-Beta剪枝的第一个选择，因此被返回。因此，在这种情况下，从最佳移动中选择一个随机移动比仅选择第一个移动更好。感谢您的帮助。 - sage88

如果您已经找到了这个问题的解决方案，您可以自己回答它，如果您愿意的话。 - Christian Ammer

Answer 1

我注意到你说你找到了问题，但不应该是最小最大Alpha Beta剪枝吗？

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

- Adrian

---

不，你在那里返回beta，因为它是截止点。如果alpha超过它，那么你不想考虑它，因为其他玩家永远不会让你走这步棋。有关此内容的更多信息，请参阅Alpha-Beta剪枝的维基百科文章http://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning。我知道这是正确的代码，因为它已经针对其他40个极小化算法运行并排名第二。 - sage88

然而，从最小节点返回alpha是不正确的。最小节点总是将其最终beta返回给其父max节点以作为新的alpha进行考虑。 - gknicker

Answer 2

2013年3月16日，sage88提问：

在for循环中，从递归调用中恢复多个整数值是否有技巧？ 我的极小化和极大化实现都能正常工作，但alpha-beta剪枝似乎产生了一些奇怪的结果。

在alpha beta剪枝中，唯一感兴趣的输出值是节点的分数：min节点中beta的最终值被视为其父max节点的alpha值；同样地，max节点中alpha的最终值被视为其父min节点的beta值。因此：

你的问题的答案就是算法本身，因为它是最相关的技巧。

话虽如此，在你的实现中存在两个错误：1）正如Adrian Blackburn最初指出的那样，它错误地从min节点返回alpha，从而扭曲了它的准确性；2）它通过过早地考虑当前节点的父alpha或beta而放弃了修剪机会。这个版本修复了返回值并最大化了修剪：

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

- gknicker

---

嘿，感谢您发布这个。这是一个非常古老的项目，我需要找出来看一下。 - sage88

当然，这很有趣。我想看看我是否能在这么长时间后为您的问题提供一个可接受的答案 :) - gknicker

Answer 3

你已经解决了问题，但你遇到的问题非常普遍。因此，每当你为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)

---

不要忘记，minimax和alpha-beta只返回最佳值，而在实际游戏中你需要的是一个移动。可以方便地修改它们以返回移动，但这取决于开发人员决定如何返回移动。这是因为有许多移动导致最佳解决方案（可以返回第一个、最后一个或找到所有移动并返回随机移动）。在你的情况下，问题出在返回值的随机性上，所以在测试期间好的方法是固定随机性。

- Salvador Dali

Answer 4

仅回答你的问题：

从for循环中的递归调用中恢复多个整数值有什么技巧吗？

是的，在Java中，您需要将一个对象传递到递归函数调用中，然后修改该对象的内容。在函数返回后，您将能够访问修改后的值。

例如：

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

- DanLatimer

Answer 5

为了获得最佳的剪枝结果，您应该实现某种移动排序。在国际象棋中，通常是吃子或将军。这些类型的移动往往会改变评估值，因此它们对剪枝有很大的影响。在跳棋中，可能是拿走对手的棋子或在第8排晋升自己的棋子（抱歉不知道使用的术语）。

- Ales Dolecek