算法合集之《人工智能在围棋程序中的应用》

人工智能在围棋程序中的应用复旦大学附属中学施遥【关键字】围棋，搜索，模式匹配，博弈树【摘要】围棋程序的编制被称作人工智能的“试金石”，是人工智能技术的一大难题。本文介绍了人工智能在围棋程序中的应用与发展，对比了围棋与国际象棋博弈算法的差别和复杂度，从而分析围棋算法的难点，讨论各种博弈算法（气位理论、模式匹配与博弈树）在围棋程序中的融合运用。并给出了围棋死活程序的算法实例（附程序），以供参考【正文】『目录』一、概述二、围棋的复杂性三、博弈（棋类）算法及其在象棋与围棋中的对比四、围棋算法五、围棋棋形识别六、围棋死活的算法与实现七、展望一、概述1、围棋简介围棋相传为尧所创，纵横一十九道，天元是为太极，太极生两仪，为黑白子；两仪生四象，为四个角。《弈旨》（［汉］班固）云：“棋有白黑，阴阳分也，骈罗列布，效天文也。”可知围棋本是仿效天文而制，逐渐演变为博弈游戏。２、计算机与围棋计算机运用于棋类方面几乎与计算机的诞生的历史一样长。这方面内容主要属于人工智能技术。人工智能作为一门科学首先是在五十年代提出的，随即便运用于棋类。由于技术的进步，计算机速度的提高、算法的不断发展，目前电脑国际象棋的水平已极高，然而围棋水平却徘徊不前。就围棋而言，人弈棋凭的是经验，即“棋感”。人类的优势是模糊判断、灵敏的直觉，高手往往会有灵机一动而弈出妙手。当然事物有其两面性，即人的情感、直觉有时也会误导自己形成错误，而棋手的心态也是至关重要的一环，“成也萧何，败也萧何”，直觉既是人类的法宝，亦是败因（当然是指败给人了）。计算机的优势是计算速度快，劣势是不擅模糊判断、不能根据经验选点导致搜索量过大。计算机不为情绪所困，不为直觉所惑，故地域广狭、大小之分能较为准确，其耗时亦少，然而计算机毕竟没有棋感，不知道哪步好、哪步不好，只有一点点地去试，要么费时甚巨（也未必有用），要么草草了事，结果也可想而知。二、围棋的复杂性围棋全局与其死活问题其复杂性都大致可归纳为如下三点：1、模糊性“围棋”之名自是取自围地之意，倘若是双方落子一开始便是紧紧相贴的，那么可想而之行棋的速度（即占领地盘的速度）是极慢的，故而布局、中盘以至大官子阶段，双方只是围出一个大概的轮廓，甚而连轮廓都不明显。黑白势力难分，形状犬牙差互。这对于计算机处理形成了极大的困难。2、反复性象棋中棋子一旦被吃，则永远从棋盘上提去，而在围棋棋盘上，被吃的地方仍可重新落子，甚而将对方反吃回来，如此一来，搜索的难度便大大增加。如“倒脱靴”之形，送子后再吃子，一块空可以几易其主。所以“死子”不死，“活子”有时倒是堪虞。所以在计算机处理中不可以简单确定一块棋子的死活和对周围的影响。3、灵活性象棋的灵活，至多体现在兑子上，所谓“宁弃一子，不失一先”，也仅是一子而已，若是两子、三子呢？恐怕在双方实力相当的情况下必败无疑。而且在象棋算法中多有将各种棋子折合为一定的价值相加的做法，如，在国际象棋中以一个兵为单位，一个马约可等于三个半兵，一个车约可等于五个半兵，等等，最多再根据棋子所处位置加以一定的折算。而围棋的灵活远胜于此，有时弃去十来个子以取势，弃去二、三十目的角地以转换。再者，围棋棋子的价值是难以估量的，其价值不完全在其本身，而常于在周围的配置，有些影响甚而可斜跨整个棋盘。三、博弈（棋类）算法及其在象棋与围棋中的对比一九九七年，IBM的电脑“深蓝”一举战胜卡斯帕罗夫，震惊世界。其实电脑国际象棋的水平早在七、八十年代已挤身世界高手之林，而中国象棋软件也已几乎具有大师水准，非一般爱好者能望其项背。唯独围棋举步维艰，连业余下手都胜券难握，更莫论一等一的高手，究其原因不外是围棋之博大精深、纵横变换繁复，棋手多靠经验而计算机则无此功能。目前，棋类博弈算法主要有两大类：模式匹配和使用博弈树。这在国际象棋中的运用可以追溯到五、六十年代，且而十分成功。围棋和象棋一样是博弈游戏，看似仅有黑白两种棋子，简单不过。实则比起兵种繁多的象棋却复杂得多。电脑围棋起源于六十年代。两位博士Zobrist和Ryder在论文中均涉及了围棋程序，前者的算法基于模式识别；而后者的算法基于搜索，即使用博弈树。这两种在国际象棋中效果不错的算法在围棋中的表现却极差，竟然连仅有几盘棋经验的人都赢不了。我们不妨来考虑一下上述两种算法。首先，我们来看模式匹配。象棋中因为棋子个数少、种类多，那么就较易分别与归纳（实际上也是困难的，但比围棋容易实现得多）。而在围棋中，显然将所有的模式都存储起来是不可能的。那么只有模糊匹配。但这似乎也很难办。围棋中有“愚形”这个名词，一般指的是效率差的形状。那么怎样是效率差呢？就是浪费子力，在不必要的地方落子，哪怕只是一个子。而模糊的匹配在一子之差时究竟如何判断？是好形还是愚形？这就陷入了矛盾的境地。况且，根据实际情况，还有“愚形之妙手”（出自日本古局），实难判断。其次是搜索的算法。搜索的代价是极大的，据估计，国际象棋搜索7个回合约有500亿至600亿种选择（当然是在博弈树剪枝后），这个数字尽管也十分庞大，但以目前的技术水平还是可以承受的；然而在围棋中，我们稍微计算一下便知道：假设每步大约有只有一百个可行点（已经非常少了），那么14步（即7个回合）以内的变化则约有1028种，当然这只是保守的估计，已足以骇人了。可见在全局使用搜索算法是不可行的。因此当前的做法一般是在局部明确目标（如做活、杀棋、突围、切断等）的情况下，才使用博弈树进行搜索。四、围棋算法目前，世界上流行的围棋软件主要是由以下三种算法组成的：1、使每个棋子周围产生某种影响，这种影响随着距离的增加而减少，用一定的公式计算叠加这种影响，以判断形势和估计着点的价值。这与围棋的棋理相通，即对于每个棋子可估算其“势力”。此中就有著名的“气位”理论。2、建立模式库，贮存了大量模式（定式、棋形等），以供匹配。这其实涉及到围棋的许多棋谚与棋理。如“二子头必扳”、“镇以飞应”、“断从一边长”、三子正中、点方等等。这些都是根据围棋的具体情况而设计的。3、对目标明确的局部，用人工智能中的搜索法探求其结果。一般来说，现在还没有找到突破性的算法，只有在以上三种算法中细细加工。五、围棋棋形识别围棋中棋力的高下大凡凭一个棋手的感觉与经验，而这感觉正是棋手水平的主要体现。而对棋的感觉其实就是人对于棋本身（即棋形）的主观认识。这是一个识别过程。识别能力的高低是智能的一大特征。识别能力由低到高分为三个层次，仪器水平：物理识别；动物水平：模糊识别；人类水平：情感识别。物理识别是对接受到的信息实现物理、化学和生物学的量化认识。这不需要经验与智能，所以是最低层次的识别。模糊识别是在大量复杂的信息中识别出有用的部分，即对接收的信息与以往的记忆和经验进行关联认识，剔除无关的信息。情感识别是最高级的识别。它是完全的感性识别。可以说围棋中既有模糊识别，亦有情感识别。即对于一个新棋形，将之与经验中的棋形比较，综合周边情况，作出判断。其决策带有明显的个人情感倾向，这与每个人的理解有关，很多是没有定论的，因此即便九段高手之间的棋也是截然不同的，很难说孰优孰劣。而在计算机中，对于棋形却难以模糊判断，因为这既不是声音，也不是图象，一子之差，优劣迥异。一般来说，目前计算机对于围棋棋形只能作简单的识别，用以减少搜索，其实这也就是赋予了计算机一定的“经验”。六、围棋死活的算法与实现死活是围棋中的一个典型问题，可以说也是围棋算法的一个缩影。它需要融合上述的三种算法。目前，死活软件已达到较高的水平，但主要因为这只是一个局部问题，与全局千丝万缕的关系却是极难把握。注：为了叙述简便起见，下文中黑方总为攻击方，白方总为欲做活的一方，在本节中仅以白方为例来设计算法。本节中的各算法均已简化，目的只是说明方法。由于时间关系和水平所限，本节算法不免有所疏漏，望不吝指正。对于围棋死活问题，首先我们不妨看看人下棋的思路：先看有多少眼位，是否已活？如不活，计算缺多少眼位，能否补上？在做眼（或破眼）的过程中，人总是先以第一感为线索来计算，那么人的第一感是从何而来呢？其实就是长期对棋型认识的经验，经验丰富者强、经验欠缺者弱。因为在死活中有许多常见的棋型，前人也曾总结过一些棋谚，如“杀棋用扳”、“二一多妙手”等，还有如夹、点、跨等手段经常构成杀棋；而有些着点却无需考虑。因为死活是一个局部目标明确的问题，故而以搜索为主。因此一个围棋死活软件的优劣关键在于对于搜索的优化、剪枝上。我对于围棋死活问题的算法有两大部分组成：静态眼位判断搜索程序的主线是搜索，然而静态眼位判断穿插于其间。1、静态眼位判断①势力划分前面提到了，围棋黑白双方的界限是模糊的，很难精确划分，而不能精确划分的话，则在计算机中难以处理。为此，采用气位理论的的方法来近似计算“势力”。势力划分贯穿于整个静态眼位判断，作用很大。一个棋子对于周围有一定的影响，称之为“势力”，一个子的周围称为气位。气位如下划分：1、相邻位为1级气位；2、尖位为1.5级气位，扳位为2级气位（即右图中“1.5”处若是扳位，则须改为“2”）；3、关位为2级气位；4、小飞位为2.5级气位。各级别气位所受影响如下表：气位级别1级1.5级2级2.5级影响的绝对值6532黑棋的影响为正值，白棋为负值。当然，以上的各位置与原来位置之间不可有棋子隔断，否则（无论黑白）势力即为其所阻隔。另外要补充的是，每一点所受某种颜色棋子的影响只受离其最近（影响最大）的该色棋子的影响。如此一来，半敞开的区域便可为势力所封闭，一此处于重重包围的棋子由于周围对方势力太盛，自己的势力值反而为对方所颠倒，自然成为死子（但不是绝对的，如“倒脱靴”便是死棋再生的例子）。本文讲的只是一个基本方法，在真正操作时可以根据不同情况有一定的变化，对于优秀的围棋软件来说，影响力也未必是线性叠加的。②白方（做活方）眼位的确定首先，我们知道每块棋子至少要两个真眼才能做活。真眼与假眼的区别如右图：在角上A点为己方占领为真眼，反之为假眼；在边上AB两点要俱为己方占领方为真眼；在中央ABCD中己方须至少占领三点才能成其为真眼，反之为假眼，当然倘是己方已占领了其中两点，而另两点无子，亦是真眼，因为这两点见合（即两点必得其一）。现在我们来考虑何为“占领”？“占领”的含意对于黑白双方是不同的。对于白方：占领未必在该点要有白子，只需在该点的白方势力极强即可，因为如此黑方即使在此落子也必为白方所吃，最终仍为白方占据。对于黑方：占领即在该点是黑子，没有黑子的地方即使势力再强，一旦白方落子于该处，黑方也无可奈何。第二我们要明确，眼位未必非真即假，非假即真。如下图：图中白方在A位先行补一手可成真眼，反之黑方先行即成假眼。我们不妨称之为半只眼。⑴一目眼位的判断一目眼位判断较为简单，只需如上所述计算即可，分三种类型：真眼、假眼（可不计）、白方先手真眼。⑵二目以上（包括二目）五目以下（包括五目）空的判断二目以上的眼位由于形状复杂难以简单判断。尽管形状复杂，然而形状数量有限（大约基本型十几种，经旋转、翻转后为三、四十种），可以做成棋型库进行匹配，有五种类型：白方先行一个真眼、总为一个真眼、白方先行两个（两个以上）真眼、总为两个（两个以上）真眼及无真眼（可不计）。⑶五目以上（不包括五目，下同）空的判断五目以上的空，形状极多，不可胜举，故很难将之做成模式库。但值得注意的是，五目以上的空（形状完整）几乎都可以成为两个真眼。因此在判断的时候，我们暂先不妨将之判为两个（两个以上）真眼。③死活的判断有了以上眼位的确定，我们便可以切入关键了。静态眼位判断的主要目的是判断死活的类型，即白先活，白先死与白后活。⑴白先活，即白棋先行可以做活，后行则死。此种状态的条件是以下之一：一个真眼与半只眼；三个半只眼。⑵白先死，即白方即使先行也死。条件是以下之一：一个或无真眼，无半只眼；两个或两个以下的半只眼，无真眼。⑶白后活，即白方即使后行也是活棋。条件是以下之一：两个或两个以上真眼；一个真眼与两个或两个以上半只眼；四个或四个以上半只眼。简单地说，以一个真眼折合两个半只眼。若少于三个半只眼，为白先死；等于三个半只眼为白先活；大于三个半只眼为白后活。2、搜索（博