Codierungsregeln für das Schachspiel mit endlicher Zustandsmaschine

Question

Ich mache eine selbst-pädagogische Forschung über endliche Automaten. Und derzeit stolperte über interessante, aber nicht triviale Aufgabe zu erfüllen. Es ist wirklich schwierig, eine Zustandsmaschine für die Schachregeln zu definieren.

Obwohl die Regeln einfach erscheinen, ist das Spiel mit FSM schwer zu erreichen. Ich habe darüber nachgedacht, den Spielstatus als einen Zustand des Spielplans zu kodieren, in dem jedes Quadrat entweder leer ist oder ein Stück enthält. Es wird jedoch schwierig, Übergänge zu definieren, da der Übergang Fakten berücksichtigen sollte, die die Umgebung der betreffenden Zelle betreffen. Es ist auch schwierig, Übergänge für Fälle wie Enpassant oder Rochade zu definieren, besonders wenn die Rochade durch ein anderes Stück blockiert wird. Genauso ist es schwer, Bewegungseinschränkungen für Stücke zu definieren, die von anderen Steinen blockiert werden und nicht in der Lage sind, sie zu überspringen, d. H. Bauern, Läufer, Türme, Königinnen.

Wie würden Sie dieses Problem angehen? Oder vielleicht gibt es einige Erweiterungen zu FSM, die mir nicht bekannt sind. Ich bin mir ziemlich sicher, dass es viele ähnliche Anwendungen gibt, bei denen FSM unpraktisch sein wird. Wie würden Sie im Allgemeinen mit diesem Problem umgehen?

Vielen Dank im Voraus,

Answer 1

In Ihrem Ansatz jeden Staat eine Matrix von Feldern sein würde, wobei jedes Feld einen bestimmten Zustand aufweist, die eine Zusammensetzung der Farbe und den Schachfigur ist das auf sie gesetzt wird und Schachfiguren selbst sind eine Komposition aus der Farbe der Schachfigur und ihrer Art (Bauern, Turm usw.). So können Sie ganz einfach Regeln definieren, indem sie diese Matrizen verwendet:

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

Jetzt können wir Regeln evalute für die beiden weißen Figuren bewegen, basierend auf dieser Regel:

Ein Bauer kann gerade nach vorne bewegen, wenn sie nicht blockiert ist durch eine andere Figur, oder sie kann die Figur schlagen, die diagonal einen Block davon entfernt platziert ist. Der Aufbau die Übergangs-Tabelle für den obigen Zustand mit einem weißen bewegen kann als nächste in der folgenden Art und Weise erfolgen:

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 

übersetzt diese in Mathe sollte nicht allzu schwer sein. Die Zustandsübergangstabelle für jeden Staat würde alle möglichen Bewegungen für alle Figuren enthalten. Die resultierende Maschine wäre eine NFA.

Eine andere Option wäre, Übergänge als ein Paar der Schachfigur zu definieren, die Sie verschieben möchten und wo Sie sie verschieben möchten. Das würde dir erlauben, ein DFA zu konstruieren.