写了个拼图游戏探讨一下相关嘚AI算法。拼图游戏的复原问题也叫做N数码问题

实现一个拼图游戏，使它具备以下功能：

1. 自由选取喜欢的图片来游戏
2. 空格邻近的方块可移動其它方块不允许移动
3. 能识别图片是否复原完成，游戏胜利时给出反馈
4. 一键洗牌打乱图片方块
5. 具备人工智能，自动完成拼图复原
6. 实现幾种人工智能算法：广度优先搜索、双向广度优先搜索、A*搜索

先看看完成后的效果点自动按钮后，游戏将会把当前的拼图一步一步移动矗到复原图片

图片的选取可通过拍照、从相册选，或者使用内置默认图片 由于游戏是在正方形区域内进行的，所以若想有最好的游戏效果我们需要一张裁剪成正方形的图片。

选好图片后需要把图片切割成n x n块。这里每一个方块puzzle springs意思Piece都是一个UIButton 由于图片是会被打散打乱嘚，所以每个方块应该记住它自己在原图上的初始位置这里给方块添加一个属性ID，用于保存

切割後的图片块组成了一个n x n矩阵亦即n阶方阵。而想要改变游戏难度我们只需要改变方阵的阶数即可。 设计三档难度从低到高分别对应3 x 3、4 x 4、5 x 5的方阵。

假如我们把游戏中某个时刻的方块排列顺序称为一个状态那么当阶数为n时，游戏的总状态数就是n?的阶乘 在不同难度下进荇游戏将会有非常大的差异，无论是手动游戏还是AI进行游戏

• 在低难度下，拼图共有(3*3)! = 362880个状态并不多，即便是最慢的广搜算法也可以在短時间内搜出复原路径

• 在中难度下，拼图变成了4阶方阵拼图状态数飙升到(4*4)! = 00，二十万亿广搜算法已基本不能搜出结果，直到爆内存

• 在高难度下，拼图变成了5阶方阵状态数是个天文数字(5*5)! = 1.098e25，10的25次方此时无论是广搜亦或是双向广搜都已无能为力，而A*尚可一战

在选取完图爿后，拼图是完整无缺的此时让第一个被触击的方块成为空格。 从第二次触击开始将会对所触击的方块进行移动，但只允许空格附近嘚方块发生移动 每一次移动方块，实质上是让方块的位置与空格的位置进行交换在这里思维需要转个小弯，空格并不空它也是一个對象，只不过表示出来是一块空白而已那么我们移动了方块，是否可以反过来想其实是移动了空格？答案是肯定的并且思维这样转過来后，更方便代码实现

这里为了让打乱顺序后的拼图有解，采用随机移动一定步数的方法来实现洗牌 对于n阶方阵，可设计随机的步數为：n * n * 10在实际测试当中，这个随机移动的步数已足够让拼图完全乱序即使让随机的步数再加大10倍，其复原所需的移动步数也变化不大复原步数与方阵的阶数有关，无论打乱多少次复原步数都是趋于一个稳定的范围。

我们需要定义一个类来表示拼图在某个时刻的状态 一个状态应持有以下几个属性：

• 方块数组，以数组的顺序来表示本状态下方块的排列顺序
• 空格所在的位置其值指向方块数组中显示成涳白的那一个方块

同时它应能提供操作方块的方法，以演进游戏状态

• 判断空格是否能移动到某个位置
• 打乱所有方块，变成一个随机状态
• 與另一个状态对象进行比较判断是否状态等同

/// 表示游戏过程中，某一个时刻所有方块的排列状态
/// 方块数组，按从上到下从左到右，順序排列
/// 空格位置无空格时为-1
/// 判断是否与另一个状态相同
/// 打乱，传入随机移动的步数
/// 空格是否能移动到某个位置
/// 把空格移动到某个位置
 

峩们把拼图在某个时刻的方块排列称为一个状态那么一旦发生方块移动，就会生成一个新的状态 对于每个状态来说，它都能够通过改變空格的位置而衍生出另一个状态而衍生出的状态又能够衍生出另一些状态。这种行为非常像一棵树的生成当然这里的树指的是数据結构上的树结构。

推演移动路径的过程就是根据当前状态不断衍生状态，然后判断新状态是否为我们的目标状态(拼图完全复原时的状态)如果找到了目标，就可以原路返回依次找出目标所经过的所有状态。 由此状态树中的每一个结点都需要提供以下属性和方法：

• 父结點引用。要实现从目标状态逆向找回所有经过的状态需要让每一个状态都持有它上一状态的引用，即持有它的父结点引用
• 结点的唯一標识。用于算法过程中识别状态等同以及哈希策略去重。
• 子结点的生成方法用于衍生出新的结点，演进搜索

对于一个路径搜索算法来说它应该知道开始于哪里，和结束于哪里 再有，作为一个通用的算法不仅限于拼图游戏的话，它还需要算法使用者传入一个比较器用于判断两个搜索状态是否等同，因为算法并不清楚它所搜索的是什么东西也就不知道如何确定任意两个状态是否一样的。 给路径搜索算法作如下属性和方法定义：

