六子棋计算机博弈系统的研究与实现.docx

1、六子棋计算机博弈系统的研究与实现六子棋计算机博弈系统的研究与实现六子棋计算机博弈系统的研究与实现摘要：本文简述了目前计算机博弈技术的发展状况，通过将六子棋游戏作为计算机博弈技术的研究平台，提出了六子棋计算机博弈的概念。通过对国内外相关研究现状的综述，指出本课题研究的意义。通过借鉴国际象棋和中国象棋计算机博弈中的成熟技术，提出了建立六子棋计算机博弈系统的关键技术。关键词：人工智能；六子棋计算机博弈；状态表示；着法生成；棋局评估；博弈树搜索；开局库1 引言人工智能诞生50周年以来，在知识工程、模式识别、机器学习、进化计算、专家系统、自然语言处理、数据挖掘、机器人、图象识别、人工生命、分布式人工智能

2、等各个领域得到了蓬勃的发展1。计算机博弈作为人工智能领域的一个重要分支，也得到了极其快速的发展，并为人工智能带来了很多重要的方法和理论，同时也产生了广泛的社会影响和学术影响以及大量的研究成果。博弈就是对策2，是自然界中的普遍现象，它不仅存在于游戏、下棋之中，而且存在于政治、经济、军事和生物竞争中，博弈的参加者可以是个人、集体、某类生物或机器，他们都力图用自己的智力去击败对手。体现计算机博弈技术的各种棋类游戏在其博弈技术研究中已取得相当丰硕的成果，且各种棋类游戏的计算机博弈系统也日趋完善，基本上能达到大师级水平。六子棋作为最近两年才兴起的棋类游戏，其计算机博弈技术和算法的研究相对较少3。2 六子

3、棋计算机博弈的研究意义人们常常把计算机博弈描述为人工智能的果蝇，即人类在计算机博弈的研究中衍生了大量的研究成果，这些成果对更广泛的领域产生了重要影响。通过博弈问题来研究人工智能典型问题，具有以下的优点4：（1）博弈问题局限在一个小的有典型意义的范围内，研究容易深入。（2）博弈问题非常集中的体现了人类的智能，已经足以为现实世界提供新的方法和新的模型。（3）专家经验容易获取。（4）进展可以精确的展示和表现出来，不同方法和模型的优缺点也容易比较。用一棵树来表示棋局发展的种种可能性，这种树叫做博弈树。根节点表示对局的开始状态，每一种可能的走法造成的结果作为其子节点，而对每一个这样的子节点，考虑另一方的

4、各种可能应对，作为下一层的子节点，这样一直找下去就得到了博弈树。它是一棵与或树。这是一个典型的指数复杂性问题，如何在这棵树上有效的搜得到军方和政府机构的支持和赞助。随着人工智能技术的不断发展与深入，更多学者将各种棋类游戏利用计算机程序实现对弈，如中国象棋、五子棋、西洋跳棋、桥牌、麻将等。六子棋是继五子棋公平性问题10之后，由台湾吴毅成教授发明，现正逐渐兴起。六子棋作为一种新颖的棋类游戏，由于它的特殊性，每次每方下两颗棋子。直观地看，其状态空间复杂度和博弈树的复杂度会成倍地提高，同时必须考虑两步棋的综合效用，即综合评估，在搜索算法上必须做到“两步”作为“一步”处理，即综合搜索。六子棋计算机博弈和

5、其他棋类的计算机博弈一样，都会用到一些最基本的搜索算法、模式识别及智能方法，并且可以采用一些发展较为成熟的计算机博弈技术。对六子棋计算机博弈的研究，不但能促进六子棋这项运动的发展，而且更能进一步推动计算机博弈理论的发展。在计算机日益普及和大众化的现代社会，高水平的博弈系统很容易获得可观的商业价值，目前，世界领先的计算机围棋程序基本上都是商业产品。事实上，个人计算机软件市场的大约80%销售额是来自游戏软件，其中有传统的博弈游戏，而非博弈游戏中也不可缺少人工智能与博弈的成分。3六子棋计算机博弈在国内外的研究现状3.1 计算机博弈研究发展简史计算机博弈，简单的说，就是让计算机像人一样从事需要高度智能

