跳棋中的Alpha beta修剪（用于证明效率的测试用例）
我开发了一个使用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
我已经计算了游戏树的叶节点的启发式值，因为棋盘中剩下的机器碎片数量减去玩家对手碎片的数量，因为国王比棋子具有更强大的能力，启发式计算每个国王为两个正常值典当，使用哪个alpha beta搜索。
我猜我的程序工作正常，但是为游戏树的叶节点计算的启发式值最终不会改变，因为我将深度增加到9（如果我再增加深度，它可能会改变）。可以请任何人为我提供一些测试用例，使用它可以证明深度9内的效率？
你的问题是相当开放的，但这里有几点提示。
为叶节点计算的启发式值不依赖于搜索深度，因为它们是叶节点。 所以你的评论“为叶节点计算的值......没有改变”没有多大意义。 也许你的意思是根节点的值没有改变。
通常增加搜索深度会导致更好的移动。 如果您对所有搜索深度1..9获得相同的“最佳”移动，那么在某处存在错误。
评估功能是alpha-beta搜索解决方案中最重要的部分。 您需要一个更好的评估函数，而不是仅仅以简单的方式对材料进行计数，特别是如果您无法承受深度搜索。
通常人们不会使用纯粹的alpha-beta，而是使用主变量搜索，迭代加深，空移动启发式等方法来提高算法的实际效率。
构建你自己的测试用例，你知道什么是最好的举动，并验证你的算法能找到它。 例如，在你认识一名球员的最终比赛情况下，可以以三步赢得胜利。
上一篇: Alpha beta pruning in Checkers (test cases to prove the efficiency)