1、人工智能课程报告推箱子小游戏的人工智能寻路 学院：姓名：学号：班级：指导教师： 人工智能课程报告一简介推箱子游戏简介经典的推箱子是一个来自日本的古老游戏，目的是在训练你的逻辑思考能力。在一个狭小的仓库中，要求把木箱放到指定的位置，稍不小心就会出现箱子无法移动或者通道被堵住的情况，所以需要巧妙的利用有限的空间和通道，合理安排移动的次序和位置，才能顺利的完成任务。胜利条件就是把所有的箱子都推到目的地。本程序的目标就是利用启发式搜索实现电脑自动推箱子。推箱子游戏地图程序采用手机中的推箱子小游戏的程序，地图总共75张，难度由易到难，搜寻路径的计算复杂度也会越来越高。每一张地图都以文本文件的形式存储起来
2、。地图展示：（第1关）（第35关）（第56关）（第75关）保存到文本文件中的地图代码：推箱子中人的行为人只可以推箱子, 不可以拉, 而且一次只能推动一个。即使是处于目的位置的箱子也可以推走。二基本概念启发式搜索考虑一个普通的图搜索问题：给出初始状态(节点 s)和目标状态(节点 t，可以不止一个)以及 状态的产生规则，求从 s 到 t 的一条路经。搜索过程可描述如下：1待展开的节点集合(OPEN 表)为 s，已展开的节点集合(CLOSED 表)为 ，节点 s 的层深为 g(s) = 0。2每次从 OPEN 表中取出一个节点 n，根据规则扩展产生一组节点 mi，然后把 n 放入 CLOSED 表中
3、。节点 mi可能属于下列三种情况之一：（1）新的节点，则把 mi的源标记为 n，层深 g(mi) = g(n) + 1，并放入 OPEN 表中。（2）已在 OPEN 表中存在的节点，并且层深 g(mi) g(n) + 1，说明从 s 到 mi并且经由 n 的路径要比先前搜索得到的路径要短。因此，把 mi的源改记为 n，层深 g(mi) = g(n) + 1，仍放入 OPEN 表中。（3）已在 CLOSED 表中存在的节点，并且层深 g(mi) g(n) + 1。同理，把 mi的源改记为 n，层深 g(mi) = g(n) + 1，并从 CLOSED 表中取出重新放入 OPEN 表中，留待以后重
4、新搜索计算 mi的子节点的层深。3不断重复上一步操作，直到满足下列条件之一：（1）n = t，搜索成功。（2）OPEN 表为空，搜索失败。在以上过程中，如何从 OPEN 表中选取待扩展的节点是关键。如果每次均选取层深 g(n) 最小的节点，以上过程就是宽度优先搜索；如果每次均选取层深 g(n) 最大的节点，以上过程 就是深度优先搜索。启发式搜索算法A*的思想是，给节点定义一个评价函数f(n) = g(n) + h(n)(1)其中，g(n) 是节点的层深，即从 s 到 n 目前搜索已知的最短路径长度，h(n) 是节点 n 到目标节点 t 的最短路径长度的估计值，称为启发函数。拥有最小 f(n)
5、值的节点有希望成为从 s 到 t 的最短路径上的一个节点，因而被取出并扩展。启发函数 h(n) 具有下列一些性质(证明略，我也不完全懂)：如果 h(n) 处在从 n 到 t 的最短路径长度的真实值 h*(n) 的下界，即恒有 h(n) = h*(n)，则算法A*找到的一定是从 s 到 t 的最短路径。此时算法A*称为算法A*。可以想象，h(n) 越接近真实值 h*(n)，它所包含的启发信息就越多，搜索所需扩展的节点数就越少。如果对所有节点 ni和 nj(其中 nj是 ni的子节点)都有 h(ni) - h(nj) = 1，则称启发函数 h(n) 满足单调限制条件。此时，算法A*在选取节点 n
6、进行扩展时，必有 g(n) = g*(n)，在搜索过程中不会出现把 mi从 CLOSED 表中取出重新放入 OPEN 表的情况。三算法的设计与实施推箱子游戏模块推箱子游戏初始化模块画图模块移动箱子模块移动小人模块功能控制模块程序中定义的四个函数：int orderDown(NodeInfo *infos, int *opens, const int &open_used, int root);堆的向下(从根到叶)调整，内部使用int orderUp(NodeInfo *infos, int *opens, const int &open_used, int leaf);堆的向上(从叶到根)调整
7、，内部使用template int key(Node *nodes, const int &hash_size, const Node &n);在散列数组中查找节点template int solve(Node *nodes, int hash_size, Node s);搜索函数，程序的入口基于可重用性的考虑，搜索函数 solve 被定义为模板函数，它操作的对象是一个表示节点的 模板类。节点类要求具有被搜索函数使用的一些基本接口，这些接口描述了节点的基本行为和属性，而节点的 具体意义(比如表示推箱子的某个状态)则隐藏在类的实现细节中。节点类的基本接口如下：int from;节点的源，返回目标
8、路径时使用Node();空节点的构造函数int possibleMoves() const;可能的扩展节点数int move(int sw);按第 sw 种扩展方式改变节点int h() const;启发函数int isTarget() const;判断节点是否目标节点int isNull() const;判断节点是否空节点int hash() const;散列函数friend int operator = (const Node &left, const Node &right);判断两个节点是否同一void output() const;输出为了提高速度，节点的存储和查找使用开地址散列，使
9、用简单的线性探测解决冲突。程序中的 Node nodes 和 NodeInfo infos 是并列的两个散列数组，分别存储所有已展开的节点 和节点的附加信息(f 值和在 OPEN 表中的位置)。key 根据节点的散列函数 hash() 在散列数组中查找或分配节点。OPEN 表实际上是一个优先队列，因而采用堆的方式实现。程序中的 int opens 是以数组(完全二叉树)存储的堆，数组元素表示节点在散列数组中的位置，最小 f 值的节点可以在 堆的根即 opens0 处中给出。orderDown 和 orderUp 是调整堆的需要。推箱子应用通用程序求解推箱子问题，关键是节点类的实现。状态的划分推
10、箱子的状态由人和箱子的位置决定。考虑到人可以在墙壁和箱子围成的连通区域内任意行走 而不会对局面产生实质性的影响，规定人必须位于他所处的连通区域的左上角。考虑到箱子的全同性，箱子的 坐标应从小到大排序。这些都在构造函数 Box() 或者节点扩展函数 move(sw) 中完成。这时，判断 两个状态是否相等只需分别比较每个箱子和人的坐标是否相等即可。节点的扩展每个箱子可以推向四个方向，因此总的可能的扩展节点数是箱子数的四倍。考虑到人的 可到达范围(way)的限制，某些箱子的某些方向(push_directions)是不可到达的。另外，地图中 还存在一些“死位置”(dead_positions)，比如
11、墙角、两个箱子并列在墙边等等。还有，箱子的背后 可能是墙壁或者另一个箱子。这些不可能的情况都可以在节点扩展函数 move(sw) 中予以拒绝。启发函数可以计算所有箱子离最近的目标的距离之和作为启发函数 h() 的返回值。不难看出，此定义的 启发函数满足算法A*的下界条件，因而找到的目标路径一定是最优解。A*算法的伪代码如下：创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。算起点的估价值;将起点放入OPEN表;while(OPEN!=NULL) 从OPEN表中取估价值f最小的节点n; if(n节点=目标节点) break;for(当前节点n 的每个子节点X
12、) 算X的估价值; if(X in OPEN) if( X的估价值小于OPEN表的估价值 ) 把n设置为X的父亲; 更新OPEN表中的估价值; /取最小路径的估价值if(X inCLOSE) if( X的估价值小于CLOSE表的估价值 ) 把n设置为X的父亲; 更新CLOSE表中的估价值; 把X节点放入OPEN /取最小路径的估价值if(X not inboth) 把n设置为X的父亲; 求X的估价值; 并将X插入OPEN表中; /还没有排序/end for 将n节点插入CLOSE表中; 按照估价值将OPEN表中的节点排序; /实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。/e
13、nd while(OPEN!=NULL)保存路径，即 从终点开始，每个节点沿着父节点移动直至起点，这就是你的路径；哈希函数可以将所有箱子的坐标移位相加再平方取中，得到哈希函数 hash() 的返回值。以上是我的推箱子程序的主要思路，如果你感兴趣，请进一步阅读我的程序。(可能不太好读。)四调试分析我的程序在电脑配置较低的条件下(需要根据情况修改程序中 HASH_SIZE 和 HEAP_SIZE 的设置)基本上可以解六个箱子之内的关，八到十个箱子的关或者特别复杂的六个箱子的关解起来会 比较费劲，特别复杂的八个箱子以上的关基本上就解不了了。启发式搜索虽然可以在很大程度上 缩小搜索空间，但是无法根本解
14、决指数爆炸的问题。目前我能想到一些改进措施是：如果不苛求最优解，可以适当增大上文提到的启发函数值。事实上，所有箱子离最近的目标的 距离之和与实际到达目标所需的步数之间有很大的差距，因而扩展生成了许多无关的节点。增大启发函数 值，例如人为的给它乘以二，以牺牲最优解为代价更快地到达目标。用另一种方式计算每个箱子到达目标所需的步数。考虑一个箱子紧挨着一个目标的情况，因为 地图和人的位置关系，箱子很可能根本无法一步推到目标上，这时简单的以箱子和目标的距离计算就 不太合适了。一种可能的办法是，在正式搜索之前先搜索得出一个箱子从不同的位置出发推到目标所需的 步数。不过，这点改进对搜索的性能能有多大提高还是一个未知数。删除搜索树上的“死”分枝。这点属于对启发式搜索通用程序的改进，与推箱子无关。但是 测试表明，在推箱子的搜索过程中，“死”分枝的比例一般只占总节点数的一半左右。因此，这点改进带来 的效果估计也不会很明显。五结论（包括结果）结论：启发式搜索可以比较好的解决推箱子问题。运行结果：点击运行程序，显示如下图：
