Board logo

标题: AlphaGo与人类的恩怨情仇（2）-世纪难题：曲折之路、曙光，蒙特卡洛 [打印本页]
作者: 天马行空    时间: 2018-1-22 08:56     标题: AlphaGo与人类的恩怨情仇（2）-世纪难题：曲折之路、曙光，蒙特卡洛

2017年6月4日   棋艺探索

[attach]103610[/attach]


本文首发于知乎专栏——不一样的围棋，作者，不会功夫的潘达

二、曲折之路

史前时代的围棋程序，在判断与搜寻这两方面都相当原始。

一个围棋程序，想要学会像人类一样判断形势，其实是很难的：模糊判断并没有一套固定的法则，自然也就难以算法化。经常在网络对弈的棋友们应该对弈城、野狐等平台上的“形势判断”功能非常熟悉。初学者乃至有一定棋力的棋手或许会依赖这一功能，然而中高段的棋友大概经常看着程序不靠谱的判断摇头叹气，或是一笑而过。

[attach]103611[/attach]


某对弈平台，“形式判断”功能在一局棋中盘阶段末期的判断。程序判定黑白两色的方块分别为双方的“地盘”。该判断算法，形式上是对人类棋手判断方式的拙劣模仿。其实此时双方差距甚小，程序却给出了黑棋盘面领先19目（扣除贴目后，黑棋仍领先12.5目）的判断。

判断虽难，至少我们还有现成的、能够算法化的流程可用。搜寻呢？其实人类棋手从不用“搜寻”二字，而是用“棋感”、“大局观”等抽象的概念。顾名思义，棋感、大局观，非“机器”所能掌握。不仅如此，对于上世纪的围棋程序，棋感、大局观都是奢侈品——它们甚至都不会一些基本的围棋技巧。程序“手谈”的作者陈志行曾说，他那个年代的程序，连小飞被穿断的棋型都不能应付。

[attach]103612[/attach]


如图，黑方△两子呈“日”字排列，围棋术语称“小飞”。当白方同时占据1位和2位时，黑方△两子的联系就会被隔断，使得形势恶化。为此，当白方走在1位时，黑方通常应该在2位应一招，防止被穿断。陈志行教会了“手谈”这一招，而其它程序不会，于是“手谈”在九十年代大杀四方。然而，陈志行终其一生，也没能让“手谈”突破自己的“九子关”。陈志行本人勉强算个业余高手，而被陈志行让九子而不能获胜的“手谈”，实力可想而知。

模仿人类的智慧困难重重，机器短期内无法在围棋上打败人类也就成为了当年的共识。1997年，一位电脑围棋研究者，John Tromp，曾与另一位研究者Darren Cook立下赌约。赌约的内容是，在2011年以前，能否有围棋程序分先击败John Tromp. John Tromp, 一位实力约为业余1级的爱好者，自信满满地为自己押下1000美元的赌注。就在同一年，国际象棋世界冠军卡斯帕罗夫被超级计算机“深蓝”击败。若不是MCTS（蒙特卡洛树搜索）算法的应用和改进，这本该是一场毫无悬念的赌局。

三、曙光，蒙特卡洛

[attach]103613[/attach]


MCTS算法图示，引自DeepMind发表在Nature上的论文。图中的四个步骤分别为a.选择，b.扩展, c.评估, d.反向传播。

早在1992年，就有围棋程序曾采用MCTS，但并没有起到显著效果。这也不难理解。单纯的随机模拟，对于围棋来说，是不可取的：一方面，一盘围棋的平均长度达200手，计算成本甚高；另一方面，纯随机模拟常常做出一些简单的误判。有个很邪恶的围棋术语，“一本道”。这个术语说的是，一步棋落下之后，接下来的变化只有唯一可能的分支，其它的分支都可以简单判定为不可行。最简单的例子，就是征子。追杀一方虽然需要十几个回合以后才能全歼对手，但技术上没有任何难度，即使初学者一般也不会出错。然而，一旦出错，全局形势立马是一百八十度的转弯。可想而知，纯随机模拟的程序多半还以为被追杀一方胜券在握，因为在绝大多数的模拟结果里，追杀一方早晚要犯一个错误。这样一来，模拟得到的胜率就不靠谱了。

[attach]103614[/attach]


征子。黑棋在过程中一步都不能错，方能全歼白棋，否则就是万劫不复。

MCTS初显神通，还是在2006年，它的一个改进版本，UCT被发明之后。UCT对MCTS的第一步，“选择”（参见上图），做出优化。优化的结果是，程序选择优先模拟那些已知更好的“下一步棋”，但也保留模拟尚未探索过的“下一步棋”的可能性。这在一定程度上治好了围棋程序的“选择困难症”。理论上来说，采用UCT算法的程序，只要给它足够长的时间，几乎一定能找到最优的那一步。

至于实践效果，我们说回John Tromp的赌局。2006-2010年间，采用UCT算法的MoGo, ManyFaces, CrazyStone, Zen等程序在两年内越过多道关卡，从k级水平一路攀升到业余有段水平。不过，John亦非坐以待毙。十五年过去，John从当年的业余1级长棋到业余2段，并且接近业余3段的水平。当年看上去几乎必然是一面倒的赌局，到了最后期限来临之时，居然变成了棋逢对手的决斗。2010年末，John以4-0横扫程序Many Faces of Go, 赢得1000美元的赌注。一年多以后，John与程序Zen再战，结果以1-3败北。对于John来说幸运的是，这第二次与程序的决斗，他根本就没有下注。

[attach]103615[/attach]


John Tromp (黑) – Zen (白) 片段。执白的Zen最终赢得本局，将比分改写为2-1.

同年，Zen在一盘受让四子的对局中战胜了世界冠军武宫正树九段。似乎计算机围棋超越人类的那个节点就在眼前。然而，毫无征兆地，围棋程序们陷入了瓶颈。MCTS的潜力似乎已被耗尽，而其它的研究成果，不过是细节上的涂涂改改，于大局无甚助益。2015年11月，连笑七段在让四子、五子的对局中战胜当年的冠军程序Dol Baram （亚军正是Zen）, 直到让六子时才输给程序。赛后，连笑称，计算机程序想战胜职业棋手，还有很长的路要走。

2015年11月，除了一位提前知道真相、还挣扎在输棋的痛苦中的职业棋手，所有人还在梦中。

本文首发于知乎专栏——不一样的围棋，专栏地址——https://zhuanlan.zhihu.com/godifferent



欢迎光临 亦苏围棋社区 (http://ysgo.91em.com/bbs/) Powered by Discuz! 7.2