Java Minimax Alpha-Beta 修剪递归返回

Question

我正在尝试为 Java 跳棋游戏实现带有 alpha-beta 剪枝的 minimax。我的 minimax 算法完美运行。我的代码使用适当的 alpha-beta 代码运行。不幸的是，当我与标准 minimax 算法进行 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

我注意到你说你发现了问题，但 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