有限状態マシンを使ったチェスゲームのエンコーディングルール

Question

私は有限状態マシンに関する自己教育的研究を行っています。そして、現在、興味深いが、些細ではない仕事に遭遇しました。チェスのゲームのルールのための状態マシンを定義することは本当に難しいです。

ルールは単純だと思われますが、ゲームそのものはFSMを使用してアプローチするのは難しいです。私はゲームの状態をボードの状態としてエンコーディングすることを考えていました。そこでは、各四角は空であるか、または何らかの部分が入っています。しかし、遷移は対象セルの近傍に関係する事実を認識する必要があるため、遷移を定義することは難しくなります。エンパイアントやキャスティングのような場合、特にキャスティングが他の部分でブロックされている場合には、トランジションを定義することも難しいです。同じように、他の部分によってブロックされ、それらをジャンプすることができない部分、すなわちポーン、ビショップ、ルーク、クイーンの移動制限を定義することは難しい。

どのようにこの問題にアプローチしますか？あるいは、私が気づいていないFSMの拡張もあります。私は、FSMが使用するには実用的ではない多くの同様のアプリケーションがあると確信しています。あなたはこの問題を一般的にどのように扱いますか？

は、各状態がそれに配置された色とチェスの駒の組成物である各フィールドは、特定の状態を持っている分野の行列、、になり、事前にあなたのアプローチで

Answer 1

をありがとうとチェスピース自体は、チェスピースの色の構成であり、そのタイプ（ポーン、ルークなど）です。だから、簡単にこれらの行列を利用してルールを定義することができます

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

今、私たちは、この規則に基づいて2つの白い数字を移動するためのルールをevaluteことができます。

それはによってブロックされていない場合はポーンが、前方にまっすぐ移動することができます別の図形、またはそれから離れて斜めに配置されている図を打つことができます。次の白の動きと上記の状態のための遷移表を構築することは、以下の方法で行うことができます

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 

数学にこれを翻訳することはそれほど難しいことではありません。各状態の状態遷移表には、すべての数値に対するすべての可能な移動が含まれます。結果のマシンはNFAになります。

もう1つの選択肢は、移動したいチェスのペアと移動したい位置のペアとしてトランジションを定義することです。そうすれば、DFAを構築することができます。