ポセットゲーム

組合せゲーム理論において、ポセットゲームは数学的な戦略 ゲームであり、ニムやチョムプなどの多くのよく知られたゲームを一般化したものである。^{[1]このようなゲームでは、2人のプレイヤーが}ポセット（部分的に順序付けられた集合）から始め、交互にポセット内の1つの点を選択し、それより大きいすべての点を除去する。選択する点がなくなったプレイヤーは負けとなる。

半順序集合（P ,<） が与えられたとき、

${\displaystyle P_{x}=P-\{a\mid a\geq x\}}$

Pからx を取り除いて形成される半順序集合を表す。

P上の poset ゲームは、慣例的にAlice と Bob と呼ばれる 2 人のプレイヤー間で行われ、次のようになります。

• アリスは点x  ∈  P を選択し、P をP _xに置き換えて、ボブにターンを渡します。ボブはP _xでプレイし、アリスにターンを渡します。
• 自分の番なのに選択できるポイントがない場合、そのプレイヤーは負けとなります。

P が有限の 全順序集合である場合、Pでのゲームプレイは、サイズ | P |のヒープを持つNimのゲームでのゲームプレイとまったく同じです。両方のゲームで、サイズが | P |より小さい任意の数である同じタイプのゲームにつながる動きを選択することが可能です。同様に、全順序の互いに素な和集合を持つ poset ゲームは、poset 内のチェーンに等しいサイズの複数のヒープを持つ Nim のゲームと同等です。

すべての辺が緑（どちらのプレイヤーもカット可能）で、すべての構成が森の形をとるハッケンブッシュの特殊なケースは、同様に、すべての要素xに対して、 x がy をカバーする要素y が最大で 1 つ存在するようなposet 上の poset ゲームとして表現できます。x がy をカバーする場合、ゲームがプレイされる森の中で yはxの親です。

Chomp は同様に、最小値を除いた 全順序の積上の poset ゲームとして表現できます。

posetゲームは公平なゲームであり、アリスがパスを許されれば、アリスが行えるすべての動きはボブも行える。またその逆も成り立つ。したがって、Sprague-Grundy定理により、posetゲームのすべてのポジションにはGrundy値があり、これはNimゲームにおける同等のポジションを表す数値である。posetのGrundy値は、任意のP _x、x  ∈  PのGrundy値ではない最小の自然数として計算できる。つまり、^[2]

${\displaystyle G(P)=\min {\bigl (}\mathbb {N} \setminus \{G(P_{x})\mid x\in P\}{\bigr )}.}$

この数値は、poset ゲームにおける最適なゲーム プレイを説明するために使用できます。特に、現在のターンのプレイヤーが勝利戦略を持っている場合、Grundy 値はゼロ以外になり、現在のプレイヤーが対戦相手の最適なプレイに勝てない場合はゼロになります。ゲームにおける勝利戦略は、可能な限り、Grundy 値がゼロの位置に移動するというものです。

戦略窃盗の議論は、上限を持つすべての poset について、Grundy 値が非ゼロであることを示しています。たとえば、x を半順序集合Pの上限とします。P _{x の}Grundy 値がゼロの場合、上記の式により、P自体も非ゼロの値を持ちます。この場合、 x はPの必勝手です。一方、P _{x の}Grundy 値が非ゼロの場合、P _xには必勝手yが存在し、 ( P _x ) _yの Grundy 値はゼロになります。しかし、 xが上限であるという仮定により、 x  >  yかつ ( P _x ) _y  =  P _yであるため、必勝手y はPでも利用可能であり、この場合もP は非ゼロの Grundy 値を持つ必要があります。^[1]

もっと些細な理由により、最小値を持つ poset には非ゼロの Grundy 値もあります。つまり、最小値への移動は常に勝利の動きです。

任意の有限posetゲームの勝者を決定することはPSPACE完全である。^[3]これは、P = PSPACEでない限り、任意のposetゲームのGrundy値を計算することは計算上困難であることを意味する。