关于编程求解消除王最大解的尝试（by:wallknight）

概要：

一． 问题分析

1.1 消除王简介

1.2 一些我们不知道的设定

1.3 穷举就好了？

1.4 NP问题

二． 解决方法（算法）

2.1 解开枷锁

2.2 估价函数

2.3 完整算法流程

2.4 代码

三．FAQ及一些可能的改进策略

四．存疑

一、 问题分析

1.1 消除王简介

按照惯例还是要先介绍一下消除王。

“我是消除王”是《召唤与合成》中最体现消除技术的一个模式。

1） 随机，有石块沙盘进行不超过50步的合成。每一步可以任意交换两个砖块或拖拽出一个砖块。每消除或拖拽出一个白+10分，绿+40分，蓝+160分，紫+640分，橙+4000分。最后得分为每一步得分的相加

2） 接下来掉落的前4个怪会给出①。

1.2 一些人们不知道的设定

以下规律为我自己探索得出。不得不说召合其实还有许多值得我们去探索的东西，这些本该都是最基本的规律我们都还不知道。

1） 每期沙盘的掉落，都是十二个为一组循环的。第1，13，25… 都是一样的。

2） 关于合成出的高级怪的位置：

一般地，如果是通过交换产生的消除，补充的高级怪一定在交换怪的位置。

如果是掉落，按照如下法则生成：

① 对于所有消除块（单行，单列，单条对角线）

先生成一个子消除点（无实际意义，只是为了方便说明），位置为从上到下从左往右第二个。

②生成完毕后，取最高的。

Tip:如果有两种消除块最高，优先级横 > 竖 > 对角线。

如果两种消除块类型相同一样高，取左边的。

举例说明：（1为普通，2为目标位置，1.1为子消除点）

1.3穷举就好了？

分析完问题，我们接下来来思考一下如何用编程来解决。

其实，像这样的问题，如果提到编程，就算不是专业人士也知道“厉害的人，可以写个程序穷举”。

然而… 在程序设计中，有个“时间复杂度”的概念。 别着急，我会用通俗的话来解释它。

通常的计算机，每秒钟可以计算十亿次基本运算（加减乘除）。是不是听起来很快？

但是我们来看一下总共的状态数有多少。极限情况6*6的沙盘，50步，每一步可以交换两个或者拖一个。可能的操作是6*6*6*6 + 6*6 = 1332种。 所以所有的情况有1332的50次方种。

就算是1000的50次方，也是10的150次方。

有限宇宙的总质量也就是10的82次方千克。让计算机来跑，宇宙可以从大爆炸到毁灭一亿亿亿亿亿亿……次。

傻子也不会这么做。我们会发现，这样的茫茫多中情况中其实有99.99999999…%我们都是不会用到的。举个最简单的例子，虽然每次都找局部最大消除量肯定不会最优，但我想一般人在玩这个模式的时候，从来不会主动空换两个不会产生消除的怪也很少拖怪，而经过估计，对于绝大多数的状态，会产生消除的步数也就是那么十几种。

但是，按20种算，总状态数就是20的50次方。计算机最最起码要跑10的40次方年，足够太阳系出现到毁灭一亿亿亿亿亿次。

……

那怎么办呢？别着急，我们先来看一个理想的状态。假设我们研究的问题，每一步都可以找到一个唯一最优解，并且后面只要一直跟着这个状态走就可以找到最优解了。

那么计算量一下就变成了1332*50，一秒出解不解释。

显然现实不可能是这样。不过不难发现，这种方法快的原因就是每当你在移动一步的时候，不需要考虑之前做了什么，只需要为当前状态找到最优解，当所有这一阶段的状态的最优解都处理出来之后直接重新取最优就可以了。 所以我的想法，就是往这个方向靠拢。每次移动一步并且找出一些比较优的情况，每次都只研究他们并在所有的结果中再取等量比较优的情况。假设每次要取N个，做判断消除的复杂度大概是6*6*36，那么复杂度大概就是1332*50*N* （6*6* 36）.我取N= 7，如果真正能完成，那15秒之内应该是没问题的。

1.4 NP问题 ②

相信坚持到这里的人肯定要问了，那你打算怎么找这个最优情况？

很遗憾，对于我自己的做法我也给不出很合理的证明。它也不存在那种真正的完美做法。像这样的问题，在编程的学问当中被归类为“NP问题”。对于不了解它的人来说，这个词可以理解为“解决所需时间空间为玄学”的问题。这也就意味着，以后这个问题很可能会收到一个更优的解。

好了，扯了这么多，让我们开始进入正题吧。

二、 解决方法

2.1解开枷锁

