如何将自研回合制游戏单回合状态转化为有限移动序列？

游戏核心规则概览 #

• 棋盘格子分属两名玩家，棋子有X、Y、Z三种强度等级
• 可通过购买部署新棋子（当回合购买的为黄色）
• 活跃棋子支持移动、合并：X+X=Y，X+Y=Z
• 移动至己方领地仍保持活跃，移动至敌方领地变为非活跃（绿色棋子）
• 可直接召唤棋子至已有棋子完成升级

当前困境与尝试 #

当前仅支持两种移动类型：Move piece to location、Summon piece to location。若允许序列无限长，状态转化很容易实现，但业务需求要求限制序列长度。

曾尝试一种算法：若棋子最近一次操作非合并或占领，则更新该操作而非新增，虽能避免无限循环，但会产生大量冗余步骤，且存在未知边缘情况。希望获得更优解决方案，也可新增移动类型。

优化解决方案建议 #

1. 新增合并/升级专属移动类型 #

直接新增Merge pieces at location（指定位置合并棋子）或Upgrade piece at location（指定位置升级棋子）类型，跳过中间移动步骤：

• 对于需要合并升级的最终状态，直接生成对应合并/升级指令，不需要先移动多个棋子到目标位置再逐步操作
• 当最终状态是X+X→Y时，直接用Merge pieces at location替代两次Move+一次隐含合并，大幅缩短序列长度

2. 基于最终状态的逆向推导算法 #

从最终状态倒推至初始状态，只保留必要操作：

• 标记所有最终状态中需保留的棋子、等级和位置
• 逆向拆解合并关系：比如最终的Z棋子，逆向拆分为一个X和一个Y（或两个X再合并为Y），定位这些前置棋子的初始位置
• 仅生成将前置棋子移动/召唤到目标位置的必要指令，跳过任何中间冗余的移动操作

3. 状态压缩与操作合并 #

对连续的同类型操作进行合并：

• 若同一棋子多次移动到不同位置，直接保留最后一次移动指令（因为中间移动不影响最终状态）
• 对于批量召唤升级的场景，合并为Summon [n] X pieces to location for upgrade这类批量指令，减少单条指令数量

4. 领地状态优先处理 #

先处理领地归属相关操作，再处理棋子等级操作：

• 先生成所有占领敌方领地的移动指令（这类操作会改变棋子活跃状态，优先级高）
• 再处理己方领地内的棋子合并/升级，避免因活跃状态变化导致的冗余操作

内容的提问来源于stack exchange，提问作者Jez