（计算机应用技术专业论文）提高五子棋博弈搜索算法性能的方法研究.pdf

中 文 摘 要 计算机博弈是人工智能领域一个极其重要且最具挑战性的研究方向之一，它涉 及搜索方法、推理技术和决策规划，被称为是人工智能的一块试金石。它的研究为 人工智能带来了很多重要的方法和理论，产生了广泛的社会影响和学术影响以及大 量的研究成果。计算机博弈中指定决策和选择决策，与政治、军事、经济、日常生 活中的决策有很多类似之处，是一种典型的决策系统，所以它的研究对于建立现实 社会的决策支持系统有很强的参考价值。在过去的半个世纪里，世界各地的学者花 费了大量的心血对于计算机博弈包括奥赛罗、checker、国际象棋、中国象棋、五子 棋、围棋进行研究。 棋类游戏是计算机博弈的一个标准性问题，各种搜索算法、模式识别及智能方 法在计算机博弈中都可以得到广泛的应用。本文中，我们通过五子棋程序的设计， 熟悉了传统的 alpha-beta 剪枝、 极小极大搜索算法、 置换表方法和威胁空间搜索法， 在此基础上，提出了用基于进化算法解决五子棋博弈问题的构想，表明了它的可行 性，并给出了并行遗传算法解决五子棋博弈搜索的设计方案。 关键词：人工智能；五子棋；遗传算法 abstract gambling and chess is one of the important and challenging subjects in artificial intelligence. it involves searching, reasoning and decision, and is called the touchstone in the artificial intelligence field. researching on gambling and chess bring many significant theory and approaches for us, which also produce many fruits for science and society. in gambling and chess, the designation and selection of decision is a typical decision system, which is similar to the decisions in politics, military affaris, economy and dialy life. therefore making a research on the gambling and chess is very helpful to establish realistic decision systems. in the last fifty years, researches all over the world have expended much time on the gambling and chess including othello, checker, chess, chinese chess, gobang, l-go, etc. chess games are standard problems in gambling and chess. in this paper, taking gobang as an example, we investigated the classical alpha-beta pruning algorithm, maxminum searching algorithm, permute table approach and threaten space searching approach. based on these work, we proposed and expounded a gambling scheme based on evolutionary algorithm and artificial immune. two schemes based on parallel genetic alforithm and immune forgetting are studied. key words: artifical intelligence; gobang; genetic algorithm 承承 诺诺 书书 本人郑重声明：所呈交的学位论文，是在导师指导 下独立完成的，学位论文的知识产权属于山西大学。如 果今后以其他单位名义发表与在读期间学位论文相关的 内容，将承担法律责任。除文中已经注明引用的文献资 料外，本学位论文不包括任何其他个人或集体已经发表 或撰写过的成果。 学位论文作者（签章） ： 200 年 月 日 第一章 绪论 1 第一章 绪 论 人工智能是近年来很活跃的研究领域之一。人工智能与生物工程、空间技术一 起被并列为当今三大新兴的综合性很强的尖端技术。如何让计算机去实现人类智能 呢？这就是人工智能所研究的内容。 人工智能是边缘科学, 各发达国家投入巨大的人 力和物力把人工智能作为重点列入本国的高科技发展计划当中。作为一门交叉学科， 人工智能包含很多的研究领域：机器学习、决策支持系统、机器视觉、专家系统、 自然语言理解等等。计算机博弈是人工智能领域一个极其重要且最具挑战性的研究 方向之一，简单说，博弈就是策略，在现实生活中普遍存在，比如在平常棋类对决 中，对是否能获得胜利取决于下棋者在对决中采取的策略，而且存在于政治、经济、 军事和生物竞争中。博弈的研究成果产生了广泛的社会影响和学术影响，并实际应 用于军事指挥和经济决策中，同时它作为人工智能的一块试金石标示出人工智能发 展水平。 1.1 计算机博弈 博弈思想最早产生于古代的军事活动和游戏活动。在体育游戏中，经常会出现 这种情况，即甲乙双方各出三个人进行摔跤比赛。甲乙双方的领头人不是让自己的 队员随意地同对方某一队员较量，而是先了解清楚对方三名成员的实力，并把对方 三名成员的实力同己方成员的实力作客观对比，然后作出决定：谁打头阵，谁在中 间，谁压轴，以自己的弱者去对付对方的最强者，以自己的最强者对付对方的次强 者，以自己的次强者对付对方的最弱者，保证二比一稳赢对方。 计算机像人一样从事智能的对奕活动就是计算机博奕。目前围棋，国际象棋， 五子棋，中国象棋，西洋跳棋，桥牌，麻将，hearts，othello，backgammon，sarabble 等1是研究者们从事研究的计算机博奕项目。从四十年代后期开始影响最大、研究时 间最长、投入研究精力最多的作为近代计算机博奕的研究博奕项目是国际象棋，国 际象棋成为计算机博奕发展的主线。 近代计算机博弈的研究是从 20 世纪 40 年代后期开始的。1950 年， programming a computer for playing chess和a chessplaying machine是由 c shannon 发表的有关计算机博弈的奠基性文章。在上世纪五、六十年代，研究者在 进行博弈研究产生树的过程中引入专家知识即 alpha-beta 剪枝、启发搜索对博弈树 的较优的搜索算法。使得不必要的节点不再产生，并以此来提高程序的效率。1951 年，一个叫做 turochamp 的国际象棋程序由 a.turing 完成，但这个程序还不能在已 提高五子棋博弈搜索算法性能的方法研究 2 有的计算机上运行。 五年之后， 一个真正能够在 maniac-i 机器上运行的程序由 los alamos 实验室的研究小组研制成功。1957 年，bernstein 开发了第一个完整的计算机 国际象棋程序，他的程序能在标准棋盘上下出合理的走法并能在 ibm704 机器上操 作，bernstein 是利用深度优先搜索算法，每层选七种走法展开对局树，搜索四层来 完成的。1958 年，人工智能界的代表人物 h.a.simon 预言： “计算机将在十年内赢 得国际象棋比赛的世界冠军。 ” 在上世纪六十年代，对博弈研究中开始引入机器学习，使机器自己不断改进自 己的博弈水平。它的主要观点是：1、改进评价函数的一些参数使博弈更加精确和实 用。2、通过记忆错误，使已经犯过的错误不再。3、计算机记录下经常见到的模式， 找出局部最好的应对。4、计算机自己掌握规则。这些研究对于人工智能的发展起了 很大的推动作用。1967 年，由 mit 的 greenblatt 等人开发的 machack vi 程序参加 麻省国际象棋锦标赛，创造了计算机正式击败人类选手的记录2。从 1970 年起，全 美计算机国际象棋大赛开始每年举办一次。从 1974 年起，世界计算机国际象棋大赛 开始举办每三年一度次。1997 年是人工智能领域的一个里程碑，国际象棋世界冠军 卡斯帕罗夫被 ibm 公司的超级计算机“深蓝”战胜了。 在其它的博奕项目上，1959 年一个具有学习能力西洋跳棋程序由 samuel 等人 利用启发式搜索技术和对策理论编制成功，这个程序它可以学习和改善自己的棋艺 在不同的对奕中。4 年后，设计者本人被这个程序战胜了。又过了 3 年，一个保持 8 年之久的长胜不败的美国冠军也被这个程序战胜了。这个程序充分展示了机器学习 的能力，让我们对计算机博弈有了新的认识。1979 年 backgammon 游戏的世界冠军 luigi villa 被由 h.berliner 开发的程序 bkg9.8 以 7 比 1 战胜了，程序 bkg9.8 采 用 b*算法（被称为到目前为止最具有人类风格的棋手）实现的，这是有史以来人工 智能第一次在具有相当智力的棋类比赛中计算机程序击败了世界冠军。1980 年到 1989 年期间计算机博奕得到了突飞猛进的进展，因此在世界上的影响日益广泛。 1988 年，卡耐基-梅隆大学的高材生许峰雄制造出了国际象棋电脑“深思”(deep thought)，并一举战胜了世界名将丹麦棋手本特-拉尔森。一年之后，博士毕业的许 封雄受聘于 ibm，并在大学同学莫里-坎贝尔和乔-赫内的帮助下于 1995 年研制出了 电脑“深蓝”(deep blue)。1996 年 2 月， “深蓝”以 2 比 4 输给当时的国际象棋世界 冠军俄罗斯人卡斯帕罗夫。但 15 个月后的 1997 年 5 月，经过改进的“深蓝”终以 3.5 比 2.5 战胜了卡斯帕罗夫，这场比赛在全世界范围内引发了轰动，这场胜利也成 为人工智能和超级计算机发展的重要标志。 第一章 绪论 3 近二十年来，中国象棋博弈系统的研究常常通过比赛博弈的方式来验证各自研 究的成果，当前的主要比赛包括：从 1989 年起每年举办的 computerolympiad(奥林 匹克计算机游戏程序竞赛)由 icga(icga，intemational computer games asociation)； 2004 年世界电脑象棋争霸赛在台湾成功大学举办；2006 年 8 月全国计算机博弈锦标 赛。在这些赛事上，来自海内外的专家学者及 18 支代表中国象棋计算机博弈最高水 平的参赛队伍会聚一堂，进行比赛和学术交流。这些比赛极大的推动了中国计算机 博弈的普及和发展。目前知名的象棋软件有:“棋天大圣” ， “象棋奇兵” ， “象眼 (elephanteye)” ， “纵马奔流” ， “谢谢大师”等十余种，其中一些己经接近或达到大师 级水平。简单的说，计算机博弈的程序, 至少应包括如下四个部分： 1. 数据结构：用来描述棋盘及棋盘上的棋子博弈的状态。 2. 着法生成：找到某个棋盘局面所有合法的走法，与棋盘的数据结构有关系。 3. 博弈搜索： 博弈树的搜索算法是博弈系统程序的核心， 决定搜索效率的关键。 4. 函数评估：对博弈过程中实际局面优劣的判断。 1.2 计算机博弈的研究意义 棋类游戏是对现实生活中各种矛盾、战争的模拟，下棋的双方无时不在调动自 己的一切智能，充分发挥逻辑思维、形象思维和灵感思维的能力。同时它规则简单、 易于实现，所以，在人工智能领域始终将棋类的机器博弈作为常用的研究平台之一。 以棋类游戏为研究和验证平台，各种搜索算法、模式识别及智能方法在计算机博弈 中都可以得到广泛的应用。 机器博弈作为一个非常具有说服力的例证证明计算机可以模拟人的思维能力， 机器博弈是人工智能的一个重要研究分支。前面提到在政治、军事、经济、日常生 活中方方面面都用到博弈技术，他们的决策和计算机博弈中决策有很多类似之处， 所以研究计算机博弈决策对于建立现实社会的决策支持系统有很强的参考价值，在 社会中计算机博弈研究项目经常得到军方和政府机构的支持和赞助。1990 年，美军 利用超级计算机对“沙漠风暴”行动进行成功的战略模拟，充分证实了计算机博弈 的意义。计算机博弈被人们描述为人工智能的果蝇，意即人类在计算机博弈的研究 中衍生了大量的研究成果。 另外，在信息爆炸和计算机普及的现代社会，益智趣味的博弈系统很容易获得 可观的商业价值。博弈的参加者可以是个人、集体、一类生物和机器。因此，市面 所销售的游戏软件大部分都具有计算机博弈成分。 提高五子棋博弈搜索算法性能的方法研究 4 我们在下棋过程中，对于棋局发展的种种可能性用一棵树来表示，这种树我们 称为博弈树。我们对博弈树的搜索来解决计算机博弈问题，也叫博弈树法。把下棋 过程中每思考下一步往哪走，称为一个应对，它的基本思想是：搜索从棋局开始状 态(根节点)出发，找出每一种可能的走法造成的应对(子节点)，再对每一个子节点考 虑另一方的各种可能应对(子子节点)，一直找下去，直到结束，由此构成一棵树，称 为搜索树。在搜索树中找出最佳最有利的子节点，并从该节点起做最优应对方案， 这是一个典型的指数复杂度问题，但涉及到计算量目前所有的计算机都无法承受的。 因此，计算机博弈问题用搜索树法来解决的话，必须给定一个有限的深度进行搜索， 得到一个 n 层的子树，并根据这一子树的叶节点进行优劣的判断。搜索算法通常使 用极小极大值算法、 alpha-beta 剪枝法、 并行遗传算法和免疫遗忘算法来提高搜索的 效率。 1.3 五子棋博弈 棋类游戏是计算机博弈的一个标准性问题，各种搜索算法、模式识别及智能方 法在计算机博弈中都可以得到广泛的应用，众多研究者也对其进行了长时间的研究。 目前，五子棋、中国象棋等棋类游戏的计算机博弈算法研究已相对广泛，某些棋类 的计算机水平已达到了世界冠军的水平。 五子棋是一种两人对弈的纯策略型棋类游戏，是起源于中国古代的传统黑白棋 种之一。发展于日本，流行于欧美。通过一系列的演变，使五子棋游戏复杂化和规 范化，最终成为当今的职业连珠五子棋。现代五子棋有“连五子” 、 “五子连” 、 “串 珠” 、 “五目” 、 “五目碰” 、 “五格”等很多种称谓。五子棋的文化源渊流长，不仅能 增强思维能力，还能提高智力；既有“场”的概念，亦有“点”的连接。五子棋既 简单易学，又有深奥的技巧和高水平的国际性比赛。在古代，五子棋棋具虽然与围 棋相类同，但是下法却是完全不同的。正如辞海中所言，五子棋是“棋类游戏， 棋具与围棋相同，两人对局，轮流下子，先将五子连成一行者为胜。 ” 。 有关早期五子棋的文史资料与围棋有相似之处，因为古代五子棋的棋具与围棋 是完全相同的。在上古的神话传说中有“女娲造人，伏羲做棋”一说， 增山海经 中记载： “休舆之山有石焉，名曰帝台之棋，五色而文状鹑卵。 ”李善注引三国魏邯 郸淳艺经中曰： “棋局，纵横各十七道，合二百八十九道，白黑棋子，各一百五 十枚” 。可见，五子棋颇有渊源。亦有传说，五子棋最初流行于少数民族地区，以后 渐渐演变成围棋并在炎黄子孙后代中遍及开来。据日本史料文献介绍，中国古代的 第一章 绪论 5 五子棋起源是高丽(朝鲜)，然后传到日本的。在日本明治 32 年(公元 1899 年)，经 过公开征名， “连珠”这一名称才被正式确定下来。从 1899 年到本世纪初连珠活动 规则不断变化发展直到趋于完善(即对执黑棋一方的限制)，例如，1899 年规定，禁 止黑白双方走“双三” ；1903 年规定，只禁止黑方走“双三” ； 1931 年规定，黑方 不许走“双四” ，并规定将 1919 的围棋盘改为 1515 的连珠专用棋盘。五子棋 传入欧洲并迅速风靡全欧。现在五子棋有许多的变种，在某种程度上，主要是对棋 手的限制，主要是抑制黑方先行者的优势。在本文中，讨论的是通常的自由式的五 子棋对奕，并没有涉及职业五子棋的对于一些规则的限制。本论文中五子棋的基本 规则如下： (1) 棋盘：采用正方形棋盘、国际上标准的 1515 路线的； (2) 下法：对弈双方分别执黑白两色棋子，分别轮流在棋盘上选择一个无子的交 叉点落子，无子的交叉点又被称为空点或合法点； (3) 输赢判断：在平面（棋盘）横线、竖线、斜线（无实线连接）上形成连续的 五个同色“点” （棋子） ，则对弈方赢。 1.4 本文研究内容与安排 本文以计算机五子棋博弈系统作为研究课题，认真整理了对五子棋博弈的专业 知识，针对五子棋博弈规则简单、局势容易判断的特点，对五子棋常见的开局、定 式及其后的对局做了细致的统计分析， 阐明了五子棋博弈中黑白双方优劣势并非均 衡的规律，这一规律作为一个指导原则，在设计五子棋博弈系统时起到重要作用。 计算机博弈实现存储与处理五子棋博弈数据，并能具体表示下棋的过程，并能让程 序知道现在的博弈状态，进行最优走法的判断。在计算机博弈理论中，搜索算法的 基础是极大极小搜索算法。重点对五子棋博弈的内在规律和专业知识进行分析研究， 通过估值函数来判断棋局局势优劣，估值函数与具体的棋类值是紧密结合的一部分， 是博弈程序的主要部分，估值函数很大程度上决定了博弈程序的棋力高低。因此给 出了提高五子棋博弈搜索的算法方法：置换表搜索算法、威胁空间搜索算法，并对 算法作了一定的改进。由于五子棋博弈中，黑方先行者占有很强的优势，大多数局 面往往都能找到致胜威胁次序，所以采用威胁空间搜索，结果表明，可以极大的提 高程序的表现和博弈水平。主要结构安排如下： 第一章：对计算机博弈技术的发展，现状与研究意义进行了介绍。介绍了本文 主要的研究内容五子棋博弈的规则。 提高五子棋博弈搜索算法性能的方法研究 6 第二章：研究了五子棋在计算机中的表示问题，讨论了计算机中存贮棋局和识 别下棋次序，局势状态变化及局势特征、走法产生等方法。按照人工智能和计算机 博奕的一般原理设计了一个五子棋博奕系统的基本模型。 第三章：研究了利用博弈树的极小极大搜索技术及 alpha-beta 剪枝过程和剪枝 优化问题结合估值函数实现一个五子棋对弈程序设计。并给出了适合五子棋对弈的 最佳算法：置换表搜索算法、威胁空间搜索算法。结果表明，以上算法在五子棋程 序设计中是成功的。 第四章：根据五子棋的特点，提取棋局局势的若干特征，对这些特征赋加权分， 并对整个棋局进行特征统计，提出基于进化计算的五子棋博弈算法设计方案，并给 出了基于并行遗传算法的博弈算法。 第二章 五子棋博弈在计算机中的表示 7 第二章 五子棋博弈在计算机中的表示 五子棋博弈就是说把五子棋对奕问题表示成可以被计算机可执行和实现，即把 五子棋棋盘局势状态、落子的顺序、局势状态的变化等问题形式化，转化成数据存 储在计算机中，并能让搜索、估值等算法对这些数据进行操作。 2.1 表示棋盘局势状态 棋盘是整个系统的核心，我们使用什么数据结构来表示棋盘上的信息呢？这就 是棋盘所研究的。在这里需要了解一些具体的棋类知识。通常，我们可以采用一个 二维数组来描述棋盘及棋子信息。哪个位置有黑子，哪个位置有白子以及哪个位置 是空点这是计算机必须记住来了解棋盘局势状态。在编写五子棋程序过程中，五子 棋的棋盘是 15 行，15 列，因此棋盘状态建立一张表格即用一个 1515 的二维数组 表示描述。数组的每一个元素对应于 1515 的棋盘中每一个交叉点，用数组 table_address 的下标来区分和表示每个交叉点， 即若是第 9 行第 8 列的交叉点, 则 table_address 的下标为 915+8=143。用 1 表示某交叉点上有棋子， 反之用 0 表 示。并将值存放于数组 table_address 中。每一个当前的棋盘局势状态都可以用长为 225 的字符串表示，1 表示棋盘上的黑子，2 表示白子，0 表示无子用。例如棋局 状态为 0212010210， 则表示第一行的第二个节点上为白子，第三个节点上为黑子， 第四个节点上为白子， 即数组元素的第 2、3、4 个位置上均取 1，下一步就不能在 这三个节点下子，当前状态下第一行的第二、三、四节点为非法走法。最后，在程 序中定义了一个结构 struct_sposition 表示棋子的位置；定义一个结构 struct_smove 用来描述棋子的走法。 2.2 棋盘中下棋的顺序表示与状态变化 五子棋下棋过程中下棋的顺序我们用堆栈的结构表示和存储棋子坐标，先下的 子放在栈的低端，后下的放在栈的高端，这样就保持了下棋的顺序，我们利用堆栈 的特点通过访问堆栈，可以得到下棋的顺序知道哪个棋子是先下，哪个棋子是后下。 例如：如图 2-1，棋盘上有四颗棋子分别表示为： 黑子下在（10，10）位置； 白子下在（10，11）位置； 黑子下在（9，11）位置； 提高五子棋博弈搜索算法性能的方法研究 8 白子下在（11，10）位置。 图 2-1 棋子存储的结构 由于我们程序中是采用堆栈的结构，下棋的双方每下一子，棋盘状态都会发生 变化，每一方下的棋子采用入栈操作就可将其存入栈中，棋盘状态就发生变化，当 我们恢复到前一状态时，可利用搜索过程的回溯发生用出栈操作退出一子，既棋盘 的状态恢复成原来的。也就是说由于搜索过程中有回溯发生，因此状态更新后，还 要能恢复成原来的。 利用棋盘状态的特征可以对棋盘的局势状态进行判断，在程序中采用字符串结 构表示棋盘状态的特征，估值函数必须能够提取出以便对局势进行判断。例如，用 “00000” 表示一个五子相连的特征。在某一状态的棋盘中寻找是否存在一个特征 的方法是什么？可以采用模式匹配的方法。 2.3 走法产生 计算机五子棋博弈是一种完备信息博弈(games of perfect information)， 意思是指 参与双方在任何时候只要看看棋盘，就完全清楚每一个棋子是否存在，位置在哪里。 为了实现人和计算机双方对弈，假设计算机是甲方，人是乙方，人和计算机博弈的 过程可以如下表述：假设首先由乙方走棋，他面对的是一个开始局面 1，从这局面可 以有 m 种符合规则的下法。这 m 种下法分别形成了局面 2，3， m+i。假设甲 选择了形成局面 2 的下法，轮到乙下棋。甲面对局面 2，又可以有 n 种可能的下法， 形成 n 种新的局面 k+1，k+2， k+n，如图 2-2 所示。 第二章 五子棋博弈在计算机中的表示 9 图 2-2 双方面对的局面 在程序中将一个局面的所有可能的走法罗列出来的那一部分程序就是走法产 生。走法产生是用来告诉其它部分下一步可以往哪里走的模块。各种棋类随规则的 不同，走法产生的复杂程度也有很大的区别。一般说来，在一种棋类游戏种，双方 棋子的种类越多，各种棋子走法的规则越多，则在程序中，走法产生的实现就越复 杂。因为五子棋的走法产生非常容易实现，下面给出在走法产生器类中寻找所有合 法走法的的函数实现： /用以产生当前局面 positon 中所有合法的走法 /position 是包含所有棋子位置信息的二维数组 /nply 指明当前搜索的层数，每层将走法存在不同的位置，以免覆盖 /nside 指明产生哪一方的走法，white 为白方，black 为黑方 int createpossiblemove(byte positiongrid_num,int nply,int nside) int i,j; m_nmovecount=0;/此变量记录所有合法的走法总数 for(i=0;igrid_num;i+) for(j=0;j0）在 k 层。如果想搜索博弈树到终局的一切可能性，那是 不可行的，因为不说存储器难以存储下庞大的数据，就是时间上的实现也是不可行 的。 因此， 对博弈树的搜索到一定深度就不再往下走了， 可以根据一个评估值函数 f， 对局势优劣进行判断，用估计值代替实际的搜索。程序的“智能”的高低由估值函 数的好坏直接决定。 3.2 alpha-beta 剪枝法 在极小极大值搜索算法过程中，搜索算法把整棵博弈树遍历了一遍，当搜索深 度增加时，搜索节点快速大幅增加，这是搜索量很大，时间和内存空间消耗太大, 搜 索效率降低。为了保持搜索效果同时减低工作量，于是在极小极大搜索算法的基础 上提出了 alpha-beta(简写为-) 剪枝技术。 - 剪枝算法是指9 10：当甲向下搜索节点时发现走第一个子节点就可以赢 了，则剩下的节点就不需要再搜索，甲的值就是第一个子节点的值。即可以将甲的 其余后继节点抛弃，此过程称为剪枝。如果甲所在的层是 max 节点的层，则称此 剪枝为剪枝，否则成为剪枝。如图 3-2 所示，若节点 a 在极大层，而节点 b 的 值为 15，节点 d 的值为 10，则节点 c 的值必 10，而 a 的值取 15，即 c 及其后继 节点就可以剪去，此过程为剪枝。若节点 a 在极小层，而节点 b 的值为 15，节 点 d 的值为 20，则节点 c 的值必 20，而 a 的值取 15，即 c 及其后继节点就可以 剪去，此过程为剪枝。 图 3-2 极大极小树 a b c fed 第三章 基于人工智能的博弈树搜索 13 与极小极大算法相比，-剪枝需要遍历的节点远远减少，它能在较短的时间 内找到最佳的走法节点。 虽然- 算法的搜索速度大有提高，但-剪枝搜索效率与节点的排列顺序 有很大的关系，还是不太理想，不利于人机博弈真正实现。分析-算法的实现过 程，使用-算法剪枝过程用到是深度优先算法，发现在一次搜索过程中被修剪的 枝数取决于早期的-值与最终的倒推值之间的近似程度，且剪枝数越多，搜索速 度越快。因此编写程序实现时先对棋子的位置进行排序4。再者，考虑到在现实下棋 过程中对奕双方一般都是在棋盘中心位置附近下子，且双方下子的位置一般都在对 方棋子的附近某个地方，因此不必要让计算机每次都从整个棋盘开始搜索，从而减 少搜索范围提高搜索效率。如果希望获胜的机率大一点就应该在棋盘中心下棋子， 相反在中心周围下子的机率机率就低点。 3.3 置换表（transposition table）搜索 -算法改进搜索算法的目标在于将不必搜索的（冗余）分枝从搜索的过程中 尽量剔除，以达到尽量搜索少的分枝来降低运算量的目的。可以通过 alpha-beta 剪 枝来剪除两种类型的冗余/分枝节点，使得已经搜索过的节点可以免于搜索。 提高五子棋博弈搜索算法性能的方法研究 14 图 3-3 极大极小树存在重复节点 现在来看一下如图 3-3 中极大极小树的片断，该片断从节点 a 开始，有两个分 枝 b 和 c(为简化问题，其他节点从略)，b 有子节点 d，c 有子节点 e，再往下 d 有 子节点 f，e 有子节点 g。可以看到，在极大极小树的不同分枝上，存在着完全相同 的节点，节点 f 和节点 g。对于节点 f，在搜索节点 b 的时候，就可能已经搜索过 了。那么，在搜索 g 的子节点时，我们能不能直接利用已经搜索过的节点 f 的结果， 而不是重新搜索一遍节点 g 呢？想法是可行的。在这里我们就要用一张表把搜索过 的节点记录下来并记录已经搜索过的节点的结果。然后在后续的搜索中，在察看记 录在表中的这些结果发现某个节点已有记录，可以直接利用记录下来的结果。避免 了重复搜索，这种方法叫做置换表（transposition table，简称 tt）11 12。如果将每 一节点的结果都记录下来在 alpha-beta 搜索过程中， 则在搜索之前先察看这些记录， 就可避免很多的重复的操作。 第三章 基于人工智能的博弈树搜索 15 3.4 威胁空间搜索（threat space search） 在这部分里，我们将首先讨论三个方面的五子棋知识以及它们的应用。第一方面 的内容包括一些对棋手（人和计算机）来说非常重要的术语。我们将这些术语用于 “威胁次序” 。第二方面的内容介绍人类五子棋棋手思考时的策略。接下来介绍的是 常规的五子棋程序走法选择的处理过程。最后，我们研究人类和计算机在走法选择 的方法上究竟有多大程度的不同。从而使我们发现常规的五子棋程序在哪些方面有 所欠缺。 图 3-4 威胁的类型 五子棋对奕中， “威胁”是个重要的概念。最主要的威胁有以下四种类型： 1、冲四（图 3-4a） ：在有五个点的一条直线上，其中任意四个点被攻方棋子占 据，而第五个点是空白的。 2、活四（图 3-4b） ：在有六个点的一条直线上，攻方棋子占据了中间的四个位 置，并且外面的两个位置是空白的。 3、活三（图 3-4c,d） ：可以有两种情况，一是在有七个点的一条直线上，中心的 三个点被攻方棋子占据，其余的四个点是空的；或者是在有六个点的一条直线上， 中心位置的四个点中有三个被攻方的三个紧密相连的棋子占据，其余三个位置是空 白的。 4、断三（图 3-4e） ：在有六个点的一条直线上，攻方三个并非紧密相连的棋子 占据中心四个位置中的三个，而其余的三个位置是空白的。 如果棋手走出了一个冲四，他的下一步就会形成一个致胜的“威胁” 。因此，这 个威胁必须立即应对。如果在对奕过程中，走出了一个活四，那么，对手的任何应 提高五子棋博弈搜索算法性能的方法研究 16 对都太晚了，因为攻击者的下一步走子有两个空白的位置可以取胜。对于活三，攻 击者的威胁是下一步走子可以形成一个活四，因此，即使活三这种威胁需要两步才 能获胜，但是它也必须马上应对。如果活三的两侧都可以形成活四，那么就有两种 应对的走法， 都是直接走在攻击子的相邻位置(图 1c)； 如果活三只有一侧可以形成活 四，那么可以有三种应对的走法(图 1d)。另外，对于断三而言，也可以有三种应对 的走法（图 1e） 。 一个棋手若要在对手任何可能的应对情况下取得胜利， 就必须形成双重威胁 （可 以是一个活四或者是两个单独的威胁） 。在大多数情况下，若要形成双重威胁，通常 是一系列连续进行的包含若干威胁的走子。我们将上述形成（致胜的）双重威胁的 一系列威胁走子序列称之为致胜威胁次序。致胜威胁次序中每一次威胁走子都迫使 防御方应对威胁。因此，对于防御者来说，机会是有限的。 图 35 包含冲四的致胜威胁次序 在图 2 中，棋盘的形式表明，黑方可以通过只包含冲四的制胜威胁次序取得胜 利。由于冲四必须马上应对，全部的走子次序对于白方而言是唯一的也是被迫的。 黑方走黑 1 后，白必须在白 2 应，接下来的黑 3、白 4、黑 5、白 6、黑 7、白 8、黑 9、白 10、黑 11、白 12、黑 13、白 14、黑 15，以上黑方每一步走子，都形成冲四， 对于白方，都只能有唯一的应对，至黑 15，黑方已经形成活四，白方下在白 16，无 济于事，黑 17 赢。 第四章 基于并行遗传算法的博弈搜索 17 第四章 基于并行遗传算法的博弈搜索 4.1 进化算法 生命科学与工程科学的相互交叉、相互渗透和相互促进是近代科学技术进步的 一个显著特点。在这种大环境下，进化算法的蓬勃兴起正体现了科学发展的这一特 征和趋势13 14。从本世纪四十年代以来，生物模拟就开始逐步构成了计算科学的一 个重要组成部分。比如象机器能否思维、能否胜任人类的工作，以及可否使计算机 具有视听功能等问题已经称为人工智能关注的焦点。生物学家们和计算机科学家已 经开始携手进行合作研究生物计算，让生物类比得到了更为广泛的应用。 最好的计算机对于自然界中的生物体通过自身的演化就能使问题得到完美的解 决这种能力，是不完善的。计算机科学家们为了某个算法建立和修改可能要耗费数 月甚至几年的努力，而生物体通过进化和自然选择可达到这个目的。 通过近三十年来的研究与应用产生非常鲁棒性 （robust） 的计算方法进化算法 （evolutionary algorithmea） 。进化算法可以模拟由个体组成群体的集体学习过 程。进化算法从任一初始的群体出发，并在选择过程使群体中适应度好的个体进行 多次的复制机会，利用交叉算子将父辈信息结合在一起并将它们传到下代个体中， 新的变种通过变异在群体中引入。进化算法较为符合达尔文“适者生存”和随机信 息交换思想，既消除变化不适应因素，又可利用原来的知识，从而使优化过程加快， 最终获得全局最优解。 目前研究的进化算法主要有三种典型的算法：1、遗传算法（genetic algorithm ga）其中遗传算法的概念最早出现在 bagley 和 rosenberg 的博士论文中1415，有 国 michigan 大学的 holland j. h.教授对提出的遗传概念进行了总结与推广，并给出 了简明、清晰的算法描述；2、进化规划（evolutionary programmingep）最早由美 国的 fogel l. j. ， owens m. j. 和 walsh m. j. 提出17；3、进化策略（evolutionary strategieses）由德国的 rechenberg i. 和 schwefel h. p. 建立的1819。 进化算法的特点是群体搜索策略和群体中个体之间的信息交换。它们的优越性 主要表现在最优化、机器学习和并行处理等领域：首先，进化算法在搜索过程中不 容易陷入局部最优，即使在所定义的适应度函数是不连续的、非规则的或有噪声的 情况下，它们也能以很大的概率找到全局最优解；其次，它们固有的并行性；再次， 进化算法采用进化机制能够快速可靠地解决非常困难的问题；最后，它们容易介入 到已有的模型中并且具有可扩展性，以及易于同别的技术混合。 提高五子棋博弈搜索算法性能的方法研究 18 4.2 遗传算法 遗传算法是进化算法的一种，它继承了进化算法 “适者生存”机制并引入到算 法中，并具有最优化、并行处理的功能。遗传算法作为一种新的全局优化搜索算法， 具有简单通用，鲁棒性强适于并行处理以及应用范围广等显著特点。遗传算法，自 其诞生以来，人们应用其解决了多种问题，取得了非常好的效果。本文的目的就是 从理论和实践两个方面来探讨使用遗传算法解决五子棋博弈问题的可行性。 遗传算法的基本思想是：对问题的可行解进行二进制编码从而得到一个串，随 机选择若干可行解，组成原始种群。根据优化目标设计适应度函数，计算种群中每 个个体的适应度函数值，依据适应度函数值的大小确定种群中每个个体的选择概率， 让适应性强(适应度函数值大)的个体获得比较多的交叉、遗传机会，通过选择、遗传 和变异生成子代，反复迭代，最终得到问题的满意解。博弈问题的目标是在当前棋 局状态下，选择最优的应对方案，而为了判断一个应对的好坏，必需构造一个应对 链(即假设的对局双方对局记录，以下按遗传算法的惯例称为“串”) ，从而把对一 个应对的好坏的判断转化为对应对串优劣的评判，以应对串的优劣来代表一个应对 的优劣。算法的流程图如图4-1所示： 开 始 t = 0 产 生 初 始 群 体 选 择 交 叉 变 异 结 束 显 示 结 果 t t 1 y e s n o 是 否 满 足 停 机 准 则 计 算 个 体 适 应 度 图 4-1 算法流程图 第四章 基于并行遗传算法的博弈搜索 19 4.3 编码方案与适应度函数 五子棋的棋盘共有 225 个着棋点，用 a ( x, y)坐标 表示每一个着棋点，x、y 的 作用范围是： 0x14, 0y14，可以直接用一个应对的坐标作为该应对的编码。 当然，用棋盘上所有着棋点建立一个编号表，这样就可以用编号来进行编码，但在 使用中需要把编号转化成坐标才可以进行计算判断，直接用坐标方便。 在五子棋中，除了交叉点有棋子，剩余位置都是可以下棋位置。首先列出所有 可以下棋的位置，将可下棋位置随机进行排列，即得到一个应对串。在五子棋中可 以产生n个应对串，由应对串得到初始种群。需要注意的是，在五子棋中双方棋子是 交替排列的，一个应对串中包含了双方的博弈过程。 在博弈问题中，最基本的目标是找出对已方最有利的应对。遗传算法的目标就 是找出适应度函数值的极大，在遗传算法中适应度函数用来判断一个串的优劣程度。 在博弈问题中，不能简单地以对某方有利或输赢为目标，而是要以博弈质量为目标， 那么，在遗传过程中，选择那些应对串来取得适应度函数值？应该选择那些双方走 棋质量都比较高的博弈串取得比较高的适应度函数值。按这种思路设计适应度函数， 才能够通过遗传和变异最终获得高质量的博弈串，同时得到高质量的应对方案。 一个博弈串的适应度函数值的计算如何进行？第一步，先计算每个串的适应度 函数值。再分别计算实际威力值（实际威力值为一个棋子下过之后与周围的同色棋 子互相配合对整个局面的影响力）每一个串中所有棋子，求出最大威力值并记录位 置，判断最大威力值所在位置是否为已方棋子，如果是则选择最大威力值作为该串 的适应度函数值；如果位置为对方棋子，则说明该串适应度函数值对对方有利。 从程序优化的角度，并不是要算出所有棋子的实际威力值再求最大威力值，首 先求出对对方(已方)最有利的棋子位置，它的适应度函数值是绝对值最大的串，然后 在找出占据这些关键位置的博弈串，并适当增加这些串的适应度函数值。通过以上 的的调整后，即得到了每个串的适应度函数值的最终值，在进行遗传选择时，以其 适应度函数值绝对值的大小来衡量一个串的优劣。 4.4 交叉和变异 在对博弈串进行交叉操作时，必须保证每个可下棋位置只能下一个棋子，也就是 每个点在博弈串中只能出现一次。为了实现这一要求，在实际交叉时，采用多点顺 提高五子棋博弈搜索算法性能的方法研究 20 序交叉法进行交叉。例如，若博弈串的长度为8，两个父代如下: 父代1:a5a2a8a3a1a6a7a4 父代2:a6a5a4a3a8a1a2a7 随机选择a2、a3、a7 3个点为固定不变的点，其他点顺序交叉，所得到的2个 子代如下： 子代1: a6a2a5a3a4a8a7a1 子代2: a5a8a1a3a6a4a2a7 变异操作采用随机从一个串中选取若干对点进行交换，例如, 原串: a5a2a8a3a1a6a7a4 选择a5、a1 为一对,a8、a4 为一对，变异后的串如下： a1a2a4a3a5a6a7a8 4.5 基于粗粒度模型的并行遗传算法 空间层次上，遗传算法提供了并行搜索结构，因此适合进行群体并行优化。其 次，由于实际工程中需要解决的问题复杂度较高，它们要在较短的计算时间内找到 较优的解，这时算法利用并行化实现是不可缺少的。按照多处理器的连接拓扑结构 并行实现的途径： 1、 主从式(master-slave)并行化方法 2、 粗粒度模型(coarse-grained)3、 细粒度模型(fine-gained)等20。在遗传算法的并行实现中我们使用粗粒度模型。 粗粒度模型算法的主要特征是引入了迁移操作数和使用了几个同类群。具体描 述为：若干子群体构成整个群体，一些个体包含在每个子群体。一个处理器由每个 子群体支配，每个处理器相互独立地并行执行进化，并且每经过一定的间隔把最佳 个体迁移到相邻的子群体中去。粗粒度的并行算法的基本框架如下： 1. 随机产生一个初始群体，分成 n 个子群体，为子群体定义一个邻域结构； 2. 每个子群体 pi (i=1,2,n)采用并发执行 3 和 4； 3. 在所给定的进化代内对 pi 执行进化操作； 4. 较优的个体迁移到领域结构，新的一代子群体形成； 5. 若结束条件不满足，则转 2。 图 4-2 给出 5 个处理器(图 2 (a)和 20 个处理器(图 2(b)下的连接结构。ga 算法 实现图中的每个处理器。 第四章 基于并行遗传算法的博弈搜索 21 (a) 5 个子群的结构 (b) 20 个子群的结构 图 4-2 粗粒度的并行 saga 算法 4.6 基于并行遗传算法的五子棋博弈算法 五子棋游戏中，有相当的篇幅是算法的部分。无论是人机博弈，还是网络博弈， 都需要合理算法的支持，本节中将详细介绍五子棋中使用的算法。 4.6.1 判断胜负 五子棋的胜负，在于判断棋盘上是否有一个点，从这个点开始的右、下、右下、 左下四个方向是否有连续的五个同色棋子出现，如图 4-3 所示： 图 4-3 判断胜负方向 这个算法也就是 ctable 的 win 成员函数。从设计的思想上，需要它接受一个棋 子颜色的参数，然后返回一个布尔值，这个值来指示是否胜利，代码如下： bool ctable:win( int color ) const int x, y; 提高五子棋博弈搜索算法性能的方法研究 22 / 判断横向 for ( y = 0; y 15; y+ ) for ( x =