[从 math.stackexchange 重新发布]
考虑以下游戏：有一个n×n字段，其中每个单元格随机以m种颜色中的一种着色。假设一组单元格是一组相同颜色的单元格，一组中的每个单元格至少有一个与另一个相同颜色的单元格的公共边。一组s≥k单元格可以“弹出”，即从场地中移除，并为玩家分配一个分数。当一个组被移除时，剩余的单元格被替换，因为没有一个单元格下面有一个空单元格（基本上，剩余的单元格“倒下”）。如果一列因弹出而消失，则其左侧的每个非空列都会向右移动一个单元格。当场上没有任何小组时，比赛结束。分数是 s 的函数，最后计算出累积分数。游戏的目的是获得最大的累积分数。
问题是是否有一种算法可以计算给定起始单元格排列的最大可能结束分数？我怀疑它与图形搜索有关，但我对这些事情几乎没有经验。任何人都可以建议如何解决此类问题吗？我也想过用元胞自动机做点什么，但我真的怀疑这种方法（不管它有多有趣）。