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

假设棋盘上的正中心已经下有一个棋子,那么棋盘上还有224个可以放置的点位,那么博弈树搜索的第一层就需要扩展224个状态节点;
接下来,每个状态节点都剩余223个可放置棋子的位置,所以需要继续扩展223个状态节点,所以第二层会存在224 * 223个状态节点;
依次类推,第三层会有224 * 223 * 222个状态节点;
第四层会有224 * 223 * 222 * 221个状态节点
……

那么如果我们就算到第四层,总共需要搜索到:
224 + 224 * 223 + 224 * 223 * 222 + 224 * 223 * 222 * 221 = 2 461 884 544
呵呵了。每次都要搜索如此多的状态节点,这样的开销是十分可观的,因此,我们提高效率的方式就锁定到了:如何减少需要搜索的状态节点。
α-β剪枝就是一种博弈算法中最常用的剪枝算法,这个算法是被数学方法证明的,所以并不限制于具体的问题。不同于一般的教材,我想先给大家看代码,下面是上次给出的搜索算法:

这里是添加了α-β剪枝的搜索算法:

只是增加了很简单的一小段代码,这一小段代码可以让程序停止进行无意义扩展,我不是很喜欢书上的定义,但是这里我还是先贴出来给大家端详一下:

α剪枝
若任一极小值层节点的β值小于或等于它任一先辈极大值居节点的α值,即α(先辈层)≥β(后继层),则可中止该极小值层中这个MIN节点以下的搜索过程。这个MIN节点最终的倒推值就确定为这个β值

β剪枝
若任一极大值层节点的α值大于或等于它任一先辈极小值层节点的β值,即α(后继层)≥β(先辈层),则可以中止该极大值层中这个MAX节点以下的搜索过程。这个MAX节点的最终倒推值就确定为这个α值。

这两段绕口令一样的描述就是对α-β剪枝的描述,其实α-β剪枝是一个很容易理解的概念,用大白话来讲就是这样:

我已经知道了一种下法A一定比这种下法B好,那下法B就根本没必要去研究了。

还想更形象?用一个不恰当的比喻:

明知道女友想要钻石,那就没必要去纠结挑什么糖果送给她的问题了。

下面有个图可以不错的描述整个剪枝过程:

剪枝

我简单说两下:
带圈的数字代表搜索节点的次序(博弈树的搜索是DFS哦);
最底层的数字代表状态评估值,可以认为数字越大,对自己越有利,数字越小,对对方越有利。

1. 找到第一个状态节点,返回估价为0给上一层
2. 这样的话,上一层节点在扩展完其他节点之前就会知道,自己的估价值肯定不可能比0更高(因为要选择最小的~)
3. 扩展了第二个状态节点,返回估价为5
4. 此时上一层节点已经扩展完所有的子节点,因此按照博弈树的原则,自己的估价就是0啦,所以把这个值返回给再上一层
5. 再上一层获得了这个返回值之后就会明白,自己的估价肯定不会低于0的(因为它要选择子层中最大的),那么继续扩展
6. 底层节点返回了-3
7. 上一层节点就知道自己肯定会小于-3,然后瞅瞅再上一层节点,人家告诉你它不会低于0的,因此后面的搜索就没有必要进行了,直接返回就成了
8. 再上一层节点的估价确定为0,继续返回给上层
……

我就写到这里,后面的步骤请大家按照这个思路继续演练下去~你就会对整个剪枝过程有比较深的理解啦,这时候再翻过来看我写的代码,如果你之前还有些糊涂的话,相信现在也会豁然开朗了~
从那个例子我们就可以看出来,剪枝可以使搜索量大大减少,应用了这个算法过后,再运行我们的AI,我们就会发现它的速度明显的提升了,但是仅仅这样还是远远不够的。
在本文章的末尾,我将附上我的五子棋程序(不好意思,只是半成品>_<,但是可以玩耍哦),里面的注释很详尽,使用的就是我的这个系列文章所描述的方法,在我的代码中,我使用了下面两种方法来进一步提升效率:

1. 每次搜索仅搜索落子点周围一格范围内存在棋子的位置
这样可以避免搜索一些明显无用的节点,而且可以大幅度提升整体搜索速度。
2. 当搜索过程中出现了必输或必胜棋的时候直接返回不再搜索
当出现必输或必胜的局面的时候,继续搜索时没有必要的,直接返回当前棋局的估价值即可。

迫于时间精力,还有一些我想到的搜索优化的方法,通过这些方法可以大幅度提高算法的时间效率和CPU的利用率甚至是AI的智能,如果你想进一步研究,可以参考:

1. 随机化AI的下棋方式
目前算法对于给定的玩家下棋方式会给出固定的回应,这就导致玩家获胜一次之后只要此后每次都按此方式下棋,都能够获胜。为了避免这种情况,可以在AI选择下子位置的时候,在估值相差不多的几个位置中随机挑选一个进行放置,以此增加AI的灵活性。
2. 保存每次搜索的3 ~ LIMIT_DEPTH层的结果
当AI下子的时候,会向下搜索各种状态,当AI再次下子的时候,有些状态是会出现在之前搜索过的结果之中的,可以通过保存这些已经搜索过的结果,来使扩展的节点数进一步减少,提高搜索的效率。
3. 多线程
当搜索下一层的时候,可以将每一分支分配给一个线程,让多个分支并行进行运算,提高CPU的使用效率,进一步增加搜索效率。
4. 规划搜索顺序
目前搜索的时候是从棋盘“左上”至“右下”搜索的,实际上很多更有价值的下子点存在于更靠近棋盘中央的地方,如果从棋盘中央向外搜索的话,则能够提高α-β剪枝的效率,让尽可能多的分支被排除。
5. 学习
目前算法的智能一方面取决于搜索的层数,另一方面更多的取决于静态估值函数的好坏,而对于静态估值函数的设定则取决于设计者的主观意志,如果令程序在胜利或失败后,回溯博弈树中的棋局,并据此不断调整静态估值函数,则可令程序具备学习能力,这样就能进一步增强其智能。

五子棋游戏的下载地址:点击我>_<!!!

2
说点什么

2 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
  Subscribe  
最新 最旧 得票最多
提醒
Anonymous

非常感谢

Anonymous

非常感谢