Splash Back搜索程序

大家可能以前都见过一个叫Splash Back的Flash小游戏,游戏中有一个放着大小不等水滴的棋盘,玩家可以点击水滴使水滴变大,变大到一定程度的时候,水滴就会爆开,然后向上下左右射出水滴。我这里说也说不太清楚,反正大家去玩玩就知道了。这里有我下载的版本,大家想玩的话也可以直接在google搜索"splash back"或者国内的叫法“十滴水”。

最近在松鼠会论坛,流浪的鲥同学又把这个游戏翻出来了,一时技痒,写了个搜索解的程序。

其实思路也很标准化。首先,这是个单人游戏,没有明显的可以应用的算法,所以基本上就是靠搜索。典型的一局需要5~11着,平均大概需要9着,所以复杂度大概是36^9约等于2^46,如果对于比较后期的复杂局面的话,最优解有可能需要10着以上,整棵树的搜索复杂度就更高了。所以,为了在合理时间内得到解,进行大规模的剪枝是必须的。

然后就是搜索的方式,深度优先搜索对余下水滴少的局面比较有效,可以找到最优解,而且剪枝也很直观。但对于一般情况来说,由于搜索树很深,而且对于搜索深度没有一个好的上界,所以搜索很容易会被困在一枝很深的树枝中长久出不来,所以不能直接应用深度优先搜索。这种情况下,广度优先搜索是一个比较好的办法,但是由复杂度的计算看来,扩展的局面数目会非常多,内存也吃不消。所以,剪枝是必须的。

对于这种游戏的解的搜索,很常见的一种方法就是给每个局面赋予一个评价函数,然后根据评价函数的优劣来决定扩展哪个节点。如果对某个局面的评价函数是从起始状态到达这个局面的代价,再加上一个从这个局面到终结状态的代价的乐观估算的话,我们就得到了A*算法,一个在人工智能界有名的heuristic搜索算法。很遗憾,对于这个游戏,我没有想到一个对某个局面到终结状态代价的非平凡的乐观估算方法,所以虽然整个框架跟A*很像,这个算法只是很普通的Best-first搜索。

对于这种Best-first搜索来说,评价函数的选取是很重要的。我自己写了个,想法就是空格越多越好,水滴越饱满越好,手里加水滴的机会越多越好,根据这三个指标,我选取了以下的评价函数:f(Board)=2*v2(Board)+5*v3(Board)+9*v4(Board)+10*v0(Board)+25*drops(Board),其中v2, v3, v4, v0分别是2, 3, 4, 空格的个数,drops是手里加水滴的机会数。这不一定是很好的评价函数,因为也没有考虑到水滴之间的相互作用,但是这个评价函数比较好计算。

然后,由于要扩展的局面很多,所以必须剪枝以保证不消耗太多内存,这时候我借鉴了一下A*的某个有内存限制的版本,SMA*,用以限制内存使用。但是,由于我选择了最简单的,用数组实现的二叉堆来做优先队列,我没有办法简单地去除那些最差的结点。这时候的折衷方法就是直接砍掉数组的一半,也就是说砍掉了二叉堆的所有叶子结点。这样,即使不是去除了最差的结点,也达到了去除较差结点的目的。当然,这是以丢失解的可能性为代价的。

最后,如果在扩展的时候遇到一个小的局面的话,可以直接用深度优先搜索搞定。当然在Best-search的时候,各种可能的剪枝也是需要的。

算法框架的一个简单总结如下:根据我写的对局面的评价函数,我们可以计算每个局面的大致的优劣程度。在搜索开始时,把初始局面扔到一个以评价函数为优先级的优先队列里边,其实也就是用初始局面来初始化一个都是局面的堆。然后重复做如下的事情:从那堆局面里边挑出评价函数最好的局面,如果这个局面很小的话就直接用深度优先搜索处理了,否则就将一步内可以到达的局面生成出来,然后扔到堆里边。如果堆里边太多局面的话,就直接将堆里边所有叶子舍去。

这里是解答程序Solver的下载链接,以GPLv2发布。

这个程序当然还有可以改进的地方(我一共才写了三天左右)。首先是生成的局面显然是很可能有重复的,现在没有对这些重复的局面进行处理,不过可以考虑用一个简单的hash来区分它们,然后剪去较差的局面。其次评价函数也是不知道好不好的,可以尝试去改善它。

这个程序的性能还不错,在我的机器上很多时候稍等片刻就能得到(搜索的)最优解(当然中途出现的解也是可以用的)。仅靠这个程序,在原版的Splash Back中可以到达43关,添加水滴的机会可以到达游戏可以显示的最大数值99。

果然我还是患上拖延症了么……在还有实习报告要写的时候弄这个东西……

Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s