本文摘自下面链接的部分内容。
原文入口：http://blog.sina.com.cn/s/blog_73040b820102wrme.html

深蓝采用的是前面提到的约翰·麦卡锡提出的α-β剪枝算法。该算法的基本思想是，利用已经搜索过的状态对搜索进行剪枝，以提高搜索的效率。算法首先按照一定原则模拟双方一步步下棋，直到向前看几步为止，然后对棋局进行打分（分数越大表明对我方越有利，反之表明对对方有利），并将该分数向上传递。当搜索其他可能的走法时，会利用已有的分数，减掉对我方不利对对方有利的走法，尽可能最大化我方所得分数，按照我方所能得到的最大分数选择走步。从以上描述可以看出，对棋局如何打分是α-β剪枝算法中非常关键的内容。深蓝采用规则的方法对棋局打分，大概的思路就是对不同的棋子按照重要程度给予不同的分数，比如车分数高一点，马比车低一点等。同时还要考虑棋子的位置赋予不同的权重，比如马在中间位置比在边上的权重就大，还要考虑棋子之间的联系，比如是否有保护、被捕捉等等。当然实际系统中比这要复杂的多，但大概思想差不多，这里只是举例。这样打分看起来很粗糙，但是如果搜索的深度比较深的话，尤其是进入了残局，还是非常准确的，因为对于国际象棋来说，当进入残局后，棋子的多少可能就决定了胜负。这就如同用牛顿法数值计算一个曲线下的面积，用多个矩形近似曲线肯定有不小的误差，但是如果矩形的宽度足够小时，矩形的面积和就可以逼近曲线下的面积了，道理是一样的。
人工智能的里程碑：从深蓝到AlphaGo

α-β剪枝算法示意图
根据上面的介绍，α-β剪枝算法也只是搜索到一定的深度就停止，并不是一搜到底，那么是不是可以不用α-β剪枝算法，而是生成出小于该深度的所有状态，也可以达到同样的效果呢？换句话说，α-β剪枝算法对于提高搜索效率究竟有多大的提高呢？笔者曾经就这个问题请教过深蓝的主要参与者许峰雄博士，他回答说：在深蓝计算机上，如果不采用α-β剪枝算法，要达到和深蓝一样的下棋水平的话，每步棋需要搜索17年的时间。由此可见，α-β剪枝算法是非常有效的。在深蓝之后，中国象棋、日本将棋等，采用类似的方法先后均达到了人类顶级水平。2006年8月9日，为了纪念人工智能50周年，在浪潮杯中国象棋人机大战中，“浪潮天梭”系统击败了以柳大华等5位中国象棋大师组成的大师队，第二天再战许银川国际大师，双方战平。
人工智能的里程碑：从深蓝到AlphaGo

长时间以来，计算机在人机大战中一马平川，攻克一个又一个堡垒，唯独剩下了一个围棋，成为一个未开垦的处女地。为什么在其它棋类中屡建奇功的α-β剪枝算法对围棋不灵了呢？很多人认为是围棋的状态更多，更复杂，计算机还处理不了。从可能的状态数上来说，围棋确实更复杂一些，但笔者认为这不是根本的原因。前面分析过，在α-β剪枝算法中，非常依赖于对棋局的打分，无论是国际象棋还是中国象棋，都有一个共同的特点，一方面局面越下越简单，进入残局后，棋子的多少就可能决定胜负，另一方面，以将军为获胜标志，判断起来简单。而围棋就不同了，对局面的判断非常复杂，棋子之间相互联系，不可能单独计算，而且没有一个像将军这样的获胜标志，导致对棋局打分非常困难，从而使得计算机围棋的水平一直停止不前，即便国际上最好的围棋程序也达不到业余初段的水平。
计算机围棋的第一次突破发生在2006年，来自法国的一个计算机围棋研究团队，将信心上限决策方法引入到计算机围棋中，结合蒙特卡洛树搜索方法，使得围棋程序性能有了质的提高，在9路围棋上（9*9大小的棋盘）战胜了人类职业棋手。从此之后，围棋程序基本以蒙特卡洛树搜索结合信心上限决策方法为主要的计算框架，经过大家不断的改进提高，2013年计算机程序CrazyStone在受让四子的情况下，在19路（19*19大小的正式棋盘）围棋上战胜被称为“人脑计算机”的日本棋手石田芳夫九段，被认为达到了业余围棋五、六段的水平。
蒙特卡洛方法是二十世纪40年代中期由S.M.乌拉姆和J.冯·诺伊曼提出的一类随机模拟方法的总称，其名称来源于摩纳哥的著名赌城，可以用随机模拟的方法求解很多问题的数值解。著名的“蒲丰投针”就属于这类方法，通过向画有格子的纸上投针计算π值。
人工智能的里程碑：从深蓝到AlphaGo

