Java Minimax Alpha-Beta 修剪递归返回

java recursion artificial-intelligence minimax alpha-beta-pruning

2022-09-02 22:34:34

我正在尝试在Java中为跳棋游戏实现alpha-beta修剪的minimax。我的最小最大算法工作完美。我的代码在 alpha-beta 代码就位的情况下运行。不幸的是，当我玩1000个游戏与标准的minimax算法时，alpha-beta算法总是落后50个左右的游戏。

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

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

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

答案 1

我注意到你说你发现了问题，但最小值的阿尔法测试版修剪不应该是

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

答案 2

2013年3月16日，sage88问道：

有没有从 for 循环中的递归调用中恢复多个整数值的技巧？它与我的最小值和负极值实现都工作正常，但是alpha-beta修剪似乎会产生一些奇怪的结果。

在 alpha beta 修剪中，唯一感兴趣的输出值是节点的分数：最小节点中 beta 的最终值被视为其父 max 节点的 alpha 值;同样，max 节点中 alpha 的最终值将考虑为其父最小节点的 beta 值。因此：

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

也就是说，您的实现中存在两个错误：1）正如Adrian Blackburn最初指出的那样，它错误地从最小节点返回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);
}