【科普】吴飞教授：《走进人工智能》---第3讲 深蓝的胜利：突破组合爆炸的困境

由高等教育出版社、高等教育电子音像出版社出品，浙江大学上海高等研究院联合上海人工智能实验室智能教育中心共同打造了原创人工智能前沿科普有声通识数字栏目——《走进人工智能》，主理人为浙江大学上海高等研究院常务副院长，浙江大学人工智能研究所所长、中国图象图形学学会理事、动画与数字娱乐专业委员会副主任 吴飞教授 ，本栏目已在喜马拉雅平台正式上线。

本期内容为《走进人工智能》：第3讲 深蓝的胜利：突破组合爆炸的困境

《走进人工智能》

第3讲

从专家系统到深蓝：在逻辑推理与优化搜索中成长

深蓝的胜利：突破组合爆炸的困境

博弈对抗是检验人工智能能力大小的标杆。1997年5月，国际象棋冠军卡斯帕罗夫和IBM公司的“深蓝（Deep blue）”计算机程序展开了一轮令全球瞩目的人机大战。结果，深蓝计算机发挥出色，以2胜3平1负的总比分战胜了卡斯帕罗夫, 成为首个在标准比赛时限内击败国际象棋世界冠军的电脑系统，这是人工智能领域一个里程碑事件。

在国际象棋比赛中，深蓝需要判断某一时刻棋局落子对整个棋局胜负会带来怎样的影响。即基于已知规则，深蓝要从当前棋局出发，尽可能向前搜索更多可能的未来棋局，以便掌握更多信息来对当前落子的优劣进行判断。由于可选棋局众多，尽管深蓝平均每秒能够对1亿个棋局进行判断评估，还是无法在规定时间内计算得到当前棋局对胜负的潜在影响。1950年，香农（Claud Shannon）发表了一篇有关国际象棋编程的论文。在这篇论文中，香农估算国际象棋比赛中落子选择从第一次移动时的20种会增加到第二次移动时的400种，在第六次移动时可能的落子选择达到1.19亿种。香农甚至估算认为国际象棋的落子总数为10的120次方，远远超出了10的82次方这一宇宙原子总数，这就是国际象棋中的“组合爆炸”难题。

为了从海量可能落子中选择一种合适落子，以克服组合爆炸挑战，深蓝采用了由1971年图灵奖获得者约翰·麦卡锡（John McCarthy）发明的“阿尔法-贝塔（Alpha-Beta）”剪枝搜索算法。简单来说，该算法主动“剪掉”对胜败不产生任何影响的棋局，从而减少搜索空间以提高搜索效率，解决了组合爆炸难题。可以看到，搜索是很重要的一种人工智能答案求解方法。“你见，或者不见，我就在那里，不悲不喜”，解决某个问题的答案就在那里，需要运用搜索之术来获得。

小结

以上是这一讲的全部内容。从这讲内容可知，早期人工智能算法在解决具体问题时，往往是针对特定任务进行逻辑推理和搜索探寻，得到满足一定约束条件的最佳答案。逻辑推理和搜索都是人工智能能力的体现，这一阶段的人工智能也被称为有效的老式人工智能（GOFAI, Good Old Fashioned Artificial Intelligence）。下一讲我们将介绍“从信息载体到智能燃料：数据的蝶变”。

产品名称：走进人工智能∣有声通识十五讲

主理人：吴飞

出品机构：高等教育出版社 、高等教育电子音像出版社

合作机构：浙江大学上海高等研究院、上海人工智能实验室智能教育中心

出品时间：2022年1月

中国图象图形学学会高校志愿者招募

中国图象图形学学会关于征集2022重大科学问题、工程技术难题和产业技术问题的通知

中国图象图形学学会关于组织开展科技成果鉴定的通知

2022年CSIG图像图形中国行承办方征集中