预计阅读本页时间：-
第7章 人工智能中的寻路
概述
如果一个问题没有明确的解决算法，那么我们就可以考虑使用寻路算法。在这章我们将讨论两种寻路算法，一种基于博弈树，另外一种基于搜索树。这两个方法本质上都是基于一种叫做状态树的通用结构。状态树的根节点表示初始状态，边表示两个状态之间可以转换。
在树中进行搜索是非常有挑战性的，因为所有的状态并不会完全计算出来，要知道，状态的数目可是爆炸性增长的。在跳棋游戏中，有大约5×1020个不同的棋盘状态（Schaeffer，2007）。因此这样的树将会在搜索时按需逐步构造。两种方法的特征如下。
博弈树
广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元
两个玩家轮流移动棋子，即从初始状态开始修改游戏的状态。每一个游戏者都有很多赢面状态。同样也有一些“平局状态”，在平局状态下，没有人会赢得游戏。一个优秀的寻路算法能够帮助玩家最大化赢得比赛的机会，或者在不利的情况下帮助玩家保住平局。
搜索树
给一个主体分配一个任务，从一个初始状态开始，通过一系列的移动，到达期望的目标状态。寻路算法能够得到从初始状态到目标状态的转移序列。
博弈树
有一种叫做一字棋的游戏，它需要一个3×3格的棋盘，玩家在棋盘上轮流画X或者O。第一个将三个标记画在同一行的玩家将会赢得这次游戏，如果没有足够的空间画标记并且没有玩家赢得游戏，那么这场游戏就是平局。10岁的孩子都知道先手玩家不可能失败，即使对手不会犯任何错误。一个一字棋的计算机程序同样也能够完成这样的工作，这个程序使用为组合对局（例如跳棋或者象棋，但是没有扑克，因为扑克含有更多的运气成分）设计的人工智能算法。在一个组合对局中，有一个初始局面状态，每个玩家轮流地进行游戏，更新局面状态，直到达到某些胜利条件（或者是平局，没有玩家将赢得比赛）。
一字棋游戏中，仅仅只有765个局面状态（忽略掉那些对称的局面）以及26 830个不同的比赛（Schaeffer，2002）。先手玩家总能够获胜或者保平，通常计算机专业的本科生都会被要求编写使用AI算法写一个一字棋的程序。我们仅仅需要构建博弈树（图7-1所示的是树的一部分），然后从当前局面状态（树中的顶部节点）开始，寻找到一条到达目标局面状态的路径，即胜利或者平局。
博弈树的另外一个广为人知的名称是与或树，因为节点只有两种类型，与或者或。玩家O的博弈树如图7-1所示。顶部节点是一个或节点，因为我们仅仅在六个可能的下一步局面中选择一个而已。中间层节点是与节点，因为O的目标是无论X怎么下，O都能够至少收获平局。图7-1的博弈树仅仅是有一部分被展开，因为事实上在底层只有30个不同的局面状态。由于玩家O或者X都没有到达底层的局面状态，我们将会看到顶部的局面状态特别有意思。直观地说，一字棋程序至少要能够预先计算三步之后的局面，然后来指导玩家O如何应付当前的局面。
博弈树表示游戏中从初始局面开始，经过有效的规则能够达到的所有的局面状态集合，当然，由于这棵树的规模过于庞大，它不可能完全计算出来。寻路算法的目标就是从一个局面状态开始，寻找一个走法来最大化玩家赢得游戏的几率。我们因此将玩家的智能决策集合转换成一个在博弈树上的寻路问题。这个方法对于较小的博弈树来说，能够很好地完成任务，它也可以被修改来解决更加复杂的问题。
跳棋的棋盘是8×8，一开始有24粒棋子（12红12黑）。长久以来，研究人员都一直尝试着寻找先手玩家是否能够至少保平。虽然精确地计算出这个结果会很困难，但是我们还是能够估算出大概有5×1020个状态。这种情况下，博弈树的规模将会不可思议地庞大。经过近18年的计算（动用了多达200台计算机），Alberta大学的研究人员声称他们已经证明了如果双方都能完美地下每一步棋，那么结果将会是平局（Schaeffer，2007）。
在人工智能（AI）中，有些复杂的问题可以被转换成玩家轮流进行的组合对局游戏，在这种情况下，我们可以使用寻路算法来解决。早期的人工智能（Shannon，1950）研究人员考虑过制造一台下棋机器，并且研究出两种解决搜索问题的方法，并且沿用至今。
A类
考虑双方将来可能的一些走法集合，这个走法集合是固定的，这个策略为先手玩家找到有利位置。因此，第一步的走法决定了局势发展的方向。
B类
我们可以根据一些游戏的知识来添加一些自适应的决策，而不是简简单单地使用静态评估函数。显然地，（a）尽量多地评估能够达到目的的位置，来为下一步走法寻找到一个有利的位置，这时当前局面的评价真实反映了当前位置的重要性。以及（b）选择合适的走法，所以那些漫无目的的走法不会消耗宝贵的时间。
在本章中，我们将会介绍一些最广泛使用并且最有效的方法来减少组合对局问题的搜索空间。我们首先介绍A类算法，在双人对局中，这类算法搜索博弈树，然后提供给玩家最优走法。是属于一种通用的方法。这些算法包括Minimax、AlphaBeta和NegMax。更高级的B类算法也会介绍（例如迭代加深）。
本章讨论的算法复杂程度与数据建立的模型好坏程度息息相关。教科书或者Internet上的很多例子都是使用一个特定的对局来描述这类算法。但是，算法和对局结合得非常紧密。因此，我们希望设计一系列面向对象的接口，来将算法和对局分开。我们现在简单地概括一下博弈树算法的核心概念，如图7-2所示。
IGameState接口抽象出来重要的思想，这些思想能够指导局面状态的搜索。这个接口提供了如下的功能。
解释当前局面状态
isDraw()计算是否当前局面会导致平局，isWin()计算是否当前局面下某个玩家已经获胜。
管理当前局面状态
copy()返回了当前局面的一份副本。所以玩家的移动可以不破坏原始局面状态，equivalent(IGameState)决定两个局面状态是否相等。
IPlayer接口抽象出玩家能够对局面做如下操作。
评估一个局面
eval(IGameState)返回一个整数，表示玩家对当前局面的一个看法，score(IGameScore)为玩家计算局面当前的得分。
得到有效的走法
validMoves(IGameState)返回当前局面下的有效走法。
IGameMove接口定义了当前局面下的有效走法。走法类根据问题的不同而不同，因此搜索算法不需要了解这些类的特定实现。IGameScore定义了得分计算的接口。在本章中，我们使用BoardEvaluation计分函数来计算一字棋的得分，这个函数由Nil Nilsson（1971）定义。nc(gs,p)返回一字棋局面下的行数、列数或者对角数，gs表示玩家p可能在一行连成三个的局面。我们定义score(IGameState gs,IPlayer player)如下：
·+∞如果玩家能够在当前局面gs下赢得游戏。
·-∞如果玩家在当前局面gs下输掉游戏。
·nc(gs,player)-nc(gs,opponent)，如果是当前局面会导致平局。
从编程的角度来看，博弈树寻路算法的核心是实现例7-1所示的IEvaluation接口。
例7-1：博弈树寻路的通用接口
从一个表示当前局面状态的节点开始，算法假设对手走法相当完美，基于这样的假设，计算出玩家的最优走法。稍后我们将讨论如何在博弈树的搜索中使用MiniMax、NegMax以及AlphaBeta策略。
