基于Xcode的智能五子棋的设计

计 算 机 与 现 代 化 2012 年第 2 期 JISUANJI YU XIANDAIHUA 总第 198 期 文章编号: 1006-2475( 2012) 02-0185-02 收稿日期: 2011-09-09 作者简介:汪婷( 1985-) ，女，江西宜春人，南昌航空大学信息工程学院硕士研究生，研究方向:工业过程检测与自动化技术; 喻金科( 1965-) ，男，南昌航空大学信息中心主任，教授，硕士，研究方向: 计算机网络与控制，数据库技术，数据通信。 基于 Xcode的智能五子棋的设计 汪 婷1，喻金科1，2 ( 1．南昌航空大学信息工程学院，江西 南昌 330063; 2．南昌航空大学信息中心，江西 南昌 330063) 摘要: AI( Artificial Intelligence) 即人工智能是在多种学科相互渗透的基础上发展起来的一门新兴边缘学科，在这一领域 多以博弈为例进行研究。本文利用 Xcode作为开发工具，根据博弈树的启发式搜索原理，设计一个五子棋程序，实现人 与计算机的博弈。 关键词: AI; 五子棋; Alpha-beta剪枝; Xcode 中图分类号: TP18 文献标识码: A doi: 10． 3969 / j． issn． 1006-2475． 2012． 02． 049 Design of Intelligent Gobang Based on Xcode WANG Ting1，YU Jin-Ke1，2 ( 1． School of Information Engineering，Nanchang Hangkong University，Nanhang 330063，China; 2． Information Center，Nanchang Hangkong University，Nanchang 330063，China) Abstract: AI( Artificial Intelligence) is a kind of newly emerging frontier science that is developed from many sciences’interinfil- tration，in this field often is studied on game playing． This paper uses Xcode as development tool，according to the algorithm of game playing tree’s heuristic researching，designs a game of gobang，realizes game playing between human and computer． Key words: AI; gobang; Alpha-beta pruning; Xcode 0 引 言 AI是研究人类智能活动的规律，构造具有一定 智能的人工系统，研究如何让计算机去完成以往需要 人的智力才能胜任的工作，研究如何应用计算机的 软、硬件来模拟人类某些智能行为的基本理论、 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 和技术。博弈作为一类富有智能行为的竞争活动，为 AI提供了一个很好的模拟研究场所。本文以五子棋 为入口，采用博弈树的启发式搜索中的 Alpha-beta 剪 枝方法，在 Xcode环境下实现了人机对弈。 1 用户界面设计 本文以 Xcode作为开发工具，借由其优秀的监听 机制和方便的控件类设计，开发出一个友好的用户界 面。设计首先创建一个自己的类( my object) ，并创建 一个作为它实例的对象。这个对象可以接收来自各 控件的信息，并且执行相对应的动作。如图 1 所示， my object会接收来自 button1 和 button2 的信息上，进 行相应处理并且最终将结果显示在 text field 里。假 设 button1 和 button2 是已走步的两方棋子，这时 my object会根据算法去判断是否有某一方胜出。如若 胜出就把结果显示在界面上，并终止当前游戏; 否则 继续走步、判断结果。 图 1 对象间信息传递图 2 五子棋核心算法 五子棋以五子在一线上为取胜原则，在 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 的竞 技中还对先下子方设有禁手。在判断哪种走步最有 利时往往先要计算出几个走步之后的局面，从而选择 出当前的最佳走步。Alpha-beta 剪枝是一种改进的 极大值极小值搜索法，这种方法较极大值极小值法可 186 计 算 机 与 现 代 化 2012 年第 2 期 减少搜索，提高效率。 假设约定: A 方为计算机，B 方为人; A 方先走 步，评估 函数 excel方差函数excelsd函数已知函数     2 f x m x mx m      2 1 4 2拉格朗日函数pdf函数公式下载 从 A 方立场出发; 若走步后对 A 方有 利，则 A 方得分 X，B 方得分为-X。极大值极小值法 中，先生成博弈树和节点，如图 2 所示。在局势 0 对 应 A方走步的选择，A方应从局势 1 ( B11，B12) 中选 取较大的值做为最佳走步。在局势 1 中 B 方应从局 势 2( A21，A22，A23，A24 ) 中选取较小值作为其最佳 走步。由此，只要评估函数给出相应静态值，从博弈 树最底层开始，可以依次反推算出各层节点估计值。 最终可以确定最佳走步。 图 2 极大值极小值搜索示意图 很显然极大值极小值试图穷尽所有可能走步的 搜索，事实上这是不可能的。因为在 15* 15 的棋盘 中，第 1 个棋子可形成 255 种局势，而可与之形成五 子连珠的后续点至少有 30 个，假设双方下了 5 个回 合即棋盘上有 10 个棋子，可能的局势就有 3010种。 与极大值极小值不同 Alpha-beta 剪枝可剔除某些没 有意义的搜索，减少搜索量。而且它的叶节点一产生 就被评估函数赋予静态值。 假设约定，P( X) 为某节点推算值; C( X) 为某点 静态值; F( X) 为某点最终值。事实上推算值比静态 值更为准确，故某点最终值由推算值得出，静态值只 作为参考。通常把情况下认为叶结点的静态值与推 算值、最终值都相等。 图 3 Alpha-beta剪枝搜索示意图 如图 3 所示，根据深度优先法则，首先生成一系 列点 A01-B11-A21-B31-B32-B33，且同时赋予叶结点 静态值: C( B31) = 2，C ( B31 ) = － 1，C ( B33 ) = － 1。 根据极大值极小值可知，F( A21) ≥2，并且有 P( B11) ≤2。再看点 B11-A22-B34，C ( B34 ) = 0，必有 P ( A22) ≥6，且 P ( B11 ) ≤6。综合 P ( B11 ) ≤2 与 P ( B11) ≤6，可以得出 F ( B11 ) ≤2，此时即可停止对 B35 相关节点的搜索。同理，由 C ( 36 ) = 0，可得 P ( A23) ≥0，P( B12 ) ≤0。由 F( B11 ) ≤2 与 P ( B12 ) ≤0 可得，F( A01 ) ≥2。此时可停止对 B37、A24 相 关节点的搜索。故 A01 的最佳走步为 B11。 3 结 果 由图 3 可以看出利用极大值及小值方法需要搜 索 16 个点，而用 Alpha-beta 剪枝后只搜索 11 个点。 Alpha-beta剪枝减少了搜索量，但并不影响搜索结 果，从而提高了搜索速率。这种效果在博弈树越复杂 的时候效率越高。Alpha-beta 剪枝算法的优秀程序 很大程度上依赖于节点的顺序，最坏的情况会出现极 大值极小值搜索。但从多次运行程序结果来看，几乎 不会出现这种情况，就像也不会出现最好的情况一 样。从算法速度、算法复杂程序、实验结果的综合角 度来看，这种搜索算法都表现出很好的博弈水平。 4 结束语 AI关键在于能否使计算机具备和人一样思考事 情的能力，本文在 Xcode环境下实现的五子棋有足够 的响应速度、具备一定的“思考”能力，结果表明 Alpha- beta剪枝算法在智能五子棋程序设计中是成功的。 参考文献: ［1］ Nils J Nilsson．人工智能［M］．郑扣根，庄越挺译．北京: 机械工业出版社，2000． ［2］ 孙宏伟，何丰泉．五子连珠棋初步［M］．哈尔滨:黑龙江 科技出版社，1999． ［3］ 王鲁明，戴汝为．在计算机围棋中形象思维的研究［J］． 自动化学报，1997，23( 4) : 564-566． ［4］ 董红安，蒋秀英．智能五子棋博弈程序的核心算法［J］． 枣庄学院学报，2005，22( 2) : 61-65． ［5］ 王永庆．人工智能原理与方法［M］．西安: 西安交通大学 出版社，1998: 288-290． ［6］ 翟锡泉，白振兴，包建平． 棋类博弈算法的改进［J］． 现 代电子技术，2005，28( 1) : 96-99． ［7］ 肖齐英，王正志．博弈树搜索与静态估值函数［J］．计算 机应用研究，1997，14( 4) : 74-76． ［8］ Knoth D E，Moore R W． An analysis of Alpha-beta pruning ［J］． Artificial Intelligence，1995，6( 4) : 293-326． ［9］ 李勤丰． 智能五子棋中的算法研究［J］． 广西轻工业， 2007，23( 11) : 69-70，79． ［10］张海峰，白振兴，张登福．五子棋中的博弈智能设计［J］． 现代电子技术，2004，27( 7) : 25-27． ［11］王小春．游戏编程( 人机博弈) ［M］． 重庆: 重庆大学出 版社，2002． ［12］王志水．基于搜索算法的人工智能在五子棋博弈中的应 用研究［D］．东营: 中国石油大学，2006． ［13］ Bert Altenburg，Alex Clarke，Philippe Mougin． Become an Xcoder［M］．北京: 人民邮电出版社，2009．