转帖：从第四盘棋看狗狗的弱点
发信人: rdfirdfi (rdfi), 信区: Go
标 题: 从第四盘棋看狗狗的弱点
发信站: BBS 未名空间站 (Sun Mar 13 10:32:32 2016, 美东)
本人曾经有一些编写棋类程序的经验，也看了nature的那篇文章。
首先从那篇文章来看，狗狗的算法是确定的。虽然他用了"神经网络“这么个看起来很高大上的名词，在神经网络完成训练后，每次运行的结果是可预测、一定的。狗狗也不存在什么情感。它就像一个计算器，或者电子回路，总会给出一个确定答案。
狗狗比其他软件的提高主要是用大数据训练出了高超的神经网络。狗狗声称只靠神经网络，不进行深度计算，已经可以达到业余五段+的水平。
狗狗用了两种搜索方法。一种是经常被提及的”蒙特卡洛树形搜索“(Monte Carlo Tree Search, MCTS)，一种没有被提到名字，但应该是min-max搜索法。前一种方法用于围棋是在十年前开始的，使得软件的水平普遍从初学者水平提高到了业余段位。后一种方法可以用于所有双人回合制零和游戏。这两种方法都有一些根本的、难以解决的弱点。
蒙特卡洛树形搜索本质上就是摆棋谱看形势。比如在柯洁或者雷蒙讲解的时候，他们会经常摆出一些变化来分析形势。通过这种分析和讲解，有时候讲棋的人能够成功预测双方的实际落子。狗狗的蒙特卡洛搜索就是靠一个弱一点（业余段位）、但是很快（每步棋2微妙）的神经网络来判断哪些着法很可能、可能性多大，然后（加权）随机摆谱。与讲棋不同的是，每次这种谱都要摆到最后、能直接判断输赢的局面。然后狗狗统计大量对局（比如1000盘）的结果，得出一个”胜率“作为判断当前局势的评价值。这种方法在很多情况下是行之有效的，因为很多棋业余棋手就已经能下出来。再加上每次重新摆谱的时候，可以根据后面的结果适当调整某一策略的概率（权重）。这样对胜率的估算，多数情况下是适当的，或者至少是可以和别的局面相比较的。
大家可能一般认为软件的局部算力强，而没有全局观。然而蒙特卡洛法的强项却恰恰是”全局观“。因为这种方法并不会把搜索局限在某个局部，而会给出一个整体的胜率。这可能是狗狗总是走出一些出人意料的脱先的原因。
然而，如果出现了很复杂的局面（比如第四盘），很多要点可能是业余选手发现不了的。这样即使你算一千盘、一万盘，有些很要紧的点也会被忽略。或者出现了一个需要很多步才能杀的大龙。虽然每一步的随机落子都很有可能在杀大龙，但是/所有/落子都在杀大龙的概率会大大降低（比如90% 乘 5次方 就只有60%了）。对于这种局面的胜率判断也会扭曲。这也可能是狗狗不喜欢打劫的原因。
在第4局中，狗狗就冒似出现了这样的错误。而当它发现错误时，为时已晚。
另外一个狗狗的搜索方法应该是min-max法。这个方法说起来很简单——自己走一步，然后穷举（或者带有概率加权）对方的所有应手，然后找到对方最好的应手的分数（胜率）来作为对自己这一步的判断。这是一种很朴素的、人类棋手也会用的思维方式。这种搜索可以一直迭代下去，搜索很多层，只要时间允许。
然而这种搜索方法的复杂度随着搜索深度的增长呈指数增长。比如每一步可能有6个合理的应手，思考6层就会有46656种局面要判断（要知道每个局面判断可能需要1000个MCTS）。虽然存在一些剪枝方案可以是搜索层数增加至多一倍，这种搜索仍然是很消耗计算资源的、有限的。由于层数总是有限的，所有的搜索引擎都面临着一个叫做”地平线效应“(Horizon Effect)的恼人问题。
https://en.wikipedia.org/wiki/Horizon_effect
比如一个国象程序，搜索深度是6层，可以计算所有6手以内的变化。
然后电脑有一个皇后被吃死了——怎么也挽救不了。但是有一个手段，比如弃一个象，可以让对手在6手以内吃不了这个皇后，电脑可能就会走这样的“昏招”。结果是电脑不仅仅丢了个后，还白白丢了个象。
这种白白弃子延缓对方攻击的着法在人类看来是不可思议的，但是对于棋类软件来说确是正确的逻辑——它避免了在自己的搜索空间内出现坏局面。这个问题是让所有棋软设计者头疼的毛病，但是却很难解决。人类可以记忆在某个局部的变化，并且知道在别的地方交换了几手棋不会改变这个局部变化。电脑却无法判断别的地方的交换是不是真的没有影响——所以它必须重新算一次。而在别的地方的交换已经损耗了搜索层数，这样电脑可能就无法解决这个局部了。
alphago可能就是遇到了类似的“地平线效应”。当时局面很复杂，走一些损的先手棋可能会延迟坏局面在搜索树中的出现。于是就有了长自己已经死了的子的走法。雷蒙德也提到了棋软在局面落后的时候经常会走各种先手棋。这大概都是出于“地平线效应”。
“地平线效应”可不是Aja Huang一朝一夕能解决的。他今天可能发现了这个问题，但是却无可奈何。
所以对于人类棋手来说，可能需要好好利用软件搜索的弱点，多保留变化，把软件引到地平线效应的陷阱里去。顶尖棋手可以有意制造一些不符合业余棋手直觉的盘面局势，扭曲软件的胜率计算。
发信人: afool100 (a_fool), 信区: Go
标 题: Re: 从第四盘棋看狗狗的弱点
发信站: BBS 未名空间站 (Sun Mar 13 14:11:18 2016, 美东)
+1
AlphaGo 剪枝用的不是简单的 minmax。而是以policy network为基准做rollout，用value network和MCTS做剪枝。
Policy network 是用大量旧棋谱在深度神经网络上训练出来的，基本原理还是一个黑盒子。很难想像每一步都不漏掉任何最优选择。当然人类高手的棋离最优选择恐怕还有很大距离。 但认为AlphaGo已是无懈可击完全没有道理（李哲前两天的文章看了都觉得恶心）。
Zen(天顶)的作者之一 Hideki Kato 前两天（AlphaoGo:Lee 2:0后)还说，认为AlphaGo已经解了围棋还太早；因为MCTS从根本上尚无法解决复杂的对杀和双劫的问题。显然Hideki Kato 认为击败AlphaGo的办法是选择复杂的对杀。
发信人: afool100 (a_fool), 信区: Go
标 题: Re: 从第四盘棋看狗狗的弱点
发信站: BBS 未名空间站 (Sun Mar 13 14:38:55 2016, 美东)
AlphaGo 的问题应该不是 Horizon Effect，而是漏算了或算不清楚。
MCTS 是把棋一路走到终盘。但不论是rollout、还是MCTS，都可能漏掉最佳对应。
发信人: rdfirdfi (rdfi), 信区: Go
标 题: Re: 从第四盘棋看狗狗的弱点
发信站: BBS 未名空间站 (Sun Mar 13 14:54:34 2016, 美东)
我没真正实践过MCTS。MCTS没有horizon effect吗？因为alphago也用了value network和rollout来平均算一个叶结点的值。我觉得这是不是代表这个搜索有一定的min-max的性质呢？
发信人: aptget (apt), 信区: Go
标 题: Re: 从第四盘棋看狗狗的弱点
发信站: BBS 未名空间站 (Sun Mar 13 15:20:05 2016, 美东)
这段是文章里的关键
“In contrast, AlphaGo’s use of value functions is based on truncated Monte-Carlo search algorithms 8, 9, which terminate rollouts before the end of the game and use a value function in place of the terminal reward. AlphaGo’s position evaluation mixes full rollouts with truncated rollouts, resembling in some respects the well-known temporal-difference learning algorithm TD(). AlphaGo also differs from prior work by using slower but more powerful representations of the policy and value function; evaluating deep neural networks is several orders of magnitudes slower
than linear representations and must therefore occur asynchronously.”
它当然也有horizon effect，但是是软的，因为先用MC走到一个深度，接着用value network筛选局面，再由policy network把每一局下到底。所以value network的筛选就是一个瓶颈，会落掉没有训练过的高价值走法（高手终局）；前面MC的采样也是一个瓶颈，会（概率上）落掉不常见的应召路数。
发信人: rdfirdfi (rdfi), 信区: Go
标 题: Re: 从第四盘棋看狗狗的弱点
发信站: BBS 未名空间站 (Sun Mar 13 15:22:23 2016, 美东)
看那篇nature文章好像是考虑了：整体棋形、落子时间点、气、自己和对方可能吃的一块棋的大小、紧气或长后的气数、征子是否有利、着法合法性等等。另外还有点眼的围棋知识。
通篇没有提到劫的概念。
【 在 owl68 (owl) 的大作中提到: 】
: 好文！我比较好奇的是还没见过任何探讨狗训练用的feature的文章。
: 狗用了１２个feature训练初始policy网，训练fast rollout和tree policy的分别是６个和９个。
: 这些东西动一动，恐怕影响巨大。狗家好像没提这些特征是怎么确定的，中间试过哪些
: ，还有什么可选。我的感觉是偏局部。这方面其实是现在围棋高手最可能对狗的改进提
: 供帮助的。
发信人: afool100 (a_fool), 信区: Go
标 题: Re: 从第四盘棋看狗狗的弱点
发信站: BBS 未名空间站 (Sun Mar 13 15:37:34 2016, 美东)
我对 Horizon Effect 的理解是：由搜索深度限制而看不到更远的事件。
AlphoGo 算法：用 Policy Network 设分枝、建一搜索树，每一枝结（node）由 Value Network 设一价值，从每一树叶（leaf）起多次用随机下法（Monte Carlo Simulation）把棋走到终盘，根据结果输赢反馈修改所有父母枝结的价值；最后价值底的分枝被剪枝。基本原理与 minmax/alpha-bata 相同。
Deepmind 团队没有公开搜索树的深度，显然这由搜索时间、速度决定。但因为MCTS把棋走到终盘，应该没有一个绝对的地平线(Horizon):地平线以外的招法完全看不到。
【 在 rdfirdfi (rdfi) 的大作中提到: 】
: 我没真正实践过MCTS。MCTS没有horizon effect吗？因为alphago也用了value network
: 和rollout来平均算一个叶结点的值。我觉得这是不是代表这个搜索有一定的min-max的
: 性质呢？
发信人: rdfirdfi (rdfi), 信区: Go
标 题: Re: 从第四盘棋看狗狗的弱点
发信站: BBS 未名空间站 (Sun Mar 13 15:54:04 2016, 美东)
同意你的理解。
也许对于MCTS，horizon effect是由搜索深度限制而不能 精确地 看到更远的事件。
回到alphago走先手自杀棋的问题上来，可能是这招先手自杀棋拖延了“精确”看到胜率下降的搜索。
关于搜索深度，好像最大设定是40——nature文章的附表expansion threshold. 对Fan Hui的棋文章给了一个26手的主要变化图。
以此估计alphago的深度应该是20-30手。
发信人: afool100 (a_fool), 信区: Go
标 题: Re: 从第四盘棋看狗狗的弱点
发信站: BBS 未名空间站 (Sun Mar 13 16:01:37 2016, 美东)
AlphaGo 按赢棋几率高的招法走。走正手赢棋完全无望的情况下，正手就不能走了。
而 Monte Carlo Simulation 认为任何随机招法的出现几率相同。人看来是自杀，机器可以认为是延气；如不跟着应、对方就少了一气被杀；虽然可能性不大，AlphaGo 也许认为要试一下。
【 在 rdfirdfi (rdfi) 的大作中提到: 】
: 受教了：）
: 那怎么解释alphago的先手自杀的那一手棋呢？这步棋很像是horizon effect——自杀
: 先手拖延搜索深度。
: 也许Aja Huang也在纳闷吧。。。
标 题: 从第四盘棋看狗狗的弱点
发信站: BBS 未名空间站 (Sun Mar 13 10:32:32 2016, 美东)
本人曾经有一些编写棋类程序的经验，也看了nature的那篇文章。
首先从那篇文章来看，狗狗的算法是确定的。虽然他用了"神经网络“这么个看起来很高大上的名词，在神经网络完成训练后，每次运行的结果是可预测、一定的。狗狗也不存在什么情感。它就像一个计算器，或者电子回路，总会给出一个确定答案。
狗狗比其他软件的提高主要是用大数据训练出了高超的神经网络。狗狗声称只靠神经网络，不进行深度计算，已经可以达到业余五段+的水平。
狗狗用了两种搜索方法。一种是经常被提及的”蒙特卡洛树形搜索“(Monte Carlo Tree Search, MCTS)，一种没有被提到名字，但应该是min-max搜索法。前一种方法用于围棋是在十年前开始的，使得软件的水平普遍从初学者水平提高到了业余段位。后一种方法可以用于所有双人回合制零和游戏。这两种方法都有一些根本的、难以解决的弱点。
蒙特卡洛树形搜索本质上就是摆棋谱看形势。比如在柯洁或者雷蒙讲解的时候，他们会经常摆出一些变化来分析形势。通过这种分析和讲解，有时候讲棋的人能够成功预测双方的实际落子。狗狗的蒙特卡洛搜索就是靠一个弱一点（业余段位）、但是很快（每步棋2微妙）的神经网络来判断哪些着法很可能、可能性多大，然后（加权）随机摆谱。与讲棋不同的是，每次这种谱都要摆到最后、能直接判断输赢的局面。然后狗狗统计大量对局（比如1000盘）的结果，得出一个”胜率“作为判断当前局势的评价值。这种方法在很多情况下是行之有效的，因为很多棋业余棋手就已经能下出来。再加上每次重新摆谱的时候，可以根据后面的结果适当调整某一策略的概率（权重）。这样对胜率的估算，多数情况下是适当的，或者至少是可以和别的局面相比较的。
大家可能一般认为软件的局部算力强，而没有全局观。然而蒙特卡洛法的强项却恰恰是”全局观“。因为这种方法并不会把搜索局限在某个局部，而会给出一个整体的胜率。这可能是狗狗总是走出一些出人意料的脱先的原因。
然而，如果出现了很复杂的局面（比如第四盘），很多要点可能是业余选手发现不了的。这样即使你算一千盘、一万盘，有些很要紧的点也会被忽略。或者出现了一个需要很多步才能杀的大龙。虽然每一步的随机落子都很有可能在杀大龙，但是/所有/落子都在杀大龙的概率会大大降低（比如90% 乘 5次方 就只有60%了）。对于这种局面的胜率判断也会扭曲。这也可能是狗狗不喜欢打劫的原因。
在第4局中，狗狗就冒似出现了这样的错误。而当它发现错误时，为时已晚。
另外一个狗狗的搜索方法应该是min-max法。这个方法说起来很简单——自己走一步，然后穷举（或者带有概率加权）对方的所有应手，然后找到对方最好的应手的分数（胜率）来作为对自己这一步的判断。这是一种很朴素的、人类棋手也会用的思维方式。这种搜索可以一直迭代下去，搜索很多层，只要时间允许。
然而这种搜索方法的复杂度随着搜索深度的增长呈指数增长。比如每一步可能有6个合理的应手，思考6层就会有46656种局面要判断（要知道每个局面判断可能需要1000个MCTS）。虽然存在一些剪枝方案可以是搜索层数增加至多一倍，这种搜索仍然是很消耗计算资源的、有限的。由于层数总是有限的，所有的搜索引擎都面临着一个叫做”地平线效应“(Horizon Effect)的恼人问题。
https://en.wikipedia.org/wiki/Horizon_effect
比如一个国象程序，搜索深度是6层，可以计算所有6手以内的变化。
然后电脑有一个皇后被吃死了——怎么也挽救不了。但是有一个手段，比如弃一个象，可以让对手在6手以内吃不了这个皇后，电脑可能就会走这样的“昏招”。结果是电脑不仅仅丢了个后，还白白丢了个象。
这种白白弃子延缓对方攻击的着法在人类看来是不可思议的，但是对于棋类软件来说确是正确的逻辑——它避免了在自己的搜索空间内出现坏局面。这个问题是让所有棋软设计者头疼的毛病，但是却很难解决。人类可以记忆在某个局部的变化，并且知道在别的地方交换了几手棋不会改变这个局部变化。电脑却无法判断别的地方的交换是不是真的没有影响——所以它必须重新算一次。而在别的地方的交换已经损耗了搜索层数，这样电脑可能就无法解决这个局部了。
alphago可能就是遇到了类似的“地平线效应”。当时局面很复杂，走一些损的先手棋可能会延迟坏局面在搜索树中的出现。于是就有了长自己已经死了的子的走法。雷蒙德也提到了棋软在局面落后的时候经常会走各种先手棋。这大概都是出于“地平线效应”。
“地平线效应”可不是Aja Huang一朝一夕能解决的。他今天可能发现了这个问题，但是却无可奈何。
所以对于人类棋手来说，可能需要好好利用软件搜索的弱点，多保留变化，把软件引到地平线效应的陷阱里去。顶尖棋手可以有意制造一些不符合业余棋手直觉的盘面局势，扭曲软件的胜率计算。
发信人: afool100 (a_fool), 信区: Go
标 题: Re: 从第四盘棋看狗狗的弱点
发信站: BBS 未名空间站 (Sun Mar 13 14:11:18 2016, 美东)
+1
AlphaGo 剪枝用的不是简单的 minmax。而是以policy network为基准做rollout，用value network和MCTS做剪枝。
Policy network 是用大量旧棋谱在深度神经网络上训练出来的，基本原理还是一个黑盒子。很难想像每一步都不漏掉任何最优选择。当然人类高手的棋离最优选择恐怕还有很大距离。 但认为AlphaGo已是无懈可击完全没有道理（李哲前两天的文章看了都觉得恶心）。
Zen(天顶)的作者之一 Hideki Kato 前两天（AlphaoGo:Lee 2:0后)还说，认为AlphaGo已经解了围棋还太早；因为MCTS从根本上尚无法解决复杂的对杀和双劫的问题。显然Hideki Kato 认为击败AlphaGo的办法是选择复杂的对杀。
发信人: afool100 (a_fool), 信区: Go
标 题: Re: 从第四盘棋看狗狗的弱点
发信站: BBS 未名空间站 (Sun Mar 13 14:38:55 2016, 美东)
AlphaGo 的问题应该不是 Horizon Effect，而是漏算了或算不清楚。
MCTS 是把棋一路走到终盘。但不论是rollout、还是MCTS，都可能漏掉最佳对应。
发信人: rdfirdfi (rdfi), 信区: Go
标 题: Re: 从第四盘棋看狗狗的弱点
发信站: BBS 未名空间站 (Sun Mar 13 14:54:34 2016, 美东)
我没真正实践过MCTS。MCTS没有horizon effect吗？因为alphago也用了value network和rollout来平均算一个叶结点的值。我觉得这是不是代表这个搜索有一定的min-max的性质呢？
发信人: aptget (apt), 信区: Go
标 题: Re: 从第四盘棋看狗狗的弱点
发信站: BBS 未名空间站 (Sun Mar 13 15:20:05 2016, 美东)
这段是文章里的关键
“In contrast, AlphaGo’s use of value functions is based on truncated Monte-Carlo search algorithms 8, 9, which terminate rollouts before the end of the game and use a value function in place of the terminal reward. AlphaGo’s position evaluation mixes full rollouts with truncated rollouts, resembling in some respects the well-known temporal-difference learning algorithm TD(). AlphaGo also differs from prior work by using slower but more powerful representations of the policy and value function; evaluating deep neural networks is several orders of magnitudes slower
than linear representations and must therefore occur asynchronously.”
它当然也有horizon effect，但是是软的，因为先用MC走到一个深度，接着用value network筛选局面，再由policy network把每一局下到底。所以value network的筛选就是一个瓶颈，会落掉没有训练过的高价值走法（高手终局）；前面MC的采样也是一个瓶颈，会（概率上）落掉不常见的应召路数。
发信人: rdfirdfi (rdfi), 信区: Go
标 题: Re: 从第四盘棋看狗狗的弱点
发信站: BBS 未名空间站 (Sun Mar 13 15:22:23 2016, 美东)
看那篇nature文章好像是考虑了：整体棋形、落子时间点、气、自己和对方可能吃的一块棋的大小、紧气或长后的气数、征子是否有利、着法合法性等等。另外还有点眼的围棋知识。
通篇没有提到劫的概念。
【 在 owl68 (owl) 的大作中提到: 】
: 好文！我比较好奇的是还没见过任何探讨狗训练用的feature的文章。
: 狗用了１２个feature训练初始policy网，训练fast rollout和tree policy的分别是６个和９个。
: 这些东西动一动，恐怕影响巨大。狗家好像没提这些特征是怎么确定的，中间试过哪些
: ，还有什么可选。我的感觉是偏局部。这方面其实是现在围棋高手最可能对狗的改进提
: 供帮助的。
发信人: afool100 (a_fool), 信区: Go
标 题: Re: 从第四盘棋看狗狗的弱点
发信站: BBS 未名空间站 (Sun Mar 13 15:37:34 2016, 美东)
我对 Horizon Effect 的理解是：由搜索深度限制而看不到更远的事件。
AlphoGo 算法：用 Policy Network 设分枝、建一搜索树，每一枝结（node）由 Value Network 设一价值，从每一树叶（leaf）起多次用随机下法（Monte Carlo Simulation）把棋走到终盘，根据结果输赢反馈修改所有父母枝结的价值；最后价值底的分枝被剪枝。基本原理与 minmax/alpha-bata 相同。
Deepmind 团队没有公开搜索树的深度，显然这由搜索时间、速度决定。但因为MCTS把棋走到终盘，应该没有一个绝对的地平线(Horizon):地平线以外的招法完全看不到。
【 在 rdfirdfi (rdfi) 的大作中提到: 】
: 我没真正实践过MCTS。MCTS没有horizon effect吗？因为alphago也用了value network
: 和rollout来平均算一个叶结点的值。我觉得这是不是代表这个搜索有一定的min-max的
: 性质呢？
发信人: rdfirdfi (rdfi), 信区: Go
标 题: Re: 从第四盘棋看狗狗的弱点
发信站: BBS 未名空间站 (Sun Mar 13 15:54:04 2016, 美东)
同意你的理解。
也许对于MCTS，horizon effect是由搜索深度限制而不能 精确地 看到更远的事件。
回到alphago走先手自杀棋的问题上来，可能是这招先手自杀棋拖延了“精确”看到胜率下降的搜索。
关于搜索深度，好像最大设定是40——nature文章的附表expansion threshold. 对Fan Hui的棋文章给了一个26手的主要变化图。
以此估计alphago的深度应该是20-30手。
发信人: afool100 (a_fool), 信区: Go
标 题: Re: 从第四盘棋看狗狗的弱点
发信站: BBS 未名空间站 (Sun Mar 13 16:01:37 2016, 美东)
AlphaGo 按赢棋几率高的招法走。走正手赢棋完全无望的情况下，正手就不能走了。
而 Monte Carlo Simulation 认为任何随机招法的出现几率相同。人看来是自杀，机器可以认为是延气；如不跟着应、对方就少了一气被杀；虽然可能性不大，AlphaGo 也许认为要试一下。
【 在 rdfirdfi (rdfi) 的大作中提到: 】
: 受教了：）
: 那怎么解释alphago的先手自杀的那一手棋呢？这步棋很像是horizon effect——自杀
: 先手拖延搜索深度。
: 也许Aja Huang也在纳闷吧。。。