algorithm - 在 "bubble pop"游戏中寻找最高分

Question

[从 math.stackexchange 重新发布]

考虑以下游戏:有一个 n×n 字段，其中每个单元格随机着色为 m 种颜色之一。设一组 单元格是一组相同颜色的单元格 s.t.一组中的每个单元格与另一个相同颜色的单元格至少有一个公共(public)边。可以“弹出”一组 s≥k 个单元格，即从 field 中移除，并为玩家分配一个分数。当一个组被移除时，剩余的单元格被替换为 st。没有单元格下面有空单元格(基本上，剩余的单元格“掉下来”)。如果一列因弹出而消失，则其左侧的每个非空列都会向右移动一个单元格。当场上没有剩余组时，游戏结束。分数是s的函数，最后计算出一个累计分数。游戏的目的是获得最高的累积分数。

问题是是否有一种算法可以计算给定单元格起始排列的最大可能最终分数？我怀疑它与图形搜索有关，但我对此类事情的经验很少。谁能建议如何解决此类问题？我也考虑过用元胞自动机做点什么，但我真的怀疑这种方法(不管它可能多么有趣)。

Answer 1

是的，你可以在这个问题中进行图形搜索。你的根节点就是初始的棋盘，分支就是从父节点移除某组的操作，子节点就是相应移除的结果。将单个变量附加到将成为您的“分数”的每个节点，制作一棵完整的树(对于非平凡的评分函数，应探索所有节点)并找出所有叶子中最高的分数。