如何将游戏回合的游戏状态转化为一组有限的动作？

Question

我很难确定如何将游戏中特定回合的游戏状态转换为代表该回合所采取的动作的有限动作序列。我希望得到关于如何做到这一点的建议。

注意：游戏现已上线！如果有人想尝试，请访问： https: //mystikaze.com
（我最终实现了一种用于存储游戏动作的算法，该算法可能不完全有效，但我认为确实可以保证任何给定回合的动作列表不能被无界/无限长）。

游戏规则相对简单。有一个六角形棋盘，其中六角形属于 2 个玩家。在任何给定的回合中，棋子可能已经存在于棋盘上，已在上一回合中购买，或者它们可以被购买到棋盘上（黄色棋子代表其在本回合被购买到棋盘上）。

这些棋子是“活跃的”，并且仍然可以移动。碎片也可以组合起来，并且仍然保持“活跃”状态。它们可以通过将现有的一块移动到另一块上或通过购买新的块到现有的块上来组合。组合后，目标六角形上将存在升级后的棋子。棋子可以有 3 种强度；X、Y 和 Z。X 与 X 结合得到 Y，X 与 Y 结合得到 Z。

片段可以继续像这样合并并保持“活跃”。一个棋子可以移动到其自己领土内的另一个六角形并保持“活跃”。当一个棋子被移动以捕获其他玩家的六角形时，它就不再是“活跃的”。此后它无法移动，但仍然可以结合。下面的绿色表示不活动的部分。

一个棋子也可以直接召唤到另一个棋子之上，从而产生升级的棋子（如果它已经处于活动状态，则它保持活动状态；如果它处于非活动状态，则它保持非活动状态）：

现在，这很容易在游戏状态中表示；只需更新棋子和棋盘的状态以反映当前的真实情况即可。只要理论上允许该移动序列是无界的，就可以很容易地将其转换为一系列移动。碎片可以保持活跃并无限地来回移动。当然，我想限制动作的顺序。这就是我遇到麻烦的地方。我有以下2个动作：

• 将棋子移动到指定位置
• 将棋子召唤到指定位置

如何将玩家所做的动作转换为有限的动作序列，以代表玩家实际所做的事情，从而达到最终状态？我不知道我是否遗漏了一些东西，但这似乎变得几乎不可能复杂到弄清楚。如果您有棋子在自己的区域内移动并保持活动状态，您可能会认为您可以将移动就地更新到新坐标，而不是向新坐标添加新移动，但如果有另一个移动，其中一块与另一块结合形成一个升级块，它依赖于第一块移动到其第一组坐标？现在就地更新移动坐标意味着第二个组合移动成为常规移动，因为它现在移动到空六角形上，但它应该仍然是组合移动（棋盘状态实际上是已移动到新坐标）。

从概念上讲，应该始终存在可以代表任何操作的有限移动序列。然而，我发现很难弄清楚如何编写一个算法来自动执行此操作。我认为至少可以防止移动的无限性质的算法是说“如果最近的移动不是组合或捕获操作，则更新一个棋子的最近移动，而不是将新移动添加到列表中”。这应该始终导致移动集正确创建游戏状态，并防止无限循环。然而，这仍然可能导致相当多的变动。例如，如果你在一个领土上有 10 个棋子，你可以移动所有 1 个棋子，捕获 1 个棋子，移动剩余的 9 个棋子，将一个棋子与另一个棋子组合，移动剩余的 8 个棋子等等，这可能会导致 10 个棋子的移动次数超过 60 次。如果有一种算法可以把这个问题降低一点，那就太好了，而且我仍然不能 100% 确定即使这个算法也没有一些无法工作的边缘情况。

我是否缺少一种相对直接的方法来解决这个问题？规则必须保持不变，但我愿意接受有关引入新移动类型的建议，如果这也有助于解决问题的话。

Answer 1

最后，考虑到规则集的灵活性，我不得不提出与建议的算法不同的算法。我从另一端来解决这个问题；与其考虑如何绝对最小化移动次数，不如考虑是什么让移动次数具有无限的潜力？事实上，活动的棋子可以在空的六角形之间移动无限次。其他一切都受到很好的限制；一块可以移动，然后组合，仅此而已；该组合将其从棋盘上移除并升级底层棋子。它可以移动，然后捕获，但这会结束它的回合。因此，为了消除移动列表的无界性质，我最终采用了以下算法来验证移动列表：

• 一个棋子只允许进行一次召唤操作
• 对于走棋操作，吃子后禁止再进行任何走棋
• 如果该棋子的两个移动之间没有属于组合/捕获移动的移动，则禁止该棋子连续进行多个非组合/非捕获移动
• 当一个棋子被组合时，它会从棋盘上移除，并且底层棋子会升级，这意味着该棋子在组合操作后将无法移动，因为它不再存在于棋盘上

这确实意味着你可以在组合或捕获操作之前让一个棋子移动，并且如果一个棋子被其他组合的棋子分开，那么一个棋子甚至可以轮流进行多个非组合/非捕获移动 - 我认为这有点这是必要的，以防另一块移动到它上面进行组合 - 但连续多次这样的移动是非法的，很好地限制了一个回合可以提交多少移动的范围。

在客户端，它检测棋子移动是否是在其自己的区域内连续移动两次的棋子。如果不是，它只是添加移动。如果是，它会检查自现有移动以来是否存在具有相同目标坐标的移动。如果没有，它只会就地更新现有的移动。如果有，则拼接出该棋子的着法以及该子已有的着法，并将其插入到棋子列表的末尾，后面是该棋子的着法；这需要反映这样一个事实：这件作品现在正在以正确的顺序与那件作品组合。

这似乎可行，但相当复杂和令人困惑。不过，这似乎就是问题的本质！