1700530549
国际象棋是一种一次移动一步的游戏，目标就在于要选择“最优的”每一步，那么，让我们定义一种可以进行“最优走步”的呈现。把递归公式应用到国际象棋当中，我们就可以换个说法，具体如下：
1700530550
1700530551
挑选最优行动方案：“挑选最优行动方案。如果我赢了，则任务完成。”
1700530552
1700530553
先等一下，稍后你就能看出其中的道理了。我需要进一步分解国际象棋的其他方面，也就是博弈里并不是只有我一人，我还有个对手，她也在移动。先假设她也能走出好棋。如果该假设不正确，那我就得到一次机会，而不是一个问题。那么递归公式是：
1700530554
1700530555
挑选最优行动方案：“假设我的对手也会挑选最优行动方案，据此我得挑选最优行动方案。如果我赢了，则任务完成。”
1700530556
1700530557
此时，我们需要考虑递归的本质。递归规则就是依据自身进行定义的。递归规则就是一种循环，但为了追求有效性，我们可不想永远循环下去，因此还需要一个逃离循环的出口。
1700530558
1700530559
为了解释清楚递归，我们还需要考虑一个例子：简单的“阶乘”函数。要计算n的阶乘，需要用n乘以（n–1）的阶乘。这是循环的部分——我们按照其自身特点定义该函数。还需要规定1的阶乘为1。这就是我们的逃离出口。
1700530560
1700530561
现在来计算2的阶乘。根据定义，
1700530562
1700530563
2的阶乘=2×（1的阶乘）。
1700530564
1700530565
我们已经知道1的阶乘是怎么计算机的，因此得以摆脱无限递归。将（1的阶乘）=1代入，可得：
1700530566
1700530567
2的阶乘=2×1=2。
1700530568
1700530569
回到国际象棋，可以看见挑选最优行动方案这一“函数”是递归的，因为我们按照它自身定义了最佳移动方法。对弈的棋盘策略中看上去不痛不痒的一句话“如果我赢了，则任务完成”，其实是我们的逃离出口。
1700530570
1700530571
我们再考虑一下我们所知的国际象棋。此处需要仔细考虑问题的定义。我们意识到要挑选最优行动方案，需要先列出可能要走的那几步棋。这并不太复杂。对弈中任何一次移动都是由规则定义的。虽然国际象棋的规则相较其他博弈更复杂，但直接易懂且容易编程。因此，我们列出了一些棋局走法并挑选出了最优走步。
1700530572
1700530573
但哪一种才是最优的呢？如果这种移动能让我们获胜那就太棒了。所以，我们仅需参考规则并且选择一种能立刻将住对方的王的方法即可。也许我们还没那么幸运，也许所有可能的移动方法中都没有可以让我们迅速获胜的办法，但仍然需要考虑这种移动方法究竟能让我们获胜还是失败。在这种情况下，需要考虑我们制定规则附加的那个不起眼的前提“假设我的对手也会这么做”。毕竟，获胜与否还取决于对手可能怎么做，需要站在对方的立场想一想她的最佳移动方法是什么。如何做到这一点呢？这就是递归发挥作用的时候了。有一个步骤刚好可以做到，叫作“挑选最优行动方案”，可以让它来决定对手的最优走步。
1700530574
1700530575
现在就可以按照以下步骤来构架设计我们的程序了。“挑选最优行动方案”程序总结出了规则允许所有可能的移动方法。它又反过来审查了每一种可能的移动方法。对于移动的每一步，它都能生成一份假设的棋盘，显示出选择此走法后棋盘上棋子的位置。这种做法仍然只要求运用国际象棋中的规则定义即可。“挑选最优行动方案”现在站在对手的立场上，尝试决定对方的最佳移动方法，然后开始从对方棋盘的角度生成所有可能的走步。
1700530576
1700530577
“挑选最优行动方案”程序会不断对自己提要求，从而不断产生可供选择的行动方案，生成十分庞大的博弈树，我们通常把这一过程叫作“极大极小”搜索，因为我们在选择时，总是最小化对手的获胜概率、最大化我方的获胜概率。
1700530578
1700530579
那么何时才是尽头呢？该程序会一直发挥作用，直到博弈树上的每一个分支都取得胜败结果为止。每一局博弈的结果只有两种：某一方胜或双方平局。在博弈树扩展深入的过程中，该程序会碰到决定胜负的一步棋。如果这步棋能使我方获胜，则选择此步走法；如果不存在决定胜负的走步，则双方打成平局；如果既不存在胜负，也无法打成平局，那我方只能继续棋局，只能寄希望于对方出现疏忽或漏洞。
1700530580
1700530581
这些最后的走步就是博弈树上最后的枝干——叫作“树叶”。现在，我们的程序不用再继续进行“挑选最优行动方案”的选择了，而是从博弈树的末枝返回至下棋程序。在从“挑选最优行动方案”的博弈树倒推回去的过程中，它计算评估出了每一个节点的最优走步（包括对手的最优走步），由此最终选择出当下棋局的最优走步。
1700530582
1700530583
那么这样一个简易程序的对弈水平如何呢？答案是“完美水准”。程序的宗旨就是“我不能输，除非我的对手先行并且对弈水准也无懈可击”。而完美型国际象棋对弈表现确实相当出色，赢人类对手不在话下。“挑选最优行动方案”函数中最复杂也是唯一不简单的地方就是在每个节点生成所有可行的走步，而这只是整理编辑规则的事。从本质上来说，我们已经通过问题的详细定义确定了该问题的答案。
1700530584
1700530585
但我们的工作还未完成。我们的程序能够完美地进行对弈，已经十分出色，但这还不够。我们还需要考虑“挑选最优行动方案”玩家的反应敏捷度如何。假设平均一张棋盘有8种可行的走步，一局对弈中大约走30步，所以要将博弈树完全深入扩展的话，我们需要考虑830种可能的行棋序列。假设我们每秒能解析10亿张棋盘（这已经大大超过当下任何一台下棋计算机的速度了），那么每走一步就需要1018秒，也就是约400亿年。
1700530586
1700530587
遗憾的是，我们的对弈可没那么长时间。这种递归的方法和进化有些相似——二者的工作都非常出色，但速度慢得出奇，但仔细想想这也是情有可原。进化代表了另一种简单的模式，也是另一种简易公式。
1700530588
1700530589
不过，抛弃递归公式之前，让我们把人类有限的耐心和生命作为考虑因素，重新修改一下递归公式。
1700530590
1700530591
显然，我们需要限制递归的深入程度。生成博弈树的扩展深度受限于可用的计算空间，这样一来，小至腕表计算机、大至超级计算机，我们可以在任何一台计算机上使用递归公式。
1700530592
1700530593
我们限制了博弈树的大小，这就意味着我们不能利用完整的博弈树。所以我们需要及时停止博弈树的扩展，并用一种方法评估这棵不完整的博弈树上各个“最后一片叶子”。在考虑一棵完整博弈树上所有的行棋序列时，走步的评估非常简单：能赢就不要平局，不要输。但是在对弈进行时，计算评估棋盘棋子的位置就比较复杂了。不过，对于博弈树的“剪枝”方法争议也很大，我们会碰到不同的思想学派。
1700530594
1700530595
在《爱丽丝漫游仙境》（Alice’s Adventures in Wonderland）中，告诉爱丽丝选择哪条路并不重要的柴郡猫一定是递归算法的专家。这种边对弈边评估合理走法的效果很好。举例来说，如果把棋子价值（piece value）简单相加（即后10分、车5分等等），得到的价值结果相当可观。利用棋子价值评估“最后一片叶子”的方法对极大极小递归公式进行编程，之后在一台1998年的普通个人计算机上运行此公式，那么你几乎能击败所有人类对手（除了千人左右的一部分顶级高手）。
1700530596
1700530597
以下是我称之为“头脑简单”派的学派。该学派认为：使用一种简单的方法评估最后一片叶子，并竭尽可用的计算能力进行博弈树的扩展，越深入越好。另一种是“头脑复杂”派，他们认为应该使用复杂巧妙的程序来评估每一块最后一片叶子所在棋盘的“质量”。
1700530598
[
上一页 ]
[ :1.700530549e+09 ]
[
下一页 ]