五子棋AI算法的改进方法讲解实用doc.docx

1、五子棋AI算法的改进方法讲解实用doc又是本人一份人工智能作 首先道歉，从 Word 到 Livewrter ，好多格式没了，也没做代 高亮 大家凑活着看 想做个好的人机 弈的五子棋，可以 需要考 的 是很多的，我 将制作 有 大 AI 五子棋的 程分 十四步， 我来步步介 。第一步，了解禁手 做一个五子棋的程序， 自然 五子棋需要有足 的了解， 在默 大家 在和我研究五子棋之前了解是一 多的。 以 个 基 ， 介 多数人不大熟悉的方面。 五子棋的 上有两种：有禁手和无禁手。由于无禁手的 比 ，因此被更多人所接受。其 ， 于 下五子棋的人来 ，有禁手才是 。所以， 里先 “有禁手 ” 行一下

2、介 ：五子棋中 “先手必 ”已 得到了 ， 似 “花月定式 ”和 “浦月定式 ”，很多先手必 下法 然需要大量的 ， 但高手确能做到必 。 所以五子棋的 行了 化， 得到了 “有禁手 ”五子棋。五子棋中， 黑棋必然先行。 因此 “有禁手 ”五子棋 技中 黑棋有以下 “禁手 ”限制 : “三三禁 ”:黑棋下子位置同 形成两个以上的三； “四四禁 ”:黑棋下子位置同 形成两个以上的四； “ 禁 ”:六子以上的黑棋 成一 。黑棋如下出 “禁手 “ 上 掉棋局。不 如果 “ 五”与“禁手 ”同 出 “禁手 ”是无效的。所以 于黑棋只有冲四活三（后面会有解 ）是无解局面。反 白棋 多了一种 方式，那就是

3、逼迫黑棋必定要下在禁点。 了迎合所有玩家，五子棋自然需要做出两个版本，或者是可以 行禁手上的控制。第二步， 游 界面 里，我制作了一个 的界面，但是， 于人机 弈来 ， 用。和很多网上的精美界面相比，我的界面也 略 粗糙，但，开 速度 高， 用了不到半天 。下面我 看下界面的做法。界面我采用了 WPF ，表 和 完全分开，前台基本可以通 拖拽完成布局， 里就不做 多介 。根据界面截 介 1 处实际上市两个渐变 Label但是没有做事件响应。通过按钮属性。也许有人会奇怪，为什么的拼接， 2 、 3 是两个 label ， 4 、 56 、 7 、 8 、9 的控制，修改 labelButton

4、会丝毫看出不出有 Button实际上是两个 Button ，和 Button 的 Content的影子，这里战友whrxiao写过一个Style如下这里我们把这个 Style 称为 Style1 。界面逻辑上，将是否开始、是否禁手和是否电脑先行作为两个全局变量的布尔型值，通过设置和判断 bool 型值进行逻辑上的控制。中间的棋盘是个 canvas ，一个 15*15 的 Grid 放满 Button 并将每个 Button 应用 Style1 开始时候透明度设为 0 ，也就是根本看不到，在下棋的时候改变 Button 的背景和透明度，实现落子的效果，因为 Grid 的位置关系，所以可看起来好像

5、是下在横竖的交线处。第三步，进行输赢判断：因为规则不同， “无禁手 ”和 “有禁手 ”的输赢判断自然不同。先看无禁手：这个比较简单，遍历每个位置，然后从这个位置开始，分别判断它的四个方向：即横、竖、左上到右下、左下到右上。每个方向从中间点开始， 往两边数连子数， 然后将两个方向的连字数加和再加一（中间的棋子）。如果得到大于等于5 ，那么就说明下子方赢棋。对于有禁手的五子棋， 输赢判断还需要判断禁手， 禁手的判定较为复杂。将待判断点放入黑棋子。 然后搜索待判断点周边棋盘； 还原棋盘；利用搜索结果依次对各方向进行分析，判断黑棋放入后所产生的棋型是否形成长连或形成某种四连或三连的的棋型。若形成长连，

