AlphaGo 的棋局，与人工智能有关，与人生无关

第 0 层是 MAX 操作，第一个孩子返回了 5，现在我们正准备搜索第二个孩子（4 的那个，当然现在还不知道）。我们知道它的只至少是 5 了，>=5。

它是一个 MIN 操作，首先搜索到 7，所以它的取值 <=7，接着搜索到 4，所以它的取值 <=4，这个时候就可以停止了，为什么？ 因为第 0 层的节点的值已经 >=5了，而第 1 层的右边那个节点已经 <=4了，所以不管它的第三个孩子得分多少，第 0 层都不会选择了，所以可以把它剪枝掉了。max（5, （<=4）)=5。 搜索完两个孩子之后，第 0 层的值已经 >=6了，然后搜索第 1 层（5）的那个节点，它的第一个孩子已经返回 5 了，所以它的值必然<=5了，所以它的第二个孩子（8）也没有必要搜索了。因为 max（6, （<=5）)=6。 类似的，对手在 MIN 的时候也可以剪枝，min（3, （>=4）)=3。

当然上面是非常形式化的描述，其实在实际的下棋过程中我们可能自觉不自觉的使用了 alpha-beta 剪枝。

比如，我们有这样的推理：我可以走车吃对手一个兵而且对手吃不了我任何子(得分+1)；也可以走马吃对手的卒，走马后对手有很多走法，其中一个走法是吃掉我的马而且我还吃不了他任何棋子（得分-4），那么这个时候我就不会走马了，因为不管其余的走法怎么样（也许对手还有更好的走法，比如吃我一个车得 10 分；当然也有更差的走法不吃我的子让我得+1 分，但他不会这么走），这个走法下我“至少”损失一个马了，那么我现在有一个得分+1 的走法，我就不要考虑对手其它的走法了，直接剪枝掉了。用形式化的语言描述 max（1, （<=-5））=1。

alpha-beta 能否剪枝非常依赖于搜索的顺序，如果把最优的走法先搜索，那么能得到最大程度的剪枝。所以这个树的展开顺序非常重要。一般会使用很多启发式规则来排序。比如吃对方的棋子很可能是比较好的走法，而没事走动老将不是什么好的走法。

要下好象棋，计算能力和评估局面的能力缺一不可。因为人的计算能力有限（计算机也是一样），所以搜索到一定层次之后需要停下来评估局面。当然人的搜索不是固定的，而是和评估函数一起工作的，对于“简单”的局面（比如明显很差或者很好的），就不要搜索很深，而对于“复杂”的局面，则会尽可能深的搜索下去。所以好的评估局面的能力对于下象棋很重要，这个容易理解。

那么计算能力（搜索深度）的重要性呢？这个似乎更加显而易见，棋经云：“多算胜，少算不胜，况乎无算。”

不过仔细思考一下，有似乎没有那么明显。为什么搜索深比搜索浅好呢？除非你能搜索到游戏结束，否则都得提前结束使用估值函数。搜索深比搜索浅好的一个隐含假设就是越深的局面越容易评估。对于象棋来说这是很明显的，因为象棋的特定是越下棋子越少，局面也就更容易评估。而围棋就不一样，棋子越到后来越多，局面的评估难度并没有明显的下降（甚至可能上升，我个人围棋水平也就是会简单规则的程度，所以很可能不是这样）。当然围棋的评估局面比象棋也复杂很多（至少我是这么觉得的）。

当然一个人的计算能力是有限的，所以“离线”的计算对于职业棋手也很重要。很多棋手对于某些布局有非常细致的研究，他们“离线”研究了各种可能的变化，因此你如果走到了他熟悉的布局，你基本上很难战胜他。因此残局库和开局库的研究和记忆是一个职业棋手努力的方向。

要设计一个好的象棋程序也是一样，首先是计算（搜索）能力，这个对于相对于人类来说是它的强项。因此更关键的就是评估局面的函数。由于象棋的局面特征还是比较明显的，静态的棋子分值估计能解决 80%的局面，再加上一下位置特征（比如棋子在不同的位置有不同的加减分），棋子的行动力，棋子之间的保护关系等等，就能解决大部分的局面。那些非常复杂的局面可以通过更深的搜索层次来解决。另外像开局库，残局库这些对于计算机都不是问题，它的记忆能力远超人类。

有了这些重要的特征，可以人工设计估值函数，也可以用机器学习的方法学习更加准确的估值函数。所以解决象棋应该是“比较”容易的（相对于围棋）。所以现在国际象棋人类的水平和计算机差距越来越大，人类几乎没有获胜的可能了。

围棋为什么不能用类似的方法

国际象棋解决之后，大家把注意力放到了围棋上。用类似的方法效果很差，比如 GnuGo 的棋力大概在 13 级(kyu)。

13 级什么概念呢？从下图中可以看到是非常差的水平。

(from https://en.wikipedia.org/wiki/Go_ranks_and_ratings#Kyu_and_dan_ranks)

为什么对于象棋非常有效的方法用在围棋上就不行呢？我们需要分析两种棋的差别。不过由于我本人下棋水平一般，围棋更是刚入门的水平，所以更多的是从程序员的角度来分析两种棋的差异。

分支因子和深度

国际象棋的分支因子是 35，而围棋是 250（https://en.wikipedia.org/wiki/Branching_factor）。这个数值只是估计，但可以看出大致的差别。从这个角度来说围棋要比国际象棋复杂。但如果只是这一个因素的差别不可能导致最好的国际象棋程序超过人类而围棋只有 13k 的水平。

估值函数

前面我们分析的是中国象棋，国际象棋和中国象棋类似，所以它的估值函数是相对容易和准确的。而围棋就比较困难，数棋子的个数明显是没有任何用处的。

“围棋难的地方在于它的估值函数非常不平滑，差一个子盘面就可能天翻地覆，同时状态空间大，也没有全局的结构。这两点加起来，迫使目前计算机只能用穷举法并且因此进展缓慢。但人能下得好，能在几百个选择中知道哪几个位置值得考虑，说明它的估值函数是有规律的。这些规律远远不是几条简单公式所能概括，但所需的信息量还是要比状态空间本身的数目要少得多（得多）。”

（http://www.almosthuman.cn/2016/01/12/ebfzg/）

后面我讨论用深度学习(CNN)来评估局面时会分析这两个因素哪个更重要，至少从个人感觉来看，第二个更加重要一些。

围棋和象棋的差别还是挺大的，比如 MCTS 搜索，在围棋中效果不错，但是用到象棋里就没有什么效果。

MCTS 多臂老虎机(Multi-Arm Bandits) 和 UCB(Upper Confidence Bounds)

（编辑：应用网_丽江站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!