五子棋AI算法的改进方法讲解.pdf

《五子棋AI算法的改进方法讲解.pdf》由会员分享，可在线阅读，更多相关《五子棋AI算法的改进方法讲解.pdf（12页珍藏版）》请在三一文库上搜索。

1、又是本人一份人工智能作业 首先道歉，从Word贴到 Livewrter，好多格式没了，也没 做代码高亮 大家凑活着看 想做个好的人机对弈的五子棋，可以说需要考虑的问题还 是很多的，我们将制作拥有强大AI 五子棋的过程分为十四步，让我来步步介绍。 第一步，了解禁手规则 做一个五子棋的程序，自然对五子棋需要有足够的了解，现在默认大家现在和我研究五子棋 之前了解是一样多的。以这个为基础， 介绍多数人不大熟悉的方面。五子棋的规则实际上有 两种：有禁手和无禁手。由于无禁手的规则比较简单，因此被更多人所接受。其实，对于专 业下五子棋的人来说，有禁手才是规则。所以，这里先对“ 有禁手 ” 进行一下简单介绍：

2、 五子棋中 “ 先手必胜 ” 已经得到了论证，类似“ 花月定式 ” 和 “ 浦月定式 ” ，很多先手必胜下法虽 然需要大量的记忆，但高手确能做到必胜。所以五子棋的规则进行了优化，得到了“ 有禁手 ” 五子棋。五子棋中， 黑棋必然先行。 因此 “ 有禁手 ” 五子棋竞技中对黑棋有以下“ 禁手 ” 限制 : “ 三 三禁 ”: 黑棋下子位置同时形成两个以上的三；“ 四四禁 ”: 黑棋下子位置同时形成两个以上的 四； “ 长连禁 ”: 六子以上的黑棋连成一线。黑棋如下出“ 禁手 “ 则马上输掉棋局。不过如果“ 连 五” 与“ 禁手 ” 同时出现这时“ 禁手 ” 是无效的。所以对于黑棋只有冲四活三（后

3、面会有解释） 是无解局面。反观白棋则多了一种获胜方式，那就是逼迫黑棋必定要下在禁点。 为了迎合所有玩家，五子棋自然需要做出两个版本，或者是可以进行禁手上的控制。 第二步，实现游戏界面 这里，我制作了一个简单的界面，但是，对于人机对弈来说，绝对够用。和很多网上的精美 界面相比，我的界面也许略显粗糙，但，开发速度较高，仅用了不到半天时间。下面我们简 单看下界面的做法。 界面我采用了WPF ，表现层和逻辑层完全分开，前台基本可以通过拖拽完成布局，这里就 不做过多介绍。根据界面截图简单介绍 1 处实际上市两个渐变Label的拼接， 2、3 是两个 label ，4、5 实际上是两个Button， 但是

4、没有做事件响应。通过按钮6、 7、8、9 的控制，修改label和 Button的 Content 属性。也许有人会奇怪，为什么Button会丝毫看出不出有Button的影子，这里战友 whrxiao写过一个Style如下 这里我们把这个Style称为 Style1。界面逻辑上，将是否开始、是否禁手和是否电脑先行 作为两个全局变量的布尔型值，通过设置和判断bool 型值进行逻辑上的控制。中间的棋盘 是个 canvas ，一个 15*15的 Grid 放满 Button并将每个Button应用 Style1开始时候 透明度设为0，也就是根本看不到，在下棋的时候改变Button的背景和透明度，实现

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

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

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

8、 3， 80 分 死 3 活 3， 70 分 死 4， 60 分 活 3， 50 分 双活 2， 40 分 死 3， 30 分 活 2， 20 分 死 2， 10 分 单子0 分 有了估分方法，就有了五子棋AI 的基础，接下来就是一些博弈的方法了。 第五步：得到位置估分AI 单纯应用棋谱以及对五子棋当前局势的分析，对每步进行估分，程序中做如下工作：将每个 位置进行分析，假设AI 落子在该位置，用以上打分规则为AI 打分 ,并将得到的分数加一。 然后， 假设玩家落子在该点，为玩家打分，然后将所有的分值汇总。取最高分作为这个位置 的估分，接下来就是取分数最高的位置下棋了。“ 位置估分 ” ，下棋的

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

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

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

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

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

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

