スプレイグ・グランディ定理

組合せゲーム理論におけるスプレイグ・グランディの定理は、通常のプレイ規約の下でのあらゆる公平なゲームは、ニムの 1 つのヒープのゲーム、またはニムの無限一般化と同等であると述べている。したがって、これは自然数、つまりニムの同等のゲームにおけるヒープのサイズ、無限一般化における順序数、または、加算演算によって複数のヒープが結合されてニムにおける単一の同等のヒープが形成される代数システムにおける 1 つのヒープのゲームの値 であるとして表すことができる。

公平なゲームのGrundy値またはnim 値は、ゲームが対応する一意の nimber です。位置が自然数でインデックス付けされるゲームの場合 (ヒープ サイズでインデックス付けされる nim 自体など)、ゲームの連続する位置の nimber のシーケンスは、ゲームの nim シーケンスと呼ばれます。

スプレイグ・グランディの定理とその証明は、 RPスプレイグ（1936）^[1]とPMグランディ（1939） ^[2]が独立に発見した理論の主な結果を要約したものです。

スプレイグ・グランディの定理の目的上、ゲームとは、終了条件(すべてのゲームは終了する。プレイのラインは無限ではない) と通常のプレイ条件(動けないプレイヤーは負ける) を満たす、完全情報の2 人プレイの連続ゲームです。

ゲームのどの時点でも、プレイヤーの位置とは、そのプレイヤーが実行できる動きの集合です。例として、どちらのプレイヤーも正当な動きを持たない 2 人のプレイヤーのゲームをゼロ ゲームと定義できます。2 人のプレイヤーを(アリスの場合) と(ボブの場合) と呼び、各プレイヤーが実行できる動きの集合は空なので、 彼らの位置を と表します。${\displaystyle A}$${\displaystyle B}$${\displaystyle (A,B)=(\{\},\{\})}$

公平なゲームとは、ゲームのどの時点でも、各プレイヤーがまったく同じ動きのセットを行えるゲームです。通常プレイのニムは公平なゲームの一例です。ニムでは、1 つ以上のオブジェクトの山があり、2 人のプレイヤー (アリスとボブと呼びます) が交代で山を選び、そこから 1 つ以上のオブジェクトを取り除きます。最後の山から最後のオブジェクトを取り除いたプレイヤーが勝者となります。このゲームが公平なのは、山のサイズをどのような構成にしても、アリスが自分の番に行える動きは、ボブが自分の番に行える動きとまったく同じだからです。対照的に、チェッカーなどのゲームは公平ではありません。アリスが赤をプレイし、ボブが黒をプレイすると仮定すると、ボード上の任意の駒の配置では、アリスの番であれば赤い駒しか動かせず、ボブの番であれば黒い駒しか動かせません。

したがって、公平なゲームのどの構成も単一のポジションとして記述できることに注意してください。これは、誰のターンであっても動きは同じになるためです。たとえば、ゼロ ゲームの位置は、単に と記述できます。これは、アリスのターンであれば、アリスが行う動きがなく、ボブのターンであれば、ボブも行う動きがないためです。動きは、次のプレーヤーが置かれるポジションと関連付けることができます。 ${\displaystyle \{\}}$

そうすることで、位置を再帰的に定義できるようになります。たとえば、アリスとボブがプレイする次の Nim ゲームを考えてみましょう。

ヒープのサイズの移動
 ABC
  
 1 2 2 アリスはAから1を取る
 0 2 2 ボブはBから1を取る
 0 1 2 アリスはCから1を取る
 0 1 1 ボブはBから1を取る
 0 0 1 アリスはCから1を取る
 0 0 0 ボブは動けないのでアリスが勝ちます

