cos

一、フィボナッチゲーム#

説明#

基本的なフィボナッチゲーム（Fibonacci Game）は以下のように説明されます：

一堆の石があり、二人の非常に賢い人がゲームをします。最初に取る人は任意の数を取ることができますが、全てを取ることはできません。その後、毎回取ることができる石の数は少なくとも 1、最大で相手が直前に取った石の数の 2 倍です。最後の石を取った人が勝者とし、必敗の状態を求めます。

結論#

総石数がフィボナッチ数であるとき、先手は必敗です。

証明#

証明は以下の通りで、大佬の証明から転用しています。
ゼッケンドルフ定理を用います（Zeckendorf 定理）：任意の正整数は不連続なフィボナッチ数の和として表すことができます。

二、バッシュゲーム#

説明#

基本的なバッシュゲーム（Bash Game）は以下のように説明されます：

一堆の n 個の物品があり、二人が交互に物品を取ります。毎回少なくとも 1 個、最大で m 個を取ることができます。最後に全てを取った者が勝者です。

結論#

もし n % (m+1) == 0 であれば、先手は必敗です。

bool FirstWin(int n, int m) { //先手必勝の場合はtrueを返す
	return n % (m+1) != 0;
}

証明#

ゲームの過程は以下の通りです：証明
ここで簡単に説明します。
同余定理：もし n%(m+1) = r で、先に取る者が r 個を取った場合、後者は 1〜m の任意の個数を取ることができ、先手は（m+1）個を満たすためにさらにいくつかを取ることができるため、先手は必勝です。逆に先手は必敗です。n<m の場合、先手は一度に全てを取ることができ、これも必勝です。

バッシュゲームの変形#

一堆の n 個の物品があり、二人が交互に物品を取ります。毎回少なくとも p 個、最大で q 個を取ります。残りが p 個未満の場合は一度に全てを取ります。最後に全てを取った者が勝者です。

もし n%(p+q) = r であれば、r != 0 && r < p のとき先手は必勝、逆に先手は必敗です。

三、ウィソフゲーム#

説明#

基本的なウィソフゲーム（Wythoff Game）は以下のように説明されます：

二堆の物品があり、二人が交互に一堆からまたは同時に二堆から同じ数の物品を取ります。毎回少なくとも 1 個を取り、多くは制限なしで、最後に全てを取った者が勝者です。

結論#

二堆の物品がそれぞれ a、b 個あるとき、ab の差を求めて黄金比で掛け算し、その結果が ab の最小値と等しい場合、先手は必敗です。

bool FirstWin(int a, int b) { //先手必勝の場合はtrueを返す
	double G = (sqrt(5.0)+1) / 2;	//黄金比
	int t = abs(a-b) * G;
	return d != min(a,b);	
}

証明#

証明は複雑です… 一時的に板を保存しておきます。ここで証明を見てください。

四、ニムゲーム#

説明#

基本的なニムゲーム（Nim Game）は以下のように説明されます：

複数の堆にそれぞれいくつかの物品があり、二人が交互に任意の数の物品を一堆から取ります。毎回少なくとも 1 個、多くは制限なしで、最後に全てを取った者が勝者です。

結論#

N 堆の物品の数を全て排他的論理和（XOR）した結果が 0 であれば先手は必敗、そうでなければ先手は必勝です。

bool FirstWin(int a, int b) { //先手必勝の場合はtrueを返す
	int ans = 0;
	for(int i = 0; i < N; ++i) ans ^= a[i];//a[i]は物品の数
	return ans != 0;
}

証明#

証明も非常に複雑です… ここで証明を見てください。
後で SG 関数を紹介します。一般的に最終局面の SG 値を 0 と設定します。
SG 定理：ゲームの和の SG 値は各子ゲームの SG 値の排他的論理和です。
以上の結論を知ると、Nim ゲームは実際には n 個の Bash ゲームに分けることができ、Bash ゲームが無限に子を取ることができる場合、現在の局面の残りの石の数を状態とし、SG (x)=x となります。したがって、この問題の答えは各堆の石の数の排他的論理和の値であり、値が 0 であれば先手は必敗、そうでなければ先手は常に次の局面の排他的論理和の値を 0 にする戦略を持ち、後手は必敗です。