6、的博弈活动。研究者们从事研究的计算机博弈项目主要有国际象棋、围棋、中国象棋、五子棋、西洋跳棋、桥牌、麻将、Othello、Hearts、Backgammon、Scrabble 等11。六子棋是继五子棋公平性问题之后逐渐兴起了一款棋类游戏。其中二人零和完备信息博弈的技术性和复杂性较强，是人们研究博弈的集中点。二人零和随机性研究的一个代表是Backgammon，并且产生了很大影响。桥牌是研究不完备信息下的推理的好方法。高随机性的博弈项目趣味性很强，常用于娱乐和赌博，是研究对策论和决策的好例子。近代计算机博弈的研究是从四十年代后期开始的，国际象棋是影响最大、研究时间最长、投入研究精力最多的博弈项目，

7、成为计算机博弈发展的主线。1950年C.Shannon 发表了两篇有关计算机博弈的奠基性文章（Programming a Computer for Playing Chess和A Chess-playing Machine），其中提出了“极大-极小算法”(Minimax Algorithm )，奠定了计算机博弈的理论基础。随后，A.Turing完成了一个叫做Turochamp的国际象棋程序，但这个程序还不能在已有的计算机上运行。1956年Los Alamos 实验室的研究小组研制了一个真正能够在MANIAC-I机器上运行的程序（不过这个程序对棋盘、棋子、规则都进行了简化）。1957年Berns

8、tein利用深度优先搜索策略，每层选七种走法展开对局树，搜索四层，他的程序在IBM704机器上操作，能在标准棋盘上下出合理的着法，是第一个完整的计算机国际象棋程序12。1958年，人工智能界的代表人物H.A.Simon预言13：“计算机将在十年内赢得国际象棋比赛的世界冠军”。当然，这个预言过于乐观了。1967年MIT的Greenblatt等人在PDP-6机器上，利用软件工具开发的Mac Hack VI程序，参加麻省国际象棋锦标赛，写下了计算机正式击败人类选手的记录12。从1970 年起，ACM Association for Computing Machinery开始举办每年一度的全美计算机国

9、际象棋大赛。从1974年起，三年一度的世界计算机国际象棋大赛开始举办14。1981年, CRA YBL ITZ新的超级计算机拥有特殊的集成电路, 预言可以在1995年击败世界棋王。1983年, Ken Thompson开发了国际象棋硬件BELL E，达到了大师水平15。80年代中期,美国的卡内基梅隆大学开始研究世界级的国际象棋计算机程序“深思”16。1987年,“深思”首次以每秒75万步的思考速度露面, 它的水平相当于拥有国际等级分为2450的棋手.。1988年,“深思”击败丹麦特级大师拉尔森。1989年,“深思”已经有6台信息处理器, 每秒思考速度达200万步, 但在与世界棋王卡斯帕罗夫进行

10、的“人机大战”中, 以0比2败北。1997年，由1名国际特级大师, 4名电脑专家组成的“深蓝”小组研究开发出“更深的蓝”，它具有更加高级的“大脑”，通过安装在RS/6000S 大型计算机上的256个专用处理芯片, 可以在每秒钟计算2亿步, 并且存储了百年来世界顶尖棋手的10亿套棋谱, 最后“超级深蓝”以3.5比2.5击败了卡斯帕罗夫，成为人工智能领域的一个里程碑17。在其它博弈项目上，1962年Samuel等人利用对策理论和启发式搜索技术编制的西洋跳棋程序战胜了美国的州冠军。1979年H.Berliner的程序BKG9.8以7比1战胜了Backgammon 游戏的世界冠军Luigi Villa