• ゲームのステップ 6 (すべてのヒープが空になったとき) では、ボブには有効な動きがないので、位置は です。この位置を と呼びます。${\displaystyle \{\}}$${\displaystyle *0}$
• ステップ 5 では、アリスには 1 つの選択肢しかありませんでした。それは、ヒープ C からオブジェクトを 1 つ削除し、ボブに何も移動できないようにすることです。アリスの移動によってボブは位置 にいるので、アリスの位置はと記述されます。この位置を と呼びます。${\displaystyle *0}$${\displaystyle \{*0\}}$${\displaystyle *1}$
• ステップ 4 では、ボブには 2 つの選択肢がありました。B から 1 つ削除するか、C から 1 つ削除するかです。ただし、ボブがどのヒープからオブジェクトを削除したかは、実際には重要ではないことに注意してください。どちらの方法でも、アリスには 1 つのオブジェクトが 1 つの山に残ります。したがって、再帰的な定義を使用すると、ボブには実際には 1 つの動きしかありません。したがって、ボブの位置は です。${\displaystyle *1}$${\displaystyle \{*1\}}$
• ステップ 3 で、アリスには 3 つの選択肢がありました。C から 2 つを取り除く、C から 1 つを取り除く、B から 1 つを取り除くです。C から 2 つを取り除くと、ボブの位置は になります。C から 1 つを取り除くと、ボブにはそれぞれサイズが 1 の山が 2 つ残り、ステップ 4 で説明したように位置 になります。しかし、B から 1 つを取り除くと、ボブの山には 2 つのオブジェクトが残ります。この場合、彼の動きはと に なるため、彼女の動きは位置 になります。この位置を と呼びます。アリスの位置は、彼女のすべての動きの集合です。${\displaystyle *1}$${\displaystyle \{*1\}}$${\displaystyle *0}$${\displaystyle *1}$${\displaystyle \{*0,*1\}}$${\displaystyle *2}$${\displaystyle {\big \{}*1,\{*1\},*2{\big \}}}$
• 同じ再帰ロジックに従うと、ステップ2ではボブの位置は$${\displaystyle {\big \{}\{*1,\{*1\},*2\},*2{\big \}}.}$$
• 最後に、ステップ1では、アリスの位置は$${\displaystyle {\Big \{}{\big \{}*1,\{*1\},*2{\big \}},{\big \{}*2,\{*1,\{*1\},*2\}{\big \}},{\big \{}\{*1\},\{\{*1\}\},\{*1,\{*1\},*2\}{\big \}}{\Big \}}.}$$

この例のゲームで参照されている特別な名前、、および は、 nimbersと呼ばれます。一般に、nimber は、 nim ゲームで、ちょうど 1 つのヒープにちょうど 個のオブジェクトがある位置に対応します。正式には、nimbers は次のように帰納的に定義されます。 すべての 、 に対して、、 、およびです。${\displaystyle *0}$${\displaystyle *1}$${\displaystyle *2}$${\displaystyle *n}$${\displaystyle n}$${\displaystyle *0}$${\displaystyle \{\}}$${\displaystyle *1=\{*0\}}$${\displaystyle *2=\{*0,*1\}}$${\displaystyle n\geq 0}$${\displaystyle *(n+1)=*n\cup \{*n\}}$

nim berという単語はゲームnimに由来していますが、nimbers は有限で公平なゲームの位置を説明するために使用できます。実際、Sprague-Grundy の定理では、有限で公平なゲームのすべてのインスタンスは単一のnimber に関連付けることができると述べられています。

