五子棋人工智能算法实现研究-计算机人工智能论文-论文联盟
您好，游客
背景颜色：
五子棋人工智能算法实现研究
来源：论文联盟&
五子棋人工智能算法实现研究
五子棋是一种两人对弈的纯策略型棋类游戏，是起源于中国古代的传统黑白棋种之一。现代五子棋日文称之为&连珠&，英译为&Renju&，英文称之为&Gobang&或&FIR&（Five in a Row的缩写），亦有&连五子&、&五子连&、&串珠&、&五目&、&五目碰&等多种称谓[1]。因其规则简单，变化多端，容易上手，而广受大众喜爱。五子棋游戏不仅能增强思维能力，提高智力，而且富含哲理，有助于修身养性。五子棋游戏规则比较简单，棋盘通常采用类似围棋盘的15路或19路的棋盘，两人分别执黑白两色棋子，轮流在棋盘上选择一个无子的交叉点落子，无子的交叉点又被称为空点或合法点，当黑白一方有五个棋子在横、竖或斜方向上连接成一线即为该方赢。　　人工智能（Artificial Intelligence，AI），是科学的一个分支，是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及系统的一门新的综合性的技术科学。该领域的研究包括机器人、识别、图像识别、自然语言处理和专家系统等，而博弈是人工智能研究的一个重要分支。它不仅存在于游戏、下棋之中，也存在于、、军事和生物竞争中。与其他棋类游戏相比，五子棋游戏每一层棋局搜索节点数量庞大，规则简单，更便于深入研究博弈算法。本文以五子棋游戏为研究对象，采用Alpha-Beta剪枝和最大最小树原理，优化了博弈树搜索过程，通过控制搜索深度，实现了初级和高级的人机对弈。此外，本文还对优化五子棋智能算法的思路做出了初步探讨。　　一、 五子棋传统算法　　1.人机博弈传统算法。　　解决博弈问题的传统算法是搜索树法，也叫博弈树法。以甲乙两人对弈五子棋为例，假定现在该甲走棋且甲有若干种走法，而对甲的任一走法，乙也可以有与之对应的不同的多种走法，然后又轮到甲走棋，而对乙的走法甲又有若干种方法应对，如此反复。显然，可以从当前棋局状态（根节点）出发，找出所有可能的乙的走法（子节点），再从每个子节点出发找出甲对应于每个乙的走法的所有应对（子子节点），直到出现一方赢局。由此构成的树，就称为博弈树。对于19*19的棋盘而言，显然这是一个典型的指数复杂度问题，其计算量之大是目前所有的计算机都无法承受的。因此，用搜索树法来解决人机博弈时，通常只能搜索到一个非常有限的深度，并根据此有限深度的形势来判断每种走法的优劣，从而选择较优位置下子。　　2. 极小极大值算法（MinMax 算法）。　　极小极大算法[3]是考虑双方对弈本文由联盟收集整理若干步之后， 从可能的走法中选一步相对好的来走。若最大（MAX）节点为己方下的棋，此时选择估值最大的点走。最小（MIN）节点为对方下的棋，此时选择估值最小的点行走。因此MIN节点的父节点（MAX节点）所赋的倒推值等于端节点估值中的最大值。另一方面，MAX节点的父节点（MIN节点）所赋的倒推值等于端节点估值中的最小值。这样一级一级地计算倒推值，直至起始节点的后继节点也被赋以倒推值为止，即从下往上逐层交替使用极小极大的选值方法。但当搜索深度增加时，搜索节点快速大幅增加，时间和内存空间消耗太大，且利用先前信息的效率较低。于是人们在极小极大的基础上提出了&-&剪枝技术。　　3. &-&剪枝算法。　　&-&剪枝算法[2]是在极大极小算法的基础上，当甲向下搜索节点时发现走第一个子节点就可以赢了，则剩下的节点就不需要再搜索，甲的值就是第一个子节点的值。即可以将甲的其余后继节点抛弃，此过程称为剪枝。如果甲所在的层是MAX 节点的层，则称此剪枝为&剪枝，否则成为&剪枝。如图1左半部所示的一棵极大极小树的片断。其中节点下方数字为该节点的值，方形框节点代表计算机走，圆形框节点代表人走。A节点表示计算机走，由于A是极大值点，根据极小极大搜索原理它要从B和C当中选最大的值。假设目前已经通过估值得出B为18，当搜索C节点时，因为C是该人走，所以根据极小极大搜索原理要从D、E、F中选取最小的值。此时如果估出D为16，那么C的值必小于或等于16。又因为已经得出B的值为18，说明节点A的值为Max（B，C）=18，也就是说无须求出节点C的其他子节点如E、F的值就可以得出父节点A的值。这种将节点D 的后继兄弟节点剪去的方法称为Alpha剪枝。　　同理，在图1右半部一棵极大极小树的片段中，将节点D 的后继兄弟节点剪去称为Beta 剪枝。与极小极大算法相比，&-&剪枝需要遍历的节点远远减少，它能在较短的时间内找到最佳的走法节点。　　二、 五子棋智能算法实现及优化　　1. 估值函数。　　为使用极大极小算法，需要对一个估值函数Eval （p）对当前棋局进行估值，p是当前局面。即由这个估值函数确定哪个局面更好，如果Eval（p1）&eval（p2），我们就有理由相信，p2比p1更好。对于五子棋而言，由其胜负判定规则可以很容易设定不同的棋型的优先级，从而得到比较合理的估值函数。例如，四个棋子连成一线且还能继续落子的棋型（活四）显然要比只有三个棋子连成一线（活三或死三）好。另外，为了尽可能地加快搜索速度，估值函数应设计的越仔细越好。估值时，需要从四个方向上来考虑所下棋子对当前盘面的影响。这四个方向分别是以该棋子为出发点，水平、竖直和两条为45度角和135度角的线。算法中关于棋子死活的规定如下：一方落子后，它的落子连成的一条线有两条不损伤的出路，则称该棋型是活的。否则称该棋型是死的。比如关于活三的定义：不论对手如何落子，仍然至少有一种方法可以冲四。因此，b？aaa？ B中的三个A，不能算是活三；B？AAAB中的三个A，也不是活三，尽管它有可能成为活四。这样，棋型的估值设计才能比较细致。本文算法对特定棋型的估值如表1所示。="" &br=""&　　2. 算法实现及优化　　使用以上定义的估值函数和描述的算法，可以实现基本的人机对弈。但是在实现中，由于搜索深度增加后运算量呈指数级数增加，运算效率急剧下降。为提高搜索效率，增进用户体验，提出以下优化改进方法：　　减少搜索范围。对于19*19的五子棋棋盘而言，传统算法中计算机每走一步都要遍历整个棋盘，对棋面上所有空位都进行试探性下子并估值，大大影响了算法的效率。本文采用在某个时只要考虑距以棋子为中心边长为4的正方形区域即可，这样便缩小了搜索空间，提高搜索效率。　　减少计算量。为进一步减少计算量，提高计算机反应速度，通过以空间换时间的方法，在游戏过程中维持一个棋盘所有位置的估值信息的数组。每次对棋盘上的每个位置的当前估值进行计算后，存储在当前棋局信息中。当新的棋局产生时，只需更新计算新下子位置和相关位置的估值，而对其他可下子位置的估值只需查询上步棋局信息即可。这样保持的估值表虽然增大了空间需求，但可以大大减少搜索算法的估值计算时间，提高了算法执行效率。　　三、 结论及后续　　本文主要论述了五子棋游戏的基本游戏规则，传统五子棋人机对弈游戏的基本算法，描述了算法实现的MinMax算法和Alpha-Beta剪枝算法，并描述了算法实现的估值函数定义、数据结构等，并通过减少搜索范围、减少计算量和设置对弈等级的方法，对算法进行初步优化，提高了算法性能，增进了人机对弈的用户体验。下步工作主要是通过改进算法和增加搜索辅助手段的方式，探索分析优化搜索性能的方法。比如[2]，结合使用启发式搜索，利用五子棋游戏开局阶段现成的棋谱，进行启发式搜索，或者加入自学习功能等。
欢迎浏览更多 →
相关文章 & & &
本栏目最新更新文章
　　　同意评论声明
　　　发表
尊重网上道德，遵守中华人民共和国的各项有关法律法规
承担一切因您的行为而直接或间接导致的民事或刑事法律责任
本站管理人员有权保留或删除其管辖留言中的任意内容
本站有权在网站内转载或引用您的评论
参与本评论即表明您已经阅读并接受上述条款
内容分类导航拒绝访问 | www.anhui365.net | 百度云加速
请打开cookies.
此网站 (www.anhui365.net) 的管理员禁止了您的访问。原因是您的访问包含了非浏览器特征(43ef-ua98).
重新安装浏览器，或使用别的浏览器您所在的位置：
妙手杯五子棋团体赛北京队获第三名
日16:04 　
本报讯（记者刘晓星）“妙手杯”2009年全国五子棋团体锦标赛昨天收官。炫飞棋社2队荣获冠军，上海1队获亚军，北京队获第3名。承办方妙手队获第7名，上两届冠军浙江队仅获第12名。河北妙手队遇到世锦赛冠军吴镝和全国赛女子冠军李非在内的火车头体协队，顽强抵抗以2胜2负战平对手。值得一提的是，妙手队1台段然（木头鱼）顽强抵抗，最终“拍死”对手火车头体协队1台世锦赛冠军吴镝。[责任编辑：tuneluo]
有人在热爱
更多关于“”的新闻
( 06:43:00)
( 13:36:03)
( 13:33:56)
( 13:32:21)
( 11:51:30)
( 11:29:46)
( 11:19:26)
( 10:13:47)
[] [] [] []
请您文明上网、理性发言并遵守
腾讯微博：
同时更新资讯所属地
暂无更新，休息一会儿
白羊座(03.21-04.19)
金牛座(04.20-05.20)
双子座(05.21-06.21)
巨蟹座(06.22-07.22)
狮子座(07.23-08.22)
处女座(08.23-09.22)
天秤座(09.23-10.23)
天蝎座(10.24-11.22)
射手座(11.23-12.21)
摩羯座(12.22-01.19)
水瓶座(01.20-02.18)
双鱼座(02.19-03.20)
今日运势：
本日可多参与公众事务，将自己的意见与兴趣结合，提供同好们做参考，让欢乐的气氛添加一些趣味性...
24小时热帖
Copyright & 1998 - 2017 Tencent. All Rights Reserved&&&&& 刚刚完善了评价函数，这真是一个痛苦的过程。当然，所谓完善是现阶段的，因为它已经可以正常工作了，才称之为完善。从今天开始进行这个连载，当第三部分（基石）发布之后，我会把以前发的两篇删除。
&&&&& 首先，我们来认识一下&引擎&。实际上，这是一种人工智能，在国际象棋等等一些&信息完毕&的游戏中，早就实现了&计算机下棋的程序&，这些程序可以称之为&引擎&。也就是说，我们的连载的目标是实现一个五子棋的AI。实际上，网络上有很多这样或那样的&引擎&，但是我可以非常负责的告诉大家，用VB.NET写的、国内的、各种棋类的几乎没有开源的，估计不开源的也极少，用其他语言写的开源的，水平都不敢恭维，尤其是很多作者对传统的剪裁根本就没有理解或者理解是错误的。所以，写了这篇连载，主要是为了让用VB.NET并且有这方面兴趣的童鞋能够有一个参考，而我本身也是研究了&象棋小巫师&这一引擎的源码之后，写的这一系列的连载，其中非常多的东西都是参考其源码甚至照搬来的。巨建议访问来学习相关知识。
&&&&& 国际象棋的引擎起源很早，所以它对各种&信息完备&的游戏的引擎开发都具有非常重要的借鉴意义。中国象棋的引擎就是如此，而且现在已经有非常厉害的象棋引擎，象棋巫师本身的棋力也是很高的，当然，和象棋旋风等一些顶尖的象棋引擎相比，还有一些差距。那么，什么是&信息完备&的游戏呢？通俗一点说，就是知道对方有什么子！当然，对方也知道我们都有什么子。说白了，就是明棋。例如，国际象棋，中国象棋，五子棋，黑白棋（奥赛罗），兽棋，井字棋等等，不胜枚举；而像军旗、各种翻棋等等就不属于这个范畴了。
&&&&& &信息完备&的游戏，在开发引擎时，基本上都是使用剪裁的方式来进行搜索，我们搜索的越深，那么棋力应该越强。就像人类棋手下棋时一样，往往分析的步数越多，那么他下的越好。有些观点认为计算机下棋与人类棋手下棋思考方式有着根本性的差异，我本人不赞同这种观点：无论是计算机，还是人类棋手，都是在搜索，并且是非常相似的。下面来解释一下我的观点：
1、实现界面和位棋盘
2、我的五子棋引擎如何评价局面
3、基石&&超出边界的alpha-beta剪裁
4、接近人类的思考方式&&迭代加深、棋盘剪裁、空招剪裁、冲棋延伸
5、重点问题重点分析&&静态搜索
6、记住曾经的思考&&置换表
这是我们的五子棋引擎中使用的各种技术，这些技术都是为了提高搜索速度、准确度而服务的。除了位棋盘和思考方式无关之外，其他的都是与思考方式有关的：
2、我的五子棋引擎如何评价局面
评价局面，无论是计算机还是人类，都必须要做的，这是最根本的东西，它体现了这种棋类游戏的&规则&。在我的五子棋引擎中评价函数是一个比较长的函数：
首先，对棋型进行模板匹配&&因为人类棋手也是要识别哪些棋型胜利，哪些棋型失败，哪些棋型发展潜力比较大，哪些棋型要冲，哪些要堵
然后，综合考虑各个棋型&&当对方冲4，我们怎么办？当对方活4，我们是不是成5，如果不成，那很遗憾，我们输了，这也意味着对方活4之前我们走的那步棋（甚至前几步）是臭棋。这样，我们就可以给一步棋打分，当然，计算机是用确实的分数来体现的，而人类棋手是以&分数&排序来体现的。可无论如何，我们的程序还是会把走法按分值排序，因为这有利于剪裁，而剪裁越合理（理想状况下剪裁掉全部不合理走法，剩下的合理走法会很少），那么下一步要搜索的走法就越少，可以节省更多的时间来搜索更多的步数。
程序的思考和人类棋手的思考惊人的一致。
3、基石&&超出边界的alpha-beta剪裁
人类棋手会首先找到几种可能的走法，然后再继续分析，如果我这样走，对方怎么走呢？如果对方这样走，那么我怎么走呢？当发现一步棋演变若干次之后，对自己不利，那人类棋手就会舍弃这种走法。这就是剪裁。
程序的做法，和人类棋手是完全一样的。
4、接近人类的思考方式&&迭代加深、棋盘剪裁、空招剪裁、冲棋延伸
人类棋手首先会考虑当前局面下，自己认为最好的走法（对其进行深入思考），然后考虑其他走法是否好过前面的走法
程序也是这样，搜索1层，进行排序，然后从最好招法进行深入搜索
人类棋手下棋时，不会考虑离棋子很远的位置，例如棋都集中在中间时往角上下一个子明显是不明智的，尤其是五子棋这种&咬得很紧&的棋类，那样做明显是在自杀。
我的程序在生成全部走法时，从位棋盘生成一个&合理棋盘&，它包含了所有棋子周围的3格。
人类棋手经常会考虑，对方下一步会走什么棋更有利？
程序在评价每一步棋时，会在搜索之前，进行&空步剪裁&，以期知道对方的&好棋&，并且评价这个&好棋&是不是会给自己造成致命的结果，从而提出应对策略。
人类棋手下棋时，会首先考虑对方是不是已经要杀死自己了？例如，对方有一个活3，那很明显，人类棋手立刻立马上马意识到去堵或者冲比对方更快达到5的棋，为什么，因为他知道自己如果没有更好的棋再不堵上对方那就输了！
程序也是这样，当被冲的时候，就分析自己是不是比对方冲的更接近5，如何封堵对方的棋？当然，这里可能涉及到自己冲棋是否能同时解决对方的成棋并获得更有利局面。但如论无核这都是更深层搜索所要解决的问题，也就是&冲棋延伸&&&针对冲棋的情况，进行更深入的搜索，深入程度甚至有可能达到把棋盘下满！
5、重点问题重点分析&&静态搜索
人类棋手在预测若干步之后，确认某一步棋更好，如果是高手还会想一想，这步好棋若干步之后，对方还有没有什么招数呢，自己能不能产生杀招？也就是检查一下自己的思考是否有什么漏洞，对这步棋进行更深入的考虑，这往往是落子之前最后一道工序了。
程序也是这样，当进行alpha-beta剪裁得到一个满意的结果之后，会进入静态搜索，以期验证若干步之后，对方确实不会出现翻盘的情况，而自己尽可能给对方造成更多的麻烦，甚至杀死对方。
6、记住曾经的思考&&置换表
人类棋手是有记忆的，这包括刚才他分析过的各种可能，也包括以往积累下类各种经验（例如什么棋型必胜，如何走必胜）。
程序也可以这样做：
短期记忆：把分析过的局面记录下来，那么当&这种局面刚才我已经分析了！&的时候，可以不必再次分析，而直接取出分析结果。
以往经验：使用开局库，残局库等技术来实现。
下集预告：
1、实现界面和位棋盘
全部文章和源码整理完成，以后更新也会在下面地址：
Views(...) Comments()}