algorithm - Checkers 中的 Alpha beta 修剪(测试用例以证明效率)

Question

我开发了一个使用 alpha beta 修剪的并行跳棋(英式跳棋)游戏，以便找到机器可以做出的最佳 Action 。我想知道增加博弈树的深度/级别并使用 alpha beta 修剪算法对其进行搜索是否一定会演化出最佳可能的着法？

我在一台低级别的机器上运行，我无法将深度加起来超过 9。我已经使用以下测试用例检查了我的程序，但考虑到深度，我得到了相同的可能移动1至9如下。

case 1
+B+B+B+B
B+B+B+B+
+B+B+B+B
O+O+O+O+
+O+O+O+O
A+A+A+A+
+A+A+A+A
A+A+A+A+           output: (5, 0) => (4, 1)

case 2
+B+B+B+B
O+O+B+B+
+O+O+B+B
O+B+O+O+
+O+O+O+O
A+A+A+O+
+O+O+O+O
O+O+O+O+           output: (5, 2) => (4, 3)

case 3
+O+O+O+O
O+O+O+O+
+B+O+O+O
O+O+O+O+
+B+B+O+O
O+A+A+O+
+O+O+O+O
O+O+A+A+           output: (5, 2) => (3, 4)

case 4
+k+O+O+O
O+B+O+O+
+O+O+O+B
O+O+O+B+
+O+O+B+O
O+O+O+O+
+O+O+O+O
A+A+A+A+           output: (0, 1) => (2, 3)

case 5
+B+B+B+B
O+O+O+O+
+O+O+O+O
O+O+O+O+
+B+B+K+O
O+A+O+O+
+O+O+O+O
A+A+O+A+           output: (5, 2) => (3, 0)

case 6
+k+O+O+O
B+O+O+O+
+O+O+O+O
O+O+O+O+
+O+O+O+O
O+O+O+O+
+O+O+O+O
O+O+O+O+           output: (0, 1) => (1, 2)

解释在哪里，

O- Empty dark square
+- Empty white square
A- Machine's pawn
B- Opponent's pawn
k- Machine's king
K- Opponent's king

我计算了游戏树叶节点的启发式值，即棋盘上剩余的机器棋子数减去玩家对手棋子数，因为国王的能力比棋子更强大，启发式计算每个国王作为两个普通棋子，使用它应用 alpha beta 搜索。

我想我的程序运行良好，但是为博弈树的叶节点计算的启发式值最终并没有随着我将深度增加到 9 而改变(如果我进一步增加深度它可能会改变)。任何人都可以提供一些测试用例来证明深度 9 内的效率吗？

Answer 1

你的问题很开放，但这里有一些提示。

1. 为叶节点计算的启发值不依赖于搜索深度，因为它们是叶节点。所以你的评论“为叶节点计算的值......没有改变”没有多大意义。也许你的意思是根节点的值没有改变。

2. 通常增加搜索深度会导致更好的着法。如果您对所有搜索深度 1..9 都获得了相同的“最佳”着法，则某处存在错误。

3. 评估函数是 alpha-beta 搜索解决方案中最重要的部分。您需要一种比仅以简单方式计算 Material 的评估函数更好的评估函数，尤其是在您负担不起深度搜索的情况下。

4. 通常人们不使用简单的 alpha-beta，而是使用主变搜索、迭代加深、空移动启发式等方法来提高算法的实际效率。

5. 构建您自己的测试用例，在其中您知道最佳着法实际是什么，并验证您的算法是否可以找到它。例如，您知道一名玩家可以三步获胜的残局情况。