Reversi/Othello棋盘状态溯源：能否推导合法棋步序列？

前提条件 #

• 标准8x8棋盘，黑方先行，初始为中心各放置2枚双方棋子的传统布局
• 双方已走步数相同，黑方即将下一手
• 目标：找到一组合法棋步，使棋盘达到给定状态（同一状态可对应多组棋步，只要合法即可）

构思的回溯思路 #

1. 白方刚走完最后一步，搜索连续的白棋线条
2. 翻转该线条中除首尾棋子外的所有棋子
3. 移除其中一端的棋子并记录其位置（此为潜在棋步），保留另一端棋子
4. 检查棋盘是否处于有效状态

交替针对黑方、白方重复上述步骤，会出现以下三种情况：

• 情况A：回到初始状态，此时记录的棋步即为符合原棋盘状态的合法序列
• 情况B：棋盘状态有效但下一手玩家无合法棋步，记录该步为0，继续由上一玩家回溯
• 情况C：棋盘状态无效，删除之前记录的棋步并恢复棋盘状态，针对同一玩家重新搜索连续线条；若无其他线条，则撤销下一个记录的棋步，切换回另一玩家重新操作，循环直至达到情况A

现存问题与疑问 #

• 上述回溯方法的耗时会随游戏进程推进显著增加，且可能忽略部分游戏规则细节导致难度提升
• 该问题似乎比用minmax（带alpha剪枝）算法寻找最优棋步难度更高
• 是否有人已通过编程实现该功能？游戏后阶段是否可行？
• 目前尚未编写代码，正处于思路梳理阶段

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