6、 判定为禁手，返回长连禁手标识。若形成某种四连或三连的棋型，该棋型统计数加1 ，再对下一个方向进行判断， 直到各个方向分析结束。 若四连棋型或三连棋型的统计数大于，则返回为禁手。其余情况返回非禁手。第四步：构造棋型估分“有禁手 ”规则比较复杂，涉及到比较多下棋方面的技巧，而且对算法的思路没有丝毫影响，所以下面我们主要考虑无禁手规则下的 AI 设计。若设计好无禁手 AI ，只需要让 AI 执黑时坚决不下到禁手点，就可以很快构造有禁手的 AI 。虽然这种方式没有利用有禁手规则下的技巧，但这些技巧只需要修改下面所讲到的估分函数即可。我们可以将五子棋的连珠可以分为以下几种：成 5 ：即构成五子连珠活4

7、 ：即构成两边均不被拦截的四子连珠。死 4 ：一边被拦截的四子连珠活3 ：两边均不被拦截的三字连珠死3 ：一边被拦截的三字连珠活 2 ：两边均不被拦截的二子连珠死2 ：一边被拦截的二子连珠单子：四周无相连棋子根据五子棋的技巧， 可以将五子棋的棋型用连珠进行分类， 分类过后我们按照威力给每种棋型打分。因为五子棋一次只落一子， 因此很容易理解，双活三和三活三的威力是一样的，类似情况不多做解释。程序中，我以 100 分为满分，对棋型进行了以下打分：成5, 100 分活4 、双死 4 、死 4 活 3 ， 90 分双活 3 ， 80 分死3 活 3 ， 70 分死4 ， 60 分活3 ， 50 分双活

8、 2 ， 40 分死 3 ， 30 分活2 ， 20 分死 2 ， 10 分单子 0 分有了估分方法，就有了五子棋AI 的基础，接下来就是一些博弈的方法了。第五步：得到位置估分AI单纯应用棋谱以及对五子棋当前局势的分析， 对每步进行估分， 程序中做如下工作： 将每个位置进行分析，假设 AI 落子在该位置，用以上打分规则为 AI 打分 ,并将得到的分数加一。然后， 假设玩家落子在该点，为玩家打分，然后将所有的分值汇总。取最高分作为这个位置的估分，接下来就是取分数最高的位置下棋了。 “位置估分 ”，下棋的时候，既可以考虑到自己攻击对手，又能考虑到对对手的防御，可以说，很多时候可以顶上考虑两步的 A

9、I 。作实验，从网上下载了一个用博弈做的 AI ，和 “位置估分 ”对下，结果是一胜一负。谁先子，谁赢得胜利。而且一步估分毫无疑问是最快的，即使遍历所有位置，也能很快的做出决策。第六步：应用博弈树，提高AI智能做五子棋的博弈，自然会用到博弈树，这里我说下自己的思路。在对弈中 , 根据下一步由谁来走 ,AI 对任何一个局面根据前面估分方法给出一个分数 , 我们把这个估分方法汇总成一个评估函数，并返回分值。据此来选择下一步的走法。由于人和 AI 是轮流落子，可以将人的估分也算入，并将前面加负号。那么，估值越大表明对 AI 越有利，估分越小则表明对 AI越不利。那么每次 AI 选择都是从它可能的走法

10、树的某层节点，返回评估值中最大点。而用户总是从走法树的某层节点中选择最小点， 从而形成一棵极大极小搜索树， 然后根据深度优先搜索，可以最后得到固定搜索深度下的一个最好的走法。 我做了下试验， 单纯应用博弈树，可以在 100ms 之内让 AI 考虑完整的两步，由于组合爆炸，当需要考虑三步的时候，就需要6s 左右， 4 步就需要 1 分钟。拿两步来和一步估分作比较，虽然比较慢，但是确实有了一定智能。第七步：考虑层数，提高AI智能上面的设计对于返回值是统一处理的 , 但是，层数是个很重要的信息 . 因为下棋时如果能 2 步获胜 , 不应选择 4 步获胜。对于输的棋型层数就更重要 ,AI 必须尽可能拖

