“阿尔发狗”为什么盯上围棋而不是麻将传说尧作围棋以教丹朱如此算来围棋就有4000多年历史了。2009年LG杯决赛即被善于造势的韩国人渲染为“四千年之战”。当时对局的是李世石和古力颇有中韩围棋此消彼长的天王山之战的意思。如今李世石又站在了历史的关头肩负着人类四千年的高傲和尊严只是对面坐着的是谷歌的计算机棋手阿尔发狗(AlphaGo)。谷歌古哥莫非前定。围棋是什么在计算机的眼里其无非是一个桌面游戏。19*19的棋盘黑白轮流走棋。一块棋没有气了就得从棋盘上拿掉。最后无处可下了谁占的地方大谁就赢。规则如此简单。但在人类的眼里围棋早就超越了游戏的范畴。其中有历史有礼仪有美学有人生哲理。本能寺变淮上信至十番棋擂台赛见证了多少历史新布局宇宙流美学的大竹石佛与妖刀蕴含了多少风雅入界宜缓弃子争先早成了无数人的人生信条。当计算机真的坐到自己对面时人是五味陈杂的我说这是人生你却说这只是一场游戏。在浩如烟海的人类智力游戏中围棋不过是一粟而已其在民间的影响力未必能比得上麻将和扑克。相比中国寻常巷陌的麻将桌子和赌城成千上万的扑克台子下围棋多少有点曲高和寡的意思。那么为什么人工智能如此青睐围棋呢为什么不是“AlphaMajo”挑战四川麻将高手或者“AlphaHoldem”挑战德州扑克冠军呢其原因有三其一围棋有简单的输赢规则 (explicit winning condition)。这一点非常重要因为电脑需要对每一个决策的好坏做精确、量化的评估。把围棋下好可能需要十年但初学者就可以判断一盘下完的棋谁输谁赢。如果规则本身比较模糊可以去想象电脑和人类比拼现代诗或者抽象派绘画会出现什么样的结果。其二围棋是信息对称的。面对棋盘电脑和其人类对手看到的是完全一样的信息。象棋和国际象棋亦是如此。麻将、扑克和四国军棋则不同每个玩家只能看到自己一方的信息而必须通过对手的行为去推测他的底牌。这就不难解释为什么久经沙场的麻将老手往往输给不按常理出牌的新手以及为什么德州扑克里有层出不穷的骗术与心理战。信息的对称让电脑可以做绝对理性的决策不管你为什么这么下我只要下当前局面下最好的一手就行了。其三围棋广阔的搜索空间带来的挑战和诱惑是电脑无法抗拒的。人类下象棋和国际象棋早已沦为电脑的手下败将而围棋至少还能期待柯洁。电脑学下围棋到底有多难围棋究竟有多难呢对人类棋手来说这很难量化。聂卫平曾谦虚地表示“围棋境界高不可及我也只能算是刚刚入门。”职业棋手经常被问到与“围棋之神”的差距有人说让两子有人则认为围棋的发展接近尽头众说不一。人类的视野总是被眼前的山挡住等爬到山顶才知道山外又山。对计算机来说这个问题就好回答得多。围棋究竟有多少种变化呢如果对每一种变化我都能判断局面好坏那岂不就是每步都能走到最优的围棋之神了吗早期的人工智能的设计者们的确是这样想的。设想我们玩一个Tic-Tac-Toe见上图。连直线、圈叉棋的游戏3*3的棋盘玩家分别在空格中填入棋子最先连成一行、一列、或一对角线者胜。如果考虑每个空格只有黑子、白子、无子三种状态那么一共只有3^93的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-BetAlpha-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对应的局面有多少呢天文数字。胜负是怎样分布的呢不知道。那么一千盘一万盘棋对于这样的统计分析来讲只是个微不足道的样本很难得出有实际意义的结论。没关系样本不够可以多下反正是随机棋不费电。看上去不错的招咱们就多下十万盘看上去不怎么样的咱们就少下几盘甚至把这一枝减掉。深蓝用过的搜索算法咱们一样能用只要把估值函数换了就好。
)
