Beta修剪递归返回
我正在尝试用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;
}
}
我注意到你说你发现了这个问题,但不应该进行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
只是回答你的问题
在for循环中从递归调用中恢复多个整数值有诀窍吗?
是的,在Java中,您需要将对象传递给递归函数调用,然后修改该对象的内容。 函数返回后,您将能够访问修改后的值。
例如。
class ToBeReturned {
int returnValue1;
int returnValue2;
int returnValue3;
}
2013年3月16日,sage88问道:
在for循环中从递归调用中恢复多个整数值有诀窍吗? 它适用于我的minimax和negamax实现,但alpha-beta修剪似乎产生了一些奇怪的结果。
在alpha beta修剪中,唯一感兴趣的输出值是节点的分数:min节点中beta的最终值被认为是其父节点的最大节点的alpha值; 同样,最大节点中alpha的最终值被认为是其父节点的beta值。 因此:
您的问题的答案是算法本身,因为它是最相关的技巧。
也就是说,在你的实现中有两个错误:1)正如Adrian Blackburn最初指出的那样,它不正确地从一个最小节点返回alpha,反之亦然,从而扭曲了它的准确性; 2)通过过早地考虑当前节点的父值或贝塔值,放弃修剪机会。 该版本修复了返回值并最大限度地修剪:
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);
}
链接地址: http://www.djcxy.com/p/56307.html