Robím samovzdelávací výskum konečnýchštátne stroje. A v súčasnosti narazil na zaujímavú, ale netriviálnu úlohu, ktorú treba splniť. Je naozaj ťažké definovať štátny stroj pre pravidlá šachovej hry.
Aj keď sa pravidlá zdajú jednoduché, samotná hra jeťažko dostupné pomocou FSM. Premýšľal som o kódovaní stavu hry ako stavu dosky, kde každý štvorec je buď prázdny alebo obsahuje nejaký kus. Je však ťažké definovať prechody, pretože prechod by si mal byť vedomý faktov, ktoré sa týkajú susedstva s bunkou subjektu. Je tiež ťažké definovať prechody pre prípady, ako sú pasažieri alebo rošáda, najmä ak je rošáda blokovaná nejakým iným kusom. Rovnakým spôsobom je ťažké definovať obmedzenia pohybu pre figúrky, ktoré sú blokované inými figúrkami a nie sú schopné ich preskočiť, t. J. Pešiakov, biskupov, veží, kráľovien.
Ako by ste sa k tomuto problému priblížili? Alebo možno existujú nejaké rozšírenia FSM, o ktorých neviem. Som si celkom istý, že existuje veľa podobných aplikácií, v ktorých bude FSM nepraktické používať. Ako by ste riešili tento problém vo všeobecnom prípade.
Vopred ďakujem,
odpovede:
1 pre odpoveď č. 1Vo vašom prístupe by bol každý štát maticoupolia, v ktorých má každé pole špecifický stav, čo je zloženie farby a šachovej figúrky, ktorá je na nej umiestnená a samotné šachové figúrky, sú kompozíciou farby šachovej figúrky a jej typu (pešiak, veža atď.) Takže môžete ľahko definovať pravidlá pomocou týchto matíc:
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))
Teraz môžeme na základe tohto pravidla vyhodnotiť pravidlá na presunutie dvoch bielych čísel:
Pešiak sa môže pohybovať priamo vpred, ak to tak nie jeblokovaná inou postavou, alebo môže poraziť postavu, ktorá je umiestnená diagonálne o jeden blok ďalej. Budovanie prechodovej tabuľky pre vyššie uvedený stav s ďalším posunom ďalej je možné vykonať nasledujúcim spôsobom:
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
Preložiť to do matematiky by nemalo byť príliš ťažké. Tabuľka prechodu stavu pre každý štát by zahŕňala všetky možné pohyby pre všetky čísla. Výsledným strojom by bola NFA.
Ďalšou možnosťou by bolo definovať prechody ako pár šachových figúrok, ktoré chcete presunúť a kam chcete presunúť. To vám umožní zostaviť DFA.