|
围棋人机大战激斗正酣，人工智能“阿尔法狗”前三局吊打世界冠军李世石，却又在第四局走出超级烂招，引发世人猜测“电脑也会故意输棋”时，我们约请在美国大学任教的计算机专家，撰写系列评论，从阿尔发狗的前世今生揭开它表现反常的秘密！敬请关注。 ↓↓↓
文/梅俏竹（美国密歇根大学信息学院和计算机系副教授，长年从事大数据分析研究）
一，“阿尔发狗”为什么盯上围棋，而不是麻将？ 传说尧作围棋以教丹朱，如此算来围棋就有4000多年历史了。2009年LG杯决赛，即被善于造势的韩国人渲染为“四千年之战”。当时对局的是李世石和古力，颇有中韩围棋此消彼长的天王山之战的意思。如今李世石又站在了历史的关头，肩负着人类四千年的高傲和尊严，只是对面坐着的是谷歌的计算机棋手阿尔发狗(AlphaGo)。谷歌，古哥，莫非前定。 围棋是什么？在计算机的眼里，其无非是一个桌面游戏。19*19的棋盘，黑白轮流走棋。一块棋没有气了，就得从棋盘上拿掉。最后无处可下了，谁占的地方大谁就赢。规则如此简单。 但在人类的眼里，围棋早就超越了游戏的范畴。其中有历史，有礼仪，有美学，有人生哲理。本能寺变，淮上信至，十番棋，擂台赛，见证了多少历史；新布局，宇宙流，美学的大竹，石佛与妖刀，蕴含了多少风雅；入界宜缓，弃子争先，早成了无数人的人生信条。当计算机真的坐到自己对面时，人是五味陈杂的：我说这是人生，你却说这只是一场游戏。 在浩如烟海的人类智力游戏中，围棋不过是一粟而已，其在民间的影响力，未必能比得上麻将和扑克。相比中国寻常巷陌的麻将桌子和赌城成千上万的扑克台子，下围棋多少有点曲高和寡的意思。 那么为什么人工智能如此青睐围棋呢？为什么不是“AlphaMajo”挑战四川麻将高手，或者“AlphaHoldem”挑战德州扑克冠军呢？其原因有三： 其一，围棋有简单的输赢规则 (explicit winning condition)。这一点非常重要，因为电脑需要对每一个决策的好坏做精确、量化的评估。把围棋下好可能需要十年，但初学者就可以判断一盘下完的棋谁输谁赢。如果规则本身比较模糊，可以去想象电脑和人类比拼现代诗或者抽象派绘画，会出现什么样的结果。 其二，围棋是信息对称的。面对棋盘，电脑和其人类对手看到的是完全一样的信息。象棋和国际象棋亦是如此。麻将、扑克和四国军棋则不同：每个玩家只能看到自己一方的信息，而必须通过对手的行为去推测他的底牌。这就不难解释，为什么久经沙场的麻将老手往往输给不按常理出牌的新手，以及为什么德州扑克里有层出不穷的骗术与心理战。信息的对称，让电脑可以做绝对理性的决策：不管你为什么这么下，我只要下当前局面下最好的一手就行了。 其三，围棋广阔的搜索空间，带来的挑战和诱惑是电脑无法抗拒的。人类下象棋和国际象棋早已沦为电脑的手下败将，而围棋至少还能期待柯洁。
二，电脑学下围棋，到底有多难？ 围棋究竟有多难呢？对人类棋手来说，这很难量化。聂卫平曾谦虚地表示“围棋境界高不可及，我也只能算是刚刚入门。”职业棋手经常被问到与“围棋之神”的差距，有人说让两子，有人则认为围棋的发展接近尽头，众说不一。人类的视野总是被眼前的山挡住，等爬到山顶，才知道山外又山。 对计算机来说，这个问题就好回答得多。围棋究竟有多少种变化呢？如果对每一种变化我都能判断局面好坏，那岂不就是每步都能走到最优的围棋之神了吗？早期的人工智能的设计者们的确是这样想的。 设想我们玩一个Tic-Tac-Toe（见上图。连直线、圈叉棋）的游戏：3*3的棋盘，玩家分别在空格中填入棋子，最先连成一行、一列、或一对角线者胜。如果考虑每个空格只有黑子、白子、无子三种状态，那么一共只有3^9（3的9次方，即9个3相乘）＝19683种状态。就算考虑到落子的顺序，也不过是9! = 362880种变化。评估不到一百万种变化的优劣，对当今的计算机来说，自然是小菜一碟。 但是这个办法用得围棋上，一下子就傻眼了，变化太多！ 那么围棋的变化有多少呢？如果也考虑每个交叉点有黑子、白子、无子三个状态，那么一张围棋盘的状态是3^361种，除去实际不可能出现的状态，大约是10^170。相比起来，国际象棋的状态数只有不到10^50，这与围棋的复杂度相比较，完全可以忽略不计。如果考虑行棋的顺序，那么围棋有大概361!种变化，或者说是10^768（实际上没有这么多，因为总有不能落子之处）。无论哪一个，都是天文数字，因为宇宙中可观测的所有原子个数，也无非是10^80。 或许有人说，围棋之神也不一定每手都算到底吧，往后推算个三五十步差不多了。好，序盘的时候（按60手以内）推算50步大概有超过10^120种变化。10步？10^24。就算只推5步也有超过2*10^12种变化。何况对计算机来说有更严肃的问题：不走到底怎么知道谁好谁坏？ 看起来太难了！那么棋盘小一点会不会简单一点呢？答案是肯定的。在13*13的棋盘上，变化的个数降低到了10^304。9*9的棋盘上则只有10^120。张栩自创的四路棋，变化数只有10^13，而状态数更降低到了几千万个：仍然很多，但对计算机来说完全可以处理。 好了，现在我们知道围棋之神和宇宙之神大概是同一位。“她”既然能洞悉棋盘上所有的变化，大概也熟悉宇宙中所有的原子。AlphaGo真的能穷尽每一个变化吗？没关系，就算如此也并不恐怖。我们明天就把棋盘扩大到21路，那就算全宇宙所有的原子都变成AlphaGo也不行了。 三，早期的计算机围棋靠人教套路 计算机当然不是围棋之神。你可以把他想象成一个天赋异禀的少年，想要挑战武林高手。他内功极强，动作极快，但不会招数（想想刚刚学会九阳神功的张君宝或者张无忌），这样如何才能战胜招法娴熟的武林高手呢？ 由于对天文数字般的围棋变化的恐惧，最早的计算机围棋，选择了模仿人类的方式。你会我不会，但你走哪、我就走哪总会吧。这也是被专业棋手戏称为“背棋谱”的方式。小飞挂角，应以小飞。你逼住，我就跳，你跳，我就跟着跳，被人走得多的总是好的。大量的围棋知识如定式（布局的套路）、手筋（局部战斗的妙招）等，就这样从棋谱中提炼出来，然后被程序员以规则的方式告诉电脑。然后，电脑在实战中按部就班跟着走。著名国产围棋软件“手谈”的早期版本，就是走的这个路子。 这样的算法棋力，当然与规则库的完备程度相关，但基本上是相当低下的。见一招流星飞堕，便会应以一招花开见佛，这充其量是林平之他爹的水平。这种背定式的算法，实战稍微变化一下，小飞挂变成大飞挂，跳着走变成飞着走，电脑就立刻面目全非，找不到北。 当然，程序员也有对策，他们在“死记硬背”之上，逐渐加入了很多模糊匹配的尝试，在实战中见到略有不同的场面下，也可以走出下一手。这可以看成一定程度上的举一反三。当然，在差之毫厘、谬以千里的中盘战斗里，这样的模糊匹配很难奏效。 “背棋谱”的算法，还有一个重大缺陷，就是这些规则绝大多数都限于某个局部，而对全局棋子的协同则毫无章法。早期的围棋程序，最怕“征子”，即是这个缺陷的典型体现。 既然背棋谱的下法缺陷如此明显，为什么还是计算机围棋的程序员们的第一感呢？从计算机的角度讲，背棋谱极大地缩小了选择的空间。挂角除了小飞、跳、夹、尖顶、靠出，大概也没有多少应法了吧。这样值得考虑的选择就变得很少。可以大大减轻电脑的计算强度。 四，计算机围棋的另一做法是评估局势 那么有人会问，既然缩减选择范围不靠谱，咱们能缩减变化的深度吗？ 这是一个相当有趣的想法。如果每一招棋都只管当下、不想后招，那么每下一步不就只需要考虑最多三百来个变化了吗？假设我们可以判断每招棋放在棋盘上之后局面的好坏，那么选最好的一步下不就行了吗？这的确很诱人！当一盘棋只下了寥寥几十步的时候，真的可以判断局面的好坏吗？伟大的围棋之神，真的可以计算每颗棋子的效用吗？ 早期的计算机围棋，的确在此做了很多有趣的尝试。一些人在背棋谱，另一些人则在评估局势，评估局势甚至开始得更早。 这很好理解：往后推一步也不是终局，推十步也不是终局，那么只要我能精确评估局面的好坏，那么推多少步都能用得上。怎么做呢？分而治之吧！围棋不是谁围的地盘（目数）大谁赢吗？那假设棋盘上的每颗棋子都能折算成目，把它们加起来不就可以判断局势好坏了吗？从50年前（那时“计算机”的水平可以想象），就有人开始做这样的尝试。 具体的做法不一，但大致想法都差不多：离我方棋子越近的空点，越容易是我的，离对方棋子越近的点，越容易是对方的；活子，死子，和半死不活的子则分开考虑。据说第一个围棋程序诞生于1968年，其主要思想就是通过计算每一个棋子的“影响力”来评估局面，可惜其论文现在已经找不到。 另一篇发表在1981年的文章笔者倒是读了，基本的做法还是计算“气”（与棋子相邻的空位）的多少，选择最大化己方的气，最小化对方的气的下法。（因为气的多少关系到棋子的死活，也就是生存能力） 在1990年代的“手谈”软件里，其作者曾经把每个活子的影响力设置为：“对其相邻位置为4，斜位（小尖）为3，单关和小飞位为2，稍远为1。”在子效累加的基础上，设计者们又陆续加入了不少改进，以修正单子、相邻的棋子和成块的棋子的价值。 这样的做法棋力如何呢？似乎还是很糟糕。即便结合了一些人工智能的搜索算法，1990年代计算机围棋的冠军大概只是业余高手让14-16子的水平。如果说“背棋谱”算法，是打一套少林长拳，又重新打起；那这种静态评估法，有点像所谓的“乱披风”刀法，没有后招，看哪好砍就砍哪，砍到哪算哪。值得一提的是，虽然棋力不逮，静态局面评估作为中后盘的快速形势分析手段，倒是深受围棋爱好者喜欢。笔者在新浪围棋下棋的时候，经常使用其提供的形势分析工具来点目（数自己的空有多少）。在职业棋手孟泰龄的网络自战解说中，我们惊讶地发现泰哥原来有时也会用这个工具。 整个二十世纪，计算机围棋都处于背棋谱和形势评估交相辉映的时代。设计者们加入了许多启发算法以计算征子，识别打劫，模糊匹配，优化官子。可是计算机的棋力却如进了漫漫黑夜，一直上不去。 这导致围棋高手们对计算机的水平有着根深蒂固的轻视：直到阿尔法狗与李世石决战之前，罗洗河还认为自己可以轻松让AlphaGo四子。的确，如果一个学了三十年棋的人，还只能和业余高手下让子棋，他的围棋生涯恐怕早就被职业棋手判了死刑吧。 当然，在笔者看来，这种背棋谱和形势评估的计算机围棋，是远远称不上“人工智能”的。早期的设计者们播下了种子，这颗种子在黑夜里，在石头下慢慢生根发芽。它在等待掀开石头的一天，距这一天还有很多年。 五，计算机从走迷宫，去领悟下棋秘籍 计算机围棋的种子在石头下缓缓成长。让我们暂且按下不表，荡开一笔去看看真正的人工智能的研究者们在做些什么。他们绝大多数没有接触过围棋，他们从小的目标是打败国际象棋的人类棋王。 和东亚人从小就接触大棋盘不同，西方人的童年是从圈叉棋到国际象棋的过程。我们已经说过，圈叉棋的变化不到百万，国象的变化看上去似乎也不多。因此西方的研究者一上来，心里想的就是穷举法。 穷举也得有顺序。从威尼斯出发，条条大路通罗马。威尼斯是开局，罗马是终局，我们把通向罗马的过程叫做搜索。搜索在人工智能的兵器谱上稳居第一位。1990年代后由于互联网的兴起和人工智能的低谷，人们提到搜索的时候，首先想到的往往变成了Google和百度。我问，电脑告诉我…… 别忘了，搜索的本义，是寻找罗马的过程而非罗马本身！ 人类对搜索可不陌生。不就是走迷宫吗？在曼哈顿的每一个路口都有4个选择，不管选哪一个，到下一个路口又有另外4个选择在等你，直到你走出了迷宫或者穷尽了所有的选择。 从数学上讲，我们把空白的迷宫叫做“根”，每一个路口叫做“结点”，每一个路口面临的选择叫做“分支”，每一个无路可走的状态叫做“叶”，那么走迷宫所有的变化就成了一棵“树”。搜索的过程，就是按照某个顺序遍历这棵树，直到找到出口的叶子或者找遍所有的叶子。 这多么像围棋！从空白的棋盘开始，每一步的选择都带来数十成百的分支，每一个终局都是一片叶子，而每一盘赢棋都是罗马。 找到迷宫的出口或者找到罗马可不难，只要在走过的路口做记号，一直靠左或者右走就行了（在计算机算法里，这叫做深度优先搜索，它可以保证无遗漏地遍历一棵树）。难的是，到了罗马还赶得上吃顿热的。这可就难了，因此我们必须要放弃一些分支，放弃大多数叶子。在有限的时间和选择里，我们还能找到罗马吗？ 无数人工智能的先驱，前仆后继地研究这个问题，其中包括著名的Dijkstra，他的算法能让人找到威尼斯到罗马的最短路径（当然，找到这条路径的代价并不比深度优先的搜索低）。 计算机比人类擅长走迷宫，它可以自由地在已经发现的路口间跳跃（类似于机器猫的传送门）。这使得它可以每个路口都试一下再决定下一步，即是所谓的广度优先搜索。搜索算法中名满江湖的A星算法（A* Search, 最佳优先搜索的一种），即是兼备了广度优先搜索和最短路径搜索之长。它在每一个路口派出探子，回报下一个路口有多远、是哪里。它再综合当前路径的长度和对下一个路口离终点的距离的估计，来决定下一步怎么走。行军数天到离长安几百里外的陇右，似乎当然不如花十天出子午谷直逼长安城下。 这样的算法大大降低了搜索最优路径的复杂度。但是，估计威尼斯到罗马的距离容易，估计中盘到赢棋的距离，还是很难啊！ 等一等，我们似乎忘记了一件重要的事情。迷宫是一个人走，棋是两个人下的呀。不能预测对手的下法，怎么能找到自己最优的下法呢？在把搜索应用到棋类游戏的探索中，人工智能的先驱们发明了“极小化极大算法”（minmax algorithm)。听起来是不是很拗口？其实不难理解，在寻找下一步棋的时候，我们优先选择下在不管对方怎么应，我们都不会太坏的地方（而不是下在，如果对方应错了就占大便宜，应对了可能反而吃大亏的地方）。研究者们又设计了纷繁复杂的算法来进一步缩小搜索空间，以让计算机能在更有效的分支上搜索得更深，而不把时间花在一看就不行的废棋上。这其中一个相当重要的算法叫做Alpha-Beta剪枝。前文提到的1990年代的计算机围棋冠军即是用它来配合局面评估。Alpha-Beta, Alpha-Bet，Alpha-Go，前世今生，情何以堪！ 有了这些搜索算法在手，计算机在圈叉棋上战胜（或者打平）小朋友们早就不在话下了。可当人工智能的研究者们把眼光投向国际象棋的时候，却发现它的搜索空间意外的大，似乎怎么剪枝也搜不到底。 似乎也没有一个好的方法能准确估计非叶结点局势的好坏（如果子力多就好，那摆象棋残局的骗子们就都下岗了）。搞计算机围棋的一看，你象棋都搜不到底，我围棋就更别想了。于是计算机围棋又在黑暗中度过了二十年，直到一个英雄的出现。 六，“国象之神”深蓝带来的启示 1996年2月10日，一个叫“深蓝”的电脑挑战国际象棋棋王卡斯帕罗夫。让所有人跌破眼镜，它居然赢了第一局，之后两和三负。深蓝是IBM设计。双方约定一年后再战。1997年5月，双方再下六局，“深蓝”一胜五和战胜棋王。这是人工智能载入史册的里程碑事件。 值得一提的是，输棋之后的卡斯帕罗夫认为深蓝表现出的智能和创造性不可思议，必有人类棋手在背后操刀。这次谷歌显然早有准备，高调的营销，让几乎所有的人类高手都现身讲棋，从而杜绝了“机箱里躲着柯洁”的猜测。 “深蓝”为什么赢？除了摩尔定律带来的计算力的显著提高，深蓝的算法似乎也没有什么稀奇。Minmax搜索, Alpha-Beta剪枝, 为什么一夜之间武功就变得如此厉害？ 当深蓝揭开神秘面纱，人们发现，深蓝的秘密其实不外乎两点：局势评估和往前看。老熟人了，不是吗？深蓝的局势评估考虑了棋子的重要性（皇后是9，小兵是1，车取其中），每个棋子的影响范围（又很耳熟？），王的安全系数，以及先手(tempo)。这个评估并非静态的，而是往前穷举数步棋的所有变化，再对所有变化导致的局面进行估计（相传与卡斯帕罗夫下的时候，深蓝往前推了12步）。这有多难呢？粗略以每一步棋有100种下法而计（每个兵最多2-3种下法，每个马最多8种下法，每个车14种，去掉不能下的地方，以此类推），12步就是有10^24种变化，用上alpha-beta的剪枝和IBM强大的并行运算能力，完全可以处理！ 深蓝的成功，让人类第一次正视人工智能的强大潜力。让我们看看深蓝带给计算机围棋的前所未有的启示与契机。一方面，深蓝的成功宣告国际象棋已经是被解决的问题，这让大量人工智能的研究者们把目光投向了下一个挑战：围棋。另一方面，计算机围棋的设计者们从深蓝身上惊讶地领悟到了两点：其一，并没有多少专业知识，貌似蛮力的穷举搜索竟能如此有效；其二，精确的局势评估如此重要，但静态的评估并不足取。从现在开始，背棋谱不再是出路，而局势评估将以动态的搜索为基础！ 2006年，一个叫做《疯狂的石头》的黑色幽默电影席卷中国。同年，一个同名（Crazy Stone）的计算机围棋程序悄悄地在计算机奥运会上夺得9*9围棋的冠军。翌年，它在计算机奥运会上蝉联9*9冠军并夺得19*19比赛的亚军。再下一年，疯石在对真正的职业棋手（青叶熏四段）的授八子局中获胜，同年年底又赢了授7子局。5年后（2013年），疯石在对石田芳夫九段的授四子棋中取胜。第二年，同样授四子，疯石取胜棋力更强的依田纪基，在围棋界的影响力达到顶峰。 无独有偶，2010年之后网上出现了一个叫zen（禅）的计算机棋手，在KGS（一个著名的围棋服务器）上慢慢升到5段。笔者当时经常在KGS下棋，也曾和zen互有胜负。不久就只能眼睁睁看着它的棋力超过自己，扬长而去。2012年，zen也在授四子局中击败了专业九段：深受大家喜爱的武宫正树。 从此计算机围棋进入了一个新的时代，一个不断带给大家惊喜的时代。可我们不禁想问两件事：第一，“疯石”的出现离“深蓝”也有十年过去了，这十年计算机都在做些什么？第二，为什么这一切总是和“石头”有关？ 七，一株奇异的树——蒙特卡洛树
从“疯石”开始，这个时代可以被称为“蒙特卡洛时代”。当代的计算机棋手，不约而同地采用了一种叫做“蒙特卡洛树”的搜索算法（Monte-Carlo Tree Search），直到AlphaGo也不例外。它是什么独门绝学？ 深蓝带来的启示之一，是寻找精确的局势估计函数，而这个函数必须是动态的，必须要考虑到数步乃至数十步之后的局面。 这思路并非没人想过。可是相比国际象棋，它有唯一的取胜目标——杀老王，围棋的局势判断或许更为主观。什么是势？什么是厚？什么是薄？势与地如何换算？大局观究竟是什么？这些大概是围棋永恒的问题。就连顶尖棋手也常常判断不清。看顶尖高手的比赛最有趣，总是韩国解说觉得韩国人好，中国解说觉得中国人好。一边说是弃子，一边说是被吃……计算机可不喜欢横看成岭侧成峰，它需要理性和客观的决断。 那么围棋中有什么是绝对客观的呢？我们之前说过，只有终局的胜负。可那些终局的叶子在围棋的搜索树上似乎遥不可及。那么，能否不穷举所有的叶子，也能判断分支的局势呢？这个想法让人精神一振。如果一棵枝头有10片叶子，8片是赢，两片是输，我们一定要找到输赢最大的一片才能判断这个枝头的好坏吗？如果这棵枝头有100片叶子，我们难道一定要看遍所有的叶子才能判断优劣吗？ 喜爱统计的朋友们已经乐出了声：要想知道添加剂是否超标，当然不需要打开所有的罐头。抽样就行了嘛！假设对每手棋我们都抽样调查它所导致的终局，大概不需要理解地、势、厚、薄也可以做形势判断了吧？ 如何抽样？当然随机最简单。一步新着法好坏不明时，职业棋手往往提倡实战解决。计算机也一样，只是并非找两个高手下一盘，而是找两个不懂棋的小朋友下一千盘罢了。随机下一千盘棋，对电脑来说花费几何？以微秒计吧！ 这不就好办了吗！从现在起，每一个局面我都可以客观地估计好坏了，同时我并不需要遍历整个搜索树（所以请不要再叫我穷举法！）。真是这样简单吗？我不信。难道从第一手右上星位开始，随机模拟一千盘棋，发现白胜501盘，就说明黑1是败招吗？很可惜，随机抽样得到的结果是一个统计上的期望，而并非实际上的“最优”。它需要遵从统计之神的规律。第一手黑1对应的局面有多少呢？天文数字。胜负是怎样分布的呢？不知道。那么一千盘，一万盘棋，对于这样的统计分析来讲，只是个微不足道的样本，很难得出有实际意义的结论。 没关系，样本不够可以多下，反正是随机棋不费电。看上去不错的招，咱们就多下十万盘，看上去不怎么样的，咱们就少下几盘甚至把这一枝减掉。深蓝用过的搜索算法，咱们一样能用，只要把估值函数换了就好。 ———————————————————— 奇异的蒙特卡洛树，再加上“国象之神”的动态评估、剪枝等办法，计算机围棋是不是找到了通向围棋之神的正确道路了？请继续关注川报观察客户端的系列报道，专家将揭秘最强大的阿尔发狗的武功秘籍，以及它突然崩溃的根本原因！ 编辑：曾东平
|
|
|
来自： lvzhenhui1957 > 《待分类》
