一、游戏介绍
最近在3366玩了一个小游戏，觉得挺有意思的，游戏名字叫《十滴水》，
游戏地址：http://www.3366.com/flash/1000154.shtml
游戏规则如下：
一开始玩家有10滴水，玩家点击格子就会在格子里增加1滴水。
水滴达到4滴后再加水就会破裂，破裂后会向四个方向溅出四滴水。
点击水滴使水滴爆破产生连锁反应，利用连锁反应消掉全部水滴。
水滴用完则游戏结束，同时破裂3滴水滴会增加1滴水，过关也会增加1滴水。
我试玩了一下，居然只过了7关：
作为一个24k的纯屌丝，怎么可能忍受排名比好友落后呢？
所以我试着用Python写了一段自动解十滴水的代码。
二、编程过程
1、游戏的数据结构
由于格子有66格，所以可以用66的二维数组来保存数据，
数值是水滴数，如果格子上没有水滴就是0。 如上图的水滴数可以表示为：
1 | t_list = [ |
2、水滴引爆后的计算
在某个格子上增加1滴水，会出现两种结果：如果增加后数值不大于4，则不会引爆水滴；
如果数值大于4，该格子的水滴数变为0，并向4个方向溅出4滴水。溅出的水滴们每次移动一格，碰到其它水滴或超出边界则停止运动。
(1)、使用递归(错误)
一开始用了递归的方法写算法，但是有时算出的结果和在游戏里实际操作的结果不同，
因为假设有一种局面是这样的：
1 | 0 0 0 0 |
在第4行第2列滴上1滴水，如果用递归的方法，会先向一个方向执行运算，直到返回结果才会向另一个方向运算。
如果递归先向左运算的话，(4,2)会引爆(4,1)、(3,1)、(3,3)，这时(3,4)会增加1滴水变成4滴，然后(3,3)会引爆(4,3)，这样最后剩下1滴水滴。
如果递归先向右运算的话，(4,2)会引爆(4,3)、(3,3)，这时(3,4)会增加1滴水变成4滴，然后(3,3)会引爆(3,1)，(3,1)向右的水滴会引爆(3,4)，最后所有水滴都爆掉了。
这样会出现两种不同的结果，事实上游戏里溅出的水滴都是匀速运动的，溅出的水滴到达某个格子都存在一个距离的问题，而递归不能达到这个效果，因此这里不能用递归。
(2)、不使用递归
不用递归的话，就要用数组把溅出的4滴水滴的坐标保存起来，比如在坐标(2,3)处增加1滴水引爆了，则引爆数组可表示为：
1 | t_burstlist = [ |
再用一个数组来保存4个方向，分别表示向左、下、上、右移动：
1 | t_direction = [[-1,0], [0,1], [0,-1], [1,0]] |
每循环一次就把引爆的坐标加上方向值，得出新的坐标，比如第一次移动后新的坐标就是：
1 | t_burstlist = [ |
先判断坐标点是不是超出边界（小于0或等于6），超出边界就不处理。
如果没超出边界，就判断坐标上的水滴数。
如果水滴数为0则不处理。
如果有水滴就把引爆数组里的对应的坐标置为(-1,-1)，如果水滴数小于4就加上1滴水，否则就把水滴数置为0并把该坐标保存到引爆数组里。
循环直到所有水滴超出边界为止。
3、寻找最优解
找出最优解，一般都是采用贪婪算法，类似于中国象棋的AI算法，具体过程如下：
(1)、广度优先搜索
找出所有水滴的坐标，分别在每个坐标滴上1滴水，然后找出里面最优的局面。
但是只进行1层搜索往往找不到好的走法，所以要进行多层搜索。但搜索的层数越多，得出结果所花的时间就越多。不过对于6*6的数组来说，运算量不大，一般搜10层就够了，因为解出来的结果一般只需用到5滴水，很少有超出10滴水的。
比如图上有10个格子有水滴，做法就是分别在每个坐标滴上1滴水，得到10个局面。再在每个局面的每个有水滴的坐标分别滴上1滴水，然后找出其中最优的局面替换原来的局面。这样循环n层后再看哪个局面最优，就知道该点击哪个坐标了。
(2)、局面的评估
怎么知道一个局面的优劣呢，这就需要用一个数值来评估了。
比如一个格子上有4滴水总比1滴水好，因为4滴水容易引爆。所以可以按水滴数来评分，1滴算1分，4滴算4分。
但是越多格子有水滴就可能越难消除，从另一个方面来说越少格子有水滴越好，所以如果一个格子有水滴就减5分。
还有看看下面这两个3*3的局面：
1 | 4 0 4 | 4 0 0 |
虽然分值一样，但是第一个图需要1滴水就引爆了，第二个图需要两滴，所以还要找出图中孤立的格子（上下左右都没有其它水滴的格子），1个孤立的格子减1分。所以第一个图的评估值是-2分，第二个图是-4分。
当图上所有水滴都引爆时评估值为0分，0分是最大值。
评估方法都不是绝对的，大家可以再根据一些局面增加评估分，这样得出的结果可能更优。
(3)、挑选较优局面
在贪婪搜索中，对所有局面按评估值进行降序排序，排在前面的就是最优的局面。一旦搜到0分的局面就可以返回不用再搜索了。
4、算法验证
算法写好后，测一下上面的例子：
再到游戏里点击第4行第4列的点，游戏画面变成：
可见结果是正确的（不正确就不会发出来了）。
三、使用算法玩游戏
目前不能自动识别游戏界面的水滴数组，所以要自己手动输入太麻烦，所以只玩到了31关，下次再写个自动识别图像的程序吧。