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

比如我们有了一个基本的估值函数：计算棋子的静态得分，将 10000 分，车 10 分，马和炮 5 分，相士 2 分，兵卒 1 分。然后我们不断下棋，发现有些局面从棋子看双方都一样，但是棋子的不同位置会导致最终胜负的差距很大。因此我们会更新我们的估值函数：比如兵卒过河要变成两分。棋子的行动力越大分越高，越靠近中间分越高，不同的棋子如果有保护或者攻击关系，我们会增加一些分数，另外一些特殊的局面，比如空头炮，三子归边会有很高的胜率，我们也会增加分数，从而出现棋子攻杀。

因此一个棋手的棋力除了计算能力（这个更多是天赋，当然也能通过训练提高），另外一个很重要的能力就是评估局面的能力，这个就更多的靠后天的训练。而一个游戏是否“有趣”/“好玩”，其实也跟评估函数有关。如果一个游戏很容易评估，那么基本不需要搜索，看一个回合就知道最终的结果了，就没有什么意思。最有“意思”的局面是“看”起来很差但“其实”很好的棋，或者看起来某个局面很平稳，但其实某方优势很明显，所谓的“妙手”是也。什么叫“看”起来很差？就是搜索很浅的层次评估或者不搜索直接评估得分很差（比如走窝心马或者被架空头炮），但是搜索很深之后发现这是当前局面下最好的走法，甚至是反败为胜的唯一招法。高手和低手的差别也在于此，对于那种很明显的好坏，大家都能看得出来；而有些局面，对于低手来说可能觉得局面双方还差不多，但是在高手看来胜负早已了然于胸了。

Alpha-Beta 剪枝

(from https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning)

假设 minimax 是 4 层的深度优先搜索，并且是如图的从左到右的顺序。那么有些子树是不用搜索，可以被剪枝掉的。

比如下面这棵子树：

第 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)

这是强化学习里最简单的一个问题，在很多地方都有应用，比如互联网广告(https://support.google.com/analytics/answer/2844870?hl=en)，游戏厅有一个 K 臂的老虎机，你可以选择其中的一个投币，每个手臂都是一个产生一个随机的奖励，它们的均值是固定的（也有 Nonstationary 的多臂老虎机，我这里只考虑 Stationary 的）。你有 N 次投币的机会，需要想办法获得最大的回报(reward)。

当然如果我们知道这个 K 个手臂的均值，那么我们每次都选择均值最大的那个投币，那么获得的期望回报应该是最大的。

可惜我们并不知道。那么我们可能上来每个都试一下，然后接下来一直选择最大的那个。不过这样可能也有问题，因为奖励是随机的，所以一次回报高不代表真实的均值回报高。当然你可以每个都试两次，估计一下奖励的均值。如果还不放心，你可以每个都试三次，或者更多。根据大数定律，试的次数越多，估计的就越准。最极端的一种做法就是每个手臂都投一样多的次数；另外一种极端就是碰运气，把所有的机会都放到一个手臂上。后一种如果运气好是最优的，但是很可能你抽到的是回报一般的甚至很差的手臂，期望的回报其实就是 K 个手臂的平均值。前一种呢？回报也是 K 个手臂的平均值！我们实际的做法可能是先每个手臂都试探几次，然后估计出比较好的手臂（甚至几个手臂），然后后面重点尝试这个（些）手臂，当然偶尔也要试试不那么好的手臂，太差的可能就不怎么去试了。但这个“度”怎么控制就是一个很复杂的问题了。这就是 exploit-explore 的困境(dilemma)。利用之前的经验，优先“好”的手臂，这就是 exploit；尝试目前看不那么“好”的手臂，挖掘“潜力股”，这就是 explore。

（编辑：PHP编程网 - 湛江站长网）

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