人工智能在围棋程序中的应用 复旦大学附属中学 施 遥 【关键字】 围棋，搜索，模式匹配，博弈树 【摘要】 围棋程序的编制被称作人工智能的“试金石”，是人工智能技术的一大难题。 本文介绍了人工智能在围棋程序中的应用与发展，对比了围棋与国际象棋博弈算法的差别和复杂度，从而分析围棋算法的难点，讨论各种博弈算法（气位理论、模式匹配与博弈树）在围棋程序中的融合运用。并给出了围棋死活程序的算法实例（附程序），以供参考 【正文】 『目录』 HYPERLINK \l "概述" 一、概述 HYPERLINK \l "围棋的复杂性" 二、围棋的复杂性 HYPERLINK \l "博弈（棋类）算法及其在象棋与围棋中的对比" 三、博弈（棋类）算法及其在象棋与围棋中的对比 HYPERLINK \l "围棋算法" 四、围棋算法 HYPERLINK \l "围棋棋形识别" 五、围棋棋形识别 HYPERLINK \l "围棋死活的算法与实现" 六、围棋死活的算法与实现 HYPERLINK \l "展望" 七、展望 一、概述 1、围棋简介 　　围棋相传为尧所创，纵横一十九道，天元是为太极，太极生两仪，为黑白子；两仪生四象，为四个角。《弈旨》（［汉］班固）云：“棋有白黑，阴阳分也，骈罗列布，效天文也。”可知围棋本是仿效天文而制，逐渐演变为博弈游戏。 　　２、计算机与围棋 　　计算机运用于棋类方面几乎与计算机的诞生的历史一样长。这方面内容主要属于人工智能技术。人工智能作为一门科学首先是在五十年代提出的，随即便运用于棋类。 由于技术的进步，计算机速度的提高、算法的不断发展，目前电脑国际象棋的水平已极高，然而围棋水平却徘徊不前。 就围棋而言，人弈棋凭的是经验，即“棋感”。人类的优势是模糊判断、灵敏的直觉，高手往往会有灵机一动而弈出妙手。当然事物有其两面性，即人的情感、直觉有时也会误导自己形成错误，而棋手的心态也是至关重要的一环，“成也萧何，败也萧何”，直觉既是人类的法宝，亦是败因（当然是指败给人了）。 计算机的优势是计算速度快，劣势是不擅模糊判断、不能根据经验选点导致搜索量过大。计算机不为情绪所困，不为直觉所惑，故地域广狭、大小之分能较为准确，其耗时亦少，然而计算机毕竟没有棋感，不知道哪步好、哪步不好，只有一点点地去试，要么费时甚巨（也未必有用），要么草草了事，结果也可想而知。 二、围棋的复杂性 围棋全局与其死活问题其复杂性都大致可归纳为如下三点： 1、模糊性 “围棋”之名自是取自围地之意，倘若是双方落子一开始便是紧紧相贴的，那么可想而之行棋的速度（即占领地盘的速度）是极慢的，故而布局、中盘以至大官子阶段，双方只是围出一个大概的轮廓，甚而连轮廓都不明显。黑白势力难分，形状犬牙差互。这对于计算机处理形成了极大的困难。 2、反复性 象棋中棋子一旦被吃，则永远从棋盘上提去，而在围棋棋盘上，被吃的地方仍可重新落子，甚而将对方反吃回来，如此一来，搜索的难度便大大增加。如“倒脱靴”之形，送子后再吃子，一块空可以几易其主。所以“死子”不死，“活子”有时倒是堪虞。所以在计算机处理中不可以简单确定一块棋子的死活和对周围的影响。 3、灵活性 象棋的灵活，至多体现在兑子上，所谓“宁弃一子，不失一先”，也仅是一子而已，若是两子、三子呢？恐怕在双方实力相当的情况下必败无疑。而且在象棋算法中多有将各种棋子折合为一定的价值相加的做法，如，在国际象棋中以一个兵为单位，一个马约可等于三个半兵，一个车约可等于五个半兵，等等，最多再根据棋子所处位置加以一定的折算。 而围棋的灵活远胜于此，有时弃去十来个子以取势，弃去二、三十目的角地以转换。再者，围棋棋子的价值是难以估量的，其价值不完全在其本身，而常于在周围的配置，有些影响甚而可斜跨整个棋盘。 三、博弈（棋类）算法及其在象棋与围棋中的对比 一九九七年，IBM的电脑“深蓝”一举战胜卡斯帕罗夫，震惊世界。其实电脑国际象棋的水平早在七、八十年代已挤身世界高手之林，而中国象棋软件也已几乎具有大师水准，非一般爱好者能望其项背。唯独围棋举步维艰，连业余下手都胜券难握，更莫论一等一的高手，究其原因不外是围棋之博大精深、纵横变换繁复，棋手多靠经验而计算机则无此功能。 目前，棋类博弈算法主要有两大类：模式匹配和使用博弈树。这在国际象棋中的运用可以追溯到五、六十年代，且而十分成功。 围棋和象棋一样是博弈游戏，看似仅有黑白两种棋子，简单不过。实则比起兵种繁多的象棋却复杂得多。 电脑围棋起源于六十年代。两位博士Zobrist和Ryder在论文中均涉及了围棋程序，前者的算法基于模式识别；而后者的算法基于搜索，即使用博弈树

