基于Python实现的Alpha-Beta剪枝算法

我就是我 2024-04-06 10:08 61阅读 0赞

## 实现 Alpha-Beta 剪枝 ##

Alpha-Beta

Alpha-Beta 是在 MINIMAX 的基础上进行了剪枝操作，遍历的树更少，却也能得到相同的决策，在实现算法时候遇到了小坑，如下所示：

![在这里插入图片描述][62b444327cfc46e58022d06fef3c5e33.png]

图 1 不同的伪代码 两个伪代码的不同处在于画红线的地方，在 mini 中对 alpha 的判断。经过手动推演+程序运行证明左边的代码是正确的。

遇到的问题：

alpha 和 beta 的定义

在最开始的时候没有完全理解算法的含义，将这两个变量全都定义成了全局变量，这也导致了之后判断的错误。因为虽然有时，顶层的 alpha 或 beta 和最底部的 alpha、 beta 值是一样的，但是他们并不是由于直接同步而相同的。在递归回溯的过程中，存在一个值一层层向上传递的过程，而在这个过程中就存在值修正的问题：你最开始得到的值并不就是最终的结果。并且在正常情况下，后续节点的 alpha 或 beta 将会和之前节点的进行比较，进行修正，而当设置全局变量后，后续节点直接就得到了 alpha 和 beta 的值，这样步骤颠倒势必会导致结果错误。

在顶层需要添加的 action 记录

当程序在 MIN 或者 MAX 层递归运行的时候，由于其目的只是找到最小值或最大值就可以了，因此照搬伪代码就。但是当到了 MAX 顶层的时候，需要进行 action 选择的决，决策的依据就是 alpha 最大值的选择。由于之前的代码只会评判出最大值是谁，而评判不出最大值在哪，因此需要在最顶层的时候有一个 action 的记录，即当更新得到更大的 alpha 的时候，同样也更新导致这个变化的 action。最终就可以返回这个 action 作为正确的选择路径了。

结果展示解决完上述问题后，就可以通过所有的测试了，结果展示如下图所示：

![在这里插入图片描述][b58c5dd4356141f4ad992c80782218ce.png]

图 2 运行 python autograder.py -q q3 --no-graphics 的结果展示 最终运行的结果还是和上次一样，也确实，毕竟 Alpha-Beta 算法只是对 MINIMAX 进行剪枝，不会改变选择的结果。

算法时间比较 这里我直接用的 autograder 运行 q1 和 q2，来看运行时间的不同，结果如下：

![在这里插入图片描述][432e487ce6b94e7a912ab952c2164428.png]  
![在这里插入图片描述][157acdf378b446a8b3d31a22d4b19756.png]

图 3 q3 的运行时间

![在这里插入图片描述][ca86d6c70c3e4f0fbf444b5383efdb5f.png]  
![在这里插入图片描述][47afe18c56d9483987b4cda44972bb43.png]

图 4 q2 的运行时间

从上图可以明显看到，使用 Alpha-Beta 的时候，运行时间只用了 1 秒，而运行 q2 的时候用了 2 秒…好吧，并不明显…主要是因为默认似乎都是两层递归的原因，如果需要加深一下层数就能能看到更明显的差异了。

尝试了一下使用递归层数为 5 层的两种算法，差异立刻就体现出来了，在使用 AlphaBeta 的时候，能以肉眼可见的速度进行移动，到了 Minimax 的时候，等他动一步的时间可以泡杯茶了…由此可见算法速度着实提升了。

![在这里插入图片描述][6579fe184a234e92ab08bca4c1018c33.png]

图 5 使用深度 5 来测试两种算法

[62b444327cfc46e58022d06fef3c5e33.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/80ec6e3ee61d4e5c8af3f55c4d3f2944.png
[b58c5dd4356141f4ad992c80782218ce.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/61fda66e447a46dc80435262e6ac9f99.png
[432e487ce6b94e7a912ab952c2164428.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/988b48093c084ca4b04d0f23e11b760f.png
[157acdf378b446a8b3d31a22d4b19756.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/49a0294181bc4ed3a22773677f275432.png
[ca86d6c70c3e4f0fbf444b5383efdb5f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/a7258888b6d34fe08b48bf78016c23b6.png
[47afe18c56d9483987b4cda44972bb43.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/b67a1f2cb3364f0181fe3e66acd7d167.png
[6579fe184a234e92ab08bca4c1018c33.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/08c4a5f09e9a42918b16faaa07b06698.png