引き算ゲーム

組合せゲーム理論において、減算ゲームは、状態が自然数または数のベクトル（例えば、トークンの山の中のゲームトークンの数や、ボード上の駒の位置）で表され、許可された動きによってこれらの数が減る抽象的な戦略ゲームである。 ^{[1] [2]多くの場合、ゲームの動きによって、指定された}減算セットから値を減算することで任意の数が減算され、減算ゲームごとに減算セットが異なります。^{[1]これらのゲームでは、最後に動いたプレイヤーが勝つ（}通常のプレイ規則）か負ける（ミゼールプレイ規則）かによっても異なります。^[2]また、使用されているもう1つの勝利規則は、すべての数がゼロの位置に動いたプレイヤーが勝ち、それ以外の移動が不可能な位置は引き分けであるというものです。^[1]

注目すべき引き算ゲームの例には次のものがあります。

• ニムは、コインやマッチ棒などのトークンの山が複数ある状態から成り、有効な動きは単一の山から任意の数のトークンを取り除くゲームです。ニムには、各動きの目標がニムの合計がゼロである山のセットに到達することであるというよく知られた最適戦略があり、この戦略は公平なゲームにおける最適プレイのスプレイグ・グランディ定理の中心です。ただし、トークンの山が1つだけの場合、最適なプレイは簡単です（1回の動きですべてのトークンを取り除くだけです）。^[3]
• 減算平方はニムのバリエーションで、1回の移動で平方数のトークンしか削除できません。結果として得られるゲームは、トークンの山が1つであっても、自明ではない戦略を持っています。フュルステンベルク・サルコジ定理は、その勝利の位置が整数の密度ゼロであることを示しています。^[4]
• フィボナッチニムはニムの別のバリエーションで、許可される移動は同じトークンの山への以前の移動によって決まります。山への最初の移動では、山全体を取ることは禁止されており、その後の移動では、減算される量は同じ山から以前に取り除かれた量の2倍以下でなければなりません。^[5]
• ウィトフのゲームは、チェスのクイーンを大きなチェス盤の上に置き、各ステップでそれを（チェスのクイーンの通常のやり方で）盤の下側、左側、または左下隅に向かって動かすことによってプレイされます。このゲームは、2つのトークンの山で同等に説明でき、各移動で片方または両方の山から任意の数のトークンを削除でき、両方の山が減った場合は各山から同じ数のトークンを削除します。ビーティシーケンスと黄金比を含む最適戦略があります。^[6]

減算ゲームは一般に公平なゲームであり、特定の位置で実行できる移動のセットはそのプレイヤーの順番によって決まりません。このようなゲームでは、状態は- 位置 (直前に動いたプレイヤーが勝っている位置) と- 位置 (次に動くプレイヤーが勝っている位置) に分けられ、最適なゲームプレイ戦略は、可能な場合は常に - 位置に動くことです。たとえば、通常のプレイ規則と 1 つのトークンの山では、減算セット内のすべての数字は - 位置です。これは、プレイヤーがそのような数字から 0 に移動することで勝つことができるためです。^[2]${\displaystyle {\mathcal {P}}}$${\displaystyle {\mathcal {N}}}$${\displaystyle {\mathcal {P}}}$${\displaystyle {\mathcal {N}}}$

複数の数字があり、各動きでこれらの数字のうちの 1 つだけが減算され、特定の数字から可能な減算がその数字のみに依存し、ゲーム状態の残りの部分に依存しない通常のプレイの減算ゲームの場合、Sprague-Grundy の定理を使用して、各数字の「ニム値」を計算できます。これは、ニムのゲームで同等の位置を表す数字で、ゲーム状態全体の値はそのニム値のニム合計になります。このようにして、ゲーム全体の最適戦略は、単一の数字のみがある単純化されたゲーム位置のセットのニム値の計算に簡略化できます。^[7]ニム値は、-位置の場合はゼロで、-位置の場合はゼロ以外です。Tom Fergusonの定理によると、ニム値が 1 の単一数字の位置は、-位置に減算セットの最小値を追加して得られる数字とまったく同じです。ファーガソンの結果は、通常のプレイ戦略からわずかな変更を加えるだけで、マルチパイルミゼール減算ゲームにおける最適な戦略につながる。^[8]${\displaystyle {\mathcal {P}}}$${\displaystyle {\mathcal {N}}}$${\displaystyle {\mathcal {P}}}$