変形#

参考ブログNim ゲーム及びその変形

反ニムゲーム#

反ニムゲームはその名の通り、

複数の堆にそれぞれいくつかの物品があり、二人が交互に任意の数の物品を一堆から取ります。毎回少なくとも 1 個、多くは制限なしで、最後に全てを取った者が敗者です。

例題 E - ミゼレニム
先手は必勝の 2 つの状況があります。1 つは全ての堆の石の数が 1 で、排他的論理和が 0 であること、もう 1 つは石の数が 1 でない堆があり、排他的論理和が 0 でないことです。

五、SG 関数#

参考ブログ：SG 関数、組合せゲーム - SG 関数と SG 定理

1. 概念紹介#

ICG ゲーム（公平組合せゲーム）#

条件は以下の通り：問題の説明は一般に A,B の二人がゲームをします。

1. A、B が交互に操作を行います。
2. 各操作の際、選手は合法的な操作集合から任意の操作を選ぶことができます。
3. ゲームのあらゆる可能な局面に対して、合法的な操作集合はその局面自体のみに依存し、他の要因（選手や以前のすべての操作には関係ありません）には依存しません。
4. 現在の選手が合法的な操作を行えない場合、敗北と判定されます。

上記のバッシュゲームを背景に、一堆の n 個の物品があり、二人が交互に物品を取ります。毎回少なくとも 1 個、最大で m 個を取ります。最後に全てを取った者が勝者です。
公平なゲームは抽象的に有向非巡回グラフで表すことができ、このグラフの各点は一つの状態に対応し、各有向辺はある状態から別の状態への合法的な操作を表します。

必勝状態と必敗状態#

• 必敗状態（P-position）：前の選手（つまり、直前に操作を行った選手）が必勝局面にいる場合、この状態に直面する者は必敗です。
• 必勝状態（N-position）：次の選手（つまり、これから操作を行う選手）が必勝局面にいる場合、この状態に直面する者は必勝です。

性質：

• すべての終端点は必敗状態です。
• すべての必勝状態から操作を行うと、少なくとも 1 つの方法で必敗状態に入ることができます。
• どのように操作しても、必敗状態からは必勝状態にしか入れません。

2.SG 関数#

定義 mex 演算#

まず mex（minimal excludant）演算を定義します。これは集合に適用される演算で、その集合に属さない最小の非負整数を表します。

• 例えば mex {2,3,5}=0、mex {0,1,2,4}=3、mex {}=0。

任意の状態 x に対して、SG (x)=mex (S) と定義します。ここでS は x の後続状態の SG 関数値の集合です。例えば x に 3 つの後続状態 a、b、c がある場合、SG (x)=mex {SG (a), SG (b), SG (c)}。したがって、集合 S の終端状態は必ず空集合になるため、x が必敗点 P であるときに限り、SG 関数の終端は SG (x)=0 になります。

SG 関数を通じて、各 ICG は Nim ゲームに変換できます。SG 関数の定義域は ICG の決定木上のすべてのノードであり、この場合具体的には SG (x)=mex {SG (y)|y は x のノード} と定義されます。ICG の決定木上のノード u について、これを SG (u) の Nim ゲームを持つ一堆の石子の数として想像できます。SG 関数の解法はこのブログを通じて理解しました:組合せゲーム - SG 関数と SG 定理。

石を取る問題
1 堆 n 個の石があり、毎回 {1, 3, 4} 個の石を取ることができ、先に全てを取った者が勝者です。このとき各数の SG 値はどのようになりますか？

SG[0]=0、f[]={1,3,4}、

