1、算法合集之人工智能在围棋程序中的应用人工智能在围棋程序中的应用复旦大学附属中学 施 遥【关键字】 围棋，搜索，模式匹配，博弈树【摘要】 围棋程序的编制被称作人工智能的“试金石”，是人工智能技术的一大难题。 本文介绍了人工智能在围棋程序中的应用与发展，对比了围棋与国际象棋博弈算法的不同和复杂度，从而分析围棋算法的难点，讨论各类博弈算法（气位理论、模式匹配与博弈树）在围棋程序中的融合运用。并给出了围棋死活程序的算法实例（附程序），以供参考【正文】目录一、概述二、围棋的复杂性三、博弈（棋类）算法及其在象棋与围棋中的对比四、围棋算法五、围棋棋形识别六、围棋死活的算法与实现七、展望一、概述 1、围棋简介
2、围棋相传为尧所创，纵横一十九道，天元是为太极，太极生两仪，为黑白子；两仪生四象，为四个角。弈旨（汉班固）云：“棋有白黑，阴阳分也，骈罗列布，效天文也。”可知围棋本是仿效天文而制，逐渐演变成博弈游戏。、计算机与围棋计算机运用于棋类方面几乎与计算机的诞生的历史一样长。这方面内容主要属于人工智能技术。人工智能作为一门科学首先是在五十年代提出的，随即便运用于棋类。 由于技术的进步，计算机速度的提高、算法的不断发展，目前电脑国际象棋的水平已极高，但是围棋水平却徘徊不前。 就围棋而言，人弈棋凭的是经验，即“棋感”。人类的优势是模糊判断、灵敏的直觉，高手往往会有灵机一动而弈出妙手。固然事物有其两面性，即人的
3、情感、直觉有时也会误导自己形成错误，而棋手的心态也是相当重要的一环，“成也萧何，败也萧何”，直觉既是人类的宝贝，亦是败因（固然是指败给人了）。 计算机的优势是计算速度快，劣势是不擅模糊判断、不能按照经验选点致使搜索量过大。计算机不为情绪所困，不为直觉所惑，故地域广狭、大小之分能较为准确，其耗时亦少，但是计算机毕竟没有棋感，不知道哪步好、哪步不好，只有一点点地去试，要么费时甚巨（也未必有效），要么草草了事，结果也可想而知。二、围棋的复杂性 围棋全局与其死活问题其复杂性都大致可归纳为如下三点：1、模糊性 “围棋”之名自是取自围地之意，倘使是两边落子一开始即是牢牢相贴的，那么可想而之行棋的速度（即占
4、领地盘的速度）是极慢的，故而布局、中盘以至大官子阶段，两边只是围出一个可能的轮廓，甚而连轮廓都不明显。黑白势力难分，形状犬牙差互。这对于计算机处置形成了极大的困难。2、反复性 象棋中棋子一旦被吃，则永远从棋盘上提去，而在围棋棋盘上，被吃的地方仍可从头落子，甚而将对方反吃回来，如此一来，搜索的难度便大大增加。如“倒脱靴”之形，送子后再吃子，一块空可以几易其主。所以“死子”不死，“活子”有时却是堪虞。所以在计算机处置中不可以简单肯定一块棋子的死活和对周围的影响。3、灵活性 象棋的灵活，最多体此刻兑子上，所谓“宁弃一子，不失一先”，也仅是一子算了，若是两子、三子呢？恐怕在两边实力相当的情况下必败无疑
5、。而且在象棋算法中多有将各类棋子折合为必然的价值相加的做法，如，在国际象棋中以一个兵为单位，一个马约可等于三个半兵，一个车约可等于五个半兵，等等，最多再按照棋子所处位置加以必然的折算。 而围棋的灵活远胜于此，有时弃去十来个子以取势，弃去二、三十目的角地以转换。再者，围棋棋子的价值是难以估量的，其价值不完全在其本身，而常于在周围的配置，有些影响甚而可斜跨整个棋盘。三、博弈（棋类）算法及其在象棋与围棋中的对比 一九九七年，IBM的电脑“深蓝”一举战胜卡斯帕罗夫，震惊世界。其实电脑国际象棋的水平早在七、八十年代已挤身世界高手之林，而中国象棋软件也已几乎具有大师水准，非一般爱好者能望其项背。唯独围棋步
6、履维艰，连业余下手都胜券难握，更莫论一等一的高手，究其原因不外是围棋之博大精深、纵横变换繁复，棋手多靠经验而计算机则无此功能。 目前，棋类博弈算法主要有两大类：模式匹配和利用博弈树。这在国际象棋中的运用可以追溯到五、六十年代，且而十分成功。 围棋和象棋一样是博弈游戏，看似仅有黑白两种棋子，简单不过。实则比起军种繁多的象棋却复杂得多。 电脑围棋起源于六十年代。两位博士Zobrist和Ryder在论文中均涉及了围棋程序，前者的算法基于模式识别；而后者的算法基于搜索，即便用博弈树。这两种在国际象棋中效果不错的算法在围棋中的表现却极差，竟然连仅有几盘棋经验的人都赢不了。 咱们不妨来考虑一下上述两种算法
7、。 首先，咱们来看模式匹配。象棋中因为棋子个数少、种类多，那么就较易别离与归纳（实际上也是困难的，但比围棋容易实现得多）。而在围棋中，显然将所有的模式都存储起来是不可能的。那么只有模糊匹配。但这似乎也很难办。围棋中有“愚形”这个名词，一般指的是效率差的形状。那么如何是效率差呢？就是浪费子力，在没必要要的地方落子，哪怕只是一个子。而模糊的匹配在一子之差时究竟如何判断？是好形仍是愚形？这就陷入了矛盾的境界。何况，按如实际情况，还有“愚形之妙手”（出自日本古局），实难判断。 其次是搜索的算法。搜索的代价是极大的，据估量，国际象棋搜索7个回合约有500亿至600亿种选择（固然是在博弈树剪枝后），这个数
8、字虽然也十分庞大，但以目前的技术水平仍是可以经受的；但是在围棋中，咱们略微计算一下便知道：假设每步大约有只有一百个可行点（已经超级少了），那么14步（即7个回合）之内的转变则约有1028种，固然这只是保守的估量，已足以骇人了。可见在全局利用搜索算法是不可行的。因此当前的做法一般是在局部明确目标（如做活、杀棋、突围、切断等）的情况下，才利用博弈树进行搜索。四、围棋算法 目前，世界上流行的围棋软件主如果由以下三种算法组成的： 1、使每一个棋子周围产生某种影响，这种影响随着距离的增加而减少，用必然的公式计算叠加这种影响，以判断形势和估量着点的价值。这与围棋的棋理相通，即对于每一个棋子可估算其“势力”
9、。其中就有著名的“气位”理论。2、成立模式库，贮存了大量模式（定式、棋形等），以供匹配。这其实涉及到围棋的许多棋谚与棋理。如“二子头必扳”、“镇以飞应”、“断从一边长”、三子正中、点方等等。这些都是按照围棋的具体情况而设计的。3、对目标明确的局部，用人工智能中的搜索法探求其结果。 一般来讲，此刻尚未找到冲破性的算法，只有在以上三种算法中细细加工。五、围棋棋形识别 围棋中棋力的高低大凡凭一个棋手的感觉与经验，而这感觉正是棋手水平的主要表现。而对棋的感觉其实就是人对于棋本身（即棋形）的主观熟悉。这是一个识别进程。 识别能力的高低是智能的一大特征。识别能力由低到高分为三个层次，仪器水平：物理识别；动
10、物水平：模糊识别；人类水平：情感识别。 物理识别是对接受到的信息实现物理、化学和生物学的量化熟悉。这不需要经验与智能，所以是最低层次的识别。 模糊识别是在大量复杂的信息中识别出有效的部份，即对接收的信息与以往的记忆和经验进行关联熟悉，剔除无关的信息。 情感识别是最高级的识别。它是完全的感性识别。 可以说围棋中既有模糊识别，亦有情感识别。即对于一个新棋形，将之与经验中的棋形比较，综合周边情况，作出判断。其决策带有明显的个人情感偏向，这与每一个人的理解有关，很多是没有定论的，因此即便九段高手之间的棋也是截然不同的，很难说孰优孰劣。 而在计算机中，对于棋形却难以模糊判断，因为这既不是声音，也不是图象
11、，一子之差，好坏迥异。 一般来讲，目前计算机对于围棋棋形只能作简单的识别，用以减少搜索，其实这也就是给予了计算机必然的“经验”。六、围棋死活的算法与实现 死活是围棋中的一个典型问题，可以说也是围棋算法的一个缩影。它需要融合上述的三种算法。目前，死活软件已达到较高的水平，但主要因为这只是一个局部问题，与全局千丝万缕的关系却是极难把握。注：为了叙述简便起见，下文中黑方总为解决方，白方总为欲做活的一方，在本节中仅以白方为例来设计算法。本节中的各算法均已简化，目的只是说明方式。由于时间关系和水平所限，本节算法不免有所疏漏，望不吝指正。对于围棋死活问题，首先咱们不妨看看人下棋的思路： 先看有多少眼位，是
12、不是已活？如不活，计算缺多少眼位，可否补上？在做眼（或破眼）的进程中，人老是先以第一感为线索来计算，那么人的第一感是从何而来呢？其实就是长期对棋型熟悉的经验，经验丰硕者强、经验欠缺者弱。因为在死活中有许多常见的棋型，前人也曾总结过一些棋谚，如“杀棋用扳”、“二一多妙手”等，还有如夹、点、跨等手腕常常组成杀棋；而有些着点却无需考虑。因为死活是一个局部目标明确的问题，故而以搜索为主。因此一个围棋死活软件的好坏关键在于对于搜索的优化、剪枝上。 我对于围棋死活问题的算法有两大部份组成：静态眼位判断搜索 程序的主线是搜索，但是静态眼位判断穿插于其间。1、静态眼位判断势力划分 前面提到了，围棋黑白两边的界
13、限是模糊的，很难精准划分，而不能精准划分的话，则在计算机中难以处置。为此，采用气位理论的的方式来近似计算“势力”。 势力划分贯穿于整个静态眼位判断，作用很大。 一个棋子对于周围有必然的影响，称之为“势力”，一个子的周围称为气位。气位如下划分： 1、相邻位为1级气位； 2、尖位为级气位，扳位为2级气位（即右图中“”处若是扳位，则须改成“2”）； 3、关位为2级气位； 4、小飞位为级气位。各级别气位所受影响如下表：气位级别1级级2级级影响的绝对值6532黑棋的影响为正值，白棋为负值。 固然，以上的列位置与原来位置之间不可有棋子隔间，不然（无论黑白）势力即为其所阻隔。 另外要补充的是，每一点所受某种
14、颜色棋子的影响只受离其最近（影响最大）的该色棋子的影响。 如此一来，半敞开的区域即可为势力所封锁，一此处于重重包围的棋子由于周围对方势力太盛，自己的势力值反而为对方所倒置，自然成为死子（但不是绝对的，如“倒脱靴”即是死棋再生的例子）。 本文讲的只是一个大体方式，在真正操作时可以按照不同情况有必然的转变，对于优秀的围棋软件来讲，影响力也未必是线性叠加的。白方（做活方）眼位的肯定 首先，咱们知道每块棋子至少要两个真眼才能做活。真眼与假眼的区别如右图：在角上A点为己方占领为真眼，反之为假眼；在边上AB两点要俱为己方占领方为真眼；在中央ABCD中己方须至少占领三点才能成其为真眼，反之为假眼，固然倘是己
15、方已占领了其中两点，而另两点无子，亦是真眼，因为这两点见合（即两点必得其一）。 此刻咱们来考虑何为“占领”？“占领”的含义对于黑白两边是不同的。 对于白方：占领未必在该点要有白子，只需在该点的白方势力极强即可，因为如此黑方即便在此落子也必为白方所吃，最终仍为白方占据。 对于黑方：占领即在该点是黑子，没有黑子的地方即便势力再强，一旦白方落子于该处，黑方也无可奈何。 第二咱们要明确，眼位未必非真即假，非假即真。如下图： 图中白方在A位先行补一手可成真眼，反之黑方先行即成假眼。咱们不妨称之为半只眼。一目眼位的判断 一目眼位判断较为简单，只需如上所述计算即可，分三种类型：真眼、假眼（可不计）、白方先手
16、真眼。二目以上（包括二目）五目以下（包括五目）空的判断 二目以上的眼位由于形状复杂难以简单判断。虽然形状复杂，但是形状数量有限（大约大体型十几种，经旋转、翻转后为三、四十种），可以做成棋型库进行匹配，有五种类型：白方先行一个真眼、总为一个真眼、白方先行两个（两个以上）真眼、总为两个（两个以上）真眼及无真眼（可不计）。五目以上（不包括五目，下同）空的判断 五目以上的空，形状极多，不可胜举，故很难将之做成模式库。 但值得注意的是，五目以上的空（形状完整）几乎都可以成为两个真眼。因此在判断的时候，咱们暂先不妨将之判为两个（两个以上）真眼。死活的判断 有了以上眼位的肯定，咱们即可以切入关键了。静态眼位
17、判断的主要目的是判断死活的类型，即白先活，白先死与白后活。 白先活，即白棋先行可以做活，后行则死。此种状态的条件是以下之一：一个真眼与半只眼；三个半只眼。 白先死，即白方即便先行也死。条件是以下之一：一个或无真眼，无半只眼；两个或两个以下的半只眼，无真眼。 白后活，即白方即便后行也是活棋。条件是以下之一：两个或两个以上真眼；一个真眼与两个或两个以上半只眼；四个或四个以上半只眼。 简单地说，以一个真眼折合两个半只眼。若少于三个半只眼，为白先死；等于三个半只眼为白先活；大于三个半只眼为白后活。2、搜索（博弈树） 搜索算法是主线，但不如静态眼位判断来得复杂。 博弈树的奇数层为白方（计算机），偶数层为
18、黑方。如下图： 对于每一个结点，以在此状态下白活的可能性作为估价函数。 对于奇数层白棋的选点，咱们可以作如下限制： 1、不走在黑棋包围圈的外侧； 2、此子不能被黑棋一手提掉，且同被吃掉的一块棋子个数小于四个（因为四个或四个以上棋子被提，可能是“倒脱靴”的妙手）。 对于偶数层黑棋的选点，则限制在黑棋包围圈及其内部。 在列举了白棋选点后，生成某一状态，此状态倘使是“白后活”，当即返回此状态白活（白活可能性为1）；不然，查找此状态下是不是有黑棋下某一手后，白呈“白先死”，则此结点不用继续扩展，返回此状态白死（白活可能性为0）。 若不在上述两种状况之列，则扩展下一层（黑棋），按照下一层的状态中白活可能
19、性的大小来给此结点估价。 在列举子黑棋的选点后，对于每一黑棋选点，可生成一种状态。此状态下，若是“白先活”，则立该返回白活（白活可能性为1）；不然，查找此状态下是不是有白棋下某一手后，白呈“白后活”，则此结点不用继续扩展，返回此状态白活（白活可能性为1）。如非上述两种状况，则继续扩展结点，按照下一层的状态中白死可能性的大小来给此结点估价。 最后程序按照白活的可能性，选择该值最大的落点落子。固然在博弈树中应当利用-剪枝，在白棋层中将白活可能性小的结点剔除，不予扩展；在黑棋层中，将白棋活可能性大的结点剔除，不予扩展。 关于博弈树的一些具体问题可以参照有关资料。七、展望 除上述的方式外，在人工智能领
20、域还存在着这样一些可行方案：人工神经网络 由于最近几年来人工神经网络的发展，也为围棋程序找到了又一条道路，即增加人工神经网络的部份，使软件其具有必然的学习、记忆和联想功能，将之与高手对弈，以吸收必然的“知识”，培育棋感。美国Footland的MFGO就做了一些这方面的有利尝试，但目前可能还不完善。“多面围棋”的设计者、美国惠普电脑公司的工程师大卫佛特兰德所说：“强力检索对围棋全无作用，你得创造出一个像人一样精明的程序来。”。诚然，围棋是如此之复杂，仅靠机械地教电脑如何下棋是远远不够的，所以应该利用人工神经网络令电脑“伶俐”起来，让它主动学习。但这方面的技术还并无达到很高的程度，故而目前也仅是一
21、种假想。专家系统 专家系统已普遍地运用到了方方面面，其实在围棋中，也可成立专家系统。可以设立棋形知识库，按照棋谚与人们总结出来的其它经验，将其给予计算机。这是一个比较系统的方案。产生式系统 对于定式与某些常见转变，可以成立产生式系统，让计算机自己生成转变。其中关键是选择良好的控制方式，以判断好坏。这是对于局部问题预处置的一种方案。 棋无止境，在电脑围棋的漫漫征途上犹是如此。 当前，围棋软件已是人工智能技术的尖端之一，被称之为人工智能的“试金石”，倘是要更进一步，无非是软件与硬件的双重优化。算法的优化已愈来愈趋于细节化，根本性的冲破口仍然没有找到；硬件速度的提升虽然愈来愈快，但也远远不能知足其要
22、求。“手谈”是目前世界上最强的围棋软件之一，但据其作者陈志行教授称，它只有9级的棋力。陈教授说，围棋软件发展的“瓶颈”关键是“围棋太复杂”。 虽然在围棋死活问题上，计算机已达到了必然的水平，但是围棋本身是一门得与失不断转换与平衡的大学问。失之东隅，得之桑榆，得与失之间微妙的关系是目前计算机所难以掌握的。在应氏杯电脑围棋赛上，记者问参赛者们计算机还要过量少时间才能赢人类高手？回答是一百年后。这个回答无论是保守仍是夸张，总之电脑围棋的路还很长，当某一天真的圆了应昌期先生计算机胜过人类九段的梦想之时，那才是计算机真正实现了智能化的标志。【参考资料】1、青少年国际信息学（计算机）奥林匹克竞赛指导人工智能搜索与程序设计 刘福生 王建德2、人工智能引论 美E.丽奇3、 陈志行4、 围棋报电子版5、 美国围棋协会（American Go Association）