11、。1980年美国西北大MikeReeve的程序The MOOR战胜了Othello 世界冠军18。1989年第一届计算机奥林匹克大赛在英国伦敦正式揭幕，计算机博弈在世界上的影响日益广泛 19。3.2 计算机博弈关键技术发展现状机器博弈被认为是人工智能领域最具挑战性的研究方向之一。国际象棋的计算机博弈已经有了很长的历史，并且经历了一场波澜壮阔的“搏杀”，“深蓝”计算机的胜利也给人类留下了难以忘怀的记忆。在国际象棋成熟技术的基础上，结合中国象棋和五子棋计算机博弈已有的研究成果，总结出计算机博弈系统的关键技术为：棋局表示、着法生成、棋局评估、博弈树搜索。3.2.1 棋局状态表示 要让计算机下棋首先需

12、要解决的是棋盘和棋局的数字表示。以中国象棋20为例，需要对棋盘、兵种、棋子、棋盘状态和比特棋盘进行表示。棋盘上面有9路10行形成90个交叉点，它很容易用109的棋盘数偶矩阵表示与坐标的对应关系。矩阵就是对棋盘的数偶表示。国际象棋和中国象棋黑红双方都由7种不同的棋子构成，所以要表示棋局则首先要给棋种编码。如图3.1是象棋兵种的中英文对照和棋天大圣、象棋明星的兵种编码。国际象棋KingRookKnightCannonQueenBishopPawn中国象棋KingRookHorseCannonGuardElephantPawn红子帅车马炮仕相兵Null字母代号krhcbep棋天大圣兵种编码12345

13、670象棋明星兵种编码020408060c0a0e黑子将车(砗)马(码)炮(砲)士象卒字母代号KRHCBEP棋天大圣兵种编码1234567象棋明星兵种编码121418161c1a1e图3.1象棋兵种的中英文对照以及棋天大圣、象棋明星的兵种编码要表示棋局则首先要给棋子编码，应该说编码的方法是任意的，只要能够满足棋局表示的唯一性和可区分性，都是可行的编码。如果考虑和追求棋局处理的节俭与快捷，那么在编码上还是具有研究的余地。如下图3.2是棋天大圣对棋子进行的编码。编码12345678910111213141516棋子黑将黑车黑马黑炮黑士黑象黑兵编码17181920212223242526272829

14、303132棋子红帅红车红马红炮红士红相红兵图3.2 棋天大圣棋子编码根据已经定义的编码方法和棋盘的初始局面，我们可以得出对弈过程中的棋局状态矩阵、棋子状态矩阵、棋子位置矩阵和比特棋盘矩阵。比特棋盘矩阵常用于着法生成过程中。在对弈过程中，有时只关心棋子的分布，而不关心是什么棋子，这时就会用到比特棋盘矩阵。比特棋盘是一个位长度的变量，用来记录棋盘上的某些布尔值。因为棋盘上有格，所以位正好对应它的格。比特棋盘位表示方法定义为：其中表示当前棋盘状态矩阵中某一位置的数值，表示对应位置有棋子，这时取1；表示对应位置为空，即无子，为0。3.2.2 着法生成着法生成方法一般有棋盘扫描法、模板匹配法和预置表法

15、，时常还结合使用。(1) 棋盘扫描法根据各种棋类游戏的规则，首先需要定义可行区域。在着法生成的过程中需要在棋盘上反复扫描有效区域、制约条件和落子状况，确定有效的落子位置。不同的棋类游戏有不同的规则，比如六子棋，棋盘有效区域内的所有空白的交叉点都是可行落子点；中国象棋根据行棋规则的不同，对落子位置有较多的限制，不适合用该方法。在着法的表达上，棋盘扫描法最为直观，在六子棋、围棋等棋类设计中经常使用，但时间开销巨大。(2)模板匹配法以中国象棋为例，当动子确定之后，其落址与提址的相对关系便被固定下来。于是可以为某些动子设计“模板”，只要匹配到提址，便可以迅速找到落址。如图3.3所示象棋中走马匹配模板。

