《天天星消灭》游戏的最佳策略搜寻

KeyTo9_Fans

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

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



游戏规则：

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

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

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

一次消除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)是多少？

KeyTo9_Fans

如果编写一个简单的程序，每次都随机点击一处消除，直到一局结束，

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

那么对于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万局，但我感觉还是太低效了，很难玩出更高的得分。

我们接下来应该怎样优化程序，才能让它更快地搜寻到更优的策略呢？

KeyTo9_Fans

在随机玩出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)

mathe

不应该贪心，尽量先选择数目多的吗？
残局比较好处理，可以动归。开局是不是可以试一试选择几个数目较多的方案，试探几次，然后减枝，不知道效果会如何

KeyTo9_Fans

写了一个估价函数，

然后每个局面只枚举估价函数值为前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

剪枝条件：

对于 估价函数值<=当前最高得分 的分支，则直接跳过，不进行更深层次的枚举

KeyTo9_Fans

在手机上玩，发现奖励分的计算方法和电视上玩是不同的：

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

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

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

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

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

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

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



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



换一个关卡，也是类似的策略：



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

所以在N很大的时候，能过N关的概率应该会收敛到一个大于0的常数，而不是0