解决重叠牌游戏的结构/算法
考虑一个类似于塔式纸牌、三峰纸牌或球道纸牌的纸牌游戏：桌子由一些可以立即使用的纸牌组成，每张纸牌都可能覆盖其下面的其他纸牌（阻止它们被玩）。你有一张“基础”牌，如果一张牌恰好比你的基础牌高一级或低一级，你可以从牌桌上删除一张牌，此时它就成为你的新基础牌。当您无法打出牌桌上的牌时，您可以抽取的替换牌数量有限，因此您通常希望打出尽可能长的牌序列。
首先，您将如何代表董事会促进寻找解决方案？其次，您将使用什么算法来找到最长的可播放序列？
示例：
-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 之间的边，因为其中一个可以在另一个之后播放？如果是这样，它们可以按任意顺序（3 然后 2，或 2 然后 3）播放的事实是否会在图中形成一个循环，从而阻止您使用有效的“最长路径”算法？ （我相信如果图中包含循环，则找到图中最长的路径是 NP 完全的。）
Consider a card game along the lines of Tower Solitaire, Tripeaks, or Fairway Solitaire: the table consists of some number of cards which are immediately available, each of which might be covering other cards underneath it (blocking them from being played). You have one "foundation" card, and you can remove a card from the table if it's exactly one rank above or below your foundation card, at which point it becomes your new foundation card. You have a limited number of replacement cards to draw from when you can't play a card from the table, so you generally want to play the longest sequence of cards possible.
First, how would you represent the board to facilitate finding a solution? Second, what algorithm would you use to find the longest playable sequence?
Example:
-4a- -5- -3- -2- -4b-
Cards on the bottom block cards on top from being removed: you can't remove 4a until both 3 and 2 are gone. Assuming your starting card is an ace, the optimal play here would be 2, 3, 4b, 5, 4a. (You could play 2, 3, 4a instead, but that's not as good.)
I suppose this should be represented as some kind of directed graph. You'd have edges from 3 and 2 to 4a and from 2 and 4b to 5, but would you also have edges between 3 and 2 and between 4a and 5, since one is playable after the other? If so, would the fact that they can be played in either order (3 then 2, or 2 then 3) form a cycle in the graph that prevents you from using the efficient "longest path" algorithms? (I believe finding the longest path in a graph is NP-complete if the graph contains cycles.)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果你将其表示为游戏状态图（动态计算潜在的下一个状态），那会怎么样？它不会有循环，这意味着它是游戏潜在状态（可能仍然很多）的直接 DFS起点。
What if you represent this as a graph of game-states (with potential next states computed on the fly) - that will not have loops, meaning it's a straight DFS on the potential states of the game (which could be quite numerous still) from the start point.
关键是用尽可能少的节点构建有向无环图，其节点将完全捕获问题的状态空间。然后你就可以运行你常用的算法了。
我建议根据牌桌上剩余牌的结构形状进行编码。
该状态中的第一个数据可以是最左边-最上面的卡的唯一ID。 （例如，像 4a 一样，从某种意义上说它是唯一的，因为只有一张牌 4a）。对于每张可用卡（准备好拿走的卡），形状的其余部分可以用 -1,0,1 之一表示，描述左边的下一张卡是在同一“级别”还是一个级别更深或更高。 （这是利用这样的假设：一张卡片仅与另外 2 张卡片重叠，并且该结构类似于您在示例中给出的结构）。
The point is to construct a directed acyclic graph with the fewest nodes possible, whose nodes would fully capture the state space of the problem. Then you can run your usual algorithm.
I suggest an encoding based on the shape of the structure of the remaining cards at the table.
The first data in the state could be the unique ID of the leftmost - topmost card. (like 4a for example, it is unique in a sense that there is only one card 4a). The rest of the shape can be represented by one of -1,0,1 for each available card (card that is ready to be taken) describing if the next card to the left is on the same 'level' or it is one level deeper or higher. (This is exploiting the assumption that a card overlaps only 2 other cards and that the structure looks like the one you have given in the example).