2 つのゲームは、それぞれの位置を足し合わせることで組み合わせることができます。たとえば、ヒープ、、がある別のニム ゲームを考えてみましょう。 ${\displaystyle A'}$${\displaystyle B'}$${\displaystyle C'}$

ヒープのサイズの移動
 
A'B'C'
1 1 1 アリスはA'から1を取る
0 1 1 ボブはBから1つ取る
0 0 1 アリスはC'から1つ取る
0 0 0 ボブには動く余地がないので、アリスが勝ちます。

これを最初の例と組み合わせて、、、、、、の6つ のヒープを持つ複合ゲームを作成できます。${\displaystyle A}$${\displaystyle B}$${\displaystyle C}$${\displaystyle A'}$${\displaystyle B'}$${\displaystyle C'}$

ヒープのサイズの移動
 ABC A' B' C'  
  
 1 2 2 1 1 1 アリスはAから1を取る
 0 2 2 1 1 1 ボブはA'から1を取る
 0 2 2 0 1 1 アリスはB'から1を取る
 0 2 2 0 0 1 ボブはC'から1を取る
 0 2 2 0 0 0 アリスはBから2を取る
 0 0 2 0 0 0 ボブはCから2を取る
 0 0 0 0 0 0 アリスには動く余地がないので、ボブが勝ちます。

2 つのゲームを区別するために、最初の例のゲームでは、開始位置にラベルを付け、青色で表示します。 ${\displaystyle \color {blue}S}$$${\displaystyle \color {blue}S={\Big \{}{\big \{}*1,\{*1\},*2{\big \}},{\big \{}*2,\{*1,\{*1\},*2\}{\big \}},{\big \{}\{*1\},\{\{*1\}\},\{*1,\{*1\},*2\}{\big \}}{\Big \}}}$$

2 番目のサンプル ゲームでは、開始位置にラベルを付けて赤色にします。 ${\displaystyle \color {red}S'}$$${\displaystyle \color {red}S'={\Big \{}\{*1\}{\Big \}}.}$$

複合ゲームの開始位置を計算するには、プレイヤーが最初のゲームで移動して 2 番目のゲームをそのままにするか、2 番目のゲームで移動して最初のゲームをそのままにするかのいずれかを実行できることを覚えておいてください。したがって、複合ゲームの開始位置は次のようになります。 $${\displaystyle \color {blue}S\color {black}+\color {red}S'\color {black}={\Big \{}\color {blue}S\color {black}+\color {red}\{*1\}\color {black}{\Big \}}\cup {\Big \{}\color {red}S'\color {black}+\color {blue}\{*1,\{*1\},*2\}\color {black},\color {red}S'\color {black}+\color {blue}\{*2,\{*1,\{*1\},*2\}\}\color {black},\color {red}S'\color {black}+\color {blue}\{\{*1\},\{\{*1\}\},\{*1,\{*1\},*2\}\}\color {black}{\Big \}}}$$

位置を追加するための明示的な式は であり、これは、追加が交換法則と結合法則の両方を満たすことを意味します。 ${\displaystyle S+S'=\{S+s'\mid s'\in S'\}\cup \{s+S'\mid s\in S\}}$

公平なゲームにおけるポジションは、次のプレイヤー（順番が回ってきたプレイヤー）が勝つ（- ポジション）か、前のプレイヤーが勝つ（- ポジション）かの 2 つの結果クラスに分類されます。したがって、たとえば、は - ポジションですが、 は-ポジションです。 ${\displaystyle {\boldsymbol {\mathcal {N}}}}$${\displaystyle {\boldsymbol {\mathcal {P}}}}$${\displaystyle *0}$${\displaystyle {\mathcal {P}}}$${\displaystyle *1}$${\displaystyle {\mathcal {N}}}$

2 つの位置と は、どのような位置が追加されて も、常に同じ結果クラスにある場合、同等です。正式には、がと同じ結果クラスにある場合のみです。 ${\displaystyle G}$${\displaystyle G'}$${\displaystyle H}$${\displaystyle G\approx G'}$${\displaystyle \forall H}$${\displaystyle G+H}$${\displaystyle G'+H}$

実行例を使用すると、上記の 1 番目と 2 番目のゲームの両方で、すべてのターンで、アリスはボブを- 位置に追い込む動きをすることができることがわかります。したがって、と は両方とも - 位置です。(組み合わせたゲームでは、ボブが- 位置を持つプレーヤーであることに注意してください。実際、は - 位置であり、補題 2 で説明するように、 を意味します。) ${\displaystyle {\mathcal {P}}}$${\displaystyle \color {blue}S}$${\displaystyle \color {red}S'}$${\displaystyle {\mathcal {N}}}$${\displaystyle {\mathcal {N}}}$${\displaystyle \color {blue}S\color {black}+\color {red}S'}$${\displaystyle {\mathcal {P}}}$${\displaystyle \color {blue}S\color {black}\approx \color {red}S'}$

主定理を証明するための中間ステップとして、あらゆる位置およびあらゆる-位置に対して、同値性が成り立つことを示します。 上記の同値性の定義により、これは、 とがすべての に対して結果クラスを共有することを示すことに相当します。 ${\displaystyle G}$${\displaystyle {\mathcal {P}}}$${\displaystyle A}$${\displaystyle G\approx A+G}$${\displaystyle G+H}$${\displaystyle A+G+H}$${\displaystyle H}$

が - ポジションであると仮定します。すると、前のプレイヤーは に対して勝利戦略を持ちます。 の手には に対する勝利戦略(これは- ポジションであるために存在します) に従って対応し、の手には に対する勝利戦略(これは同様の理由で存在します)に従って対応します。したがって、 も - ポジションである必要があります。 ${\displaystyle G+H}$${\displaystyle {\mathcal {P}}}$${\displaystyle A+G+H}$${\displaystyle A}$${\displaystyle A}$${\displaystyle A}$${\displaystyle {\mathcal {P}}}$${\displaystyle G+H}$${\displaystyle G+H}$${\displaystyle A+G+H}$${\displaystyle {\mathcal {P}}}$

一方、 が- 位置である場合、も - 位置です。これは、次のプレーヤーが勝利戦略を持っているためです。つまり、オプションの中から - 位置を選択し、前の段落から、その位置に追加しても - 位置のままであると結論付けます。したがって、この場合、は と同様に - 位置である必要があります。 ${\displaystyle G+H}$${\displaystyle {\mathcal {N}}}$${\displaystyle A+G+H}$${\displaystyle {\mathcal {N}}}$${\displaystyle {\mathcal {P}}}$${\displaystyle G+H}$${\displaystyle A}$${\displaystyle {\mathcal {P}}}$${\displaystyle A+G+H}$${\displaystyle {\mathcal {N}}}$${\displaystyle G+H}$

これらが 2 つのケースのみであるため、補題は成立します。

次のステップとして、が -位置である場合に限り、 であることを示します。 ${\displaystyle G\approx G'}$${\displaystyle G+G'}$${\displaystyle {\mathcal {P}}}$

順方向では、 と仮定します。 との同値の定義を適用すると、 (加法の可換性により と等しい) は と同じ結果クラスにあることがわかります。 しかし、は -位置である必要があります。 の 1 つのコピーで行われたすべての動きに対して、前のプレイヤーは別のコピーで同じ動きで応答できるため、常に最後の動きを行うことができます。 ${\displaystyle G\approx G'}$${\displaystyle H=G}$${\displaystyle G'+G}$${\displaystyle G+G'}$${\displaystyle G+G}$${\displaystyle G+G}$${\displaystyle {\mathcal {P}}}$${\displaystyle G}$

逆の方向では、仮定により は - 位置であるため、最初の補題 から が導かれます。同様に、も- 位置であるため、最初の補題から の形式で が導かれます 。結合法則と可換法則により、これらの結果の右辺は等しくなります。さらに、は同値関係です。なぜなら、等値は結果クラス上の同値関係だからです。の推移性により、 と結論付けることができます。 ${\displaystyle A=G+G'}$${\displaystyle {\mathcal {P}}}$${\displaystyle G\approx G+A}$${\displaystyle G\approx G+(G+G')}$${\displaystyle B=G+G}$${\displaystyle {\mathcal {P}}}$${\displaystyle G'\approx G'+B}$${\displaystyle G'\approx G'+(G+G)}$${\displaystyle \approx }$${\displaystyle \approx }$${\displaystyle G\approx G'}$

構造的帰納法によって、すべてのポジションがニンバーと同等であることを証明します。より具体的な結果、つまり、与えられたゲームの初期ポジションはニンバーと同等でなければならないという結果は、ゲーム自体がニンバーと同等であることを示しています。

ポジション を考えてみましょう。帰納法の仮説により、すべてのオプションは数字 と同等です。つまり、 とします。 が、数字 の最小除外 (mex)、つまり、ある と等しくない最小の非負整数であることを示します。 ${\displaystyle G=\{G_{1},G_{2},\ldots ,G_{k}\}}$${\displaystyle G_{i}\approx *n_{i}}$${\displaystyle G'=\{*n_{1},*n_{2},\ldots ,*n_{k}\}}$${\displaystyle G\approx *m}$${\displaystyle m}$${\displaystyle n_{1},n_{2},\ldots ,n_{k}}$${\displaystyle n_{i}}$

まず最初に注意すべきことは、2 番目の補題により、 であるということです。がゼロの場合、主張は自明に真です。 それ以外の場合は、 について考えます。 次のプレーヤーがでに手を打った場合、前のプレーヤーはでに動くことができ、逆に次のプレーヤーが で に手を打った場合は となります。 この後、補題の順方向含意により、位置は -位置になります。 したがって、 は -位置であり、補題の逆方向含意を引用すると、 となります。 ${\displaystyle G\approx G'}$${\displaystyle k}$${\displaystyle G+G'}$${\displaystyle G_{i}}$${\displaystyle G}$${\displaystyle *n_{i}}$${\displaystyle G'}$${\displaystyle G'}$${\displaystyle {\mathcal {P}}}$${\displaystyle G+G'}$${\displaystyle {\mathcal {P}}}$${\displaystyle G\approx G'}$

ここで、 が - ポジションであることを示します。これは、2 番目の補題をもう一度使用すると、 を意味します。これは、前のプレーヤーの明示的な戦略を与えることによって行います。 ${\displaystyle G'+*m}$${\displaystyle {\mathcal {P}}}$${\displaystyle G'\approx *m}$

と が空であると仮定します。 すると は空集合となり、明らかに-位置になります。 ${\displaystyle G'}$${\displaystyle *m}$${\displaystyle G'+*m}$${\displaystyle {\mathcal {P}}}$

または、次のプレイヤーが のオプションのコンポーネントに移動する場合を考えます。は最小の除外数であるため、前のプレイヤーはに移動できます。また、前に示したように、任意の位置にそれ自体を加えたものは-位置です。 ${\displaystyle *m}$${\displaystyle *m'}$${\displaystyle m'<m}$${\displaystyle m}$${\displaystyle G'}$${\displaystyle *m'}$${\displaystyle {\mathcal {P}}}$

最後に、次のプレイヤーがコンポーネント をオプション に移動するものとします。の場合、前のプレイヤーはに移動します。そうでない場合、 の場合、前のプレイヤーはに移動します。どちらの場合も、結果は の位置プラスそれ自身になります。(はすべての と異なるように定義されているため、は不可能です。) ${\displaystyle G'}$${\displaystyle *n_{i}}$${\displaystyle n_{i}<m}$${\displaystyle *m}$${\displaystyle *n_{i}}$${\displaystyle n_{i}>m}$${\displaystyle *n_{i}}$${\displaystyle *m}$${\displaystyle n_{i}=m}$${\displaystyle m}$${\displaystyle n_{i}}$

まとめると、および が成立します。推移性により、が期待どおり成立すると結論付けられます。 ${\displaystyle G\approx G'}$${\displaystyle G'\approx *m}$${\displaystyle G\approx *m}$

が公平なゲームのポジションである場合、となる唯一の整数はGrundy 値または Grundy 数と呼ばれ、この値を各ポジションに割り当てる関数は Sprague–Grundy 関数と呼ばれます。RL Sprague と PM Grundy は、nim ポジションとの同値の概念に基づかずに、この関数の明示的な定義を独立に与え、次の特性があることを示しました。 ${\displaystyle G}$${\displaystyle m}$${\displaystyle G\approx *m}$

• サイズ の単一 nim パイル(つまり、位置) の Grundy 値は です。${\displaystyle m}$${\displaystyle *m}$${\displaystyle m}$
• あるポジションが次に動くプレイヤーにとって負けとなるのは、そのグランディ値がゼロの場合のみである。${\displaystyle {\mathcal {P}}}$
• 位置の有限集合の合計のグランディ値は、その加数のグランディ値のニム和に過ぎません。

これらの結果から、あるポジションが のグランディ値を持つ場合、 は と同じグランディ値を持ち 、したがって、任意のポジション に対して同じ結果クラスに属することが直接的に示されている。したがって、Sprague と Grundy は、この記事で説明した定理を明示的に述べたことはないが、この定理は彼らの結果から直接導かれ、​​彼らに帰属している。^{[3] [4]これらの結果は、その後、}リチャード・ガイ、エルウィン・バーレカンプ、ジョン・ホートン・コンウェイらによって組合せゲーム理論 の分野に発展し、現在では、ここで説明した形式で Sprague–Grundy 定理とその証明にまとめられている。この分野は、Winning Ways for your Mathematical PlaysおよびOn Numbers and Gamesという書籍で紹介されている。 ${\displaystyle G}$${\displaystyle m}$${\displaystyle G+H}$${\displaystyle *m+H}$${\displaystyle H}$

• 属理論
• 区別不能指数

• グランディのカット・ザ・ノットのゲーム
• UCLA 数学科による読みやすい入門書
• sputsoft.com の Nim のゲーム
• Milvang-Jensen, Brit CA (2000)、組み合わせゲーム、理論と応用(PDF)、CiteSeerX  10.1.1.89.805