16、当马对准提址，表示蹩马腿的制约条件，表示符合“走日”规则的落址，根据的具体分布，很容易判断可能的落址。再通过单项比特矩阵比对，实现“本方子则止，对方子则吃”，完成“提-动-落-吃”内容的确定。图 3.3 走马匹配模板(3)预置表法预置表法是使用最为经常的着法生成方法。它的基本思想就是用空间换时间。为了节省博弈过程中的生成着法的扫描时间，将动子在棋盘任何位置(提址)、针对棋子的全部可能分布，事先给出可能的吃子走法和非吃子走法。在中国象棋计算机博弈中，对于炮、车等可以利用预置表法进行定义。图3.4炮的一个行着法预置表以图3.4炮的一个行着法预置表为例，炮的提址为某行的第6列，该行考虑的棋子分布为1

17、01000010布尔向量形式。不难得出，此时炮的非吃子着法的落址为000110100，而可能的吃子着法的落址为100000000。将这样的输入(炮的列号、该行棋子的布尔分布)和输出(吃子落址和非吃子落址的布尔表示)关系写入一个预置表中，在使用时通过查表，便很快可以得到可行的着法。而且还可以区分开吃子着法和非吃子着法，必然有利于搜索路径的选择(先吃，后不吃)。3.2.3 评估函数评估函数是模式识别和智能算法应用最为广泛的领域。不管多么复杂的评估函数，都可以表示为一个多项式。评估函数一般来说必须包括5个方面的要素，分别是固定子力值、棋子位置值、棋子灵活度值、威胁与保护值、动态调整值，每一方面的值又

18、是由许多参数值构成的。即使最简单的评估函数也有20多个参数，将这些值线性地组合在一起得到最终的评估值21。 很多函数可以对局面进行评价，把这些函数加起来就可以组合成评估函数。以下是一些获取评估函数中数值的方法：（1）爬山法(Hill-Climbing)爬山算法22是一种局部择优的方法，采用启发式方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策。爬山算法一般存在以下问题：第一，局部最大；第二，高地，也称为平顶，搜索一旦到达高地，就无法确定搜索最佳方向，会产生随机走动，使得搜索效率降低；第三，山脊，搜索可能会在山脊的两面来回震荡，前进步伐很小。对局面进行评价时，每次对权重作很小的改

19、变，测试改变后的表现，仅当成绩提高时才采纳这个改变，需要重复很多次。这个方法看上去很慢，并且只能找到“局部最优”的组合(即评价可能很差，但是任何很小的改变都会使评价更差)。（2）模拟退火法(Simulated Annealing)模拟退火23是一种通用概率算法，用来在一个大的搜寻空间内找寻命题的最优解。模拟退火来自冶金学的专有名词退火。退火是将材料加热后再经特定速率冷却，目的是增大晶粒的体积，并且减少晶格中的缺陷。材料中的原子原来会停留在使内能有局部最小值的位置，加热使能量变大，原子会离开原来位置，而随机在其他位置中移动。退火冷却时速度较慢，使得原子有较多可能可以找到内能比原先更低的位置。模拟

20、退火的原理也和金属退火的原理近似：我们将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。对局面进行评价时，类似于爬山法，也是对权重做出改变来提高成绩的。但是如果改变没有提高成绩，有时候(随机地，给定一个几率)也采纳改变，试图跳出全局最优。这个方法需要给定一些几率，从几率高、梯度大的条件开始，然后逐渐减小。模拟退火法比爬山法更慢，但是最终可能得到比较好的值。（3）神经网

21、络(Neural Networks)实际上这更多地是一种评价函数的类型，而不是用来选择权重的：神经元是阈值(输入权重的和)的函数，第一层神经元输入的关于局面的性质(例如位棋盘表示中的某几个位)就可以构造网络，然后前一层的结果输入到后一层。因此单输入神经元的单层网络就等同于我们上次讨论过的一阶评价函数，但是接下来就可以构造更复杂的神经网络了，而且用这种方法作为评价函数是不难的(只要根据输入的改变来重新计算神经元的输出就可以了)。问题仍然像前面所说的，如何设置权重？除了前面的方法外，针对神经网络还发展出一些方法，例如“暂时差别学习”(Temporal Difference Learning)。其基