蒲丰投针方法求解π值
前面提到过，传统方法之所以在围棋上失效，一个主要原因就是围棋的棋局难于估计，于是有人就想到了用蒙特卡洛随机模拟的方法对棋局进行估值。其思想很简单，对于当前棋局，随机地模拟双方走步，直到分出胜负为止。通过多次模拟，计算每个可下棋点的获胜概率，选取获胜概率最大的点走棋。在围棋程序中实际使用的是一种被称为蒙特卡洛树搜索的方法，边模拟边建立一个搜索树，父节点可以共享子节点的模拟结果，以提高搜索的效率。其基本原理如下图所示，分为一下四个过程：
l 选择：以当前棋局为根节点，自上而下地选择一个落子点。
l 扩展：向选定的节点添加一个或多个子节点。
l 模拟：对扩展出的节点用蒙特卡洛方法进行模拟。
l 回传：根据模拟结果依次向上更新祖先节点的估计值。
人工智能的里程碑：从深蓝到AlphaGo

围棋中的蒙特卡洛树搜索方法

上述过程有点类似于人类下棋时的计算过程，搜索树的深度相当于向前看多少步棋，对棋局的判断则是通过“模拟”这个过程实现的。人在计算的过程中，对可能的走棋点会分轻重缓急，重要的点多考虑，次要的点少考虑，甚至不考虑。计算机程序在第一步“选择”过程中如何体现这一想法呢？信心上限决策方法的引入就是这一思想的体现。
信心上限决策是研究多臂老虎机问题时提出的一个统计决策模型，根据该模型，可以最大化效益。在围棋问题中，每个可落子点相当于多臂老虎机的一个臂，要选择可带来最大化效益的那个节点扩展。按照信心上限决策方法，要考虑两个因素：
l 优先选择模拟过程中到目前为止胜率最大的节点，以进一步考察它是否是一个好点。
l 优先选择那些到目前为止模拟次数比较少的节点，以考察这些点是否有潜在的好点。

信心上限决策方法就是对上述两个因素的加权折中，选取Ij最大的点进行扩展，其中Ij按下式计算，是上述两个因素的加权和：
人工智能的里程碑：从深蓝到AlphaGo

其中，Xj是节点j目前的收益（比如获胜概率），n是目前为止的总的模拟次数，Tj（n）是节点j目前的模拟次数，C是加权系数，对二者的重要性进行调节。
在蒙特卡洛树搜索中引入信心上限决策方法后，计算机围棋水平得到很大的提高，最好的围棋程序已经可以达到业余5段左右的水平。由于是通过模拟的方法对棋局进行评估，如果想达到比较准确的评估，需要模拟更多的次数。因此，蒙特卡洛树搜索存在两个不足，影响了其水平的提高：（1）虽然采用了信心上限决策方法选择扩展的棋子，但是其选择范围还是全体可下子点；（2）每次模拟必须一下到底，完成整局棋的模拟，直到分出胜负为止。由于围棋可能存在的状态非常巨大，这两点均极大地影响了搜索效率，阻碍了计算机围棋水平的提高。