找回密码
 欢迎注册
查看: 1790|回复: 7

[讨论] 《天天星消灭》游戏的最佳策略搜寻

[复制链接]
发表于 2023-5-7 12:50:44 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
《天天星消灭》游戏由于局面数多达5的100次方,无法暴力枚举出最佳策略。

本贴打算讨论一下,是否有启发式算法,求出游戏策略的近似最优解。

1.jpg

游戏规则:

每次可以点击一个方块,点击后的效果是消除这个方块所在的同色连通块

消除之后,上方悬空的方块会往下掉

如果是某一列的方块消空了,则右边隔空的列会往左靠

一次消除2个方块得20分,3个方块得45分,4个方块得80分,……,k个方块得k*(5k)分

不允许单独消除1个方块

如果剩下的方块都不可消除,则本局结束,本局的得分为:每次消除的得分 + 奖励分

奖励分的计算方法:如果剩余方块数>9,则奖励分为0,否则奖励分=(10-剩余方块数)*(10+剩余方块数)*20

(上面是在电视上玩的奖励分,如果在手机上玩,则奖励分=(10-剩余方块数)*100)

过关规则如下:

=====

如果第1局得分<1000,则游戏结束,否则晋级第2局

如果第1局得分+第2局得分<3000,则游戏结束,否则晋级第3局

如果前3局得分之和<6000,则游戏结束,否则晋级第4局

如果前4局得分之和<10000,则游戏结束,否则晋级第5局

……

如果前n局得分之和<2000*(2n-3),则游戏结束,否则晋级第(n+1)局

……

=====

假设每一局的10行10列方块的颜色都是随机生成的(5种颜色被选中的概率均为20%且相互独立)

问最佳策略下,能晋级到第n局的概率p(n)是多少?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-5-13 13:18:35 | 显示全部楼层
如果编写一个简单的程序,每次都随机点击一处消除,直到一局结束,

然后多次重复游戏,一旦遇到更高分的结果,就把分数和策略输出来,

那么对于1楼图片里的关卡1,程序的输出结果如下:

=====
第1次随机玩,获得1730分,依次点击的行号和列号为:
(6,5)(4,3)(6,3)(10,9)(8,5)(1,8)(3,1)(4,1)(9,8)(10,5)(7,10)(5,7)(9,8)(10,5)(8,8)(9,7)(8,4)(5,1)(9,2)(10,3)(10,3)(9,6)(10,2)(10,4)(9,2)(10,4)(9,5)(10,5)

第4次随机玩,获得1835分,依次点击的行号和列号为:
(8,4)(10,3)(8,8)(7,5)(3,8)(8,5)(7,10)(7,4)(10,7)(8,7)(6,1)(4,2)(10,10)(7,3)(10,2)(9,3)(9,6)(7,7)(10,6)(10,4)(8,6)(10,4)(10,4)(7,1)(10,3)(10,2)(10,2)

第14次随机玩,获得1880分,依次点击的行号和列号为:
(4,7)(1,1)(8,8)(3,2)(6,5)(5,10)(9,9)(10,9)(9,3)(10,1)(8,6)(8,5)(10,10)(8,2)(9,6)(7,6)(10,5)(6,1)(6,1)(9,1)(8,4)(9,4)

……

第24511918次随机玩,获得5010分,依次点击的行号和列号为:
(8,9)(7,3)(8,7)(8,9)(4,3)(4,1)(4,1)(7,8)(10,10)(8,3)(10,7)(5,6)(9,4)(5,1)(8,5)(6,5)(8,5)(9,5)(9,5)(10,8)(10,3)(10,2)(10,6)(10,4)(10,3)(10,1)

第57852264次随机玩,获得5135分,依次点击的行号和列号为:
(7,4)(7,5)(8,4)(8,2)(2,1)(4,8)(10,8)(3,2)(4,1)(8,2)(7,9)(7,9)(9,3)(9,7)(7,7)(7,4)(8,7)(10,7)(10,1)(10,6)(9,6)(10,4)(9,4)(9,7)(10,4)(9,2)(10,3)

第99350245次随机玩,获得5500分,依次点击的行号和列号为:
(4,1)(8,4)(3,6)(7,3)(5,3)(8,4)(7,6)(4,7)(10,7)(6,7)(8,5)(10,9)(8,2)(5,1)(9,8)(8,1)(10,2)(10,2)(9,1)(8,7)(10,6)(9,8)(10,6)(9,4)(10,6)(10,5)(9,3)(10,3)(10,2)

