在「泡沫彈出」查找最大得分遊戲

Question

[從math.stackexchange重新發布這個]考慮以下游戲：有一個n×n的字段，其​​中每個小區被隨機地的一個着色m顏色。假設一個組的是一組相同顏色的單元s.t.一個組中的每個單元與另一個相同顏色的單元至少有一個公共邊。一組s「k細胞可以被」彈出「，即從場地移除並且爲玩家分配一個分數。當一個組被刪除時，剩下的單元格被移動s.t.沒有細胞在其下面有一個空單元（基本上，剩下的單元「倒下」）。如果某列因彈出而消失，則左側的每個非空列都會向右移動一個單元格。當場上沒有組時，比賽結束。得分是s的函數，最後計算累計分數。遊戲的目的是獲得最大累計分數。

問題是如果有一種算法可以計算給定的細胞起始排列的最大可能的最終分數？我懷疑它與圖搜索有關，但我對這種事情一無所知。任何人都可以請建議如何解決這樣的問題？我也想過用元胞自動機做一些事情，但我真的懷疑這種方法（不管它有趣）。

Answer 1

是的，你可以在這個問題上做圖搜索。您的根節點將成爲初始板，分支將成爲刪除某個組關閉父節點的操作，子節點將成爲相應刪除的結果。將一個變量附加到每個節點上，這些節點將會是你的「分數」，製作一個完整的樹（對於非平凡的評分函數，應該探索所有節點），並找出所有樹葉中最高的分數。