Reglas de codificación para el juego de ajedrez utilizando una máquina de estados finitos - algoritmo, máquina de estados finitos

Estoy haciendo una investigación autoeducativa sobre finitomáquinas de estado. Y actualmente tropecé con una tarea interesante pero no trivial para lograr. Es realmente difícil definir la máquina de estado para las reglas del juego de ajedrez.

Aunque las reglas parecen simples, el juego en sí esDifícil de abordar con FSM. Estaba pensando en codificar el estado del juego como un estado del tablero, donde cada casilla está vacía o contiene alguna pieza. Pero se hace difícil definir las transiciones, porque la transición debe ser consciente de los hechos que conciernen a la vecindad de la celda sujeto. También es difícil definir transiciones para casos como pasajero o enroque, especialmente cuando el enredo está bloqueado por alguna otra pieza. Del mismo modo, es difícil definir limitaciones de movimiento para piezas que están bloqueadas por otras piezas y no son capaces de saltarlas, es decir, peones, obispos, torres, reinas.

¿Cómo abordarías este problema? O tal vez hay algunas extensiones de FSM que no conozco. Estoy bastante seguro de que hay muchas aplicaciones similares donde FSM será poco práctico de usar. ¿Cómo tratarías este problema en un caso general?

Gracias de antemano,

Respuestas

En su enfoque, cada estado sería una matriz decampos, donde cada campo tiene un estado específico, que es una composición del color y la pieza de ajedrez que se coloca sobre él y las piezas de ajedrez en sí son una composición del color de la pieza de ajedrez y su tipo (peón, torre , etc.) Para que pueda definir fácilmente las reglas utilizando estas matrices:

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))

Ahora podemos evaluar las reglas para mover las dos figuras blancas según esta regla:

Un peón puede moverse hacia adelante, si no esbloqueado por otra figura, o puede vencer a la figura que se coloca diagonalmente a una cuadra de distancia. La construcción de la tabla de transición para el estado anterior con un movimiento blanco a continuación se puede hacer de la siguiente manera:

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

Traducir esto a las matemáticas no debería ser demasiado difícil. La tabla de transición de estado para cada estado incluiría todos los movimientos posibles para todas las figuras. La máquina resultante sería un NFA.

Otra opción sería definir las transiciones como un par de la pieza de ajedrez que desea mover y dónde desea moverla. Eso "le permitiría construir un DFA.