首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >Java Minimax Alpha-Beta剪枝递归返回

Java Minimax Alpha-Beta剪枝递归返回
EN

Stack Overflow用户
提问于 2013-03-16 17:20:05
回答 5查看 19.9K关注 0票数 18

我正在尝试为Java中的一个跳棋游戏实现带有alpha-beta剪枝的minimax。我的极大极小算法工作得很好。我的代码与alpha-beta代码一起运行。不幸的是,当我玩1000场游戏而不是标准的极大极小算法时,alpha-beta算法总是落后50场左右。

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

我还在代码中加入了print语句(为了减少混乱,这些语句已被删除),并且返回的值正确无误。尽管我尽了最大的努力,我还是找不到逻辑错误所在。这是我第三次尝试实现它,所有的尝试都有相同的问题。

我不能在这里发布完整的代码,因为它太长了,所以我已经包含了与错误相关的方法。我不确定,但我怀疑问题可能出在非递归的move()方法中,尽管我找不到它中的逻辑错误,所以我只是在它周围翻来覆去,可能会让事情变得更糟,而不是变得更好,而不是没有理由。

循环中,是否有从递归调用中恢复多个整数值的技巧?它在我的minimax和negamax实现中都工作得很好,但α-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;
    }
}
EN

回答 5

Stack Overflow用户

回答已采纳

发布于 2015-10-16 10:19:54

您已经修复了您的问题,但您遇到的问题非常常见。因此,无论何时为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只返回最优值,而您对真正的游戏感兴趣的是一步棋。修改它们的方式很简单,这样它们就可以返回一个移动,但这要由开发人员决定如何返回移动。这是因为可能有许多步可以导致最佳解决方案(你可以返回第一步,最后一步,或者最常见的一步是找到所有的步并返回随机的一步)。

在您的例子中,问题出在返回值的随机性上,所以在测试期间,最好的方法是修复随机性。

票数 1
EN

Stack Overflow用户

发布于 2013-09-02 21:27:38

我注意到你说你发现了问题,但最小最大αβ剪枝不应该是

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
EN

Stack Overflow用户

发布于 2014-12-12 08:34:47

2013年3月16日,sage88询问:

有没有在循环中从递归调用中恢复多个整数值的技巧?它在我的minimax和negamax实现中都能很好地工作,但α-beta修剪似乎会产生一些奇怪的结果。

在alpha beta剪枝中,唯一感兴趣的输出值是节点的得分: min节点中的beta的最终值被视为其父max节点的alpha值;同样,max节点中的alpha的最终值被视为其父min节点的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);
}
票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/15447580

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档