最近看到Master_Chivu的博文[Drops 十滴水] 强大的搜索(中)，博文主人使用深度优先与广度优先相结合的方法搜索放置水滴的最优序列。

此游戏可参考十滴水页面。

规则比较简单，6X6的棋盘上有大小不同的水滴，共有五种状态[0,1,2,3,4]，每加入一滴水就会使水滴体积变大，当水滴体积为4的时候，如果有外来水滴汇入，则该水滴会爆裂为上下左右四个方向上飞行的水滴。飞行的水滴将于沿途遇到的其他静止水滴合并（不与飞行的水滴合并），到达边界时消失。

游戏的目的是使用最少的水滴（棋盘右侧显示还剩余多少可使用的水滴），利用水滴爆裂的连锁反应消除棋盘上所有的水滴。

我尝试了一下，手工玩我也就最多玩到Level4，看来机器求解还是很有发展空间的。Master_Chivu给出了搜索算法的源程序，但没有使用启发式策略，按照他的说法称为“裸搜”。但是Master_Chivu也提到使用启发式算法会使搜索效率提高，这句话倒给我了启发。

我的研究方向是自然计算，而而自然计算很多应用都是优化算法，能不能使用哪一种自然计算算法求解最优序列呢？

搜索空间在6步的时候就会达到36^6=2 176 782 336，20多亿种状态，枚举当然不行，随机搜索更不行。由于状态之间是离散的，粒子群算法和差分进化并不能体现很大的优势。选来选去，还是传统的遗传算法实现最简单。

 

具体实施方法如下

1）令最大序列为N，种群规模为D，随机生成2DXN的矩阵XX，并满足

奇数行为序列的横坐标，偶数行为序列纵坐标，每两行组成一条染色体。

2）使用每条染色体代表的序列，应用于初始棋盘状态AA，AA满足

每次在染色体代表的一个坐标相对应的棋盘位置上加以水滴，待棋盘状态稳定（没有处在飞行状态中的水滴）后，按顺序应用序列中第二组坐标，直到棋盘上元素之和为0或到达序列尾部。

3）记录每条染色体使棋盘清零所需的步数，若未清零，则步数为N。

4）按照染色体清零棋盘步数大小排序，使用步数的倒数为适应度，并使用轮盘赌按照选择概率Ps选出Ps×D条染色体。使用随机值重新生成剩下的D-D×Ps条染色体，组成新的种群。

5）按照交叉概率Pc选择D×Pc条染色体，随机进行单点交叉。新生成的染色体与未交叉的组成新种群。

6）按照变异概率Pm随机选择D×Pm条染色体，并在随机的位置初始化一对坐标。

7）返回第2步或到达最大迭代次数后终止，返回清零步数最小的序列与所需步数。

 

上面的算法使用Matlab实现，并测试了效果。在Level10之前，基本上种群数20，最大序列25，迭代次数500就可以找到比较好的解，每次寻优过程在我的老机器上大概需要30秒。我用这个程序给出的序列去玩十滴水，效果还真不错。

如图

打到Level16的时候还有42个水滴，到达Level20应该不成问题。

 

存在的问题：

Level10以后出解的效率降低，经常出现十步以上的最优序列，而根据经验，如果要一直持续的进行升级，步数应该控制在12以下。增加了最优个体保存策略，并降低了选择概率（剔除很多无用的染色体，他们的清零步长全是最大值），提高变异概率后，可以坚持到Level16以后。但在测试中，这一局却始终找不到满意解（低于20），尽管曾经解出过18步的解，但由于对水滴消耗太大，暂时没有采用。

 

改进的建议：

适应度选取了清零步长的倒数，可以使清零步长最小化，但是游戏过程中每连续消除三个水滴将会获得一个奖励水滴，这个并没有计算在内。由于游戏的目的应该是在一局结束的时候使剩余水滴数达到最大，那么使用步长（消耗水滴）+奖励水滴=剩余水滴作为适应度应该更为合理。此外，由于能力有限，找不到很好的描述棋盘特性的数学表达，这也制约了算法设计。转化为纯数学问题的求解应该效率更高。

 

总结：

很多益智游戏的本质是求解最优序列，而且他们的求解难度并不比常用的标准测试函数低。测试一种算法最好的办法就是拿到实际中使用。

 

水平所限，文中内容难免出现错误，请看官不吝赐教。也希望本文能起到抛砖引玉的作用，引起大家对智能计算的兴趣。

转载本文请联系原作者获取授权，同时请注明本文来自张永韡科学网博客。
链接地址：https://m.sciencenet.cn/blog-477321-364286.html