我制作了一个游戏（Connect-4），并使用了MinMax算法和Alpha-Beta剪枝来实现计算机AI。有什么好的方法可以测试我的Alpha-Beta是否正确？我不确定它的正确性，有时在与我的AI对战时，它不会进行使游戏时间更长的操作，即使它已经看到了更深层次的失败，而且当它开始搜索时，手动检查和单元测试很困难（只搜索7-9步）。如何解决这个问题？（如果Alpha-Beta剪枝掉了某些可以更难获胜但是不失败的东西，我知道这一点）
使用Alpha-Beta剪枝测试MinMax算法和游戏策略
5
- Mbentt
3
这是 Floyd-Warshall 算法吗？ - Micromega
不，Floyd算法主要是用于找到带有权重的图中最短路径的。也许可以将问题转换为Floyd算法，但这是标准的MinMax算法与阿尔法-贝塔剪枝的结合。链接 - Mbentt
1我不熟悉Connect-4（作为程序）。你是在寻找确定性值（胜利/失败/平局），还是有一种启发式方法（评估）？ - H H
1个回答
3
Alpha-beta剪枝只是基本MiniMax算法的优化（即排除敌方肯定不会走的路径），因此我会将alpha-beta算法的结果与简单的MiniMax算法进行比较。一旦它们产生分歧，你就会发现两种算法中的一个有错误。
这简化了问题，可以测试你的MiniMax算法是否正确，我想不出任何特殊的技巧 - 但由于它是一个递归函数，应该可以为所有情况编写单元测试。
- Voo
4
然后，除了移动的值之外，人们还必须选择某种排序方式来比较MiniMax和Alfa-Beta之间的差异，否则Alfa-Beta可能会剪枝MiniMax选择的移动。实际上，即使是像Connect-4这样简单的游戏，我也必须使用截断函数，因此我不知道这个测试如何工作，因为由于树中节点的数量，无法搜索到Minimax的底部。 - Mbentt
一个带有AlphaBeta的MiniMax应该能够找到与没有修剪的搜索相同的_score_变体，但不一定是相同的移动链。这是测试的基础，但我认为您需要挑选相当多的测试用例才能获得一些信心。 - H H
只要你对两个算法使用相同的启发式，它就不会影响结果。是的，你只能降落在具有相同分数的节点上 - 尽管我认为只要你按照相同的顺序访问节点，并让极小化始终选择第一条路径（即 alpha beta 也会找到的路径），那么你应该会降落在相同的节点上（嗯，乍一看我认为这是一个有效的假设，但可能存在边缘情况）。而且由于 Alpha-beta 只是扩展了极小化，如果移动的顺序发生变化，那将是令人惊讶的。 - Voo
好的，我要关闭这个并接受没有“标准方法”可以在没有相当多的人工交互的情况下完成这个。 - Mbentt
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接