电脑应用技术 二零零九总第七十二期 基于神经网络思想及 α-β 方法的五子棋算 法设计 唐永强 1 汪波 2 1 大庆石油学院 电气信息工程学院，黑龙江 大庆，163113 2 大庆钻探工程公司 钻井一公司，黑龙江 大庆，163411 摘 要：本文设计了一种基于神经网络思想及α-β方法的五子棋算法。结合神经网络思 想及α-β方法，本文探讨博弈的搜索方法及推理技术中优化五子棋算法的思路，并最终 利用VB语言实现了五子棋最优路径的选择。 关键词：优化 算法 五子棋 规则 α-β剪枝 神经网络 An Algorithm of the Gobang based on NN and α-β pruning Zoro Tang1 Wang Bo2 1 Daqing Petroleum Institute, School of Electric Information Engineering, Heilongjiang Daqing, 2 Daqing Drilling Engineering Company, the First Drilling Company, Heilongjiang Daqing, Abstract: Based on NN and Alpha-Beta pruning, this article introduces an algorithm of the gobang. Through operations of VB including finding, calculating, statistical computing and selecting data in the link, the optimism point will present. Keywords: optimism; algirism; gobang; rules; Alpha-Beta pruning; neural net 1 引 言 人工智能是一门综合性很强的边缘科学，它研究如何使计算机去做那些过去只能靠人 的智力才能做的工作，而博弈是人工智能研究的一个重要分支。 传统五子棋的棋子为黑白两色，采用围棋棋盘15×15，棋子放置于棋盘线交叉点上。 两人对局，各执一色，轮流下子，先将横、竖、斜的5个或5个以上同色棋子连成不间断的 一排者为胜。因传统五子棋在落子后不能移动或拿掉，所以也可以用纸和笔来进行游戏[1]。 五子棋是起源于中国古代的传统棋种之一，是一种两人对弈的纯策略型棋类游戏，是 起源于中国古代的传统黑白棋种之一。发展于日本，流行于欧美。。与其他棋类相比，虽 然五子棋每一层搜索节点数量庞大，但因其规则简单，估值函数可以做到比较细致。本文 在Alpha-Beta搜索与神经网络算法结合估值函数方法的基础上，提出一系列优化五子棋搜 索及算法的措施，设计完成一个智能程度较高的五子棋系统[2]。 27 

电脑应用技术 二零零九总第七十二期 2 传统五子棋算法介绍及初步实现 一般地，传统五子棋的算法主要包括：估值函数和搜索算法等。 2.1 估值函数 不同的棋型，其优先级不同。例如，某一点落子后单纯形成死四加活三，而不考虑其 他因素的前提下，显然其优先级与活四是等价的，而比双活三的优先级要高。要使计算机 正确地做出这种判断，就要把这种棋型的估值设高。 为方便分析棋盘上的格局，本文中约定以“0” 代表棋盘上空位， “1”代表黑子，“2” 代表白子，“？”代表当前空位。本文以本方所持子为黑子即“1”为例，对特定棋型的估值的 标准如表1所示。 表1 特定棋型的估值标准 棋型名称 死一 活一 死二 活二 死三 活三 死四 活四 棋型模式 2100 00100 21100 001100 211100 0011100 2111100 00111100 估值 0 10 20 30 40 70 80 150 算法中关于棋子死活的规定如下：一方落子后，它的落子连成的一条线有两条不损伤 的出路，则称该棋型是活的，否则称该棋型是死的。例如棋型“2011102”就不能认为黑子 是一个活三，而大致与死三等价。棋型“20111002”也不是活三，但由于它有可能成为活四， 因而分数介于死三和活三之间。这样，棋型的估值设计才能比较细致。 估值一点的数值时，需要从水平、竖直和两条为45 度角和135 度角的线四个方向上 来考虑所下棋子对当前盘面的影响，但是一步绝杀或双杀的棋除外。而且这只是一步的情 况，本文程序模拟并推算到第四步，而最终落子要由第一、二步综合考虑决定，除非三、 四步出现绝杀。 2.2 Alpha–Beta 搜索 正如上所诉，在博弈问题中，每一个格局可供选择的行动方案都有很多，因此就生成 十分庞大的博弈树。例如本文第一步就要取进攻分数最高的3个点，防守分数最高的3个点 和综合分数最高的3个点共9个点（9个点可能有重合），除非第一步就出现绝杀或双杀的 情况。当然本文考虑对手只看一步，但考虑最糟糕的情况，第二步有9×9×9种情况，并且 要储存9×9种棋盘。在极大极小搜索的过程中，存在着一定程度的数据冗余，因此本文引 入Alpha– Beta(α-β剪枝)方法。 文献[3]详细解释了α-β剪枝方法，这里只做简单描述。α剪枝为因为某条分支多部节 28 

