Ich mache eine Selbstinformationsforschung über EndlichkeitStaatsmaschinen. 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 selbstschwer mit FSM zu nähern. 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,
Antworten:
1 für die Antwort № 1In Ihrem Ansatz wäre jeder Staat eine Matrix vonFelder, in denen jedes Feld einen bestimmten Status hat, der eine Komposition der Farbe und der darauf platzierten Schachfigur ist, und Schachfiguren selbst sind eine Zusammensetzung der Farbe der Schachfigur und ihres Typs (Bauern, Turm, Turm) usw.) .Somit können Sie Regeln leicht definieren, indem Sie diese Matrizen verwenden:
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 die Regeln für das Verschieben der beiden weißen Zahlen basierend auf dieser Regel berechnen:
Ein Bauer kann sich geradeaus bewegen, wenn nichtblockiert durch eine andere Figur, oder es kann die Figur schlagen, die diagonal einen Block davon entfernt platziert ist. Das Erstellen der Übergangstabelle für den obigen Zustand mit einer weißen Bewegung kann wie folgt durchgeführt werden:
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
Das Übersetzen in Mathe sollte nicht zu 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. Damit können Sie ein DFA erstellen.