18

我正在尝试用 alpha-beta 修剪为 Java 中的跳棋游戏实现 minimax。我的极小极大算法完美运行。我的代码使用 alpha-beta 代码运行。不幸的是，当我与标准 minimax 算法玩 1000 场比赛时，alpha-beta 算法总是落后 50 场左右。

由于 alpha-beta 修剪不应该降低移动的质量，只是实现它们所需的时间，所以一定是有问题的。但是，我已经拿出纸笔，画出了假设的叶节点值，并使用我的算法来预测它是否会计算出正确的最佳移动，并且似乎没有任何逻辑错误。我使用了这个视频中的树：Alpha-Beta Pruning来跟踪我的算法。它在逻辑上应该做出所有相同的选择，因此是一个有效的实现。

我还将打印语句放入代码中（它们已被删除以减少混乱），并且值正在正确返回它出现并且确实发生了修剪。尽管我尽了最大的努力，我还是无法找到逻辑错误的所在。这是我实现这一点的第三次不同尝试，他们都遇到了同样的问题。

我这里不能贴出完整的代码，太长了，所以我已经包含了与错误相关的方法。我不确定，但我怀疑问题可能出在非递归 move() 方法中，尽管我无法在其中找到逻辑错误，所以我只是在它中翻来覆去，可能会做一些事情没有押韵或理由，更糟而不是更好。

是否有从 for 循环中的递归调用中恢复多个整数值的技巧？它适用于我的 minimax 和 negamax 实现，但 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;
    }
}
4

5 回答 5

2

我注意到你说你发现了问题，但 minimax 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
于 2013-09-02T13:27:38.433 回答
2

2013年3月16日，sage88问：

是否有从 for 循环中的递归调用中恢复多个整数值的技巧？它适用于我的 minimax 和 negamax 实现，但 alpha-beta 修剪似乎会产生一些奇怪的结果。

在 alpha beta pruning 中，唯一感兴趣的输出值是节点的分数：min 节点中 beta 的最终值被认为是其父 max 节点的 alpha 值；同样，最大节点中 alpha 的最终值被考虑为其父最小节点的 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);
}
于 2014-12-12T00:34:47.180 回答
1

只回答你的问题

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

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

例如。

class ToBeReturned {
    int returnValue1;
    int returnValue2;
    int returnValue3;
}
于 2014-05-27T12:58:05.940 回答
1

你已经解决了你的问题，但是你遇到的问题很常见。因此，每当您为 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 只返回最佳值，而您对真实游戏感兴趣的是走法。可以直接修改它们以使其可以返回移动，但这取决于开发人员来决定如何返回移动。这是因为可能有许多动作会导致最佳解决方案（您可以返回第一个、最后一个或最常见的一个是找到所有动作并返回随机一个）。

在您的情况下，问题在于返回值的随机性，因此在测试期间，好的方法是修复随机性。

于 2015-10-16T02:19:53.573 回答
0

要获得下注修剪结果，您应该实施某种移动排序。在国际象棋中，它通常是捕获或检查。这些动作最容易改变评估，因此对剪枝有很大的影响。在跳棋中，它可能会在第 8 级上使用对手的石头或提升自己的石头（抱歉不知道使用的术语）。

于 2014-12-08T12:50:43.743 回答