Regole di codifica per il gioco degli scacchi usando una macchina a stati finiti - algoritmo, macchina a stati finiti

Sto facendo una ricerca autodidatta sul finitomacchine a stati. E attualmente inciampato su un compito interessante ma non banale da svolgere. È davvero difficile definire una macchina a stati per le regole del gioco degli scacchi.

Anche se le regole sembrano semplici, il gioco stesso èdifficile avvicinarsi usando FSM. Stavo pensando di codificare lo stato del gioco come uno stato del tabellone, in cui ogni quadrato è vuoto o contiene un pezzo. Ma diventa difficile definire le transizioni, perché la transizione dovrebbe essere consapevole dei fatti che riguardano il vicinato della cellula soggetto. È anche difficile definire le transizioni per casi come en-passant o castling, specialmente quando il castling è bloccato da qualche altro pezzo. Allo stesso modo è difficile definire le limitazioni di spostamento per pezzi che sono bloccati da altri pezzi e che non sono in grado di saltarli, ad esempio pedine, vescovi, corvi, regine.

Come affronteresti questo problema? O forse ci sono alcune estensioni di FSM di cui non sono a conoscenza. Sono abbastanza sicuro che ci sono molte applicazioni simili in cui FSM non sarà pratico da usare. Come affronteresti questo problema in generale.

Grazie in anticipo,

risposte:

Nel tuo approccio ogni stato sarebbe una matrice dicampi, in cui ogni campo ha uno stato specifico, che è una composizione del colore e del pezzo degli scacchi che è posto su di esso e i pezzi degli scacchi stessi sono una composizione del colore del pezzo degli scacchi e il suo tipo (pedone, torre , ecc.) Quindi puoi facilmente definire le regole utilizzando queste matrici:

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

Ora possiamo valutare le regole per spostare le due figure bianche in base a questa regola:

Una pedina può spostarsi in avanti, se non lo èbloccato da un'altra figura, oppure può battere la figura posizionata in diagonale a un isolato di distanza da essa. La creazione della tabella di transizione per lo stato precedente con una mossa bianca successiva può essere eseguita nel modo seguente:

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

Tradurre questo in matematica non dovrebbe essere troppo difficile. La tabella di transizione dello stato per ogni stato includerebbe tutte le mosse possibili per tutte le figure. La macchina risultante sarebbe un NFA.

Un'altra opzione sarebbe quella di definire le transizioni come una coppia del pezzo degli scacchi che si desidera spostare e dove si desidera spostarlo. Che ti permetterebbe di costruire un DFA.