• x=1 のとき、1 - f {1} 個の石を取ることができ、残りは {0} 個なので SG [1] = mex { SG [0] }= mex {0} = 1;
• x=2 のとき、2 - f {1} 個の石を取ることができ、残りは {1} 個なので SG [2] = mex { SG [1] }= mex {1} = 0;
• x=3 のとき、3 - f {1,3} 個の石を取ることができ、残りは {2,0} 個なので SG [3] = mex {SG [2],SG [0]} = mex {0,0} =1;
• x=4 のとき、4- f {1,3,4} 個の石を取ることができ、残りは {3,1,0} 個なので SG [4] = mex {SG [3],SG [1],SG [0]} = mex {1,1,0} = 2;
• x=5 のとき、5 - f {1,3,4} 個の石を取ることができ、残りは {4,2,1} 個なので SG [5] = mex {SG [4],SG [2],SG [1]} =mex {2,0,1} = 3;

このように続けます…
x = 0 1 2 3 4 5 6 7 8…
SG[x] = 0 1 0 1 2 3 2 0 1…

上記の例から SG 関数値の求解手順が得られます。1〜n の SG 関数値を計算する手順は以下の通りです：

1. 配列 f を使用して現在の状態を変更する方法を記録します。
2. 別の配列を使用して現在の状態 x の後続状態をマークします。
3. 最後に mex 演算をシミュレートします。つまり、マークされた値の中から未マークの最小値を検索し、それを SG (x) に割り当てます。
4. ステップ 2-3 を繰り返すことで、1〜n の関数値を計算します。
   テンプレートは以下の通りです：

//f[N]:現在の状態を変更する方法、Nは方法の種類、f[N]はgetSGの前に前処理する必要があります
//SG[]:0〜nのSG関数値
//S[]:xの後続状態の集合
int f[N],SG[MAXN],S[MAXN];
void  getSG(int n){
    int i,j;
    memset(SG,0,sizeof(SG));
    //SG[0]は常に0であるため、iは1から始まります
    for(i = 1; i <= n; i++){
        //毎回前の状態の後続集合をリセットする必要があります
        memset(S,0,sizeof(S));
        for(j = 0; f[j] <= i && j <= N; j++)
            S[SG[i-f[j]]] = 1;  //後続状態のSG関数値をマークします
        for(j = 0;; j++) if(!S[j]){   //現在の後続状態SG値の中で最小の非ゼロ値を検索します
            SG[i] = j;
            break;
        }
    }
}  

3.SG 定理#

1. ゲームの和の SG 関数はすべての子ゲームの SG 関数の排他的論理和です。
2. したがって、すべての堆の SG 関数の排他的論理和が 0 でないとき、先手は必勝です。

六、グリーンハッケンブッシュ（木の上の辺を削除するゲーム）#

最初の問題でつまずき、解答を検索したところ、学んだことのないグリーンゲームであることがわかりました。
参考ブログ：ゲーム - グリーンハッケンブッシュ、以下の内容はここからのものです。

1. ハッケンブッシュゲームの概要#

ハッケンブッシュゲームは、根付きグラフの特定の辺を削除することで、床に接続されている辺がなくなるまで続きます。床は破線で示され、特定の辺を削除すると、その辺の上に接続されているすべての辺も削除されます。ここでは、このゲームの公平なバージョンについて議論します。各プレイヤーは自分のターンに任意の辺を削除できます。このバージョンをグリーンハッケンブッシュと呼び、すべての辺は緑色です。以下では GH ゲームと略します。 ここには不公平なバージョンもあり、青赤ハッケンブッシュと呼ばれ、一部の辺は青、一部は赤であり、プレイヤー 1 は青い辺のみを削除でき、プレイヤー 2 は赤い辺のみを削除できます。一般的に、ハッケンブッシュゲームには、プレイヤー 1 が削除できる青い辺、プレイヤー 2 が削除できる赤い辺、両方のプレイヤーが操作できる緑の辺が含まれます。

2. クロン原理（Colon Principle）#

木の特定の点について、その分岐はこの点を根とする竹に変換できます。この竹の長さは、その各分岐の辺の数の排他的論理和です。

すべての辺の重みが 1 の場合、これは裸のグリーンゲームであり、各点の sg 関数は子ノードの sg 関数の排他的論理和 + 1 です。
重みが異なる場合、AB の重みが 1 の場合、sg [A]=sg [B]+1 です。
AB の重みが偶数の場合、sg [A]=sg [B] です。
AB の重みが奇数の場合、sg [A]=sg [B]^1 です。