电脑应用技术 二零零九总第七十二期 点分数总合还不及某一节点单步分值，而去掉那条分支不考虑；β剪枝为因为某一节点单 步分值远大于其他节点（即可能出现绝杀)，而去掉其他节点不考虑。 α-β剪枝方法的代码是网上的公共资源，所以这里不再给出。 由于本文本来就是选取最大的情况，α-β剪枝方法常常不起作用，而使减少计算量的 效果不明显；而且α-β搜索随着搜索层数的增加，算法的效率大大下降（多步后的绝杀棋可 能由于前几步分值过低而被无视）。所以搜索的效率还是不理想。 3 神经网络思想对五子棋算法的优化 因此，本文在上述基础上继续研究，通过引入神经网络思想的方法对算法的优化与修 正，针对五子棋本身的特点和规律，提出采取以下优化措施，显著地提高了五子棋程序对 弈的水平，降低计算量。 3.1 分类评分 在对一点进行评估打分时，由于在实战中遇到的情况千差万别，而本文要尽量取到所 有情况，所以计算量非常大，而且没有绝对固定评分算法。为了能对每种情况进行打分， 要先对所有情况进行分类，然后根据分类后的不同情况，进行再分类或采用不同方法进行 再分类。为了方便分类评分，本文引入了神经网络的思想，没种情况的打分方法都可以看 成一个专家系统。下面以某一点的单步单方向评分为例来具体讲解。 表2 单向取点可能取到的所有情况 取1点 取2点 取3点 ?1 ?0 ?11 ?10 ?01 ?00 ?111 ?110 ?101 ?011 ?010 ?100 取4点 ?1110 ?1101 ?1011 ?0111 ?1100 ?1010 ?0110 取5点 ?11101 ?11011 ?10111 ?11100 ?11010 ?10110 ?01110 以本方所持子为黑子，方向为水平方向为例讨论统计方法。由棋盘上待分析的点为中 心向左右取点，累计到计数器S1、S2、S3、S4中。S1为该点所在线上白子（不同色棋子） 或棋盘边界之间子数，S2为统计与该点直接相连的黑子（同色棋子）的个数，S3为正向空 位个数，S4为反向空位个数。以向右取点为例，具体规则为：每取一点S1加1，如果取到 黑子S2加1，如果取到空位S3加1，当取到该方向的第一个空位时S1不再计数，如果取到白 子或碰的棋盘边界停止取点，如果S3累加到2即取到两个空位时停止取点，如果始终未出 现停止情况最多取5点。最后将所有该点所在线上白子或棋盘边界之间棋子存入字符串变 量（字符型数组）temporary。所有单向取到的情况如表2所示，但双向情况就太多了。 本文初次分类按照S1即字符串temporary的长度进行分类，分为S1<4、S1=4、5、6、7、 8、9、10八类。其中第一类由于总长度不足5，所以全都得0分；第八类的所有情况都是与 活四等价的绝杀，所以都得150分。第二类比较适合再分类方法，按照S3+S4=1、2、3、4 29 