第230436103次随机玩,获得5720分,依次点击的行号和列号为:
(2,1)(4,2)(8,4)(3,2)(4,6)(4,3)(4,7)(8,4)(4,7)(7,6)(5,1)(9,8)(9,9)(9,7)(8,4)(8,2)(7,10)(10,8)(9,7)(9,8)(10,8)(9,6)(10,6)(10,2)(10,5)(8,3)(10,1)(8,3)(10,2)
=====

虽然程序每秒能随机玩1万局,但我感觉还是太低效了,很难玩出更高的得分。

我们接下来应该怎样优化程序,才能让它更快地搜寻到更优的策略呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-5-14 07:44:11 | 显示全部楼层
在随机玩出5720分的基础上,模仿这局的策略,以(2,1)(4,2)(8,4)(3,2)(4,6)(4,3)(3,7)为开头,进行地毯式搜索,目前得到了1个6015分的策略:
(2,1)(4,2)(8,4)(3,2)(4,6)(4,3)(3,7)(4,1)(4,4)(5,5)(7,3)(9,2)(9,8)(9,9)(10,8)(8,9)(8,8)(9,6)(8,8)(8,5)(8,4)(9,2)(6,10)(9,5)(7,4)(9,4)(9,4)(10,5)(10,4)(9,3)(9,3)(10,1)(10,1)

#####2023-05-16 20:25更新#####
以(2,1)(4,2)(8,4)(3,2)(4,6)(4,3)(3,7)为开头的分支终于暴力枚举完了,这个分支下的最高得分是6135,策略是:
(2,1)(4,2)(8,4)(3,2)(4,6)(4,3)(3,7)(4,1)(5,5)(7,3)(8,4)(9,8)(9,9)(10,8)(4,6)(8,9)(8,8)(9,6)(7,4)(8,8)(9,2)(6,10)(9,5)(9,4)(9,4)(10,5)(10,4)(9,3)(9,3)(10,1)(10,1)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-5-14 10:31:37 | 显示全部楼层
不应该贪心,尽量先选择数目多的吗?
残局比较好处理,可以动归。开局是不是可以试一试选择几个数目较多的方案,试探几次,然后减枝,不知道效果会如何

点评

在此基础上,最佳策略还会很巧妙地收拾残局,最后只剩1个方块,奖励了1980分。这6千多分有将近2千是奖励分,3千多是单次消除得分,还有几百分是散乱的消除得分  发表于 2023-5-17 10:39
会尽量把数目最多的方块连在一起消掉,例如1楼的局面,红色最多,最佳策略是巧妙地消除其余方块,让红色连在一起,然后一次性消除20多个红色方块,一步得到3000多分  发表于 2023-5-16 20:31
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-5-17 10:36:48 | 显示全部楼层
写了一个估价函数,

然后每个局面只枚举估价函数值为前2名的走法,耗时0.1秒,没有枚举出更优解;

然后每个局面只枚举估价函数值为前3名的走法,耗时2.5秒,没有枚举出更优解;

然后每个局面只枚举估价函数值为前4名的走法,耗时44秒,得到了1个更优解:
6170(3,6)(2,4)(9,9)(1,1)(8,3)(4,6)(5,5)(7,3)(4,1)(9,2)(9,2)(5,1)(8,2)(8,4)(8,9)(9,6)(6,7)(5,10)(10,5)(10,4)(9,3)(9,6)(10,5)(10,4)(9,3)(9,2)(10,1)

然后每个局面只枚举估价函数值为前5名的走法,耗时28分钟,没有枚举出更优解;

然后每个局面只枚举估价函数值为前6名的走法,耗时7.4小时,得到的更优解是:
6250(3,6)(2,4)(9,9)(8,3)(4,6)(5,5)(7,3)(4,1)(9,2)(9,2)(5,1)(8,2)(8,4)(8,9)(9,6)(6,7)(5,10)(10,5)(10,4)(9,3)(9,6)(10,5)(10,4)(9,3)(8,1)(10,1)
6330(3,6)(4,2)(3,3)(3,4)(4,1)(3,1)(8,3)(5,1)(5,5)(7,3)(9,2)(9,2)(8,4)(9,1)(9,8)(8,9)(6,8)(5,6)(5,7)(9,6)(9,9)(8,5)(8,8)(6,10)(10,5)(10,4)(9,3)(10,4)(10,3)(8,2)(10,2)(9,3)
6380(2,4)(4,2)(3,3)(3,1)(4,1)(4,7)(8,3)(2,5)(3,6)(4,7)(7,3)(8,4)(8,2)(9,2)(9,1)(6,5)(9,8)(8,9)(9,9)(8,8)(8,8)(5,6)(9,1)(10,4)(9,2)(9,1)(10,1)

