Alpha Beta修剪搜索未能最大限度地减少

我已经对井字变化（不完全相同的游戏）实现了minimax算法，并且它或多或少成功了。但是当试图实施alpha-beta修剪时，它不再有效。请在这里看到一个正确缩进副本：http://gist.github.com/lukealbao/f0b348788632ff96bace Alpha Beta修剪搜索未能最大限度地减少

（我不知道怎么的代码块，以便粘贴到并保留缩进。）

的score和getMoves功能测试，工作正常。前者返回一个绝对值介于0和7之间的整数，如果为最小化玩家得分则返回负值。（A 7是赢/输。）的getMoves函数返回对象的形式的数组：

{player: number, game: number}

player是表示玩家的位置的棋盘，并且game是表示播放机和对手的棋盘。由于这个版本的游戏工作方式，我们搜索每个玩家的动作，而不是简单地查看游戏状态的单个位图板。

这也是为什么每个递归调用alphaBeta都适用于对手而不是玩家。

除此之外，我认为这是非常标准的alpha-beta的东西。

问题：它不会返回最佳移动。在调试rootSearch函数时，我看到根级别的每个节点都具有相同的分数（通常得分/得分为7分）。结果是，搜索过于乐观。即使最小化者在下一步移动时有杀手，最大化AI也不会阻止，但会继续追逐自己的获胜动作。

我根本找不到问题所在。任何帮助表示赞赏。

来源

2015-01-26 Luke

您能否正确缩进您的代码以使其更易于阅读？ – kraskevich 2015-01-26 18:54:50

@ILoveCoding，你会介意看问题中的要点吗？我不知道如何缩进SO，除了每行的手动4个空格键点击之外。 – Luke 2015-01-26 18:59:50

这是一个错误，我发现（可以有更多）：

if (maximizer) { 
    ... 
    if (alpha >= beta) { 
     return beta; 
    } 
} else if (!maximizer) { 
    ... 
    if (alpha >= beta) { 
     return alpha; 
    } 
}

是错误的。它应该是：

if (maximizer) { 
    ... 
    if (alpha >= beta) { 
     return alpha; 
    } 
} else if (!maximizer) { 
    ... 
    if (alpha >= beta) { 
     return beta; 
    } 
}

来源

2015-01-26 18:58:14 kraskevich

好的。尽管如此，仍然存在同样的问题。（我更新了要点以包含此修复程序。） – Luke 2015-01-26 19:10:47

Alpha Beta修剪搜索未能最大限度地减少

回答

相关问题