• 2019-02-17 09:50:58
  • 3075 views

关于编程求解消除王最大解的尝试(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。该加的注释都加进去了,欢迎阅读。

https://paste.ubuntu.com/p/qxKs2MXMcV/

三、 FAQs

Q:你为什么会想到写这么一个程序?

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

 

Q:你想了多久?

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

 

Q:接下来你打算做什么?

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

 

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

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

 

 

四、 存疑

 

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

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

 

发表回复

  • 素衣
  • 2楼
  • Played game for 249 hours 37 minutes
不明觉厉
牛逼牛逼
TIP:

因为掉落补充(主要是补充)的模拟有问题,代码暂时还什么都做不了... 只是大致看看思路,算法的。
收拾一下去召合上班!
  • Bin.Go
  • 6楼
  • Played game for 586 hours 25 minutes
不明觉厉
  • 嗷哟.
  • 7楼
  • Played game for 107 hours 39 minutes
....牛
  • 阿柴
  • 8楼
  • Played game for 2 minutes
nb!膜拜!
另外告诉你消除王的图和掉落是固定,有循环的,如果每天录屏记录一轮第一名的操作步骤,接下来每一轮你都可以照着走,天天都是第一名哦/手动滑稽
  • 竟然有这招,怪不得排名无奖励

  • 啊?我就知道掉落是一组12个循环,3个家族各4个。。。

  • Beike
  • 9楼
  • Played game for 211 hours 36 minutes
消除王纯粹混熟练度,真想开个自动......
  • 10楼
  • 2000+ hrs on record
阔怕  !!
  • 莫小年
  • 11楼
  • Played game for 419 hours 45 minutes
假装能看懂
楼主很厉害,具体看不懂,不过消除王拿第一与最后一名有什么区别么?
楼主有这个本领,不如开发一个竞技场的合成解决方案,肯定比这个火。
  • 消除王和竞技场的区别就是补充队列是否可知而已,消除王搞定了,竞技场才有希望搞出来,路要一步步走嘛。

  • 那给你加油。

  • 首先竞技场没那么容易做因为还要考虑对面战力。然后,竞技场如果真的写了也不会轻易挂tap,不然别人没得玩了...

我觉得有必要叫燃灯大湿他们过来!!!
(突然想起来燃灯大湿刚升级做父亲,还在喜悦中估计没空)
让橙子小姐姐把老冰跟彪哥叫来跟你透露下具体掉落合成规则吧!!!
  • 找不到他们...

  • QQ群里私聊应该比较靠谱,或者微信公众号询问这样子

  • 小木水
  • 14楼
  • Played game for 511 hours 5 minutes
假装能看懂系列
遗传算法会不会更有可能收敛到全局最优解呀
楼主做的是很优秀的工作,尤其是横>竖>斜,是具有洞见的。这里我提出几点看法,希望帮到楼主:
第一,关于大连块的消除原理,用一张图做一个猜想
这里我用绿色代表不会受到影响的区域,蓝色代表会受影响的其它怪物,实际上对1而言这一块有两个连接点,即有边框的两格,这时我们分别考虑这两个连接点,结合“横>竖>斜”原则,就会发现出现了这样两个2,至于1应该是都消掉了的。但是我目前没有见过这么神奇的情况,甚至难以设计出,但是楼主应该看一眼就知道是怎么回事了。
第二,关于掉落补充,在我所见过消除中,这种掉落就是从左到右从上到下的。
我认为,消除过程是一个消除-掉落-补充的循环过程,直到掉落后无法消除为止,消除规则上已叙述,至于掉落,我猜测是这样的:

全部掉落后,序列中的前6个白怪应该会顺序落到第1列、第2列、第3列、第3列、第4列、第4列,这个顺序据我观察是没有问题的。

这是关于规则的问题。
你怎么这么骚啊
关于算法问题,穷举是不可能穷举的,单步最佳一定是基本思路,当然在此基础上还可以作出一些补充的规则,我建议先不要考虑。
我没有观察过消除王的补充序列,如果是循环的,又是固定的,那完整的无限序列就是已知的。
就我个人经验,消除王中好的步骤一定是每一步都造成消除的,竞技场中不可预见的序列同样不适合说先单纯交换,然后下一步来个超级连消,所以每一步也不是穷举所有可能操作,而是穷举所有会造成消除的操作(拖出或交换)。那么我们就可以从二连(包括ABA这种)出发来寻找造成消除的所有操作。当然紫怪需要单独考量,这一点可以再议。
对于消除,首先要有一种描述方法,譬如前述的一个经典过程:

这个过程我把它称之为5+5,…(“,”表示掉落补充,“…”代表后续不可预知),对于任何一个消除过程都可以这样描述,比如一个简单最简单的消除的描述为3,一个简单双消描述为3+3,一个如下的连消描述为3,3。
根据这种描述我们可以进一步做一些数学的工作来优化判断“单步最佳”的准则,有时间的话我会再推进。
楼主所说的R群我找不到哈,楼主想找我沟通的话可以Q825346034,记得备注。
  • R群是2063917。还有那个补充真的没这么简单,你多试几个状态就知道一般的从下到上从左到右都不符合实际了。

明天到召合UC震惊部上班

优秀的ACMER
真的是大佬😂
求群号 或是私戳方式
大四计算机学生面临毕业,毕业设计选择了《三消游戏的较优解》这个课题(没错就是玩召合想到的,肯定也是升级与保留这个模式)
有不少想法,希望交流
  • R群群号2063917 我Q是438521303

13楼说的那个找燃灯和冰姐 在哪里找啊...
  • 都是官方制作人员,可以去官方发布的帖子里找。

楼主可以回来试试新的战旗模式的模拟算法嘛,我觉得更有用些
作为一个大学生,这种主动去解决问题,并不断学习,且有耐心做重复的事的态度是最棒的
App 内打开

We recommend you to visit TapTap global site. If you still need CN content, you can choose to click Download App.