22、本思想是确定网络何时会作出坏的评价，并且让每个权重增加或减小看是否会评价得更好，这很类似于爬山法。跟其他自动学习的方法相比，神经网络的好处就在于它不需要很多人类的智慧：你不需要懂得太多的棋类知识，就可以让程序有个比较好的评价函数。但是根据目前我们掌握的情况，根据自己的智慧来做评价函数，要比机器学习做得好，并且做得快。（4）遗传算法(Genetic Algorithms)爬山法和模拟退火法可以得到一组好的权重，它们是逐渐变化的。而遗传算法24可以得到几组不同的好的权重，不断增加新的组合跟原来的做比较(取用某组中的某个权重，另一组中的另一个权重，互相交换得到新的)，通过淘汰坏的组合来控制种群的数量

23、。3.2.4 博弈树的搜索所有棋类的计算机博弈都涉及到搜索算法，搜索算法就是要根据当前的棋局状态以及规定的搜索深度和宽度，在博弈树中找到一条最佳路径。搜索算法是博弈树25求解的灵魂，只有有了有效的搜索算法才能在有限的时间内找到正确的解。搜索法是求解此类图模型的基本方法。我们无法搜索到最终的胜负状态，于是搜索的目标便成为如何在有限深度的博弈树中找到评估值最高而又不剧烈波动的最佳状态(棋局)，于是从当前状态出发到达最佳状态的路径便为最佳路径(Principal continuation)，它代表着理智双方精彩对弈的系列着法。而最佳路径上的第一步棋便成为当前局面的最佳着法(The best move

24、)。所谓“不剧烈波动”就是说最佳棋局不是在进行子力交换与激烈拼杀的过程当中。需要注意的是博弈树不同于一般的搜索树,它是由对弈双方共同产生的一种“变性” 搜索树。(1) 极大极小搜索我们考虑两个玩家对弈，分别为MAX和MIN。MAX先走，之后两人交替走步直到游戏结束。由于不可能对完整解图进行搜索，我们定义一个静态估计函数f，以便对游戏状态的当前势态进行估值26。一般规定有利于MAX的状态取f(p)0，有利于MIN的状态取f(p)0。用井字棋为例给出极大极小搜索的5个步骤27。a. 生成整个博弈树，即扩展树的每个节点。b. 用静态估值函数f 对每个叶节点进行估值，得出每个终节点的评价值。c. 用终

25、节点的估值来得到其搜索树上一层节点的估值。d. 重复c过程在MAX 层取其分支的最大值，MIN 层取其分支的最小值，一直回溯到根结点。e. 最终，根结点选择分支值最大的走步走2829。这就是极大极小搜索过程(MINIMAX Decision)。(2) 剪枝搜索在极小极大搜索方法30中，由于要先生成指定深度以内的所有节点，其节点数将随着搜索深度的增加呈指数增长。这极大地限制了极小极大搜索方法的使用。能否在搜索深度不变的情况下，利用已有的搜索信息减少生成的节点数呢？剪枝搜索31：剪枝搜索是一种基于剪枝32( cut-off)的深度优先搜索(Depth-first search)。它去掉了一些不影响

26、最终结果的分支而返回与MINIMAX相同走步的过程。剪枝：在对博弈树采取深度优先的搜索策略时，从左路分枝的叶节点倒推得到某一层MAX节点的值，可表示到此为止得以“落实”的着法最佳值，记为。显然此值可作为MAX方着法指标的下界33。在搜索此MAX节点的其它子节点，即探讨另一着法时，如果发现一个回合(2 步棋)之后评估值变差，即孙节点评估值低于下界值，则便可以剪掉此枝(以该子节点为根的子树)，即不再考虑此“软着”的延伸。此类剪枝称为剪枝。图3.5给出了搜索和剪枝过程34，最后得到如粗箭头所示的最佳路径片断。图3.5 剪枝剪枝：同理，由左路分枝的叶节点倒推得到某一层MIN节点的值，可表示到此为止对方

