五子棋游戏[4] – 人机博弈 – α-β剪枝及改进与总结

五子棋游戏[4] – 人机博弈 – α-β剪枝及改进与总结
继续填坑。按照计划,剪枝和改进总结本应该分为两次写,但是经过整理,发现剪枝部分的内容并不丰富,而改进与总结其实和剪枝一样,都是为了更快的搜索到一个比较优秀的解,故此我就在这一篇文章中全部写完。 在上一次的文章中我写了博弈类算法中最为重要的工具 – 博弈树的构造方式,并且描述了对其搜索的算法。另一方面也写了博弈算法的核心 – 状态评价的一种方案。经过上一次文章的描述,你应该已经可以写出一个可以和你进行玩耍的AI了,但是你会发现,和这个AI下棋,每一步都会很慢很慢,这种情况就是在提醒我们就需要考虑到搜索的效率了。 上一篇文章的博弈树搜索算法可以用这样一句话来评价:简单粗暴。没错,短短几行代码就完成了整个博弈的智能,但是对于搜索而言,简单粗暴并不意味着非常有效。我们可以来分析一下: 假设棋盘上的正中心已经下有一个棋子,那么棋盘上还有224个可以放置的点位,那么博弈树搜索的第一层就需要扩展224个状态节点; 接下来,每个状态节点都剩余223个可放置棋子的位置,所以需要继续扩展223个状态节点,所以第二层会存