11、延输的时间，就有更大的可能让 AI 化险为夷。这样，可以通过设置一个 dep 值。深度约浅， dep 越大，用dep 和得到的得分相乘，得到搜索节点的得分，再进行以上算法，进一步提高 AI 的智能。第八步：应用 - 剪枝，提高 AI 速度在搜索博弈树的过程中，实际上搜索有很多点是多余的，例如下图图中，方形框节点是该AI 走 , 圆形框节点是该人走 .比如 C 节点 , 它需要从 E和 F 当中选取最大的值。目前已经得出E 为 2, 当搜索 F 节点时 , 因为 F 是人走的节点，那么F 需要从 K LM 中选取最小的，因为K 已经是 1 ，也就是说 F=1 ，那么 L， M 就不需要搜索，因此

12、就发生了 剪枝。 然后看 A 节点，该人走了， 需要从 C 和 D 中选取最小值， 因为 C 节点是 2 ，而 G 是 7 ，那么 D 至少是 7 。因此， D 的其他节点不必再考虑，就发生如上图所示的剪枝。总结上面规律，我们可以得到剪枝方法如下：当前为 AI 下棋节点：剪枝：如果当前节点的值不比父节点的前兄弟节点的大值大, 则舍弃此节点。剪枝：如果当前节点子节点的值不比当前节点的前兄弟节点中的最小值小, 则舍弃该子节点和该子节点的所有后兄弟节点。当前为用户下棋节点：剪枝：如果当前节点的某子节点的值不比当前节点的前兄弟节点中的最大值大, 则舍弃该子节点和该子节点的所有后兄弟节点。剪枝：如果当前

13、节点的子节点的值不比当前的父节点的前兄弟节点中的最小值小则舍弃此节点。经过 - 剪枝，可以极大的减少搜索的数量，很多时候，能把几十亿的搜索数量，缩小到几亿，那么，就可以把搜索深度增 1 。第九步：应用下棋范围，提高AI速度当前节点的子节点的数量和排列顺序对于搜索的速度起着至关重要的影响。 根据五子棋的特点, 可以产生一个棋面搜索范围。 记录当前棋面所有棋子的最左最右最上最下点构成的矩形我们认为下一步棋的位置不会脱离这个框 3 步以上。这样在棋子较少的时候，搜索节点的数量大大减少。可以将 AI 的速度提高一倍左右。,第十步：利用棋型得分，提高AI速度因为每种下法都对应一种得分， 所以，可以每次只

14、考虑当前得分前十的节点进行下一步搜索大大减少了搜索范围，可以进一步增加搜索的深度。，第十一步：利用置换表，提高AI速度我们一般用递归的方法实现博弈树， 但是，递归的效率是低的，而且很明显，有很多重复搜索的节点， 所以，我们可以用一个表，记录下所有搜索过节点的情况， 然后只要遇到搜索到的节点， 就可以直接得到结果。 置于这个 “表 ”是什么， 就是一个置换表， 利用 Zobrist 算法，进行 Hash 处理，使在表中查找的时间大大缩短，这样 AI 的速度又能提高一个数量级。第十二步：利用多线程，提高AI速度我们其实可以利用多核技术，利用多个线程，让算法实现并行计算，提高 AI 的速度。我们在第

15、一层用一个线程分配器把第二层的候选节点分配给多个线程 , 每个线程包含着从第二层一个候选节点开始的搜索 ,然后等所有线程结束后 , 将所有线程的结果进行汇总 ,选出最大值。并行的程序，可以将速度提高一倍左右。第十三步：利用随机化算法，让确定方法不能必胜由于 AI 算法的固定性，所以一担玩家一次获胜，按照相同的走法，必然会再次获胜。但除了必杀招或者必防招 , 一个局面很多时候没有绝对最好的走法。 而是有一些都不错的走法 , 那么可以把这些评分差不多走法汇集起来 ,然后随机选择它们中的一种走法 , 避免 AI 的走法的固定 . 这样最简单的方法避免固定方法 AI 必输。第十四步：让AI自学习，不再

