Java Minimax Alpha-Beta剪枝递归返回
Java Minimax Alpha-Beta剪枝递归返回
提问于 2013-03-16 17:20:05
我正在尝试为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;
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/15447580
复制相关文章
相似问题