解决具有重叠卡片的游戏的结构/算法

Question

考虑一个类似于 Tower Solitaire、Tripeaks 或 Fairway Solitaire 的纸牌游戏：桌子上有一些立即可用的牌，每张牌下面可能会盖着其他牌（阻止它们被玩）。你有一张“基础”牌，如果一张牌与你的基础牌相差一点点，你就可以从桌子上移走一张牌，并将其作为新的基础牌。当你无法从桌子上打出一张牌时，你只能从有限的替换牌中抽取，因此通常要尽可能打出最长的牌序列。

首先，为了方便找到解决方案，你将如何表示棋盘？其次，你将使用什么算法来查找最长可玩序列？

例如：

  -4a- -5-
-3-  -2- -4b-

底部的牌会阻挡顶部的牌被移除：在 3 和 2 都被移除之前，你不能移除 4a。假设你的起始牌是一张 A 牌，那么这里的最佳打法是 2, 3, 4b, 5, 4a。（你也可以选择 2, 3, 4a，但那不是最好的。）

我想这应该表示为某种有向图。你会从 3 和 2 到 4a，从 2 和 4b 到 5 有边，但是在 3 和 2 之间以及在 4a 和 5 之间也有边吗？如果是这样，它们可以按任意顺序播放的事实是否形成了图中的循环，阻止你使用高效的“最长路径”算法？（我相信，如果图包含循环，则在图中查找最长路径是 NP 完全的。）

- Tara McGrew

---

动态规划...背包问题...你可以在图上应用Dijkstra算法... - Ritwik Bose

Dijkstra算法可以找到最短路径。如果权重取反，则会找到最长路径，但如果图包含循环，那么这种方法将行不通，是吗？ - Tara McGrew

我会想直接对其进行暴力破解。实际上，它似乎不太可能在操作中呈指数级增长。 - Jason Orendorff

Jesse：不，它无法找到最长的路径。如果存在负权重，则Dijkstra算法无论是否有环都无法工作。 - Juan Besa

一张卡片能否覆盖任意数量的其他卡片，还是有一个上限？一张卡片能否被任意数量的其他卡片覆盖，还是有一个上限？（我猜覆盖关系不能是循环的...）在你的例子中，以及我玩过的纸牌游戏中，这两个问题的上限都是两个，但这是实际的上限还是这个例子的属性？ - JaakkoK

原则上，我不认为一张牌不能直接覆盖或被3张或更多张牌覆盖，但至少在Fairway Solitaire中，我没有看到过这种情况。如果只能处理两张牌的情况，我会感到满意。当然，如果一张牌在一摞牌的顶部或底部，那么它就可以间接地覆盖或被任意数量的牌覆盖。 - Tara McGrew

Answer 1

如果将其表示为游戏状态的图表（动态计算潜在的下一个状态），那么它将没有循环，这意味着从起点开始对游戏的潜在状态进行直接深度优先搜索（可能仍然非常多）。

- James

Answer 2

重点是构建一个节点最少的有向无环图，其节点完全捕获问题的状态空间。然后您可以运行您通常的算法。

我建议一种基于剩余牌桌结构形状的编码方式。

状态中的第一个数据可以是最左边-最上面的卡片的唯一ID。（例如4a，它在某种意义上是唯一的，因为只有一张4a卡片）。剩下的形状可以由每个可用卡片（准备取走的卡片）的-1、0、1之一表示，描述下一张卡片是否在同一“级别”上，或者比它高或低一级。（这利用了一个假设，即一张卡片仅与其他两张卡片重叠，并且结构看起来像您在示例中给出的那样）。

- supo