1

我开发了一个使用 alpha beta 剪枝的并行跳棋（英语选秀）游戏，以便找到机器可以做出的最佳移动。我想知道增加游戏树的深度/级别并使用 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

我计算了博弈树叶节点的启发式值，即棋盘中剩余的机器棋子数减去玩家对手的棋子数，因为国王的能力比棋子强大，启发式将每个国王视为两个正常pawns，使用它应用 alpha beta 搜索。

我想我的程序运行良好，但是当我将深度增加到 9 时，为游戏树的叶节点计算的启发式值最终没有改变（如果我进一步增加深度，它可能会改变）。任何人都可以请提供一些测试用例，我可以使用它们来证明深度 9 内的效率？

4

1 回答 1

0

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

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

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

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

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

  5. 构建您自己的测试用例，您知道实际上最好的移动是什么，并验证您的算法是否可以找到它。例如，您知道一名玩家可以在三步中获胜的最终游戏情况。

于 2014-01-05T13:16:01.683 回答