对决（上）：机器下围棋

userzzn

阿法狗战胜顶尖围棋手的消息震惊了围棋界。

2016年1月27日出版的《自然》期刊以封面论文的形式，介绍了谷歌公司研发的一种能与专业棋手对弈围棋的人工智能程序——AlphaGo的算法。论文称，Alphago于去年10月，以5:0的成绩战胜了欧洲围棋冠军樊麾。而且，Alphago将于3月份在首尔挑战过去十年被认为是世界围棋冠军的李世乭；比赛一共5轮，时间分别为9日、10日、12日、13日和15日；获胜者将获得100万美元的奖金。

早在1997年5月11日，IBM公司研发的“深蓝”超级计算机就击败了国际象棋世界冠军卡斯帕罗夫。但发明逾2500年的中国围棋远比国际象棋复杂，在搜索的广度和深度上被认为是人类发明的最复杂的棋类游戏。因此，Alphago战胜顶尖围棋手的消息震惊了围棋界，也被誉为人工智能的重大进展。而今年3月的棋局更是激起了人们的好奇心，也再次掀起有关了人工智能前景的讨论。

那么，人工智能战胜人类棋手是否必然？Alphago是如何下棋的？Alphago与李世乭对弈的胜算如何？人工智能与人类是否存在本质差异？人工智能是否可能取代并最终消灭人类？



围棋是可破解的

我在念小学时曾尝试过一种简单的虎豹棋，玩了不久后就发现先行方可找到一种策略保证赢棋。当时的困惑是，是否其他确定性棋类游戏也一定存在类似的策略呢？在博弈论中，如果两方对弈的确定性棋类游戏中的一方能找到保证自己不输的策略，这个游戏被称为“已破解”。根据此定义，前面提到的虎豹棋可被简单破解，而很多其他较简单的棋类游戏也已破解。比如，加拿大阿尔伯塔大学计算机游戏专家 Jonathan Schaeffer于2007年7月破解了西洋跳棋。他的做法是把西洋跳棋的对弈分成各种可能步骤，并做归类，然后使用50到200台个人电脑，花费18年时间用穷举法检验所有可能步骤。

那么，任何一种两人对弈的确定性棋类游戏，是否都是可破解的呢？更准确地说，在一个规则明确、棋局有限、信息完全、确定性的两方对弈的棋类游戏中，是否有一方一定可找到一种策略，在任何情况下都能保证不输棋呢？从直觉来看，这个结论应该是正确的。实际上，德国数学家Zermelo在1913年就证明了上述结论，他的证明在1997年被翻译成英文。他的结论是，任何一个两方对弈、信息完全的确定性棋类游戏都是可以破解的。

