1700530591
显然，我们需要限制递归的深入程度。生成博弈树的扩展深度受限于可用的计算空间，这样一来，小至腕表计算机、大至超级计算机，我们可以在任何一台计算机上使用递归公式。
1700530592
1700530593
我们限制了博弈树的大小，这就意味着我们不能利用完整的博弈树。所以我们需要及时停止博弈树的扩展，并用一种方法评估这棵不完整的博弈树上各个“最后一片叶子”。在考虑一棵完整博弈树上所有的行棋序列时，走步的评估非常简单：能赢就不要平局，不要输。但是在对弈进行时，计算评估棋盘棋子的位置就比较复杂了。不过，对于博弈树的“剪枝”方法争议也很大，我们会碰到不同的思想学派。
1700530594
1700530595
在《爱丽丝漫游仙境》（Alice’s Adventures in Wonderland）中，告诉爱丽丝选择哪条路并不重要的柴郡猫一定是递归算法的专家。这种边对弈边评估合理走法的效果很好。举例来说，如果把棋子价值（piece value）简单相加（即后10分、车5分等等），得到的价值结果相当可观。利用棋子价值评估“最后一片叶子”的方法对极大极小递归公式进行编程，之后在一台1998年的普通个人计算机上运行此公式，那么你几乎能击败所有人类对手（除了千人左右的一部分顶级高手）。
1700530596
1700530597
以下是我称之为“头脑简单”派的学派。该学派认为：使用一种简单的方法评估最后一片叶子，并竭尽可用的计算能力进行博弈树的扩展，越深入越好。另一种是“头脑复杂”派，他们认为应该使用复杂巧妙的程序来评估每一块最后一片叶子所在棋盘的“质量”。
1700530598
1700530599
IBM那台跨越了历史限制的“深蓝”计算机，使用的树叶评估法要比棋子价值简单相加的评估方法更为精细。然而，就在1997年那次历史性胜利的几星期之前，我同“深蓝”团队领头人莫里·坎贝尔（Murray Campbell）进行了一次交谈，坎贝尔认为“深蓝”计算机的评估方法更偏向于“头脑简单”派而不是“头脑复杂”派。
1700530600
1700530601
递归算法中的非数字符号型语言“伪代码”
1700530602
1700530603
以下是递归算法的基本模式。递归算法中可能会出现许多变量，系统设计者需要提供一些特定的关键参数和方法，细节如下：
1700530604
1700530605
递归算法
1700530606
1700530607
定义一个函数（程序）,“挑选最优行动方案”。函数返回值为“成功”（已经解决了问题）或者“失败”（没有解决问题）。如果返回值是成功，函数也会同时将解决问题的选定步骤序列值一起返回。在此过程中，“挑选最优行动方案”执行具体如下操作：
1700530608
1700530609
挑选最优行动方案
1700530610
1700530611
·判断该程序是否可在此节点脱离连续递归。（本条项目符号和下两条项目符号主要说明脱离递归的操作。）首先，判断问题现在是否已经解决。因为有可能是程序自身启动了“挑选最优行动方案”程序这一步，所以我们现在可能得到了一个满意的解决方案，比如：
1700530612
1700530613
i）在博弈情境下（比如国际象棋），棋局获胜的最后一步（比如将军）。
1700530614
1700530615
ii）在解决数学定理问题的情境下，证明定理成立的最后一步。
1700530616
1700530617
iii）在艺术创作程序的情境下（比如用计算机作诗或者谱曲），创作出与下一个词或音符匹配的最后一步。
1700530618
1700530619
如果能得出令人满意的解决方案，程序的返回值则为成功。在这种情况下，“挑选最优行动方案”同时返回选定的步骤序列值。
1700530620
1700530621
·如果问题未被解决，则判断某一个解决方案是否会走入死胡同，比如：
1700530622
1700530623
i）在博弈情境下（比如国际象棋），此走步会让我们输（比如说，被对方将军）。
1700530624
1700530625
ii）在解决数学定理问题的情境下，这一步违背了定理。
1700530626
1700530627
iii）在艺术创作程序的情境下（比如用计算机作诗或者谱曲），这一步与下一个词或音符不匹配。
1700530628
1700530629
如果此时这种解决方案被判定会走入死胡同，程序的回归值则为失败。
1700530630
1700530631
·若递归扩展至此节点时，问题既未得到解决也没有走入死胡同，则判断是否终止递归继续扩展。这是设计中十分关键的一步，需要考虑到我们可消耗在计算机上的时间有限，比如：
1700530632
1700530633
i）在博弈情境下（比如国际象棋），这一步可让我方足够“领先”或“落后”。进行这一步判断时或许无法像前两种情况那般直截了当，但又是设计中非常重要的一步。所幸一些简单的方法（比如棋子价值的简单相加）仍能提供不错的结果。如果该程序判定我方已经遥遥领先，那么“挑选最优行动方案”将返回至判断棋局获胜的那一步（即返回值为成功）;如果该程序判定我方已远远落后，那么“挑选最优行动方案”将返回至判断棋局走入死胡同的那一步（即返回值为失败）。
1700530634
1700530635
ii）在解决数学定理问题的情境下，这一步需要判断证明中的一连串步骤是否无法被论证。如果是这样，则此种论证无效，“挑选最优行动方案”将返回至判断违背定理的那一步（即返回值为失败）。这种情境下，不存在“类似成功”的对等值，直到该数学问题被确确实实地解决之后，我们才能返回成功。这就是数学的本质。
1700530636
1700530637
iii）在艺术创作程序的情境下（比如用计算机作诗或者谱曲），这一步需要判断步骤的排列顺序（如诗歌中的词，歌曲中的音符）是否无法满足下一步的需求。如果是，则此种选择无效，“挑选最优行动方案”将返回至判断无法匹配下一个词或音符的那一步（即返回值为失败）。
1700530638
1700530639
·如果“挑选最优行动方案”还未返回（因为此时程序既未判定成功还是失败，也未判定在此节点是否终止该递归），那么此时我们还没有脱离递归的后续扩展。在这种情况下，我们就要列出此节点下会出现的所有可能步骤。此时就需要介入问题的详细精确说明了：
1700530640
[
上一页 ]
[ :1.700530591e+09 ]
[
下一页 ]