16、同一个地方犯错上面的算法还没有自学习的能力 , 这样 AI 在下棋时还可能会重蹈覆辙。 因此在每盘棋结束时如果 AI 输，则进行大于搜索深度的步数回退。可以把倒数为搜索深度数目的局面定为目标局面，从倒数深度加一步局面进行预测 ,找到不会导出必败目标局面的局面。然后记录下这个局面和前面的局面，并据此修改评分函数。这样 AI 就不会犯曾经犯过的错误，达到自学习的效果。,做到以上十四步，一个拥有强大AI的五子棋游戏即可诞生！五子棋 算法可简可繁 ,要看你对自己五子棋程序智能的要求 , 人机对战的意思就是人和 电脑下, 也就是说电脑会思考如何下棋 .其实这才是五子棋程序的核心 .如果只实现人与人对战的

17、话 ,是一件很简单的事情 , 无非就是绘制棋盘 ,然后绘制下棋的效果 ,再写个下棋合法性判断 ,胜负判断 .大概就搞定了 .所以核心其实是人机对战的电脑那部分 人工智能 .这东西吧 ,可以研究的很多 , 不过主要的几个设计要点就是 搜索算法 和估值 算法 ,这两个是最主要的 ,还有提高电脑思考销率的方法就有多 cpu 的计算机多线程 思考的设计 .通过一些手段让电脑变得更像人类棋手的 ,例如利用一些 遗传算法 之类的让电脑具有学习能力 ,可以在失败中吸取教训 ,开局库 ,历史启发之类的一大堆 . 但是总而言之 ,这一系列算法的设计没有一个标准 ,只要能让你的电脑下棋下的更聪明 ,更快那就是好算

18、法 .国内有一个叫 王晓春 的写过一本叫 的书 ,这是一本研究人机博弈程序很经典的书 ,书的后面还附了一个五子棋的程序实例 ,你可以参考一下 .下面是 csdn 的下载地址 ,你也可以自己去搜一下 . 五子棋的核心算法五子棋是一种受大众广泛喜爱的游戏，其规则简单，变化多端，非常富有趣味性和消遣性。这里设计和实现了一个人机对下的五子棋程序， 采用了博弈树的方法， 应用了剪枝和最大最小树原理进行搜索发现最好的下子位置。 介绍五子棋程序的数据结构、 评分规则、 胜负判断方法和搜索算法过程。一、相关的数据结构关于盘面情况的表示，以链表形式表示当前盘面的情况，目的是可以允许用户进行悔棋、回退等操作。CL

19、ist StepList;其中 Step 结构的表示为：struct Stepint m; /m,n 表示两个坐标值int n;char side; /side 表示下子方;以数组形式保存当前盘面的情况，目的是为了在显示当前盘面情况时使用：char FiveAreaFIVE_MAX_LINEFIVE_MAX_LINE;其中 FIVE_MAX_LINE 表示盘面最大的行数。同时由于需要在递归搜索的过程中考虑时间和空间有效性，只找出就当前情况来说相对比较好的几个盘面，而不是对所有的可下子的位置都进行搜索，这里用变量 CountList 来表示当前搜索中可以选择的所有新的盘面情况对象的集合：CLis

20、t CountList;其中类 CBoardSituiton 为:class CBoardSituationCList StepList; / 每一步的列表char FiveAreaFIVE_MAX_LINEFIVE_MAX_LINE;struct Step machineStep; /机器所下的那一步double value; / 该种盘面状态所得到的分数二、评分规则对于下子的重要性评分，需要从六个位置来考虑当前棋局的情况，分别为： -,|,/,/,实际上需要考虑在这六个位置上某一方所形成的子的布局的情况，对于在还没有子的地方落子以后的当前局面的评分， 主要是为了说明在这个地方下子的重要性程

21、度， 设定了一个简单的规则来表示当前棋面对机器方的分数。基本的规则如下：判断是否能成 5,如果是机器方的话给予100000 分，如果是人方的话给予100000分；判断是否能成活4 或者是双死 4 或者是死4 活 3，如果是机器方的话给予10000 分，如果是人方的话给予 10000 分；判断是否已成双活3，如果是机器方的话给予5000 分，如果是人方的话给予5000分；判断是否成死 3 活 3，如果是机器方的话给予1000 分，如果是人方的话给予1000分；判断是否能成死4，如果是机器方的话给予500 分，如果是人方的话给予500 分；判断是否能成单活3，如果是机器方的话给予200 分，如果是

