Page 43 - 高中 信息技术 选择性必修4 人工智能初步

 2.2 启发式搜索

差和利用α-β剪枝算法来尝试预测对手的行为、与对手博弈。多年来，人工智能研究者
们一直以攻克各类游戏为目标，因为这些任务规则简单，可以为真实世界的应用做铺垫。
人工智能研究者们不仅在国际象棋上，也在跳棋和双陆棋等棋盘游戏中有过很多研究。

启发式搜索不是搜索引擎式的搜索。在真实情况下，由于可能性过多，很多时候无法
搜索全部信息。在棋类游戏中，最引人注目的自然是被认为复杂性最高的围棋了。
“阿尔法围棋”的学习过程是线下的，它通常预先发展出若干神经网络以待比赛中使
用。蒙特卡洛树搜索（Monte Carlo Tree Search，简称MCTS）是其主要的决策算法，用于

决定一局比赛中的每一步棋。这种算法通过结合博弈树搜索算法、机器学习到的知识和模
拟全局游戏来决定每一步。这些算法中最重要的部分是深度神经网络。其中一个网络（策

略网络）负责选择搜索中最有希望的落子位置，另一个网络（价值网络）负责评估其在搜
广东教育出版社
索中遇到的数千乃至数百万个棋盘局面。在获取棋局信息后，“阿尔法围棋”的策略网络
会探索哪些位置具备潜在价值，在分配的搜索时间结束时，探索过程中被系统考察最多的
位置将成为“阿尔法围棋”的最终选择。经过前期的全盘探索和过程中对最佳落子的不断

揣摩后，高效的算法与强大的计算能力使其实现超越人类的直觉判断。启发式学习经历了
三四十年的发展，它是“阿尔法围棋”背后的动力，也是多个领域的核心算法。
启发式搜索虽然已经在多个领域的应用中获得成功，但仍然面临一些挑战。例如博弈

过程中，如果对手改变惯有套路，系统就难以在智能机器知识库中搜索，从而无法做出正
确解答。 在自动驾驶、医疗等性命交关的应用上，不能允许深度学习和启发式搜索出现
任何小概率偏差，这意味着我们还有很长一段路要走。我们目前还面临着两个挑战：如何

使启发式搜索的结果更精确；当不知道全局规则的时候，如何让机器解决问题。

实 践

迷宫问题是一个典型的导航搜索问题。如何找到

迷宫的出口？在遇到死胡同的时候如何返回？如何防
止走重复的路程？写出求解如图2-7所示迷宫问题的
算法思路。

项目实施

各小组根据项目选题及拟订的项目方案，结合本
节所学知识，对自动驾驶系统的启发式搜索算法进行
图2-7 迷宫问题
剖析。
1. 选择一种启发式搜索算法，规划一条从A地到B地的行驶线路。
2. 总结、归纳、比较各种启发式搜索算法的优劣。

35 35

21Y3228.indd 35 2019/10/10 14:23:29