然后每个局面只枚举估价函数值为前7名的走法,耗时2.4天,得到的更优解是:
6500(3,6)(2,4)(4,2)(3,3)(3,1)(4,1)(4,1)(8,3)(5,5)(7,3)(8,4)(8,2)(9,2)(9,8)(9,9)(5,6)(10,8)(5,7)(8,9)(8,8)(9,6)(8,8)(6,6)(9,5)(9,4)(9,4)(9,3)(10,1)(9,1)(9,2)
6550(3,6)(4,2)(3,3)(3,1)(4,1)(4,1)(8,3)(5,5)(7,3)(8,4)(9,8)(9,9)(5,6)(10,8)(5,7)(8,9)(8,8)(7,4)(9,2)(9,6)(8,8)(6,6)(9,5)(9,4)(9,3)(9,3)(10,1)(9,1)(9,2)

然后每个局面只枚举估价函数值为前8名的走法,耗时7天,得到的更优解是:
6640(3,6)(2,4)(4,2)(3,3)(3,1)(4,1)(8,3)(5,5)(7,3)(8,4)(8,2)(9,2)(9,8)(9,9)(5,6)(10,8)(5,7)(8,9)(8,8)(9,6)(8,8)(6,6)(9,5)(9,4)(9,4)(9,3)(10,1)(7,1)(9,1)(8,2)
6690(3,6)(4,2)(3,3)(3,1)(4,1)(8,3)(5,5)(7,3)(8,4)(9,8)(9,9)(5,6)(10,8)(5,7)(8,9)(8,8)(7,4)(9,2)(9,6)(8,8)(6,6)(9,5)(9,4)(9,3)(9,3)(10,1)(7,1)(9,1)(8,2)

然后每个局面只枚举估价函数值为前10名的走法,耗时16天,得到的更优解是:
6720(2,4)(3,6)(8,3)(5,5)(7,3)(8,2)(3,1)(8,2)(7,2)(4,1)(10,7)(9,9)(10,8)(5,5)(8,4)(5,7)(8,9)(9,6)(8,8)(8,8)(8,1)(9,5)(9,4)(9,4)(10,3)(10,1)(7,1)(9,1)(10,1)
6760(4,2)(3,1)(8,3)(5,5)(5,4)(7,3)(4,1)(8,4)(10,7)(9,9)(10,8)(5,5)(5,7)(8,9)(8,2)(9,2)(9,6)(8,8)(8,8)(8,1)(9,5)(9,4)(9,4)(10,3)(10,1)(7,1)(9,1)(10,1)

然后枚举所有可能的走法,耗时30天,没有枚举出更优解

因此得出结论:

对于1楼的局面,所有可能的走法中,得分最高的走法是:
6760(4,2)(3,1)(8,3)(5,5)(5,4)(7,3)(4,1)(8,4)(10,7)(9,9)(10,8)(5,5)(5,7)(8,9)(8,2)(9,2)(9,6)(8,8)(8,8)(8,1)(9,5)(9,4)(9,4)(10,3)(10,1)(7,1)(9,1)(10,1)

其中:

估价函数值=当前得分+最大消除分+最大奖励分

最大消除分=求和(5*该颜色的剩余个数^2)for(剩余个数大于1的颜色)

最大奖励分=(10-剩余个数为1的颜色数)*(10+剩余个数为1的颜色数)*20

剪枝条件:

对于 估价函数值<=当前最高得分 的分支,则直接跳过,不进行更深层次的枚举
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-6-10 21:48:30 | 显示全部楼层
在手机上玩,发现奖励分的计算方法和电视上玩是不同的:

电视上玩的奖励分:(10-剩余方块数)*(10+剩余方块数)*20
手机上玩的奖励分:(10-剩余方块数)*100

现在要在手机上玩,因此需要修改估价函数:

估价函数值=当前得分+最大消除分+最大奖励分
最大消除分=求和(5*该颜色的剩余个数^2)for(剩余个数大于1的颜色)
最大奖励分=(10-剩余个数为1的颜色数)*100

然后继续按照楼上的算法搜寻最佳策略,

然后借助哈希map,把以前搜索过的局面跳过(否则会遇到大量相同的局面,重复处理它们浪费很多时间),

然后再借助剪枝条件,很快就完成整个策略空间的搜索了

搜索结果标明,取胜的关键是想办法把同一颜色的方块堆在一起,

1686402928348.jpg

然后一次性消除大量的方块,如下图所示:

1686402928343.jpg

换一个关卡,也是类似的策略:

1686402928355.jpg

这样每局的期望得分应该是可以保持在4000分以上的,

所以在N很大的时候,能过N关的概率应该会收敛到一个大于0的常数,而不是0
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 14:28 , Processed in 0.071290 second(s), 23 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表