15、面的评分，主要是为了说明在这个地方下子的重要性程度，设定了一个简 单的规则来表示当前棋面对机器方的分数。 基本的规则如下： 判断是否能成5, 如果是机器方的话给予100000 分，如果是人方的话给予100000 分； 判断是否能成活4 或者是双死4或者是死4 活 3，如果是机器方的话给予10000 分，如果是 人方的话给予10000 分； 判断是否已成双活3，如果是机器方的话给予5000 分，如果是人方的话给予5000 分； 判断是否成死3 活 3，如果是机器方的话给予1000 分，如果是人方的话给予1000 分； 判断是否能成死4，如果是机器方的话给予500 分，如果是人方的话给予500 分

16、； 判断是否能成单活3，如果是机器方的话给予200 分，如果是人方的话给予200 分； 判断是否已成双活2，如果是机器方的话给予100 分，如果是人方的话给予100 分； 判断是否能成死3，如果是机器方的话给予50 分，如果是人方的话给予50 分； 判断是否能成双活2，如果是机器方的话给予10 分，如果是人方的话给予10 分； 判断是否能成活2，如果是机器方的话给予5 分，如果是人方的话给予5 分； 判断是否能成死2，如果是机器方的话给予3 分，如果是人方的话给予3 分。 实际上对当前的局面按照上面的规则的顺序进行比较，如果满足某一条规则的话，就给该 局面打分并保存， 然后退出规则的匹配。 注

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

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

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

