Java Minimax Alpha-Beta修剪递归返回

Question

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

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

我还将print语句放入代码中(它们已被删除以减少混乱),并且正确返回值,并且修剪确实发生.尽管我付出了最大的努力,但我一直无法找到逻辑错误所在.这是我实现这一点的第三次尝试,所有这些尝试都有同样的问题.

我不能在这里发布完整的代码,它太长了,所以我已经包含了与错误相关的方法.我不确定,但我怀疑这个问题可能出现在非递归的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;
    }
}

Answer 1

您已经解决了您的问题，但您遇到的问题很常见。因此，每当你为人工智能代理构建算法的一部分时，你都必须对其进行正确的测试。因此，一旦您的极小极大算法正确，您就可以生成许多随机树并检查结果是否相同。例如，在 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)

不要忘记，极小极大和 alpha-beta 仅返回最佳值，而真正的游戏中您感兴趣的是一步棋。以可以返回移动的方式修改它们很简单，但这由开发人员决定如何返回移动。这是因为可能有很多移动可以导致最佳解决方案（您可以返回第一个、最后一个或最常见的移动是找到所有移动并返回随机移动）。

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