电脑应用技术 二零零九总第七十二期 （按空位数分类）分为四类，S3+S4=1时的所有情况都与死四等价，所以都得80分，S3+S4=2 时的所有情况都与死三等价，所以都得60分，等等。第七类比较适合类表比对方法，除了 “0011?01110”、“0101?01110”、“0110?01110”、“01110?0110”、“01110?1010”、“01110?1100” 六种情况得90分外，所有其他情况都是与活四等价的绝杀，所以都得150分。剩下的几种 比较复杂，需要综合分类，这里就不再讨论。 这样就得到了一个基本的分值，但由于存在很多分数相同的情况，还是不能真正的体 现出差别，而且最后选择时也会较难取舍。因此这个分值还要加上S2的平方，棋子越集中， S2的数值就越大。例如“00110100”的分值为74，小于活三的分值，活三“0011100” 的分值 为79。 其他方向也是同样的算法，然后把各个方向的分数累加到一起得出这个位置一步进攻 的总分值SSA。计算该位置防守的总分值SSD时，调用与计算进攻的总分值同样的函数， 只是输入值将“1”与“2”调换即可。SSA+SSD就是该位置的综合总分值。扫描所有点即可取 出进行一步时，进攻、防守和综合分数各自最高的3个点。 3.2 记录特殊情况 由于有一些棋型虽然分值很大但应不是杀棋，举 个极端的例子，一个死四加三个死三的分值很大： 80+42+3×(40+32)=243，如图1的点0，因此电脑可能会 误 以 为 是 杀 棋 。 而 点 1 的 综 合 分 值 为 ： 70+32+50+1+2×(20+22)=172，其中进攻分值为148，但 却是绝杀。所以有必要储存所有绝杀的棋型。 解决这一问题可以借鉴神经网络的存储功能之一 特性记录所有的较特殊情况。本文也适当的记录了一些 五步的棋路。 但特殊情况之中，大多数情况还是存在共性的。此 1 0 外本文设计程序时，在统计的四步中，如果任何一步出现 图1 记录特殊情况 在一个方向上的进攻分值大于150的情况，就说明该点是绝杀点，于是返回分值时直接返 回这一点及以上各步落点的坐标值；如果任何一步出现在两个方向的进攻分值都大于70的 情况，就说明该点同样可能是绝杀点，同样返回这一点 及以上各步落点的坐标值。本文设计程序防守时，也所 采用了同样的方法。 而且神经网络还有学习功能，即如果出现未记录的 情况时，电脑自动将其储存，但本文并不具备这样的学 习能力，所以方法还有待进一步改进。 3.3 减少搜索范围 五子棋棋盘大小为15×15，传统算法中计算机每走 一步都要遍历整个棋盘，对于棋面上所有空位都进行试 探性下子并估值，这样大大影响算法的效率。其实在某个 图2 减少搜索范围 30 

电脑应用技术 二零零九总第七十二期 时刻，棋盘上很多的位置都是可以不用去考虑的[2]。比如下第一步棋，如图2只有黑子周 围16个点的综合值比其他点高且相等。其中靠近黑子的8个点防守值最大。但如果一个位 置附近的24个位置如果都是空位或者为出界时，那这点就直接跳过而不必考虑了。 4 建立模型数据结构 本文采用的编程语言为VB。首先，应该将棋盘进 行了数据化，五子棋采用的一般是15×15 的棋盘，如图 3所示。故采用的一个15×15的二维数组wzq()来存储棋盘 数据[4]，几个15×15三维动态数组来存储临时棋盘数据， 数据元素为字符型。而存储各点进攻、防守、综合评分 的变量为三个二维结构体型数组，其中分数与坐标绑定。 Private Type MS MS As Integer ’分值 Mx As Integer ’横坐标 My As Integer ’纵坐标 End Type 图3 程序的界面 5 结论与展望 本文提出了结合神经网络思想的五子棋优化算法、提高系统智能的措施。与其他五子 棋程序相比，由于采用上述优化策略，本文实现的五子棋程序在对弈的水平和搜索效率方 面的提高。 参考文献 [1] 国家体育总局棋牌运动管理中心. 中国五子棋竞赛规则(2009版). 北京体育大学出版社. 2009(2) [2] 王长飞, 蔡强, 李海生. 智能五子棋算法的设计实现. 系统仿真学报. 2009. 21 (4):1051- 1054 [3] 张 聪 品, 刘 春 红, 徐 久 成. 博 弈 树 启 发 式 搜 索 的α-β 剪 枝 技 术 研 究. 计 算 机 工 程 与 应 用. 2008. 44(16):54-97 [4] 郝伟. 一种优化模型对五子棋人工智能算法的分析与应用. 电脑知识与技术. 2009. 5(14): 3775-3776 [5] 李宁. 利用WPF实现基于MSN协议的五子棋游戏. 电脑编程技巧与维护. 2009. 11:70-77 [6] 仇宾, 苏双雷. 用Java实现五子棋人机博弈. 电脑编程技巧与维护. 2009. 5:73-77 31