20、 （3）父节点的值oldValue； （4）当前的搜索深度depth。 double Search(CBoardSituation board,int mode,double oldvalue,int depth) CList m_DeepList; if(deptholdvalue)= TRUE) if(mode=max) value=select(value,search(successor Board,min,value,depth 1),max); else value=select(value,search(successor Board,max,value,depth 1),min

21、); return value; else if ( goal(board)0 表示已经可以分出胜负 return goal(board); else return evlation(board); 注意这里的goal(board)函数是用来判断当前盘面是否可以分出胜负，而evlation(board) 是对 当前的盘面从机器的角度进行打分。 下面是 Select 函数的介绍， 这个函数的主要目的是根据PlayerMode 情况， 即是机器还是用 户来返回节点的应有的值。 double Select(double a,double b,int mode) if(ab mode=max)| (a

22、 b mode=min) return a; else return b; 五、小结 在 Windows 操作系统下，用VC 实现了这个人机对战的五子棋程序。和国内许多只是 采用规则或者只是采用简单递归而没有剪枝的那些程序相比，在智力上和时间有效性上都要 好于这些程序。 同时所讨论的方法和设计过程为用户设计其他的游戏（如象棋和围棋等）提 供了一个参考。 大部分算法中， 都要进行两步。第一步是优先级的计算，然后是打分。 但是我在想能不能通 过某种数学模式把这两种计算融合在一起。也就是说， 我们能够从所打的分中间识别出优先 级。这使我想到了数学十进制中的位。反正我最主要是从四个方向进行判定，所以某

23、些优先 级低的， 我们在给其打分的时候，就将它的分数设为处在其优先级之上的十分之一。其实我 觉得这里只要大于其分数的八倍就可以，因为我最后选取最优位置的方法是累加法，算出分 数和最高的位置，这样的话， 即使在四个方向上某较低优先级都出现了，但是即使全加起来 也不会超过较高优先级的分数，这样的话， 如果出现优先级较高的情况，那么我们计算的结 果必然是优先级较高的分数最高。这样，变省去了一些不必要的分类，使得算法更直接，更 容易理解。 首先我们先来看一下置棋时的优先级分布以及我为其所指定的打分方案： 首先声明的是， 对于已经五子相连的情况，我们在此部分算法中不再实现，因为这个时候胜 负已经分出，我

24、们调用checkboard类的 judge 的方法便可以了。这只不过是在电脑AI 后 再将 judge 的代码复制过去罢了。 我们的目的是给棋盘上的空位进行打分，进而算出分数最高的位置。那么我在这里想运用试 探法，因为我觉得这样的话代码比较好写。所谓试探法就是，我们找出棋盘上的所有空位， 然后我们假设这个空位上放置的是白棋，然后看看相连的情况，然后打分， 并将分数加至存 储该空位分数的变量；再假设这个空位上放置的是黑棋，然后再看相连的情况，然后打分， 并将分数加至存储该空位分数的变量；这样遍历完所有的空位的时候，我们便完成了打分工 作，然后再比较空位的分数，选出分数最高的空位，该位置即为最优的

25、位置。 下面是一些情况的优先级排列：（假设我们是白棋）下列情况均为在该空位置棋之后： 在实现的时候，我们还需要定义两个临时的Checker指针变量，用来保存相连的一串棋子 前后的位置的状态。color 用来保存棋子的颜色，count 用来保存相连的棋子的个数，temptr1 与 temptr2 用来保存两端的棋子指针。文中的我们是电脑哦！ 情况所打 分数 color=1&count=5我们先赢，赢了再说100 000 0000 Color=0&count=5对方要赢，如果我们不能先赢，那么一定得先阻拦10 000 0000 Color=1&count=4&!temptr1&!temptr2双方

26、均不会赢，如果我们能成活四，那么 敌方必输，所以要先置棋 1 000 0000 Color=1&count=4&(!temptr1&temptr2)|(temptr1)&!temptr2)双方均不会赢，100 那么如果我们能成冲四，则要先置棋，牵着敌方的鼻子走，因为下过本步棋之后敌方 一定会来阻止我们 0000 Color=0&count=4&!temptr1&!temptr2双方均不会赢，如果对方能成活四，那么 我们一定要优先阻拦，否则便会输棋 10 0000 Color=1&count=3&!temptr1&!temptr2双方均不会赢，如果我们能成活三，则要 优先这个位置 1 0000

27、Color=0&count=4&(!temptr1&temptr2)|(temptr1)&!temptr2)双方均不会赢， 如果敌方能成冲四，那么我们要尽力阻拦 1 000 Color=1&count=3&(!temptr1&temptr2)|(temptr1)&!temptr2)双方均不会赢， 如果我们能成冲三，那么要优先这个位置 1 00 Color=1&count=2&!temptr1&!temptr2双方均不会赢，如果我们能成活二，则要 优先这个位置 1 0 Color=1&count=2&(!temptr1&temptr2)|(temptr1)&!temptr2)双方均不会赢， 如果

28、我们能成冲二，那么要优先这个位置 1 其他情况0 这个算法的主要思想是，对于敌方构不成威胁的情况，（即活四以下，但是这里我们把冲四 也算进来了，并赋予了较高的优先级），我们暂不理会，而是一心想着自己怎么能赢。这里 我们只能分成这么多情况，因为假设我们的分数是long 型的， 那么它的长度是32 位，转换 成十进制， 位数也就是10 位， 因而我选了最大的分数为1000 000 000 ，这样刚好能满足要 求。 但是这里有个小小的问题，就是在刚开始落子的时候，怎么落？我想这个时候我们可以 事先设置某个空位的分值为髙值，落棋之后分数便置为0 了。当对方先下的时候，我们就 将第一个棋子放在对方棋子的周围，启动AI，这样接下来问题便简单了，因为一定会出现 冲二，进而便是对方的活四，然后再防守，这样一步步，便展开了。