与图灵同时代的另外两位天才则把计算机下棋这件事情理论化了，冯·诺依曼在 1944 年与经济学家奧斯卡·摩根斯顿（Oskar Morgenstern）合著的《博弈论》中首次提出两方对弈的“ Minimax 算法”，这是一种零和算法，主要思路是一方要在可选的分支中选择将其优势最大化的路径，另一方则选择令对手优势最小化的路径，两者的对弈过程就构成一棵博弈树。今天很多计算机系的大学生都会用这个算法来编写“井字过三关”之类的游戏程序，但是这个算法相对于博弈树的深度而言是指数级时间复杂度解决方案，所以没有办法直接处理较深的搜索规模，如果不加优化的话就只能用来做井字棋这样的小玩意了。达特茅斯会议上麦卡锡分享的“ α-β 剪枝”搜索就是对 Minimax 算法树的深度进行控制的一种有效的优化手段，多数情况下在走到叶子节点前就可以判断出是否有必要把该分支搜索完，直至今天它还在各种棋类程序上被广泛使用。也就是最近几年，计算机终于敢挑战下围棋这种即使摩尔定律再稳定运行个几千年都无法靠硬计算和剪枝完成搜索的终极棋类游戏了，基于概率搜索剪枝的蒙特卡洛树搜索<sup>○</sup>才成为计算机棋界的新宠。
香农在 1950 年发表了论文《程序实现计算机下棋》（“ Programming aComputer for Playing Chess”），开启了计算机下棋的理论研究。他把棋盘定义为二维数组，然后从数学角度给出了一个棋类游戏复杂度的评估方法。以前我们只是知道围棋要比国际象棋难，国际象棋要比跳棋难，这是一个定性的结论，根据香农的这篇论文，我们终于可以定量地回答到底计算机攻克国际象棋要比攻克跳棋难多少，而攻克围棋又要比攻克国际象棋难多少这样的问题了。
从此之后，大多数棋类程序，从塞缪尔的西洋跳棋程序（见图 2-10）、纽厄尔和司马贺的国际象棋程序，到战胜人类国际象棋冠军的 IBM 深蓝，都是在香农、冯·诺依曼和麦卡锡他们总结的理论和算法之上运作的，多年来的改进主要集中在硬件的进步和小范围的技巧优化上，直至基于深度学习和概率的评估函数等新方法得到应用实践的证明，计算机下棋在理论层面才算有了较大的进步。
第 2 章 迈向人工智能
55
○一 概率在人工智能上的应用很早就出现了，在麦卡锡的达特茅斯会议计划书中就出现了“蒙特卡洛方法”来简化大脑思维模型的建议。这里写的“最近几年”是指在人工智能研究的后期这种方法的价值才被真正发现。