27、着法的钳制值34，记为。显然此值可作为MAX方可能实现着法指标的上界。在搜索该MIN节点的其它子节点，即探讨另外着法时，如果发现一个回合之后钳制局面减弱，即孙节点评估值高于上界值，则便可以剪掉此枝，即不再考虑此“软着”的延伸35。此类剪枝称为剪枝。图3.6给出了搜索和剪枝过程，最后得到如粗箭头所示的最佳路径片断。图 3.6 剪枝1975年Knuth和Moore给出了算法正确性的数学证明36。剪枝算法的效率与子节点扩展的先后顺序相关。有人将剪枝作用延伸到多个回合之后，于是又出现了深层剪枝(Deep cut-off) 算法37，也取得很好效果。(3) 窗口搜索从剪枝原理中得知，值可作为MAX方可实

28、现着法指标的下界，而值(应对方的钳制值)便成为MAX方可实现着法指标的上界，于是由和可以形成一个MAX方候选着法的窗口。围绕如何能够快速得到一个尽可能小而又尽可能准确的窗口，也便出现了各种各样的窗口搜索算法38。如Fail-Soft Alpha-Beta、Aspiration Search (渴望搜索)、Minimal Window Search (最小窗口搜索)、Principal Variable Search (PVS 搜索)/ Negescout 搜索、宽容搜寻(Tolerance Search)等39。(4) 迭代深化搜索在搜索过程中，博弈树深度为D-1层的最佳路径，最有可能成为深度

29、为D层博弈树的最佳路径。Knuth和Moore分析表明40，对于分枝因子为B的博弈树，利用-剪枝搜索D层所需时间大约是搜索D-1层所需时间的倍。如果国际象棋取B=36，每多搜一层就要花上原先的6倍时间。于是CHESS4.6和DUCHENSS课题组开始采用逐层加深搜索算法17。先花1/6的时间做D-1层的搜索，找到最佳路径，同时记载同形表、历史启发表、杀手表等有价值信息，以求达到D层最好的剪枝效果41，可谓“磨刀不误砍柴功”。目前几乎所有高水平的博弈程序都采用迭代深化算法，并在不断改进。如PV记录(Principal Variation)42，以及和渴望窗口搜索(Aspiration Windo

30、ws Search)43的结合，都会对走法排序产生非常好的效果。另外，逐层加深的搜索算法比固定深度搜索算法更适合于对弈过程的时间控制。(5) 启发式搜索(Heuristic search)具体问题的领域决定了初始状态、算符和目标状态，进而决定了搜索空间。因此，具体问题领域的信息常常可以用来简化搜索。此种信息叫做启发信息，而把利用启发信息的搜索方法叫做启发性搜索方法13。(6) 负极大值算法4445前面谈到博弈树的搜索是一种“变性”搜索。在偶数层进行“Max搜索”，而在奇数层进行“Min搜索”。这无疑给算法的实现带来一大堆麻烦。Knuth和Moore充分利用了“变性”搜索的内在规律，在1975年提出了意义重大的负极大值算法。它的思想是：父节点的值是各子节点值的变号极大值，从而避免奇数层取极小而偶数层取极大的尴尬局面。其中为的子节点。从以上有限的介绍不难看出，博弈树的搜索算法丰富多彩，改革、重组与创新的余地很大，一定会成为机器博弈研究的重点。3.3 六子棋计算机博弈的研究现状由于六子棋10发明不久，目前在学术界引起的关注较少。但是六子棋是一种新颖、有趣、易学难精的棋。由于每人每次下两步（第一步除外），所以它的对攻性强，可变性大，棋路开阔，且又免去了五子棋繁杂的禁手，