 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
[精品论文]参考文献资料--五子棋中alpha-beta搜索算法的研究与改进
下载积分：1000
内容提示：[精品论文]参考文献资料--五子棋中alpha-beta搜索算法的研究与改进
文档格式：PDF|
浏览次数：9|
上传日期： 18:12:27|
文档星级：
该用户还上传了这些文档
[精品论文]参考文献资料--五子棋中alpha-beta搜索算法
官方公共微信 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
五子棋中Alpha-Beta搜索算法的研究与改进.pdf
下载积分：800
内容提示：五子棋中Alpha-Beta搜索算法的研究与改进.pdf
文档格式：PDF|
浏览次数：1|
上传日期： 08:13:17|
文档星级：
该用户还上传了这些文档
五子棋中Alpha-Beta搜索算法的研究与改进.pdf
官方公共微信2666人阅读
【目标】使用cocos2d编写一个简单的五子棋程序
2、TestCpp工程
3、（虽然是VB，但是写的很好）
4、&（这书其实很一般）
& & & & 9月份颓废了好一阵子，下旬的时候才重新上阵，看到周围的同事在玩五子棋，就忍不住自己也写了一个，写了半个多月。现在算是一个还算拿得出手的小作品。这里总结一下。
一、五子棋游戏框架
& & & &作为一个只有一个棋盘和两种棋子的游戏来说，如果单纯只是一个人类选手对战的五子棋平台，那么整个架构比起扫雷来说复杂不了多少。
& & & &但是这次却是我写过最复杂的一个程序了，其复杂性主要在于引入了AI。整体的架构如下：
& & & & 对这张图做一些解释：
<span style="font-size:18 color:#、界面部分
& & & 抽象分层使用cocos的scene——layer——sprite机制，出于对于逻辑管理与图像处理混搭的恐惧症状，在本部分只集中管理UI，将逻辑处理部分抽象到了辅助层中。
<span style="font-size:18 color:#、辅助工具部分
& & & 主要包括两个工具：
& & & 一是回合管理。五子棋是两个棋手轮流下，途中可能发生走棋、悔棋、投降、胜利等等情况。另外开始的时候还要设置两个棋手的身份：是不是AI？总之，将这一部分的逻辑处理集中到了 playerController中，而 Gamelayer 继承了这个类，是在实际游戏过程中的回合管理者。
& & & 二是触屏管理。在“8.自己的触屏管理——添加ClickManager”里面我就提到过这个东西。这次总体变化不大，只是优化了一下代码。需要接受触屏事件的类，只需要持有一个ClickDelegate变量，然后自己继承一下ClickListener就可以。总体机制类&#20284;于android中的onClickListener。
<span style="font-size:18 color:#、AI部分
& & & 这是本次架构比较失败的一块，只要是写单实例的时候，没有考虑游戏重启的情况，后面改BUG的时候偷懒就没有调整接口。
& & & ComputerPlayer是供外部调用的接口部分，他主要承担两个功能：一是扮演电脑玩家，和玩家对弈；二是充当裁判，判定是不是已经胜利。
& & & 而这些功能，算法实际上是由computerIntellegence（以下简记为CI）实现的。CI会调用Evaluator来评估场上局势，从而获取最佳的落子点，或者判断是不是已经获胜。
& & & 至于评估的依据，则是来源于MapHelper中记录的数据，这里记录的数据主要有：用一个二维数组记录了地图上所有点的情况，另外用两个vector记录了两个玩家的落子记录。点和方向的数据结构则是由Point 和 &Direction 两个类提供。
& & &另外在评估局势的时候，需要根据棋型打分。棋型的信息，由shape类提供
二、cocos2D-x中的多线程
& & 由于AI计算最佳落子点耗时比较久，不能放在UI线程来做，所以需要使用多线程。这里主要参照《》一文实现，简单说就是
& & 1、添加pthread头文件依赖
& & 2、添加pthread库依赖
& & 3、使用pthread即可
& & 在移植到android的时候，倒是不需要做任何特殊的处理，毕竟linux一般都是带pthread的。
三、在界面处理中，在本程序过程中学习到的技术
& & & 界面使用CCTMXTiledMap来实现，没有太多的难点。这里主要记录一些可能会遇到的问题。
<span style="font-size:18 color:#、label文字的刷新
& & & 由于一般的CCLabelTTF在setSttring的时候，实际上需要重新创建一个新的&CCLabelTTF，代价太大，所以一般来说，如果可以预见到这个label需要改变内容，是不推荐使用CCLabelTTF的。根据实际情况，有以下两种选择。
& & &1）UI线程上的刷新：如果是只是需要在UI线程上刷新文字，那么可以参考cocos中帧率显示的机制，使用CCLabelAtlas，初始化的时候，指定一个字体文件，在需要改变的时候，使用setString即可，不过我在实际使用的时候，发现如果初始化的时候设置字符串为空字符串的话，后续可能不能显示，所以开始最好还是先把位置占好。
& & &2）非UI线程上的刷新：上面的方式基本可以满足大多数的需求，但是在某些机器上（谨慎怀疑和显卡有关），如果在非UI线程上，使用上面的更新方式，可能会在运行的时候，报出“This&application&has&requested&the&Runtime&to
terminate it in an unusual way”的告警信息，并导致程序崩溃。可能是由于openGL绘制是不能在非UI线程上进行的。
& & &我这里给出一种规避方案。以我这里的需求为例，label字样内容需要在BLACK和WHITE两种中进行切换，那么事先就干脆创建两个label，一个是WHITE，一个是BLACK，两个重合放置，通过setVisible隐藏其中的一个来达到需求。由于setVisible只是设置一个标志位，并通知UI线程界面数据脏，所以并不会引发问题。当然代价就是需要多创建部件。
<span style="font-size:18 color:#、界面中，子布局获取父节点的引用
& & &我以前写的代码中，在需要获取父节点的引用时，通常都是在构造函数中传入，一来是交叉引用，二来不能使用默认的CREATE_FUNC宏，也比较麻烦。实际上，可以通过getParent来获取父节点的引用，不过代价是需要用cast进行类型转换，过多的类型转换当然也不是好的编码风&#26684;。
<span style="font-size:18 color:#、menu的元素间隔设置
alignItemsVerticallyWithPadding(float padding)
<span style="font-size:18 color:#、cocos中输出LOG
& & &cocos2d::CCLog，要在win32下输出还需要在main中打开调试宏，这个LOG是平台兼容的，比我自己写的好多啦。
<span style="font-size:18 color:#、几个很有用的类
& & 1）CCLayerMultiplex：实现layer切换，Test程序中大量用到，这样不需要切换Scene也可以进行布景切换
& & 2）CCMenuItemToggle：类&#20284;于combo-button，可以从多个选项中选取一个，当前的&#20540;，可以通过
dynamic_cast&CCMenuItemToggle*&(pSender)-&getSelectedIndex();
& & 来获取
四、简单的AI设计
& & &总体来说，有了前面的扫雷和音乐炫台的设计，五子棋的UI设计还是很简单的，这次的重心是AI的设计。
<span style="font-size:18 color:#、AI的总体流程
& & 当轮到AI行动时，AI首先获得所有可以下的点。然后对其中的每一点，进行试探和评估，最终从中选出得分最大的点，作为自己的落子点。
& & 这里有两个最核心的点：试探、评估。下面分开来评述。
<span style="font-size:18 color:#、评估函数
& & 评估解决的问题是，给定两个棋局，判定哪一个形势更好。
& & 这个评估函数需要满足几个条件，好适应后面的MIN-MAX算法：首先要只和当前形势有关，和未来局势无关，这样就不需要附加信息。其次要同时和双方相关，这样无论是MIN还是MAX来调用，都可以获得同样的结果。
& & 这里采用了一个简单的方法：对一个指定的棋子来说，他的得分是和他所在的棋型有关的。比如说，如果他在一个五连当中，那立刻就赢了，就给他50000分；他如果横向冲四，纵向也冲四，那构成一个双四，给他10000分；依次类推。
& & &而对于一方势力来说，其得分就是他最高的那个棋子得分。而对于整个局势来说，得分就是双方得分的差&#20540;。
& & &需要注意的一点，由于一个棋子需要同时观察四个方向：横、竖、左上到右下、左下到右上。那么有质变性的棋型得分，就应该至少相差4倍。例如五连和活四，由于五连是立刻取胜，所以比活四高一个档次，那么得分至少要是活四的四倍。这样才能保证当有点A，在四个方向同时构成活四，另一个点B直接构成五连的时候，点B的评分更高。
<span style="font-size:18 color:#、min-max
& & 有了估&#20540;，下面来研究试探。简单来说，就是走几步，然后来进行一次评估，看这几步走的怎么样，最终选出一种最好的下法。
& & MIN-MAX是基于深度搜索的一种简单博弈算法，他的思想是，双方都想会选最好的落子点。比如两个棋手A和B，局面估分是用A的得分减去B的得分，即
& &那么，当轮到A下的时候，他就会选使得得分最高的那个点来下：
A'(1) : max {V(1, 0) = A(1) - B(0)}
& &这个符号表达可能不规范，意思是最终选取的 A 的第一步（记为 A'(1)），是使得 A(1) - B(0) 得分最高的那个点。
& & 但是这个选择可能是不好的：因为没有考虑B的应对。如果考虑下面的场景（O是A的子，X是B的子，_是空&#26684;，左上角为(1, 1)点）
& &当前A的得分是活二 100分，B的得分是活三415分，如果A选择自己连成活三的话，那么局面估&#20540;就是0分，如果选择堵B的话，那么得分就是活二减去冲三，在我的程序中得分是 100 -&210 = -110分，所以A应该选择自己连成活三。
& & 不过显然，这是不正确的，因为无视了B的应对：如果不堵B的话，那么下一步B就会形成活四，那么此时的局面得分是 &415 - 10000 = -9585，而如果堵B的话，那么得分可能会是 活二减去冲四，得分是 100 -&450 = -350。所以如果考虑B的应对的话，应该堵B，这也和我们人自己的认识是一样的。
& &那么如何去考虑B的应对呢，可以认为，无论A选择了什么棋，B都会在A下过之后，选择对B最有利的那个点来下，就是
B'(1) : min { V(1, 1) = A(1) - B(1) }
& &所以如果考虑B的应对，A的策略应该是：
A'(1) : max { V(1, 1) = A(1) - B'(1) }
& &两者一综合，就是
A'(1) : max {
min{ A(1) - B(1) } }
& &即取最大的那个最小&#20540;。
& &这个循环可以一直不停地继续下去，B的行动也需要考虑A的应对。这里的B就是MIN选手，A就是MAX选手。
& &用状态空间树也可以表征这个过程。如果把双方的选择路径用树来表示，那么可能是这样的
& &这里考虑3步棋，那么如果A选择了第一步落在 A-1 点，B会落在哪一点呢？如果B落在 B-1 点，那么相应的A就会选择 A-12点，得分是100分，如果落在 B-2 点，A只能下在 A-13点，得分也是100分。也就是说，B下在B-1的预期得分是100分，下在B-2的预期得分也是100分，那么B随便在B-1和B-2间选一个就好了。这样一来，A-1点的预期得分就是100分。
& & 类&#20284;的，可以知道，如果下在A-2点，那么B就会选择下在 B-4点，A-2的预期得分是 -40分。两者一对比，显然A-1 的预期得分更高，A应该选择落在 A-1点。
& &这个流程，我们可以在这张图上标示出来，点B-1标示B落完子，那么轮到A行动了，A是MAX选手，他会选择子节点中得分最高的进行上溯。而在A-1节点，是B在行动，他会选择子节点中得分最低的进行上溯，这个过程如下：
& & 如果AI按照这个方法选择最优点，那么就是所谓的MIN-MAX博弈算法。
<span style="font-size:18 color:#、alpha-beta剪枝
& & &对上面的算法来说，其复杂度是呈指数增长的，一般来说，一个棋手可以下的落子位有几百个，那么即使只考虑2~3步棋，也是不小的开销，更不要说更高的深度了。实际上，我们不需要遍历树的每一条路径，就可以获得最优解，有些路径一看就没必要走，这就是剪枝的思想。
& & &下面具体说alpha-beta剪枝
& & &1）先说alpha，alpha是记录一个max节点（即图中的MAX行动节点）当前可选的最大&#20540;，如上图中的现状点，首先评估A-1点的得分，遍历其子树最终的达到得分是100，那么此时“现状节点”可选的最大&#20540;alpha就是100。
& & &然后试探A-2节点。当获取到B-3节点的得分80之后，还有必要继续评估A-2的其他儿子吗？不需要了，因为B会选择最小得分点，那么A-2的最终得分，不会超过B-3节点的得分80分，所以剩下的B-4和B-5完全不用再看了，这样的剪枝，我们就称之为alpha-剪枝。
& & 2）然后说beta，beta是记录一个MIN节点当前可选的最小&#20540;，以A-2点为例，当前是B行动，他要选取最小得分点。评估完B-3点后，当前的beta&#20540;是80，（顺便一提，此时ALPHA是100，应该发生alpha剪枝），然后继续评估B-4点，发现比原来的最小&#20540;还要小，那么更新beta到-40分。
& & 然后试探B-5点，落子B-5后，先看看如果A下在A-17会怎样？结果局面得分是1000，超过了当前的beta&#20540;，这意味着，只要B下在B-5，那么A下过之后，局面的得分不会低于1000分（因为A会选择最优点），所以后面的A-18和A-19也完全不用再看了，我们称之为beta剪枝。
& & 那么，将上面的两种情况同时使用起来，就是所谓的alpha-beta剪枝。在我实际的代码使用中，在MIN-MAX搜索深度为2的情况下，使用alpha-beta剪枝，大约能减少50%以上的计算量，还是非常有效的。
& &最后附上&:&http://download.csdn.net/detail/ronintao/6380249
& &其实AI还有很大的优化空间，不过最近估计也没有什么时间去做优化了，以后掌握了新的算法再系统的改进吧。
版权声明：本文为博主原创文章，未经博主允许不得转载。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：44536次
排名：千里之外
原创：23篇
评论：22条
(2)(2)(4)(1)(2)(3)(7)(5)alpha-beta剪枝五子棋 - 下载频道
- CSDN.NET
&&&&alpha-beta剪枝五子棋
alpha-beta剪枝五子棋
纯手写，速度比较慢，结合了贪心算法，alpha-beta剪枝有时候不能出解的bug用贪心算法弥补
若举报审核通过，可奖励20下载分
被举报人：
举报的资源分：
请选择类型
资源无法下载
资源无法使用
标题与实际内容不符
含有危害国家安全内容
含有反动色情等内容
含广告内容
版权问题，侵犯个人或公司的版权
*详细原因：
您可能还需要
开发技术下载排行five c++实现的一个五子棋人机对弈程序
使用了alpha-beta剪枝算法
具有一定的棋力 Chess Poker games 棋牌游戏 240万源代码下载-
&文件名称: five
& & & & &&]
&&所属分类:
&&开发工具: C++
&&文件大小: 90 KB
&&上传时间:
&&下载次数: 65
&&提 供 者: 冯军
&详细说明：c++实现的一个五子棋人机对弈程序
使用了alpha-beta剪枝算法
具有一定的棋力-c++ achieve a Gobang man-machine chess program using alpha-beta pruning technique have棋力
文件列表(日期：~)(点击判断是否您需要的文件，如果是垃圾请在下面评价投诉):
&&&&fivechess.exe
&近期下载过的用户:
&相关搜索:
&输入关键字，在本站240万海量源码库中尽情搜索：
&[] - 非常好的五子棋源码！！！！！
我所见过的最好的一个！
&[] - 采用最新算法，即使你很厉害，也不免会败给电脑。
&[] - 一个简单的java3例子， 一个简单的java3例子，
&[] - 此代码为五子棋人机博弈+联机对战C#代码。
&[] - 高智商五子棋，人机对弈部分，运用了博弈树进行搜索，在选取最优的走步时使用极大极小分析法，考虑到搜索的时间复杂度和空间复杂度，在程序中只进行了2步搜索，即计算机在考虑下一步的走法时，只对玩家进行一步的推测
&[] - 五子棋核心算法，介绍五子棋程序的数据结构、评分规则、胜负判断方法和搜索算法过程
&[] - xl C语言写的五子棋代码.作者陈成淘,中国最早一批研究人机对弈的人之一,其个人爱好五子棋,所以此xl棋力也不错.
&[] - c++版的五子棋，大家可以试试，AI很高。
&[] - 用中国人自己创造的语言写的一款象棋游戏代码，可以体验一下国人自己的语言。
&[] - 此五子棋功能比较简单，可实现人机对弈功能