八数码游戏是在一个3×3的网格上，放着8个小方块，分别标上1～8，有一个空的格子没有方块。这个空格周围（水平的或者垂直的）方块可以移动到这里，方块原有位置形成一个新的空格。这个游戏的目标就是从一个初始状态开始，移动空格周围的方块，达到目标状态。如图7-3所示。这种游戏不存在对手玩家，但是玩家的行为和博弈树描述的行为相似。我们将问题抽象成一个初始状态（搜索树的顶部节点），以及一个从当前状态达到目标状态（标记为"GOAL"）的走法序列。从图7-3的例子中，我们可以看到从初始节点到目标节点的路径用粗体标示出来，这条路径就是解法，一共用了8步。
图 7-3 八数码搜索样例在这里我们使用术语搜索树，搜索树是表示一系列的中间棋面状态的树，寻路算法处理这些状态然后逐步推进。我们使用树这个结构是因为算法保证它不会处理两次同样的棋面状态。算法选择一种访问节点的顺序，然后根据这个顺序尝试达到目标状态。
搜索树通常会快速增长到数百万个状态，本章的算法将会告诉我们如何在搜索树中高效快速地搜索。想知道问题潜在的复杂度有多高吗？我们首先使用采用深度优先搜索和广度优先搜索的寻路算法。然后使用强有力的A*搜索算法，找到一个最小耗费的解（在特定的条件下）。我们将简单地概括一下核心概念，如图7-4所示，然后在讨论搜索树算法时使用这些概念。
图 7-4 搜索树算法的核心概念INode接口抽象出了指导搜索棋面状态的核心概念。这个接口的作用如下：
得到有效的走法
validMoves返回当前局面下的有效走法。
评估一个局面
score(int)给当前局面的打一个整数分值，score返回之前给当前局面赋予的分值。
管理棋面状态
copy返回当前棋面状态的一个副本（除开那些可选的数据），equivalent(INode)得出两个棋面状态是否等价（优秀的实现可以检测出对称棋面状态以及其他的等价情况）。key返回一个对象，如果两个棋面状态的key返回值相同，那么这两个棋面状态等价。
管理棋面状态的可选数据
storedData(Object o)得到和给定对象相关的棋面状态。storedData返回的是可能会和当前局面相关的数据。
INodeSet接口抽象出了INode集合组织形式的实现。有些算法需要队列，有些需要栈，有些需要平衡二叉搜索树。一旦选择了适当的结构（使用StateStorageFactory类），算法将会利用此结构能够支持的操作来维护INode集合。IMove接口定义了走法如何影响局面，不同的问题走法不同，搜索算法不需要关注于它们的实现。
从编程角度来看，搜索搜索树时，寻路算法的核心是例7-2所示的ISearch接口的实现。我们知道解法后，能够反推出走法。
例7-2：搜索树的寻路算法通用接口
给定一个表示初始棋面状态的节点以及一个目标节点，ISearch的实现将会计算出一条路径，不可到达时将返回null。为了和博弈树分开，在这里我们使用了“棋面状态”这个术语。