22、人方的话给予200分；判断是否已成双活2，如果是机器方的话给予100 分，如果是人方的话给予100分；判断是否能成死3，如果是机器方的话给予50 分，如果是人方的话给予50 分；判断是否能成双活2，如果是机器方的话给予10 分，如果是人方的话给予10 分；判断是否能成活2，如果是机器方的话给予5 分，如果是人方的话给予5 分；判断是否能成死2，如果是机器方的话给予3 分，如果是人方的话给予3 分。实际上对当前的局面按照上面的规则的顺序进行比较，如果满足某一条规则的话，就给该局面打分并保存， 然后退出规则的匹配。 注意这里的规则是根据一般的下棋规律的一个总结，在实际运行的时候，用户可以添加规则和

23、对评分机制加以修正。三、胜负判断实际上，是根据当前最后一个落子的情况来判断胜负的。实际上需要从四个位置判断，以该子为出发点的水平，竖直和两条分别为是否最后落子的一方构成连续五个的棋子，45 度角和 135 度角的线，目的是看在这四个方向如果是的话， 就表示该盘棋局已经分出胜负。具体见下面的图示：四、搜索算法实现描述注意下面的核心的算法中的变量 currentBoardSituation ，表示当前机器最新的盘面情况 ,CountList 表示第一层子节点可以选择的较好的盘面的集合。核心的算法如下：void MainDealFunction()value= MAXINT; / 对初始根节点的 v

24、alue 赋值CalSeveralGoodPlace(currentBoardSituation,CountList);/该函数是根据当前的盘面情况来比较得到比较好的可以考虑的几个盘面的情况，可以根据实际的得分情况选取分数比较高的几个盘面， 也就是说在第一层节点选择的时候采用贪婪算法，直接找出相对分数比较高的几个形成第一层节点， 目的是为了提高搜索速度和防止堆栈溢出。pos=CountList.GetHeadPosition();CBoardSituation pBoard;for(i=0;ivalue=Search(pBoard,min,value,0);Value=Select(value

25、,pBoard value,max);/取 value 和 pBoard value 中大的赋给根节点for(i=0;ivalue)/找出那一个得到最高分的盘面currentBoardSituation=pBoard;PlayerMode=min; / 当前下子方改为人Break;其中对于 Search 函数的表示如下：实际上核心的算法是一个剪枝过程，其中在这个搜索过程中相关的四个参数为： （ 1）当前棋局情况； （ 2）当前的下子方，可以是机器 (max) 或者是人(min) ；（ 3）父节点的值 oldValue ；（ 4）当前的搜索深度 depth。double Search(CBoar

26、dSituation board,int mode,double oldvalue,int depth)CList m_DeepList;if(deptholdvalue)= TRUE)if(mode=max)value=select(value,search(successorBoard,min,value,depth 1),max);elsevalue=select(value,search(successorBoard,max,value,depth 1),min);return value;elseif ( goal(board)0)/这里 goal(board)0 表示已经可以分出胜

27、负return goal(board);elsereturn evlation(board);注意这里的 goal(board) 函数是用来判断当前盘面是否可以分出胜负，而当前的盘面从机器的角度进行打分。evlation(board) 是对下面是 Select 函数的介绍， 这个函数的主要目的是根据PlayerMode情况， 即是机器还是用户来返回节点的应有的值。double Select(double a,double b,int mode)if(ab mode=max)| (a b mode=min)return a;elsereturn b;五、小结在Windows 操作系统下，用 VC 实现了这个人机对战的五子棋程序。和国内许多只是采用规则或者只是采用简单递归而没有剪枝的那些程序相比，在智力上和时间有效性上都要好于这些程序。 同时所讨论的方法和设计过程为用户设计其他的游戏 （如象棋和围棋等） 提供了一个参考。大部分算法中， 都要进行两步。