使用有限状态机的国际象棋游戏编码规则

Question

我正在对有限状态机进行自学研究。目前偶然发现了要完成的有趣但不平凡的任务。国际象棋的游戏规则很难定义状态机。

虽然规则看起来很简单，但使用 FSM 很难接近游戏本身。我正在考虑将游戏状态编码为棋盘状态，其中每个方块要么是空的，要么包含一些棋子。但是很难定义转换，因为转换应该知道与主题单元格的邻域有关的事实。也很难为 en-passant 或 castling 等情况定义转换，尤其是当 castling 被其他部分阻挡时。同样，很难为被其他棋子阻挡且无法跳跃它们的棋子定义移动限制，即兵、象、车、皇后。

你会如何解决这个问题？或者可能有一些我不知道的 FSM 扩展。我很确定有很多类似的应用程序在其中使用 FSM 是不切实际的。一般情况下你会如何处理这个问题。

提前谢谢你，

Answer 1

在你的方法中，每个状态都是一个字段矩阵，其中每个字段都有一个特定的状态，它是颜色和放置在它上面的棋子的组合，棋子本身是棋子的颜色和类型（兵、车等）。因此，您可以使用这些矩阵轻松定义规则：

Example for pawn:
Initial state:
   C              D              E
5  (W , (X , ?))  (B , (P , B))  (W , (P , B))
4  (B , (P , W))  (W , (X , ?))  (B , (P , W))

现在我们可以根据这个规则来计算移动两个白色图形的规则：

棋子可以直接向前移动，如果它没有被另一个人物挡住，或者它可以击败对角线放置一个街区的人物。可以通过以下方式为上述状态构建 transition-table 和下一步白棋：

S1->(a)X (just the standard way to define a transition)
a would be the figure, we want to move and S2 the resulting state
X are the reachable state.

a = Pawn at C4
we have two options evaluating the field:
    C5 is free, so we can move the pawn to that field
    D5 is held by a black pawn, so we can beat it and move to that field
a = Pawn at E4
    E5 not free, we can't move ahead
    D5 is held by a black pawn, which we can beat

将其转化为数学应该不会太难。每个状态的状态转换-table 将包括所有图形的所有可能移动。生成的机器将是 NFA。

另一种选择是将转换定义为一对您要移动的棋子和您要移动的位置。这将允许您构建 DFA。

使用有限状态机的国际象棋游戏编码规则

Encoding rules for the game of chess using finite state machine

algorithm

state-machine