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