有了前面那么多引入，我们开始来规定这个“最优”。 首先自然会有一个数字N这个“最优”将由如下3部分的值组成。

①当前分数。没有什么好解释，分数是我们的最终目标。对于每个状态，我们都会有一个分数。

但这当然不够。究其原因，主要有两个致命问题。首先，如果每步都追求分数，那毫无疑问把合出来的绿，蓝直接拖下去会是一个相当优的决策。其次，别忘了，紫橙出来是要+1步的。它们是不是要和这些一起考虑？

这两个问题我会在下面两个小节里解释。

2.2估价函数

②估价函数的值。对于每个状态我们设计这样一个估价函数。它的值为，当前场上前X大的分数值（不包括紫，橙，X为剩余步数且最多为沙盘大小）

为什么要这样设计？因为这代表假如你在剩下的步数里只做“把场上的怪拖到外面”这件事情的话你能获得的最大分数。这是你分数的一个下限。而③自然是场面上紫橙的分数总和。

2.3边界处理

至于紫橙，我的处理方法是这样的。 首先，每一步结束后把所有拖紫和橙的状态拿出来，再做一步（因为步数+1），如果局面中有多个紫和橙，重复之。需要这样处理的情况自然不多，因为紫橙是有限的。按照这样的方法处理所有步数大于1的状态。在你只剩下最后1步的时候，按照从下往上的顺序把沙盘里所有没有拖出的紫橙拖出去，再消除一次以得到最大得分。

综上，我们每模拟出一个状态，便关注这个状态下，得分+估价函数+紫橙分所得到的值。前N（代码中N= 7）个状态会被保留下来。我相信这样的计算方式不会让程序因为拖蓝紫而将其判定为最优或最劣。

2.4算法

说了这么多，终于要给出全算法了。括号部分是给那些

流程如下：

0）定义每个状态包含如下内容：沙盘状态、沙盘剩余步数、分数、已消除怪物数、三部分的得分。

1）读入初始状态及目标步数，把它压入到步数为“steps”的堆（一种便于维护前几个最大值的数据结构）中。

2）每次把每一步当中那些保留的状态拿出来，进行消除。交换或拖白绿之后没有消除的状态直接扔掉。

3）把拖了紫和橙的状态拿出来，重复2），递归到没有紫橙为止。

4）每一步的所有状态都做完后，保留（得分+估价函数+紫橙分）最大的前N= 7个状态。继续下一步。

5）当只剩下一步的时候，每拿出一个状态时先把沙盘中紫橙按照从下到上的顺序拿出来，再进行结算。完毕之后，得到最大分。

2.5代码

目前就编程时间写了11小时左右，共499行，CPP。该加的注释都加进去了，欢迎阅读。

三、 FAQs

Q：你为什么会想到写这么一个程序？

A： 因为推了一些图之后感觉研究它比刷魔王和刷图更有意思也更有意义。用曾经一起玩PVZ的那些人的话来说，这也应当算是召合游戏文化的一部分。

Q：你想了多久？

A： 非常久，除去进入状态之类的时间20多小时吧。首先在研究那些游戏机制的时候，有几次真的会有点心烦。不过也罢了，我觉得这些是我作为一个没有收入的准大学生向一个极微氪游戏致敬的一种很好的方式。

Q：接下来你打算做什么？

A：与更多人交流这个算法。同时我也很期待与召合的程序员对话。至少就现在来看如果我能知道那个掉落顺序以及消除补充的完整规律的话我应该可以把整个程序调试出来。我相信他们不可能是随机生成的。

Q：你写好了这个东西，是不是意味着消除王以后不用玩，直接问你来要程序就好了？

A：首先，到目前为止，如果掉落和补充的算法不知道，这个问题还并没有完全解决，如果有幸真正完成，那可能在给程序的时候我会先给官方。其次就如同我前面讲的，这本质上是一个NP问题，没有100%完美的方法求出最大解，只能想一些近似的方法用以解决大多数情况下的最大解，就算写出来，我暂时也不能证明他就是完全正确的。况且，消除王第一并不会给人带来什么实质好处：你拿了第一名，你也不能比别人多拿一个宝蛋啊。

四、 存疑

这个算法还有许多不完善的地方。比如，考虑到有大连消的一般是前8-10步，是不是可以考虑在这些步数上保留多一些状态，而到后面保留少一些？比如，在写估价函数的时候是不是可以考虑一下图形容不容易连消？可不可以每次枚举两步来减少N的值？更重要的，那个拖紫橙的地方，其实如果好好写是需要枚举拖动顺序，有9个紫橙就要9! = 362880次枚举的。是不是可以在优化呢？

我已经写了近500行代码，想不动那么多细节了。欢迎各位思考并来R群找我。