　　摘要：课课家快讯 自计算机技术发展以来，人工智能便是众多高端人才竞相研究的对象。近三十年此领域获得了迅速的发展，人工智能越来越热，科技公司也纷纷进行布局。人机博弈更是人工智能一个重要的研究方向。

　　快讯 自计算机技术发展以来，人工智能便是众多高端人才竞相研究的对象。近三十年此领域获得了迅速的发展，人工智能越来越热，科技公司也纷纷进行布局。人机博弈更是人工智能一个重要的研究方向。

　　人机博弈，每每引起人们的广泛关注。当人类与自己制造出来的机器斗智斗勇时，输赢之间似乎已不再是简单的技术问题了。

　　说起人机博弈，早在19世纪60年代就已经出现了若干博弈程序，并达到了一定的水平。比较有影响的是1960年NNS国际象棋机的出现，以及60年代初期IBM完成的具有自学习、自组织、自适应能力的西洋棋程序等等。

　　最早击败世界冠军的“奥赛罗”人机对弈系统

　　李开复就读于卡内基梅隆大学期间，了“奥赛罗”人机对弈系统，因为1988年击败了人类的国际象棋世界冠军而名噪一时。李开复曾表示，我们击败“得过世界团体冠军的Brian Rose”，他曾在1987年代表美国队获得奥赛罗世界锦标赛冠军。约定三战两胜，但他大败一局之后弃权，

　　卡斯帕罗夫大战“深蓝”睡不着觉

　　历史上最伟大的一次较量来自于1997年世界首席国际象棋大师卡斯帕罗夫与IBM公司生产的“深蓝”的较量。早在1989年他曾击败过IBM的“深思”电脑棋手。而在1997年这次较量中，经过几轮激烈的角逐，“深蓝”最终以2:1战胜了卡斯帕罗夫。这是人工智能飞速发展的一个重要标志。IBM推出的“深蓝”运算速度要比当年的“深思”要快1000倍。卡斯帕罗夫赛前曾发誓要“为捍卫人类的尊严而战”。

　　中国象棋大师与机器博弈也是输

　　1995年9月21日，IBM公司为了庆祝IBM中国研究中心的建成，在落成庆典上，邀请国际象棋冠军谢军与挑战者--IBM公司生产的电脑对奕，经过两个小时的较量，谢军以1：1与电脑握手言和。而在2004年中国首届国象人机大战上，中国棋后诸宸连输两场，最终负于紫光之星。此后中国的国象人机大战上中国选手战败也是家常便饭。

　　人类似乎在国际象棋上没赢过机器了

　　在1997年之后人类似乎就没赢过了。1998年REBEL5:3战胜了当时世界排名第二的维斯瓦纳坦?阿南德，自1997年至今著名的国际象棋大师与电脑对战，多是败局，或是平局。2009年Pocket Fritz 4的棋力达到了特级大师级别，等级分2898。现在排名第一的马格努斯?卡尔森也才2882。

　　复杂的中国游戏——围棋也将落败

　　社交网站Facebook的首席执行官马克?扎克伯格透露，他的公司已开发出了一个人工智能系统，足以匹敌最顶尖的人类围棋高手。当然，Facebook并不是唯一一家用电脑玩围棋的公司。早在2004年，微软的研发部门就开始开发针对围棋的人工智能软件。六年后，它将该技术应用到了一款Xbox视频游戏中。

　　谷歌人工智能5:0击败欧洲围棋冠军

　　1月28日谷歌DeepMind人工智能研究团队研究的人工智能系统Go挑战了三度欧洲围棋冠军樊麾。在番棋赛中，AlphaGo以5:0击败了樊麾。这是软件首次在全尺寸棋盘对职业棋手的比赛中取得这样的成绩。

　　在公布这一消息后后，DeepMind团队已向全球最优秀的围棋选手之一，韩国的李世石发出挑战。这一比赛将于2016年3月进行。

　　1997年，当卡斯帕罗夫负于“深蓝”时，著名棋评家菲舍套用莎士比亚的名句评论说：您是愿意投降呢，还是一定要我为您流汗。要是我流起汗来，那是你亲友的眼泪，悲泣着您的死亡。 当人工智能发展越来越深入，人们关心的已经不只是结果，更关乎未来。