机器学习解十滴水游戏

十滴水游戏及其求解人工智能第一次大作业黄青虬自2320120114382014/10/19目录1.概述...............................................................................................................................................22.游戏简介........................................................................................................................................23.游戏界面设计及功能简介............................................................................................................23.1选择关卡.............................................................................................................................33.2搜索求解.............................................................................................................................33.3开挂....................................................................................................................................43.4注意事项.............................................................................................................................44.算法设计........................................................................................................................................44.1搜索算法.............................................................................................................................44.1.1宽度优先搜索..........................................................................................................54.1.2A算法......................................................................................................................54.1.3A*算法.....................................................................................................................64.2遗传算法.............................................................................................................................64.3算法优劣比较.....................................................................................................................75.参考资料及备注............................................................................................................................85.1参考资料.............................................................................................................................85.2备注....................................................................................................................................81.概述本次作业在VS2012平台下使用C#语言完成了两件事情。一是实现了十滴水小游戏；二是使用了多种算法对其求解，包括三种搜索算法：宽度优先搜索、A算法、A*算法，以及一种智能优化算法：遗传算法。2.游戏简介如图一所示，十滴水游戏是在一个6×6的棋盘上，通过填补水滴来引爆原有的水滴，直到棋盘上所有水滴消失。棋盘上每个格子可以放0、1、2、3、4滴水，当格子上有4滴水时，再往上面滴一滴水，则该水滴会爆，即格子上的水滴变为0，同时向四周各溅出一滴水，溅出的水如果遇到其他水滴就会并入，如果并入后水滴数又大于4了，则会有新一轮的引爆。点击格子则在其上面滴一滴水。水滴是有限制的，如图一，右上角会有一个水缸显示当前你还可以用的水滴数。每引爆三滴水可以让水缸增加一滴水。图一.网络上十滴水游戏界面3.游戏界面设计及功能简介本次作业主界面如图二所示，左方的棋盘和右上角的水缸与原游戏的功能一样，点击相应的格子即可在格子上加水，同时水缸的水量会根据使用的水量和奖励的水量做相应的变化。同时在游戏原有的模块上又增加了以下模块和功能：图二.游戏主界面图三.关卡选择界面3.1选择关卡主界面右下方有“选择关卡”按钮，点击该按钮，会弹出选择关卡界面，如图三所示。点击想要的关卡即可跳转到该关卡。在主界面的中上方会显示当前在第几关。3.2搜索求解搜索求解包括主界面右方的算法选择按钮、搜索结果显示文本框和“搜索求解”按钮。算法选择按钮中可以选择“宽搜”、“A*”、“A”、“遗传算法”中的一种，然后点击“搜索求解”按钮，就会在搜索结果显示文本框中显示搜索到的解。搜索到的解如图四所示，从上往下表示每一次要点击的格子。每一次要点击的格子表示为（x，y）的形式。以左上角为起点（即左上角的格子表示为（1,1）），横向为x轴，向右递增，竖向为y轴，向下递增。对于搜索算法，由于十滴水游戏的状态空间巨大，如果不对搜索深度和时间做限制，对于比较复杂的解，将会出现内存不足或者在有限时间内无法求解的情况。所以求解时对时间和搜索深度做了限制。宽搜和A*的限制为：时间小于30s，深度小于5；A限制为：时间小于30s。如果计算过程中不满足这些限制条件，将不再计算，退出并给出提示。提示如图五所示。对于遗传算法，由于有迭代代数的限制，所以无需再对时间做限制，但由于迭代代数的限制，所以有一定概率不能给出解，此时也会给出提示（由于在有限的测试集内未出现这种情况，这里无法给出图示）。图四.搜索结果图五.解不满足限制条件提醒3.3开挂由于有些关卡难度较大，而且对于步数大于5的解，宽搜和A*在有限的时间和空间内无法计算出来，而A和遗传算法给出的不是最优解，所以得到的解可能会有比较长的步数。所以增设了“开挂”按钮，每点击一次水缸中增加10滴水。3.4注意事项1.点击水滴爆破后可能会引起一连串水滴爆破，所以动画时间较长，在动画过程中为了防止玩家乱按，将屏幕点击响应以及“搜索求解”、“开挂”、“选择关卡”三个按钮全部锁定，即此时不可点击格子放置水滴，也不能点击相应按钮实现其功能（按钮上的字会变颜色，如图六），直到不再有飞溅的水滴了，才恢复正常。2.对于一些比较复杂的情况，搜索求解时时间可能会比较久，此时屏幕和按钮也会失去响应，但并非程序死了，而是在计算，计算完成后即恢复正常。图六.水滴还在飞溅时按钮锁定4.算法设计本次作业针对十滴水游戏设计了三种搜索算法和一种智能优化算法，用6×6矩阵来表示状态，矩阵上的元素为数字0~4，分别表示有0~4滴水。现在对每种算法分别做一定分析：4.1搜索算法搜索算法的总体框架基本是一致的，总体框架如图七所示。三种搜索算法的区别就在于队列的维护，即队首元素是怎么选择出来的，也就是𝑓(𝑛)的选取不同。图七.搜索算法流程图4.1.1宽度优先搜索估计函数𝑓(𝑛)=𝑔∗(n)即只以过去所走的步数作为评价。队列维护而所走步数小的状态肯定会先进入队列，即𝑓(𝑛)越小越先进入队列，也应该越先出队被拓展。所以只需使用“先进先出”的普通队列即可实现，无需对队列里的元素进行排序。4.1.2A算法估计函数𝑓(𝑛)=g(n)+h(n)即不仅考虑过去所走的步数，还要对达到目标状态所要走的步数有一个估值h(n)，通过这个估值来指导应该先拓展那个状态。程序中所使用的h(n)是这样定义的：h(n)=ℎ1(𝑛)+ℎ2(𝑛)其中ℎ1(𝑛)=−5m+∑∑−𝑑𝑟𝑜𝑝[𝑖,𝑗]6𝑗=16𝑖=1ℎ2(𝑛)=3𝑙注：m表示没有水滴的格子数量，因为没有水滴的格子不必再去消除，所以加了最大的负权值；𝑑𝑟𝑜𝑝[𝑖,𝑗]表示第i行第j列的格子上的水滴数，因为水滴越大越容易消除，所以加了负的权值，且水滴越大数值越小；𝑙表示孤立水滴的数量，孤立水滴即同一行同一列的格子上均没有水滴，因为孤立水滴是不利于消除的，所以加了一个正的权值。而g(n)是这样定义的：g(n)=𝑘∗𝑔∗(n)即实际所走步数乘上一个权值k。k的选取将对A算法的性能产生比较大的影响。K越大则得到的结果越优（即解的步数越短），但同时要搜索的空间也越大，当k→∞时，A算法实际上就是宽度优先搜索。反之，k越小则搜索的空间会越小，但得到的结果可能越差。经过试验测算，综合考虑了性能，最后程序中的A算法k取值为2。队列维护由于每次出队的状态都必须是队列里𝑓(𝑛)最小的，所以队列不能是普通的队列。最简单的解决办法是每次要出队之前对队列里的元素按照𝑓(𝑛)从小到大做一个排序，但是这样的话复杂度是nlog𝑛，明显会使得效率大大降低。实际上我们每次只要取到最小值就够了，也就是说我们并不用保持全局有序。考虑到这个，程序中用了优先队列（弗洛伊德最小堆）来维护这种有序关系。即将队列里的元素存储成一个二叉堆的形式，保证所有父节点小于等于子节点。这样每进来一个元素，只需做一次复杂度为log𝑛的上滤操作即可（出队同理）。4.1.3A*算法估计函数𝑓(𝑛)=g(n)+h(n)与A算法类似，所不同的是A*算法要保证{g(n)≥𝑔∗(n)h(n)≤ℎ∗(n)所以程序中所使用的g(n)和h(n)分别是这样定义的：𝑔(𝑛)=𝑔∗(n)h(𝑛)=∑∑{[5−𝑡(𝑎[i,j]+𝑑𝑟𝑜𝑝[𝑖,𝑗])]∗𝛿(drop[i,j])}6𝑗=16𝑖=1其中t(x)={𝑥,𝑥≤45,𝑥4，𝛿(x)={1,𝑥00,𝑥≤0，𝑎[𝑖,𝑗]=∑[𝛿(drop[i