Java Minimax Alpha-Beta修剪递归返回?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (268)

我正在尝试用Java的alpha-beta修剪来实现一个跳棋游戏的minimax。我的minimax算法完美运作。我的代码与alpha-beta代码一起运行。不幸的是,当我玩标准极小极小算法的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;
    }
}
提问于
用户回答回答于

只是回答你的问题

在for循环中从递归调用中恢复多个整数值有诀窍吗?

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

例如。

class ToBeReturned {
    int returnValue1;
    int returnValue2;
    int returnValue3;
}
用户回答回答于

我注意到你说你发现了这个问题,但不应该进行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

扫码关注云+社区

领取腾讯云代金券