人工智能在围棋程序中的应用

(_仯帥ゞ

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

象棋

确实极待发展。。。。。。。。。。。

老好人

目前比较强的围棋软件都不是用1楼的算法

一个真正天才的想法只是常人没想到而已，它本身不会很复杂的，因此我觉得十分钟足矣。


MC方法
我先介绍蒙特卡罗（即MC）方法，这是一个赌城的名字，Monte Carlo，位于摩纳哥。这个方法与赌博有关，如果你愿意，你也可以把它叫做拉斯维加斯方法，或者麻糕方法，没听过麻糕？那么插播一个笑话：


a:听到一特好听的歌，歌词只记得是“一个芝麻糕，不如一针细”，求歌名啊！
b:你可知Macau，不是我真姓……－_－!



为了启发她使用MC方法，我从她熟悉的事物说起：


你前段时间经常玩新浪空间的我爱老虎机游戏，你知道你玩的老虎机胜率是多少吗？

什么胜率？

就是类似你炒股一样，有个投资回报率，或者换个说法叫收益率。

平均100个币能变成200吧

这么说，收益率就是100%了？

嗯，对。



大家看，我妻子已经用MC方法计算出了老虎机的收益率，她没有看过老虎机的源代码，不知道它何时吐币多少的内部规律，可是她能知道收益率。如果给我源代码，我也能算出来期望值是多少，但是以前我反编译过那个老虎机的flash，发现其吐币逻辑在服务器端，所以我很难得到源代码。


UCB算法
在启发她知道什么是MC方法后，我决定给她一个难题，考察她灵活运用MC方法的能力。


我说，你看，现在老虎机游戏每天只能在一个好友那里投10次币，每个好友只有一台老虎机，假设游戏改一下规则，每个好友那里有10台老虎机，每个人的每台老虎机收益率都不同，并且每天一变，那现在你怎么玩这个游戏呢？

我妻子想了想，说，我每台老虎机投10个币，看看哪台赚的多，然后就玩哪台。

我说，不错，你已经掌握了MC方法的精髓了，但是每天在一个好友那里最多只能投100个币，你10台都试完了就不能再投币了，你已经知道哪台收益率最高，可是第二天收益率就变了，这时候你该怎么办？

我妻子说，不知道了。

我说，没关系，因为接下来我要给你介绍的方法是人工智能领域里最前沿的算法，这个方法叫UCB，你不用管它的名字，它其实就是用来玩老虎机的。我在纸上画了10个老虎机，指着其中一个说，假设你一开始玩这个，得到了一些收益，然后你如何决定接下来玩哪个呢？有个科学家提出了UCB算法，他对每个老虎机计算一个UCB值，这个值由两部分相加而组成：第一部分是这台老虎机以前的收益情况，第二部分与这台老虎机被玩的次数及你总共玩的次数有关。第一部分好理解，因为以前的收益情况，提供你选择的标准，通常都会选以前收益最大的，第二个部分就是说，如果一台老虎机你都没玩过，你怎么知道它的收益好不好呢？所以你要给它一个机会，也给你自己机会。就是说被玩次数少的，UCB值的第二部分会给出一个较大的增益，让它有被选择的机会……

我妻子顿悟：我知道了，就好像我喜欢吃烤鸡腿堡，但也不能老吃，偶尔也要吃吃大白菜。

我说，恭喜你，你已经站在了人工智能领域的最高峰了，我怎么就没想到这样浅显的比喻呢！以后UCB算法也可以叫鸡腿堡算法了。



这样，我妻子很快就明白了UCB方法的含义了，尽管她还不知道UCB公式的细节：UCB=X+sqrt(2ln(N)/T)，X表示以前的收益，N表示所有机器玩过的总次数，T表示这台机器玩过的次数。


MC之于围棋
现在我们要切入正题，我要讲的是围棋AI的设计。假设我下了一步想走在这里，那么我怎么知道这步棋好不好呢？有个科学家就提出了，假设你这步棋已经下到这了，找两个傻子，让他们随便下，把棋下完，看看是黑棋胜还是白棋胜。只有两个傻子，这结局太有偶然性了，那么我们找10000对傻子来下一万盘棋（妻子突然打断我，弱弱的问，这一万盘棋都是由电脑来模拟吧），然后统计一下是黑棋赢的多还是白棋赢的多，这样我就得到了这一手棋的获胜概率，然后我把所有可能下法的获胜概率都这样算出来，选择获胜概率最大的下法。这个方法是不是有点眼熟？


哈哈，和前面10台老虎机问题时，我妻子给出的方法如出一辙。（由于我妻子不懂树(Tree)，接下来我都在纸上画给她看，因此她的作用在本文中到此为止了。）到这里为止，本文给出的mogo的算法细节还没超出关于mogo的新闻报道，而下面的内容会难一点，如果读者就此打住，那么凭此文也就能遐想一下围棋AI的前景，你无法得到mogo算法的奥义。


UCT登场
MC直接用在围棋上的缺点十分突出，首先是浪费了模拟次数，因为在有限的时间内只能模拟出一定的棋局数。其次，它没有考虑对方的下一手，如果我们把MC当做估值函数，那么对比传统的人机博弈程序，简单的MC相当于只搜索了一步。如果估值无比精准的话，那么一步足矣。实际上围棋还不存在这么精确的估值，以MC的估值速度，往深算几步，耗费的时间无法接受。


博弈搜索可以理解成一个树形结构上搜索，在树形搜索上结合UCB，就是UCT算法了（UCB for Tree）。


假设我们已经有了一棵树，每一个叶子节点上有一台老虎机，我们怎么用UCB算法来玩这些老虎机呢？方法一是把所有的叶子节点都列出来，然后按公式计算每一个叶子节点的UCB值，从中取最大值的那个叶子节点来玩。这个方法有点笨，既然这样，何必要用树呢？


方法二，由每一个非叶节点汇总它下面的节点的收益和玩过的次数，如果下面节点也不是叶节点，那么也向下汇总。这样计算UCB值时，只需要计算直接子节点中的最大值，然后进入这个子节点，再去选择它的下一级节点的最大值，以此类推，最终选到的那个叶节点就是我们要玩的那台老虎机。


方法二与方法一选出来的最大值不是同一个，因为，方法二多出一个假定，我要选的最大值是在我的最大分支里面。而实际上一个最有钱的城市里不一定住着最有钱的人，因此，这个假定不一定合理，不过无所谓了，就算找出来的不是最有钱的，也不会太平庸，何况我面对的是一个概率，而不是确切的多少钱，如果你这个分支整体上都表现很差的话，我凭什么相信你呢？


方法二与方法一的分歧我们先放一放，以后实现时可以两种方法都试一下。总之，我们所说的UCT就是方法二。为了确定读者是否明白了UCT方法，我再把算法步骤写下来。


UCT算法描述：
对于已经建立的一棵树

从根节点开始

利用UCB公式计算每个子节点的UCB值，选择最大值的子节点

若此节点不是叶节点，则从此节点开始，重复2

直到遇到叶节点，play叶节点，得到收益，将这个收益更新到该节点及它的每一级祖先节点上去

回到1，除非时间结束或者达到预设循环次数

从根节点的子节点中挑选平均收益最高的，作为最佳点

如果有疑问，可以先跳过下下一节，那里会有一个比这更复杂的等着你。



UCT之于围棋
如果把UCT用于围棋，我们会面临两个问题：一，UCT的树是已经建立好的，而对于围棋，初始情况下是没有树的，树如何建立？二，围棋是黑白双飞轮流下子，这个又当如何考虑呢？下面解决这两个疑问。


首先，如果我们假设（注意仅仅是假设），事先建立起了一棵庞大无比的博弈树，它的节点已经包含了全部的n层对局，就是任意下n手，得到的局面都已经出现在了这棵树的节点上。这个时候，我们不就可以利用UCT进行搜索了吗？不错，但是这个时侯最多也只能搜索n层，你做的还不够。而且，大部分节点你根本来不及去使用，为何要预先把它们造出来呢？


因此，我们一开始建立根节点，再为根节点建立它的第一层子节点，除此之外我们不再预先建立子节点，而仅在需要的时候再建造。这个时候我们开始寻找这棵树的最大UCB值的叶节点了，就用上一节中的UCT算法，遇到叶节点后，我们开始玩它，得出了一个胜负结果，然后更新它的祖先节点，直到此时，算法的进行与UCT一模一样，现在又开始下一轮寻找最大UCB了，假设找到的还是上一轮的那个节点，我们发现，它竟然是已经被玩过的，与上一节的UCT差别就在这，玩过的我们不要，我们为它生成它的下一层子节点，然后继续用UCT的方法寻找最大的UCB值，然后继续玩。


这里的玩，就是指来一次模拟对局，现在我们发现按这种方法，其实每一个节点所代表的局面，最多只进行一次模拟对局，因为下次再选中它时，就会继续深入到它的子节点了。这再一次印证了UCT的思想，不要最强的节点，只要最强的分支。因此单个节点由于运气表现不好时，只要整个分支表现好，还是有机会的。


我们能够建立这棵树了，那么双方轮流下子的问题怎么解决呢？很简单，每一层子节点所属的是黑子还是白子这是可以知道的，所以我们在更新胜负结果数时，只更新对应颜色的胜局数。举个例子，你代表的是黑色的节点，你下面的节点向你报告，黑方胜利，那么你把自己的玩过的局数加1，胜利局数加1，然后往上报；而如果下面报告说白方胜利，那对不起，你把玩过的局数加1，胜利数没你的份了。


按照这样的方式汇总胜负数，在寻找UCB最大值时，就刚好是符合双方都走最强应对的原则。因为每方只记录自己这方的胜利数，选择的时候，都是选使得自己这方胜率最大的节点。


按照这样的算法，我们有理由相信，mogo能走对任意步数的征子，而实际上它的确能走对。


这样看来，UCT算法用在围棋AI上，恰好实现了一种高明的剪枝，而且它用的是循环而不是递归，它的棋力跟循环次数有关，而不像传统程序一样由递归深度来控制。


我仍然给一个算法说明，来检验一下读者是否看明白了：


UCT应用于围棋的算法描述：
由当前局面建立根节点，生成根节点的子节点
从根节点开始

利用UCB公式计算每个子节点的UCB值，选择最大值的子节点

若此节点不是叶节点，则从此节点开始，重复2

直到遇到叶节点，如果叶节点曾经被模拟对局过，为这个叶节点生成子节点，从此节点开始，重复2

否则对这个叶节点进行模拟对局，得到胜负结果，将这个收益按对应颜色更新到该节点及它的每一级祖先节点上去

回到1，除非时间结束或者达到预设循环次数

从根节点的子节点中挑选平均收益最高的，作为最佳点
实际运用中，不必每次从头建立根节点，只要把上一手棋选择的节点作为根节点，其他分支简单抛弃掉，因为它们在实际对局中不会再用到了（这好像浪费掉了因不同手顺而产生的同一局面的统计结果，不过我还不知道如何解决同局不同顺的问题，先不管它了）。


看完这个介绍，有没有想要自己实现一个类似于mogo的程序呢？貌似现在mogo的源代码还没有公开，公开源代码的有名的程序叫gnugo，基于模式匹配的，那个复杂呀，棋力还不行，远不及mogo的优雅简单。