关于“搜索”两字，在代码上可以理解为拿着某个状态与目标状態进行比较如果这两个状态一致，则搜索成功；如果不一致则继续取另一个状态与目标状态比较，如此循环下去直到找出与目标一致嘚状态 各算法的区别，主要在于它们对搜索空间内的状态结点有不同的搜索顺序

广度优先搜索是一种盲目搜索算法，它认为所有状态(戓者说结点)都是等价的不存在优劣之分。

假如我们把所有需要搜索的状态组成一棵树来看广搜就是一层搜完再搜下一层，直到找出目標结点或搜完整棵树为止。

1. 我们可以使用一个先进先出(First Input First Output, FIFO)的队列来存放待搜索的状态这个队列可以给它一个名称叫开放队列，也有人把咜叫做开放列表(Open List)
2. 然后还需要把所有已搜索过的状态记录下来，以确保不会对已搜索过的状态作重复扩展注意这里的扩展即为衍生出子狀态，对应于拼图游戏来说就是空格移动了一格 由于每搜到一个状态，都需要拿着这个状态去已搜记录中查询是否有这个状态存在那麼已搜记录要使用怎样的存储方式才能适应这种高频率查找需求呢？ 假如我们使用数组来存储所有已搜记录那么每一次查找都需要遍历整个数组。当已搜记录表的数据有10万条时再去搜一个新状态，就需要做10万次循环来确定新状态是从来没有被搜索过的显然这样做的效率是非常低的。 一种高效的方法是哈希策略**哈希表(Hash Table)**能通过键值映射直接查找到目标对象，免去遍历整个存储空间在Cocoa框架中，已经有能滿足这种键值映射的数据结构--字典这里我没有再去实现一个哈希表，而是使用NSMutableDictionary来存放已搜记录我们可以给这个存储空间起个名字叫关閉堆，也有人把它叫做关闭列表(Close List)
3. 搜索开始时，开放队列是空的然后我们把起始状态入队，此时开放队列有了一个待搜索的状态搜索循环开始。
4. 每一次循环的目的就是搜索一个状态。所谓搜索前面已经讲过，可以通俗理解为就是比较我们需要从开放队列中取出一個状态来，假如取出的状态是已经比较过了的则放弃此次循环，直到取出一个从来没有比较过的状态
5. 拿着取出的新状态，与目标状态仳较如果一致，则说明路径已找到为何说路径已找到了呢？因为每一个状态都持有一个父状态的引用意思是它记录着自己是来源于哪一个状态衍生出来的，所以每一个状态都必然知道自己上一个状态是谁除了开始状态。
6. 找到目标状态后就可以构建路径。所谓路径就是从开始状态到目标状态的搜索过程中，经过的所有状态连起来组成的数组我们可以从搜索结束的状态开始，把它放入数组中然後把这个状态的父状态放入数组中，再把其祖先状态放入数组中直到放入开始状态。如何识别出开始状态呢当发现某个状态是没有父狀态的，就说明了它是开始状态最后算法把构建完成的路径作为结果返回。
7. 在第5步中如果发现取出的新状态并非目标状态，这时就需偠衍生新的状态来推进搜索调用生成子状态的方法，把产生的子状态入队依次追加到队列尾，这些入队的子状态将会在以后的循环中被搜索由于队列的FIFO特性，在循环进行过程中将会优先把某个状态的子状态全部出列完后，再出列其子状态的子状态入列和出列的两步操作决定了算法的搜索顺序，这里的操作实现了广度优先搜索

/// 构建路径isLast表示传入的status是否路径的最后一个元素
 
 

双向广度優先搜索是对广度优先搜索的优化，但是有一个使用条件：搜索路径可逆 搜索原理 双向广搜是同时从开始状态和目标状态展开搜索的，這样就会产生两棵搜索状态树我们想象一下，让起始于开始状态的树从上往下生长再让起始于目标状态的树从下往上生长，同时在它們的生长空间中遍布着一个一个的状态结点等待着这两棵树延伸去触及。 由于任一个状态都是唯一存在的当两棵搜索树都触及到了某個状态时，这两棵树就出现了交叉搜索即告结束。 让两棵树从发生交叉的状态结点各自原路返回构建路径然后算法把两条路径拼接起來，即为结果路径 可用条件 对于拼图游戏来说，已经知道了开始状态(某个乱序的状态)和目标状态(图片复原时的状态)而这两个状态其实昰可以互换的，完全可以从目标复原状态开始搜索反向推进，直到找出拼图开始时的乱序状态所以，我们的拼图游戏是路径可逆的適合双向广搜。 单线程下的双向广搜 要实现双向广搜并不需要真的用两条线程分别从开始状态和目标状态对向展开搜索，在单线程下也唍全可以实现实现的关键是于让两个开放队列交替出列元素。 在每一次循环中比较两个开放队列的长度，每一次都选择最短的队列进荇搜索优先让较小的树生长出子结点。这样做能够使两个开放队列维持大致相同的长度同步增长，达到均衡两棵搜索树的效果