トークンの山が 1 つあり、減算セットが固定されている (ただし、無限である可能性もある) 減算ゲームの場合、減算セットのメンバー間に任意の大きなギャップがある場合、ゲームの - 位置の集合は必然的に無限になります。^[9]有限減算セットを持つすべての減算ゲームでは、nim 値は制限され、 - 位置と- 位置への分割と nim 値のシーケンスは最終的に周期的になります。周期は減算セットの最大値よりも大幅に大きくなる可能性がありますが、最大 です。^[10]ただし、制限された nim 値を生成するが、これらの値のシーケンスは非周期的である無限減算セットが存在します。^[11]${\displaystyle {\mathcal {P}}}$${\displaystyle {\mathcal {P}}}$${\displaystyle {\mathcal {N}}}$${\displaystyle x}$${\displaystyle 2^{x}}$

減算ゲームでは、減算セットが固定されている（ただし、無限の場合もある）場合、特定の値までの数の P 位置と N 位置への分割は、の時間で計算できます。 までのすべての数の nim 値は、 の時間で計算できます。ここで、 は減算セットのサイズ（ まで）を表し、 はこの計算で発生する最大の nim 値を表します。^[12]${\displaystyle n}$${\displaystyle O(n\log ^{2}n)}$${\displaystyle n}$${\displaystyle O(\min(ns,nm\log ^{2}n))}$${\displaystyle s}$${\displaystyle n}$${\displaystyle m}$

自然数のベクトル上で行われる減算ゲームの一般化では、そのベクトルが正の係数と負の係数を持つ減算セットを使用して、2つのゲームが同じP位置とN位置を持つかどうかを判断することは決定不可能な問題です。 ^[13]

• グランディのゲームとオクタルゲームは、動きによってトークンの山が2つに分割される減算ゲームの一般化である。

• Althöfer, Ingo ; Bültermann, Jörg (1995)、「いくつかの減算ゲームにおける超線形周期長」、理論計算機科学、148 (1): 111–119、doi :10.1016/0304-3975(95)00019-S、MR  1347670
• バーレカンプ、エルウィン R. ;コンウェイ、ジョン H. ;ガイ、リチャード K. (2001)、数学的プレイの勝利の方法、第 1 巻 (第 2 版)、AK ピーターズ
• ブートン、チャールズ L. (1901–1902)、「ニム、完全な数学理論を備えたゲーム」、数学年報、第 2 シリーズ、3 (1/4): 35–39、doi :10.2307/1967631、JSTOR  1967631
• Coxeter, HSM (1953)、「黄金分割、葉序、および Wythoff のゲーム」、Scripta Mathematica、19 : 135–143、MR  0057548
• Eppstein、David (2018)、「減算ゲームの高速評価」、伊藤、ヒロ;レオナルディ、ステファノ。Pagli, リンダ;プレンシペ、ジュゼッペ（編）、Ｐｒｏｃ．第 9 回アルゴリズムを楽しむ国際会議 (FUN 2018)、ライプニッツ国際情報学論文集 (LIPIcs)、vol. 100、ダグシュトゥール、ドイツ: Schloss Dagstuhl – Leibniz-Zentrum für Informatik、pp. 20:1–20:12、doi : 10.4230/lipics.fun.2018.20
• ファーガソン、TS (1974)、「最後のプレイヤーが負けるグラフゲームの合計について」、国際ゲーム理論ジャーナル、3 (3): 159–167、doi :10.1007/BF01763255、MR  0384169
• ゴロム、ソロモン W. (1966)、「テイクアウェイゲームの数学的調査」"、組み合わせ理論ジャーナル、1（4）：443–458、doi：10.1016 / S0021-9800（66）80016-9、MR  0209015
• Larsson, Urban; Fox, Nathan (2015)、「Nim 次元 2 の非周期減算ゲーム」(PDF)、Journal of Integer Sequences、18 (7)、Article 15.7.4、arXiv : 1503.05751、MR  3370791
• ラーソン、アーバン; ルビンシュタイン-サルゼド、サイモン (2016)、「フィボナッチ数のグランディ値」、国際ゲーム理論ジャーナル、45 (3): 617–625、arXiv : 1410.0332、doi :10.1007/s00182-015-0473-y、MR  3538534
• ラーソン、アーバン、ウェストランド、ヨハン (2013)、「マッチの山から計算可能性の限界まで」、電子ジャーナル オブ コンビナトリクス、20 (3): P41:1–P41:12、arXiv : 1202.0664、doi :10.37236/2244、MR  3118949
• ウィニハン、マイケル・J. (1963)、「フィボナッチ・ニム」(PDF)、フィボナッチ・クォータリー、1 (4): 9–13
• ワシントン州ワイソフ(1907)、「ニム ゲームの修正」、Nieuw Archief voor Wiskunde、7 (2): 199–202