スプラーグ・グランディの定理

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

公平なゲームのグランディ値またはニム値とは、そのゲームが等価となる唯一のニンバーのことです。ゲームの位置が自然数でインデックス付けされている場合（ヒープサイズでインデックス付けされているニム自体のように）、ゲームの連続する位置に対応するニンバーの列は、そのゲームのニム列と呼ばれます。

スプラーグ・グランディの定理とその証明は、RP スプラーグ(1936 年) ^{[ 1 ]}とPM グランディ(1939 年) ^{[ 2 ]によって独立に発見された理論の主な結果をまとめたものである。}

スプラーグ・グランディの定理の目的上、ゲームとは、終了条件（すべてのゲームは終了する：無限のプレイラインは存在しない）と通常プレイ条件（動けないプレイヤーは負ける）を満たす、完全情報を持つ2人プレイの逐次ゲームである。

ゲームのどの時点においても、プレイヤーのポジションとは、そのプレイヤーが実行できる一連の手を指します。例として、ゼロゲームとは、どちらのプレイヤーも合法的な手を一切持っていない2人対戦ゲームと定義できます。2人のプレイヤーを${\displaystyle A}$（アリスのために）そして${\displaystyle B}$（ボブの場合）彼らの位置を次のように表します。${\displaystyle (A,B)=(\{\},\{\})}$各プレイヤーが行える動きの集合は空であるため、

公平なゲームとは、ゲームのどの時点においても、各プレイヤーが全く同じ一連の動きを許されるゲームのことです。通常のニムは公平なゲームの一例です。ニムでは、1つ以上の物の山があり、2人のプレイヤー（アリスとボブとしましょう）が交互に山を選び、そこから1つ以上の物を取り除きます。最後の山から最後の物を取り除いたプレイヤーが勝者となります。このゲームが公平なのは、山のサイズのどの組み合わせにおいても、アリスが自分の番にできる動きは、ボブが自分の番にできる動きと全く同じだからです。対照的に、チェッカーのようなゲームは公平ではありません。アリスが赤、ボブが黒でプレイしていると仮定すると、盤上の駒の配置がどうであれ、アリスの番であれば赤い駒しか動かすことができず、ボブの番であれば黒い駒しか動かすことができないからです。

したがって、公平なゲームのどの構成も単一の局面として記述できることに注意してください。なぜなら、どちらのターンであっても動きは同じだからです。たとえば、ゼロゲームの局面は単純に次のように記述できます。${\displaystyle \{\}}$なぜなら、アリスの番であれば彼女には何もする手がなく、ボブの番であれば彼にも何もする手がないからです。手は、次のプレイヤーが置かれる位置と関連付けることができます。

そうすることで、局面を再帰的に定義することが可能になります。例えば、アリスとボブがプレイする次のニムゲームを考えてみましょう。

山のサイズ 移動 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 ボブは動けないので、アリスの勝ち 

山のサイズ 移動   A' B' C' 1 1 1 アリスはA'から1を取ります 0 1 1 ボブはBから1つ取る 0 0 1 アリスはCから1つ取る 0 0 0 ボブにはもう動ける手がないので、アリスの勝ちです。 

山のサイズ 移動 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 アリスにはもう動かせる手がないので、ボブの勝ちです。 

主定理を証明するための中間段階として、あらゆる位置について以下を示す。${\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}}}$-位置。

前進方向では、${\displaystyle G\approx G'}$等価性の定義を適用する${\displaystyle H=G}$すると、${\displaystyle G'+G}$（これは${\displaystyle G+G'}$（加法の交換法則により）は、同じ結果クラスに属します。${\displaystyle G+G}$。 しかし${\displaystyle G+G}$でなければならない${\displaystyle {\mathcal {P}}}$-位置: 1 つのコピーで行われたすべての移動に対して${\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'}$。

構造的帰納法を用いて、すべての局面がニンバーと等価であることを証明する。より具体的な結果として、与えられたゲームの初期局面がニンバーと等価でなければならないという結論は、ゲーム自体がニンバーと等価であることを示している。

ポジションを検討${\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}$は、数値の最小除外値（mex）です。${\displaystyle n_{1},n_{2},\ldots ,n_{k}}$つまり、ある値に等しくない最小の非負整数${\displaystyle n_{i}}$。

まず最初に注目すべき点は、${\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'}$。

それでは、${\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}$ご希望に応じて。

もし${\displaystyle G}$は公平なゲームの位置であり、唯一の整数である${\displaystyle m}$そのため${\displaystyle G\approx *m}$は、そのグランディ値またはグランディ数と呼ばれ、このような各位置にこの値を割り当てる関数は、スプラーグ・グランディ関数と呼ばれます。RL スプラーグと PM グランディは、ニム位置との等価性の概念に基づかずに、この関数を独立に明示的に定義し、次の性質を持つことを示しました。

• 単一のニムパイルのサイズのグランディ値${\displaystyle m}$（つまり、その位置の）${\displaystyle *m}$） は${\displaystyle m}$;
• ポジションは、次に動くプレイヤーにとっての損失です（つまり、${\displaystyle {\mathcal {P}}}$-位置) は、そのグランディ値がゼロの場合に限る。
• 有限個の位置の和のグランディ値は、その和の項のグランディ値のニム和に等しい。

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

• 種族理論
• 区別不能指数

• グランディの結び目切断ゲーム
• UCLA数学科による、読みやすい入門書。
• sputsoft.comの「ニムのゲーム」
• Milvang-Jensen, Brit CA (2000), Combinatorial Games, Theory and Applications (PDF) , CiteSeerX 10.1.1.89.805