围棋是一种规则明确、信息完全、确定性的两人对弈的游戏。围棋棋盘只有19*19个落子点，而每个落子点只可能呈现黑子、白子、空白三种状态，所以围棋最多只有3^(19*19）种可能的棋局，因此也是一种棋局有限的游戏。根据Zermelo定理，围棋是一种可破解的游戏。即，围棋中必有一方拥有不败策略，不管对方如何走，都能确保自己赢棋或者和棋。这意味着，如果计算机有无限的计算能力，那么计算机就可以为对弈中的一方找到这种不败策略，让对方在任何情况下也无法赢棋。

但是，围棋可破解，并不意味着它像西洋跳棋那样能够被破解。这是因为围棋的搜索空间远比西洋跳棋要大。比如，在8*8的棋盘和24个棋子的情况下，西洋跳棋共有10^20种可能的棋局，而且由于很多棋局可被视为等价，破解者Jonathan Schaeffer只需要进行了10^14次计算就能找到破解算法。相比之下，即使去掉不符规则的棋局，围棋的棋局数量也达到0.01196 * 3^(19*19) = 2.081682*10^170，这也要远远大于整个宇宙的所有原子的数量的估计数10^80。相比之下，国际象棋仅有10^47种棋局，而西洋跳棋仅有10^20种棋局，都要远远低于宇宙中的原子数量。这说明使用类似于Jonathan Schaeffer破解西洋跳棋的穷举法根本不可能破解围棋。

由于围棋搜索空间的广度和深度远超过任何计算机的处理能力，很多人认为计算机战胜专业围棋手将遥不可及。甚至有人认为，围棋的顶尖水平需要哲学甚至艺术思维，不可能被计算机掌握。在Alphago登场之前，人工智能围棋程序的最高水平也仅与业余棋手相当，要战胜专业棋手被认为至少是10年以后的事情。

因此，Alphago以五战五胜的成绩战胜欧洲围棋冠军樊麾，让很多人对人工智能刮目相看。特别是，包括2016年1月5日获梦百合杯世界围棋公开赛冠军的柯杰在内的许多专业棋手，在观察对弈棋谱之后认为，与之前的围棋程序不同，Alphago下棋风格与人类无异。如果隐去对弈者的识别信息，根本无法判断对弈双方哪个是Alphago，哪个是樊麾。这说明，Alphago模仿了人类的思维方式。那么Alphago是如何做到这点的呢？

机器如何战胜欧洲围棋冠军

根据《自然》期刊论文的介绍，Alphago使用了两种深度学习神经网络，即“策略网络”和“价值网络”。深度学习神经网络是近年人工智能领域的热门，在笔迹识别、自动驾驶、自然语言理解、图像和语音处理等方面都极为成功。在人工智能领域，神经网络是一种模拟生物神经系统的模型，由许多单向连接的神经元组成，可将输入信号转换为输出信号；具体如何转换取决于链接神经元的各种参数。神经网络的学习就是根据训练样本不断更新参数的过程。比之一般的神经网络，深度学习神经网络使用隐含的多层复杂结构，以及非线性变换，来表达对数据的高度抽象。这些特征更接近于生物大脑，也因此更容易实现人类大脑的某些功能。相对简单的神经元加上多层级的复杂结构也适宜于大规模并行计算，而且可将数据在不同层面进行抽象表达，并赋予结构化概念的意义。

围棋的搜索空间可由广度和深度来表示。搜索广度是指在当前棋局下的下一步落子的范围，而搜索深度是指未来的步数。由于不可能穷举搜索空间，围棋程序本质上都在追求缩小搜索空间的广度和深度。Alphago的“策略网络”负责减少搜索的广度——针对当前棋局，判断下一步该在哪里落子，判断结果表述为落在不同位置的概率；Alphago的“价值网络”则负责减少搜索的深度——对每一个棋局，判断赢棋的概率；根据未来棋局的赢棋概率来决定是否需要继续搜索下去。Alphago采用“蒙特卡洛树搜索”算法将“策略网络”和“价值网络”综合起来决定走哪一步。

Alphago的决策方式与人类相似。“策略网络”类似于战术大脑，负责短程思考，学习高水平棋手的一些基本功，用相对“局域和短期”的视角来决定下一步落子的大概位置；“价值网络”则类似于战略大脑，负责长程思考，学习如何判断未来各种棋局的赢棋的几率，用这种判断来快速思考各种落子选择会遇到何种局面。而“蒙特卡洛树搜索”算法类似于围棋中的“长考”，即根据当前棋局，确定自己可能的步子，再在假想状态下演绎双方对弈的可能性较大的路径，最终选择在假想演绎中赢率最大的步子。

那么“策略网络”这个“战术大脑”是如何学习的呢？论文描述了两种学习方法：

“监督训练”：类似于专家手把手训练“战术大脑”。训练样本是3000多万个棋局和专家的相应棋步，训练目标是让“战术大脑”选择的步子尽量接近专家的棋步。“策略网络”的13层结构便于将棋局表达成具有各种抽象概念之间的关系，能较好地模拟专家的思维。由于搜索空间中可能性棋局太多，“策略网络”只能将棋局信息压缩到一个较小的表达空间上，而这个空间未必足以充分反映棋局的各种细节。

“强化训练”：类似于让经过了“监督学习”后的初学者之间相互对弈来提高棋艺，即让“策略网络”自我对弈来改进“战术大脑”。如果说“监督学习”的目标是让“战术大脑”下得尽量像专家，那“强化学习”的目标则是不断提升“战术大脑”在对弈中的赢棋概率。在这种学习过程中，那些从“监督学习”中获得的有助于在实战中赢棋的思维倾向得到强化。

需要注意的是，专家的“长程思维”不是直接反映在“策略网络”的训练输出上，而是通过“策略网络”的多层结构中某些神经元所代表的概念，或者“强化训练”中对棋步选择带来的最终输赢的奖惩来得到间接体现。因此，经过“监督学习”训练出来的“策略网络”在实际对弈中因未直接接受“长程思维”的训练而比较短视，还可能因为遗漏某些细节而会下出一些“抽风”的棋步。

不同于之前人工智能围棋程序的是，Alphago使用“价值网络”这个“战略大脑”来直接反映“长程思维”。“价值网络”的结构类似于“策略网络”，输入信号是各种棋局，但输出的是该棋局自己一方最终赢棋的概率。如果说训练“策略网络”是为了让“战术大脑”通过模仿专家自我对弈来学会下一步落棋子位置的相对概率，训练“价值网络”则是为了训练“战略大脑”来对不同棋局估算赢输几率。“价值网络”的训练样本来自“强化训练”出来的“策略网络”自我对弈的各种棋局以及赢输结果。

除了使用“价值网络”的“战略大脑”外，Alphago还通过“随机滚示”来估算棋局的赢率。一次“随机滚示”是指，对弈双方按训练出的“战术大脑”的概率，随机选择棋步进行对弈直至结束。面对特定棋局时，一方赢棋的概率可以用多次“随机滚示”中该方最终赢棋的频率来估算。为了节省时间，“随机滚示”使用“战术大脑”是精简版的“策略网络”，其模仿专家的准确度要比完整版的“策略网络”低，但速度要远快于完整版。

在实战“长考”中，Alphago使用“价值网络”和“随机滚示”两种估算的加权平均来判断棋局最终赢输几率。实战模拟显示，这种判断比单独使用“价值网络”或“随机滚示”的估算更能提升Alphago的棋力。原因是这两种估算是互补的：“价值网络”估算了强但慢的“策略网络”的对弈结果；而“随机滚示”则估算了弱但快的“策略网络”的对弈结果。

在实际对弈时，Alphago采用“蒙特卡洛树搜索”的“长考”方式来决定在哪里落子。具体来说，就是综合“短程思维”和“长程思维”来搜索并分析各种较可能的对弈路径，确定最好的棋步。这相当于人类棋手在面向当前棋局时，考虑自己最可能要下的棋步，以及对方相应要下的棋步，并依此演绎下去。路径搜索树的顶端节点是当前棋局，下面每一条边是一个可能的棋步，之下则是该棋步对应的棋局。

Alphago在“长考”过程中，对每个可能选择的棋步计算“行动价值”；所谓“行动价值”是指采用“价值网络”和“随机滚示”两种方法对相应棋局输赢几率估算的加权平均。“行动价值”会加上一个“奖励项”，该奖励项与该棋步被“策略网络”选择的概率成正比，但随该棋步在“长考”中被遍及的次数递减，以鼓励“长考”探索不同棋步。树的搜索过程会选择“行动价值”加上“奖励项”得值最大的步子。然后，在相应棋步的子树下进一步扩展，并使用子树各节点的估算来更新上个节点的“行动价值”，得出对赢率更精确的估算。

在大量重复上述树搜索过程的基础上，Alphago将选择在搜索中遍历次数最多的步子。Alphago这个“长考”过程相当于，根据对赢输几率的判断，不断演绎未来双方可能的棋步，并在这种演绎中对不同棋步的输赢几率得出更准确的判断，最后选择最有可能赢棋的棋步。

机器能否赢得与顶级棋手的关键对决

由于Alphago并非对棋局进行精确判断和搜索，而是根据专家棋谱学习基本棋步并在此基础上通过自我对弈来提升棋力，这些算法所涵盖的空间虽然非常大，但依然只是可能性空间中的极小一部分。因此，李世乭赢Alphago的可能性还是存在的。在首局中，李世乭或许应该把Alphago当成正常的人类对手来对弈。如果李赢得首局，那说明Alphago现有算法构成的搜索空间依然不足以涵盖人类顶尖围棋手的思考范围，在后续对弈中李可采用相同的策略。

但如果李输掉首局，那说明他的对弈策略已经落入了Alphago的搜索范围，因此李世乭需要独辟蹊径才可能在后几局中反败为胜。由于在对弈中选择的是赢棋几率最大的棋步，Alphago的风格会趋于保守，偏向于选择那些最终赢棋概率较大，但所赢目数较少的棋步。而且，Alphago在“长考”中会较多演绎那些最优或者较常出现的步子。因此，在输掉首局的前提下，李世乭或许可在后面的对弈中侧重于“长考”一些通常情况下不太选择的棋步。

Alphago给人留下的深刻印象之一是，它可以每天自我对弈上百万次来提高棋力，这种训练力度让人类棋手叹为观止。但在现有框架下，不断训练给Alphago带来的棋力提升效果受制于三个因素。

首先，围棋的棋力未必能充分地表达为“策略网络”的短程大脑和“价值网络”的长程大脑。比如，围棋高手对棋局平衡的感觉或许就难以在框架中得以体现。其次，“策略网络”未必能充分反映短程大脑，“价值网络”也未必能充分反映长程大脑。如果这两个深层神经网络本身不能表达出某些细节，即使训练无穷次给出最好的参数估计，这两个网络本身也不能完全表达“完美”的“短程大脑”和“长程大脑”。再者，训练的最初样本是专家的3000万个棋局，这些棋局本身未必能充分反映各种对弈可能，而可能偏离实际对弈时对手的棋风。当然，Alphago可将李世乭的历史棋谱作为部分样本来专门提升其针对李赢棋的概率。

因此，如果这次在比赛中输给了李世乭，Alphago在未来要反败为胜可能还需要进一步改进框架，而不能指望只对算法进行更多的训练。当然，增加深层网络的层级和神经元的数量或许也会有帮助。

Alphago与李世乭的比赛激起了很多人的猜测与好奇心。笔者所在的一个微信群针对比赛结果有一个象征性的对赌，参与者可以两边押注。在参与赌局的人中，有49注押Alphago赢，44注押李世乭赢，一人赌某方全赢或全输，另一人赌双方互有输赢。

值得一提的是，假如双方势均力敌，任何一方赢的概率是0.5，且各次对弈的结果相互独立，那在5轮对弈中，一方全赢或者全输的概率是 2*0.5^5 = 0.0625，而互有输赢的概率是0.9375。如果各轮对弈结果是独立的，那么一方赢输概率要达到6.725:1才能让全输全赢的概率上升到0.5。此外，如果各次输赢是关联的，即使双方势均力敌，一方全赢或者全输的概率也不会是0.0625。所谓关联是指，某次对弈的输赢概率不仅取决于双方的水平，还取决于前次对弈的结果。一个典型的例子是，在人类对弈中，前轮输棋可能会导致棋手情绪紧张，因而发挥更差。

如果对弈双方都是机器，且机器程序不根据前轮比赛结果进行调整，那可以假设各次对弈结果相互独立。现在一方为Alphago，另一方是人类棋手李世乭。假设Alphago的程序不会根据前轮对弈结果进行调试，那本轮对弈和前轮对弈结果的关联性将只会来自李世乭的情绪反应和策略调整。比如，李世乭输了第一轮后，情绪紧张可能导致更容易输掉第二轮，或者他调整策略提升了赢棋概率。总之，既有因素促使各轮对弈结果正相关，也有因素促使各轮对弈负相关。对弈结果正相关会提升一方全赢全输的概率，而负相关将会提升双方互有输赢的概率。

由于达到Alphago围棋水平的人工智能新近才出现，我们无法获得机器与人类之间这类比赛的、具有可比意义的输赢记录，因此也难以根据背景数据对Alphago和李世乭比赛的输赢几率做出合理估算。不过，谷歌作为一个商业公司，参与研发人工智能围棋程序应该会有自身的考量。从这个角度来思考或许有助于判断Alphago对李世乭比赛的战局。

从论文报道来看，Alphago的程序设计和对弈水平在不断提升。在决定让Alphago与李世乭进行比赛之前，Alphago与人类棋手应该进行过多次实战，谷歌对Alphago的水平应有一个大致判断。从公关角度来考虑，谷歌让Alphago挑战李世乭的最好时机是，Alphago水平接近但略低于李世乭，而且在可预见的将来能够超越李世乭。这样，Alphago输掉最初的比赛，将给公众留下巨大的悬念并能最大限度地吸引公众的关注。之后，进一步提升Alphago的棋力，在未来第二或第三次比赛中以各轮皆赢的成绩战胜人类顶级棋手，留给公众人工智能技术进步神速的印象，激发人们对人工智能的热情，并同时塑造出谷歌不遗余力地追求人类智慧极致的形象。