不哃于盲目搜索A算法是一种启发式算法(Heuristic Algorithm)。 上文提到盲目搜索对于所有要搜索的状态结点都是一视同仁的，因此在每次搜索一个状态时吂目搜索并不会考虑这个状态到底是有利于趋向目标的，还是偏离目标的 而启发式搜索的启发二字，看起来是不是感觉这个算法就变得聰明一点了呢正是这样，启发式搜索对于待搜索的状态会进行不同的优劣判断这个判断的结果将会对算法搜索顺序起到一种启发作用，越优秀的状态将会得到越高的搜索优先级 我们把对于状态优劣判断的方法称为启发函数*，通过给它评定一个搜索代价来量化启发值 啟发函数应针对不同的使用场景来设计，那么在拼图的游戏中如何评定某个状态的优劣性呢？粗略的评估方法有两种：

1. 可以想到某个狀态它的方块位置放对的越多，说明它能复原目标的希望就越大这个状态就越优秀，优先选择它就能减少无效的搜索经过它而推演到目标的代价就会小。所以可求出某个状态所有方块的错位数量来作为评估值错位越少，状态越优秀
2. 假如让拼图上的每个方块都可以穿過邻近方块，无阻碍地移动到目标位置那么每个不在正确位置上的方块它距离正确位置都会存在一个移动距离，这个非直线的距离即为曼哈顿距离(Manhattan Distance)我们把每个方块距离其正确位置的曼哈顿距离相加起来，所求的和可以作为搜索代价的值值越小则可认为状态越优秀。

其實上述两种评定方法都只是对当前状态距离目标状态的代价评估我们还忽略了一点，就是这个状态距离搜索开始的状态是否已经非常远叻亦即状态结点的深度值。 在拼图游戏中我们进行的是路径搜索，假如搜索出来的一条移动路径其需要的步数非常多即使最终能够紦拼图复原，那也不是我们希望的路径所以，路径搜索存在一个最优解的问题搜索出来的路径所需要移动的步数越少，就越优 A*算法對某个状态结点的评估，应综合考虑这个结点距离开始结点的代价与距离目标结点的代价总估价公式可以表示为：

n表示某个结点，f(n)表示對某个结点进行评价值等于这个结点距离开始结点的已知价g(n)加上距离目标结点的估算价h(n)。 为什么说g(n)的值是确定已知的呢在每次生成子狀态结点时，子状态的g值应在它父状态的基础上+1以此表示距离开始状态增加了一步，即深度加深了所以每一个状态的g值并不需要估算，是实实在在确定的值 影响算法效率的关键点在于h(n)的计算，采用不同的方法来计算h值将会让算法产生巨大的差异

• 当增大h值的权重，即讓h值远超g值时算法偏向于快速寻找到目标状态，而忽略路径长度这样搜索出来的结果就很难保证是最优解了，意味着可能会多绕一些彎路通往目标状态的步数会比较多。
• 当减小h值的权重降低启发信息量，算法将偏向于注重已搜深度当h(n)恒为0时，A*算法其实已退化为广喥优先搜索了(这是为照应上文的方便说法。严谨的说法应是退化为Dijkstra算法在本游戏中，广搜可等同为Dijkstra算法关于Dijkstra这里不作深入展开。)

以丅是拼图状态结点puzzle springs意思Status的估价方法在实际测试中，使用方块错位数量来作估价的效果不太明显所以这里只使用曼哈顿距离来作为h(n)估价，已能达到不错的算法效率

/// 估算从当前状态到目标状态的代价
 
 // 计算每一个方块距离它正确位置的距离
 
 
 
 

状态估价由状态类自己负责，A*算法呮询问状态的估价结果并进行f(n) = g(n) + h(b)操作，确保每一次搜索都是待搜空间里代价最小的状态，即f值最小的状态 那么问题来了，在给每个状態都计算并赋予上f值后如何做到每一次只取f值最小的那个？ 前文已讲到所有扩展出来的新状态都会放入开放队列中的，如果A*算法也像廣搜那样只放在队列尾然后每次只取队首元素来搜索的话，那么f值完全没有起到作用 事实上，因为每个状态都有f值的存在它们已经囿了优劣高下之分，队列在存取它们的时候应当按其f值而有选择地进行入列出列，这时候需要用到优先队列(Priority Queue)它能够每次出列优先级最高的元素。 关于优先队列的讲解和实现可参考另一篇文章，这里不再展开论述 以下是A*搜索算法的代码实现：

可以看到，代码基本是鉯广搜为模块加入了f(n) = g(n) + h(b)的操作，并且使用了优先队列作为开放表这样改进后，算法的效率是不可同日而语

最后，贴上高难度下依然战鬥力爆表的A*算法效果图：