パスあり石取りゲームの必勝判定法
本記事で扱う石取りゲームについて
石取りゲームとは、2人のプレイヤーがいくつかの山から石を交互に取っていき、最後に石を取った者が勝ちであるというゲームである。buku
- 初めに複数の山を作っておく
- 2人のプレイヤーが交互にどれかの山を選んで、その山からいくつでもよいので石をとる。
- すべての山から石がなくなった状態（終了局面）にした者が勝ち
本記事では、上記のシンプルな石取りゲームをパスなしの石取りゲームと呼び、それに加えてパスが使える石取りゲーム（パスありの石取りゲーム）も取り扱う。ただし、パスは2人のプレイヤーで1回のみである。片方のプレイヤーが使用するともう一方のプレイヤーは使用できない。
パスなしの石取りゲーム(理系通信, 佐藤)
まず、パスなしの石取りゲームについて必勝法を説明していく。
ゲームの例
最初に山X、山Y、山Zの3山あり、それぞれの石の数が3、2、1個であったとする。この局面を(3,2,1)とあらわすこととする。各数字が山X、Y、Zの石の個数を表している。先手が山Xから2個の石をとると、局面は(1,2,1)となる。次に後手が山Yから2個とると、局面は(1,0,1)となる。次に先手が山Xから1つの石をとると局面は(0,0,1)となる。最後に後手が山Zから1個の石をとると、局面は終了局面(0,0,0)となるため、後手の勝ちである。
1山の場合
山が1つの局面から開始する場合、最初に何個の石があろうと、初手でそのすべての石をとってしまえるので、先手必勝である。
2山の場合
山が2つの場合、2つの山の石の数をそろえることが必勝法となる。例えば、山Xの石が2つで、山Yの石が5つの局面の場合、山Yの石から石を3つ取り山X、山Yいずれも石の数を2つにして相手に手番を渡す。そうすると相手は片方の山から石を取らないといけないため、2つの山の石の数が等しくなくなる。これを繰り返せば、最終的には両方の山の石の数が0になった終了局面に持ち込め勝つことができる。
すなわち、開始局面で2つの山の石の数が異なっている場合は先手必勝であり、2つの山の石の数が等しい場合は後手必勝である。
3山以上の場合
3山以上の場合の場合は、やや複雑ではあるものの必勝法が研究されている。
最小除外数（mex）
ある非負整数の集合Tがあったとき、その最小除外数(mex)とはTに属さない最小の非負整数のことである。すなわち、
\begin{eqnarray}
mex(T)=min(\mathbb{N}-T)
\end{eqnarray}
である。
T={0,1,3,4}の場合、
\begin{eqnarray}
mex(T)=min({2,5,6,\cdots})=2
\end{eqnarray}
である。
T={1,3,4}の場合、
\begin{eqnarray}
mex(T)=min({0,2,5,6,\cdots})=0
\end{eqnarray}
である。
Grundy数(グランディ数)の定義
Grundy数は以下のように定義される。
- 終了局面のGrundy数は0とする。
- ある局面のGrundy数は、その次に取りうる局面のGrundy数の集合の最小除外数とする。
定義どおりのgrundy数の計算例1
山が1つで石が1つの場合、次局面は終了局面のみであり終了局面のGrundy数は0であるため、
\begin{eqnarray}
Grundy数=mex({0})=min({1,2,3,\cdots})=1
\end{eqnarray}
である。
山が1つで石が2つの場合、次局面は、石が0個の終了局面と石が1つの局面の2局面である。それら次局面のGrundy数はそれぞれ0、1であるため、$$ Grundy数=mex({0,1})=min({2,3,4,\cdots})=2 $$である。
同様に計算していけば、山が1つで石がn個の場合のGrundy数はnであるとわかる。
定義どおりのGrundy数の計算例2
山が2つで、いずれの山も石が1つの局面(1,1)の場合、次局面は山が1つでその山の石の数が1つのみの局面((0,1)または(1,0))しかない。その局面のGrundy数は先ほど求めた通り1であるため、現局面のGrundy数は
\begin{eqnarray}
Grundy数=mex({1})=min({0,2,3,\cdots})=0
\end{eqnarray}
である。
山が2つで、各山の石数が1、2の局面(1,2)の場合、次局面は(0,2),(1,1),(1,0)の3種類である。それらの局面のGrundy数は順に、2, 0, 1である。したがって、現局面のGrundy数は
\begin{eqnarray}
Grundy数=mex({2, 0, 1})=min({3,4,5,\cdots})=0
\end{eqnarray}
である。
Grundy数と必勝法の関係
Grundy数の定義より、Grundy数が0の局面の場合、次の局面のGrundy数には0が含まれていない。したがって、Grundy数が0の局面で相手の手番となっていれば、相手はどのような手を指したとしても、自分にはGrundy数が0以外の局面が回ってくる。一方、Grundy数が0以外の局面の場合、次の局面の中にはGrundy数が0の局面が含まれている。すなわち、Grundy数が0以外の局面で自分の手番となっていれば、Grundy数が0の局面にして相手に手番を渡すことができる。
つまり、Grundy数が0の局面が開始局面の場合は後手必勝であり、0以外の局面は先手必勝である。
次の項からGrundy数を簡単に求める方法について説明する。
排他的論理和
排他的論理和は数を2進法で表し、繰り上がりなしで各位の和を計算する方法である。2進法で1桁の場合は、
\begin{eqnarray}
0 \oplus 0 = 0 \\
0 \oplus 1 = 1 \\
1 \oplus 0 = 1 \\
1 \oplus 1 = 0 \\
\end{eqnarray}の4種類である。
3、5、7の排他的論理和は、
\begin{eqnarray}
011 \\
101 \\
\oplus ) 111 \\
―――\\
001
\end{eqnarray}より1である。
排他的論理和によるGrundy数の求め方
石の数がx、y、zの山がある局面(x,y,z)のGrundy数をg(x,y,z)と表す。
実は、以下の式のように、Grundy数は排他的論理和で計算できるのである。$$
g(x,y,z)=x \oplus y \oplus z
$$
この式は山数は3以外でも成り立つ。
排他的論理和によるgrundy数の計算例1
1つ山の場合、排他的論理和をおこなわないと考えてもよいし、他の山の石の数が0として0と排他的論理和をおこなうと考えてもよいが、いずれにしろGrundy数は石の数がGrundy数となる。つまりGrundy数は0以外であり、先手必勝である。
排他的論理和によるgrundy数の計算例2
2つ山の場合、石の数が同じ場合、排他的論理和は0となり、後手必勝である。石の数が異なる場合、排他的論理和は0以外となり、先手必勝である。
排他的論理和によるgrundy数の計算例3
最初に挙げた局面(3,2,1)の場合、$ 3 \oplus 2 \oplus 1 = 0$であるため、g(3,2,1)=0であり後手必勝である。奇数手目が先手番、偶数手目が後手番と数えると、1手目のあとg(1,2,1)=2の局面となり、2手目のあとg(1,0,1)=0の局面となり、3手目のあとg(0,0,1)=1の局面となり、4手目のあとg(0,0,0)=0の終了局面となる。後手は2手目で的確にGrundy数が0となるように石を取って勝利している。
排他的論理和の性質
任意の非負整数nについて、
\begin{eqnarray}
n \oplus n = 0
\end{eqnarray}
排他的論理和は2進数に変換し位ごとに計算するのであった。
同じ数同士の排他的論理和では、すべての位で同じ数の排他的論理和となる。
\begin{eqnarray} 0 \oplus 0 = 0 \\ 1 \oplus 1 = 0 \\ \end{eqnarray}
であるため、任意の非負整数nの自分との排他的論理和は、すべての位で0となる。したがって、
\begin{eqnarray}
n \oplus n = 0
\end{eqnarray}
が成り立つ。
任意の異なる非負整数m、nについて、
\begin{eqnarray}
m \oplus n \neq 0
\end{eqnarray}
排他的論理和は2進数に変換し位ごとに計算するのであった。
異なる数同士の排他的論理和では、いずれかの位で異なる数の排他的論理和となる。
\begin{eqnarray} 0 \oplus 1 = 1 \\ 1 \oplus 0 = 1 \\ \end{eqnarray}
であるため、任意の異なる非負整数m、nの排他的論理和はいずれかの位が1となっている。したがって、
\begin{eqnarray}
m \oplus n \neq 0
\end{eqnarray}
となる。
2つ山のGrundy数と3つ山の必勝判定の関係（パスなしバージョン）
- z=g(x,y)ならば、g(x,y,z)=0
- z≠g(x,y)ならば、g(x,y,z)≠0
z=g(x,y)
⇒ g(x,y)$\oplus$z=0 ($\because$補題1)
⇒ x$\oplus$y$\oplus$z=0
⇒ g(x,y,z)=0
z≠g(x,y)
⇒ g(x,y)$\oplus$z≠0 ($\because$補題2)
⇒ x$\oplus$y$\oplus$z≠0
⇒ g(x,y,z)≠0
パスありの石取りゲーム
前項までに記したように、パスなしの場合、Grundy数を排他的論理和で計算することができ、先手必勝か後手必勝かを容易に判別できる。パスありの石取りゲームについて詳細に説明した参考文献は見つけられなかった。私が調べた結果を以下に示す。
山の数は1、2、3のいずれかとする。パスは2人のプレイヤーで1回のみである。片方のプレイヤーが使用するともう一方のプレイヤーは使用できない。
局面をパスの残数と石の数で(p,x,y,z)のように表すこととする。パスの数と石の数を混同しないように、パスが残っているときp=p1、パスが残っていないときp=p0と表す。例えば、パスが残っていて、石の数が2、4、7の局面は(p1,2,4,7)と表す。
終了局面
パスは使わなくても良い。とにかく、すべての石がなくなった局面が終了局面であり、最後に石を取った方が勝ちである。
3つ山の場合、終了局面は(p0,0,0,0)と(p1,0,0,0)の2通りとなる。
Grundy数
Grundy数の定義はパス無しの場合と同じである。
- 終了局面のGrundy数は0とする。
- ある局面のGrundy数は、その次に取りうる局面のGrundy数の集合の最小除外数とする。
局面(p,x,y,z)のGrundy数はg(p,x,y,z)と表す。
1つ山の場合
パスが残っていて石の数がxの局面を(p1,x)と表し、パスが残っておらず石の数がxの局面を(p0,x)と表す。終了局面は(p0,0)と(p1,0)である。したがって、$$
g(p0,0)=g(p1,0)=0
$$である。
パスが残っていない1つ山の局面では石の数がGrundy数であった。すなわち、$$
g(p0,x)=x
$$である。
(p1,1)の次局面はパスを使った場合の(p0,1)と石を取った場合の(p1,0)のみであり、それらのGrundy数は、\begin{eqnarray}
g(p0,1)=1 \\
g(p1,0)=0
\end{eqnarray}
であるため、\begin{eqnarray}
g(p1,1)=mex(1,0)=min(2,3,4, \cdots )=2
\end{eqnarray}である。このように逐次的にGrundy数を求めることができる。
以下の表は1つ山のGrundy数を表している。
1行目は石の数を、2行目はパスが残っている場合のGrundy数を、3行目はパスが残っていない場合のGrundy数を表している。
| 0 | 1 | 2 | 3 | 4 | … | |
|---|---|---|---|---|---|---|
| パスあり(p=p1) | 0 | 2 | 1 | 4 | 3 | … |
| パスなし(p=p0) | 0 | 1 | 2 | 3 | 4 | … |
例えば、局面(p1,3)の次局面は(p0,3),(p1,0),(p1,1),(p1,2)であり、それらのGrundy数は3,0,2,1であるため、それらの最小除外数よりg(p1,3)=4と求まる。
一般に、パスあり1つ山の場合、石の数が奇数(2n-1)の場合、Grundy数は2nとなり、石の数が偶数2nの場合、Grundy数は(2n-1)となる。つまり、nが自然数のとき、\begin{eqnarray}
g(p1,2n-1)=2n \\
g(p1,2n)=2n-1
\end{eqnarray}である。
2つ山の場合
まず、パスなしの場合のGrundy数を表で示す。一番上の行と一番左の列の数字が2つの山の石の数を表しており、それらから下と右に伸ばした線が交差するセルの値がGrundy数を表している。例えば、g(p0,3,6)=5である。2つの山の石の数が等しいとき、g(p0,n,n)=0であることも確認できる。
- パスなしのGrundy数
0 1 2 3 4 5 6 7 8 9 10 0 0 1 2 3 4 5 6 7 8 9 10 1 1 0 3 2 5 4 7 6 9 8 11 2 2 3 0 1 6 7 4 5 10 11 8 3 3 2 1 0 7 6 5 4 11 10 9 4 4 5 6 7 0 1 2 3 12 13 14 5 5 4 7 6 1 0 3 2 13 12 15 6 6 7 4 5 2 3 0 1 14 15 12 7 7 6 5 4 3 2 1 0 15 14 13 8 8 9 10 11 12 13 14 15 0 1 2 9 9 8 11 10 13 12 15 14 1 0 3 10 10 11 8 9 14 15 12 13 2 3 0
次に、パスありの場合、Grundy数は以下の表のようになる。
- パスありのGrundy数
0 1 2 3 4 5 6 7 8 9 10 0 0 2 1 4 3 6 5 8 7 10 9 1 2 1 0 3 4 5 6 7 8 9 10 2 1 0 2 5 7 3 8 4 6 12 11 3 4 3 5 1 0 2 7 6 9 8 12 4 3 4 7 0 1 8 9 2 5 6 13 5 6 5 3 2 8 1 0 9 4 7 14 6 5 6 8 7 9 0 1 3 2 4 15 7 8 7 4 6 2 9 3 1 0 5 16 8 7 8 6 9 5 4 2 0 1 3 17 9 10 9 12 8 6 7 4 5 3 1 0 10 9 10 11 12 13 14 15 16 17 0 1
例えば、石の数が2、4の2つ山の時のGrundy数はg(p1,2,4)=7である。これは以下のように求まる。局面(p1,2,4)の次局面のGrundy数を太字赤字にした。次局面のGrundy数が0～6であるため、Grundy数は7と求まる。
パスなしのGrundy数
0 1 2 3 4 0 0 1 2 3 4 1 1 0 3 2 5 2 2 3 0 1 6 パスありのGrundy数
0 1 2 3 4 0 0 2 1 4 3 1 2 1 0 3 4 2 1 0 2 5 7
パスありの表から、いくつかの性質を推測できる。
\begin{eqnarray} g(p1,x,y)=g(p1,x,y) \end{eqnarray}
山Xと山Yを入れ替えてもGrundy数は同じである。
次に、以下の性質もありそうである。
\begin{eqnarray} g(p1,x,y)=nのとき、\\ g(p1,x,n)=y \\ g(p1,n,y)=x \end{eqnarray}
例えば、\begin{eqnarray}
g(p1,2,4)=7のとき、\\
g(p1,2,7)=4 \\
g(p1,7,4)=2
\end{eqnarray}となっている。
この性質は3つ山の必勝判定と関係しているため、なぜ、このような性質が成り立つのか次項で説明する。
最後に、
パスあり2つ山の場合、(p1,2n-1,2n)、(p1,2n,2n-1)の局面にてGrundy数が0になっており、これが後手必勝の局面である。
それ以外の局面は先手必勝である。
(p1,2n-1,2n)、(p1,2n,2n-1)以外の局面でGrundy数が0とならない理由を説明をしておく。パスあり、パスなしのいずれにも言えることであるが、各列、各行で数字は1回ずつしか出てこない。行を例に説明すると、あるセルの局面を考えた場合、そのセルの左には次局面が並んでいる。次局面のGrundy数を除いた非負整数の中から現局面のGrundy数が決まるため、同一の行で同じGrundy数が登場することはない。
したがって、Grundy数が0となるセルは各行、各列に1回だけであり、(p1,2n-1,2n)または(p1,2n,2n-1)の局面は、各行、各列に1回現れるため、これらですべての後手必勝局面を網羅している。
複数の局面及びGrundy数の表記方法
複数の局面及びGrundy数をシンプルに書くために、以降、以下のような表記方法を用いる。
複数の局面やGrundy数の集合を(p0,<2,<2,3)のように不等号を使って表すこととする。この例の場合、(p0,0,0,3),(p0,0,1,3),(p0,1,0,3),(p0,1,1,3)の4つを表す。
また、(p0,2,2,3)のように不等号がないとき、文脈によっては、要素が1つの集合とみなすこととする。
以降、和集合を記号$\cup$を用いず、{ }内に集合をカンマで区切って表すことがある。{(p1,2,2,2),(p0,<2,2,2),(p0,2,<2,2)}は、(p1,2,2,2)$\cup$(p0,<2,2,2)$\cup$(p0,2,<2,2)の意味である。
x=0の場合、xより小さい非負整数は存在しないので、(p0,<x,<2,3)のような集合は空集合$\varnothing$となる。
また、ある集合に空集合との和集合を考えても元の集合のままであるため、x=0かつy≠0のとき、{(p0,<x,y,z),(p0,x,<y,z)}は(p0,x,<y,z)と同じである。
(p1,≦x,≦y)の範囲の局面の集合から(p1,x,y)のみを除いた局面集合を{(p1,≦x,≦y)-(p1,x,y)}と表す。
例えば、{(p1,≦2,≦2)-(p1,2,2)}は{(p1,0,0),(p1,0,1),(p1,0,2),(p1,1,0),(p1,1,1),(p1,1,2),(p1,2,0),(p1,2,1)}の意味である。
（現時点では使用していないが、今後、本記事を修正する際に使用する可能性がある以下の表記方法をメモしておく。）
N(p,x,y,z)で、局面(p,x,y,z)の次局面の集合を表すこととする。
gN(p,x,y,z)で、局面(p,x,y,z)の次局面のGrundy数の集合を表すこととする。
3つ山の場合
3つ山のGrundy数の表
3つ山の場合の局面(p0,≦10,≦10,≦4)、(p1,≦10,≦10,≦4)のGrundy数の表を以下に示す。
ついでに、局面(p1,7,4,2)の次局面のセルを赤字にしており、その中に0がないことから局面(p1,7,4,2)のGrundy数は0と求まる。式にすると、\begin{eqnarray}
g(p1,7,4,2)
&=& mex(g(p0,7,4,2),g(p1,<7,4,2),g(p1,7,<4,2),g(p1,7,4,<2)) \\
&=& mex(1,(7,2,1,4,3,5,6),(4,5,9,7),(2,3)) \\
&=& 0
\end{eqnarray}である。
- パス無し（z=0）
0 1 2 3 4 5 6 7 8 9 10 0 0 1 2 3 4 5 6 7 8 9 10 1 1 0 3 2 5 4 7 6 9 8 11 2 2 3 0 1 6 7 4 5 10 11 8 3 3 2 1 0 7 6 5 4 11 10 9 4 4 5 6 7 0 1 2 3 12 13 14 5 5 4 7 6 1 0 3 2 13 12 15 6 6 7 4 5 2 3 0 1 14 15 12 7 7 6 5 4 3 2 1 0 15 14 13 8 8 9 10 11 12 13 14 15 0 1 2 9 9 8 11 10 13 12 15 14 1 0 3 10 10 11 8 9 14 15 12 13 2 3 0
- パス無し（z=1）
0 1 2 3 4 5 6 7 8 9 10 0 1 0 3 2 5 4 7 6 9 8 11 1 0 1 2 3 4 5 6 7 8 9 10 2 3 2 1 0 7 6 5 4 11 10 9 3 2 3 0 1 6 7 4 5 10 11 8 4 5 4 7 6 1 0 3 2 13 12 15 5 4 5 6 7 0 1 2 3 12 13 14 6 7 6 5 4 3 2 1 0 15 14 13 7 6 7 4 5 2 3 0 1 14 15 12 8 9 8 11 10 13 12 15 14 1 0 3 9 8 9 10 11 12 13 14 15 0 1 2 10 11 10 9 8 15 14 13 12 3 2 1
- パス無し（z=2）
0 1 2 3 4 5 6 7 8 9 10 0 2 3 0 1 6 7 4 5 10 11 8 1 3 2 1 0 7 6 5 4 11 10 9 2 0 1 2 3 4 5 6 7 8 9 10 3 1 0 3 2 5 4 7 6 9 8 11 4 6 7 4 5 2 3 0 1 14 15 12 5 7 6 5 4 3 2 1 0 15 14 13 6 4 5 6 7 0 1 2 3 12 13 14 7 5 4 7 6 1 0 3 2 13 12 15 8 10 11 8 9 14 15 12 13 2 3 0 9 11 10 9 8 15 14 13 12 3 2 1 10 8 9 10 11 12 13 14 15 0 1 2
- パス無し（z=3）
0 1 2 3 4 5 6 7 8 9 10 0 3 2 1 0 7 6 5 4 11 10 9 1 2 3 0 1 6 7 4 5 10 11 8 2 1 0 3 2 5 4 7 6 9 8 11 3 0 1 2 3 4 5 6 7 8 9 10 4 7 6 5 4 3 2 1 0 15 14 13 5 6 7 4 5 2 3 0 1 14 15 12 6 5 4 7 6 1 0 3 2 13 12 15 7 4 5 6 7 0 1 2 3 12 13 14 8 11 10 9 8 15 14 13 12 3 2 1 9 10 11 8 9 14 15 12 13 2 3 0 10 9 8 11 10 13 12 15 14 1 0 3
- パス無し（z=4）
0 1 2 3 4 5 6 7 8 9 10 0 4 5 6 7 0 1 2 3 12 13 14 1 5 4 7 6 1 0 3 2 13 12 15 2 6 7 4 5 2 3 0 1 14 15 12 3 7 6 5 4 3 2 1 0 15 14 13 4 0 1 2 3 4 5 6 7 8 9 10 5 1 0 3 2 5 4 7 6 9 8 11 6 2 3 0 1 6 7 4 5 10 11 8 7 3 2 1 0 7 6 5 4 11 10 9 8 12 13 14 15 8 9 10 11 4 5 6 9 13 12 15 14 9 8 11 10 5 4 7 10 14 15 12 13 10 11 8 9 6 7 4
- パスあり（z=0）
0 1 2 3 4 5 6 7 8 9 10 0 0 2 1 4 3 6 5 8 7 10 9 1 2 1 0 3 4 5 6 7 8 9 10 2 1 0 2 5 7 3 8 4 6 12 11 3 4 3 5 1 0 2 7 6 9 8 12 4 3 4 7 0 1 8 9 2 5 6 13 5 6 5 3 2 8 1 0 9 4 7 14 6 5 6 8 7 9 0 1 3 2 4 15 7 8 7 4 6 2 9 3 1 0 5 16 8 7 8 6 9 5 4 2 0 1 3 17 9 10 9 12 8 6 7 4 5 3 1 0 10 9 10 11 12 13 14 15 16 17 0 1
- パスあり（z=1）
0 1 2 3 4 5 6 7 8 9 10 0 2 1 0 3 4 5 6 7 8 9 10 1 1 0 3 2 5 4 7 6 9 8 11 2 0 3 4 1 2 7 9 5 10 6 8 3 3 2 1 0 7 6 5 4 11 10 9 4 4 5 2 7 0 1 8 3 6 11 12 5 5 4 7 6 1 0 3 2 13 12 15 6 6 7 9 5 8 3 0 1 4 2 14 7 7 6 5 4 3 2 1 0 12 13 17 8 8 9 10 11 6 13 4 12 0 1 2 9 9 8 6 10 11 12 2 13 1 0 3 10 10 11 8 9 12 15 14 17 2 3 0
- パスあり（z=2）
0 1 2 3 4 5 6 7 8 9 10 0 1 0 2 5 7 3 8 4 6 12 11 1 0 3 4 1 2 7 9 5 10 6 8 2 2 4 0 6 1 8 3 9 5 7 12 3 5 1 6 3 4 0 2 7 8 9 10 4 7 2 1 4 3 5 6 0 9 8 14 5 3 7 8 0 5 4 10 1 2 11 6 6 8 9 3 2 6 10 4 11 0 1 5 7 4 5 9 7 0 1 11 3 14 2 13 8 6 10 5 8 9 2 0 14 3 4 1 9 12 6 7 9 8 11 1 2 4 3 15 10 11 8 12 10 14 6 5 13 1 15 3
- パスあり（z=3）
0 1 2 3 4 5 6 7 8 9 10 0 4 3 5 1 0 2 7 6 9 8 12 1 3 2 1 0 7 6 5 4 11 10 9 2 5 1 6 3 4 0 2 7 8 9 10 3 1 0 3 2 5 4 8 9 6 7 11 4 0 7 4 5 2 3 10 1 12 13 6 5 2 6 0 4 3 5 1 8 7 14 13 6 7 5 2 8 10 1 6 0 3 11 4 7 6 4 7 9 1 8 0 2 5 3 15 8 9 11 8 6 12 7 3 5 2 0 14 9 8 10 9 7 13 14 11 3 0 2 1 10 12 9 10 11 6 13 4 15 14 1 2
- パスあり（z=4）
0 1 2 3 4 5 6 7 8 9 10 0 3 4 7 0 1 8 9 2 5 6 13 1 4 5 2 7 0 1 8 3 6 11 12 2 7 2 1 4 3 5 6 0 9 8 14 3 0 7 4 5 2 3 10 1 12 13 6 4 1 0 3 2 5 4 7 6 10 12 8 5 8 1 5 3 4 2 11 7 0 9 10 6 9 8 6 10 7 11 2 4 1 0 3 7 2 3 0 1 6 7 4 5 8 14 11 8 5 6 9 12 10 0 1 8 7 2 4 9 6 11 8 13 12 9 0 14 2 5 16 10 13 12 14 6 8 10 3 11 4 16 5
2つ山のGrundy数と3つ山の必勝判定の関係（パスありバージョン）
2つ山の項に記したように、g(p1,7,4)=2であった。
そして今、確認したようにg(p1,7,4,2) =0である。
一般的にg(p1,x,y)=zのとき、g(p1,x,y,z)=0となり、g(p1,x,y,z)=0のときg(p1,x,y)=zとなると思われる（後で命題を整理し、証明を示す）。すなわち、2つ山のGrundy数の表を作成すれば、3つ山でGrundy数が0か0以外か、すなわち、後手必勝か先手必勝かが分かるのである。
振り返ってみれば、1つ山のGrundy数と2つ山の必勝判定にも同様の関係が成り立っている。すなわち、g(p1,2n-1)=2nであり、g(p1,2n-1,2n)=0である。
2つ山の項の最後に触れた以下の性質について説明する。
\begin{eqnarray} g(p1,x,y)=nのとき、\\ g(p1,x,n)=y \\ g(p1,n,y)=x \end{eqnarray}
g(p1,x,y)=nならば、g(p1,x,y,n)=0である。
山を入れ換えても同等の局面であるため、g(p1,x,n,y)=0であり、g(p1,n,y,x)=0である。
g(p1,x,n,y)=0よりg(p1,x,n)=yが導け、
g(p1,n,y,x)=0よりg(p1,n,y)=xが導ける。
それでは、以下で、この2つ山と3つ山の関係の証明を示す。
命題 2つ山のGrundy数と3つ山の必勝判定の関係（パスありバージョン）
任意の非負整数x、y、zに対して以下が成り立つ。
- z=g(p1,x,y)ならば、g(p1,x,y,z)=0
- z≠g(p1,x,y)ならば、g(p1,x,y,z)≠0
命題4は以下の命題と同値である。
任意の非負整数x0、y0に対して、そのパスありGrundy数をz0と置く。
g(p1,x0,y0)=:z0
この時、以下が成り立つ。
- 0$\notin$g(p1,x0,y0,<z0)（以下、※1）
- g(p1,x0,y0,z0)=0（以下、※2）
- 0$\notin$g(p1,x0,y0,>z0)（以下、※3）
方針
- (p1,0,0)において命題4が成立する。（①）
- {(p1,≦x,≦y)-(p1,x,y)}おいて命題4が成立しているという仮定の下、(p1,x,y)において命題4（又は命題5の※1、※2、※3）が成立する。（②）
の2つを証明できれば、任意の自然数a,bに対しても、
(p1,0,0)$\cdots$(p1,0,b),
(p1,1,0)$\cdots$(p1,1,b),
$\cdots$
(p1,a,0)$\cdots$(p1,a,b),
のようにドミノ倒し的に命題4が成り立つことが示せたことになる。
①の証明
(p1,0,0)及び(p1,0,0,0)は終了局面であるため、g(p1,0,0)=g(p1,0,0,0)=0である。
z=0のとき、命題4の1つ目、『z=g(p1,x,y)ならば、g(p1,x,y,z)=0』が成立している。
z>0のとき、g(p1,0,0,0)=0より、Grundy数の決まり方から、g(p1,0,0,z)≠0であるため、命題4の2つ目、『z≠g(p1,x,y)ならば、g(p1,x,y,z)≠0』が成立している。
②の証明
{(p1,≦x0,≦y0)-(p1,x0,y0)}の範囲の任意の(p1,x,y)について、命題4が成立している、すなわち
- z=g(p1,x,y)ならば、g(p1,x,y,z)=0
- z≠g(p1,x,y)ならば、g(p1,x,y,z)≠0
が成り立っているものとし、（仮定★）
このとき、命題4と同値な命題5
- g(p1,x0,y0)=z0ならば、0$\notin$g(p1,x0,y0,<z0)（※1）
- g(p1,x0,y0)=z0ならば、g(p1,x0,y0,z0)=0（※2）
- g(p1,x0,y0)=z0ならば、0$\notin$g(p1,x0,y0,>z0)（※3）
が成立することを示す。
g(p1,x0,y0)=z0ならば、0$\notin$g(p1,x0,y0,<z0)（※1）の証明
g(p1,x0,y0)=z0より、Grundy数の決まり方から、
{<z0} $\subset$ g{(p0,x0,y0),(p1,<x0,y0),(p1,x0,<y0)}
すなわち、z0より小さい任意のz1に対して、
z1 $\in$ g{(p0,x0,y0),(p1,<x0,y0),(p1,x0,<y0)}
が言える。
z1=g(p0,x0,y0)の場合、
パスなしの2つ山と3つ山の関係より、g(p0,x0,y0,z1)=0であり、g(p1,x0,y0,z1)≠0が示せた。
以下、z1 $\in$ g{(p1,<x0,y0),(p1,x0,<y0)}とする。
つまり、{(p1,<x0,y0),(p1,x0,<y0)}の範囲の、ある(p1,x1,y1)にて、
z1=g(p1,x1,y1)となっている。
仮定★より{(p1,≦x0,≦y0)-(p1,x0,y0)}の範囲で命題4が成立しており、(p1,x1,y1)はこの範囲内にあるため、
z1=g(p1,x1,y1)ということは、g(p1,x1,y1,z1)=0である。
上述のx1,y1の取りうる範囲に注意して、
0$\in$g{(p1,<x0,y0,z1),(p1,x0,<y0,z1)}
Grundy数の決まり方より、g(p1,x0,y0,z1)≠0となる。
z0より小さい任意のz1について、これが成立するため、0$\notin$g(p1,x0,y0,<z0)となる。
よって、（※1）が示せた。
g(p1,x0,y0)=z0ならば、g(p1,x0,y0,z0)=0（※2）の証明
Grundy数の定義より、以下が成り立てば、g(p1,x0,y0,z0)=0となる。
- g(p0,x0,y0,z0)≠0
- 0 $\notin$ g(p1,x0,y0,<z0)
- 0 $\notin$ {g(p1,x0,<y0,z0),g(p1,<x0,y0,z0)}
g(p0,x0,y0,z0)≠0の証明
仮定よりg(p1,x0,y0)=z0であるから、g(p0,x0,y0)≠z0である。
パスなしの2つ山と3つ山の関係より、g(p0,x0,y0,z0)≠0
0 $\notin$ g(p1,x0,y0,<z0)の証明
(※1)にて証明済み。
0 $\notin$ {g(p1,x0,<y0,z0),g(p1,<x0,y0,z0)}の証明
仮定よりg(p1,x0,y0)=z0であるため、Grundy数の決まり方から、
z0 $\notin$ {g(p1,x0,<y0),g(p1,<x0,y0)}
仮定★より、{(p1,x0,<y0),(p1,<x0,y0)}の範囲の任意の(p1,x,y)について、命題4が成立しているので、
0 $\notin$ {g(p1,x0,<y0,z0),g(p1,<x0,y0,z0)}
よって、（※2）が示せた。
g(p1,x0,y0)=z0ならば、0$\notin$g(p1,x0,y0,>z0)（※3）の証明
（※2）より、g(p1,x0,y0,z0)=0であるから、Grundy数の決まり方より0$\notin$g(p1,x0,y0,>z0)となる。
よって、（※3）が示せた。
（証明おわり）
n山のGrundy数と(n+1)山の必勝判定の関係
2つ山のGrundy数と3つ山の必勝判定の関係の証明は、ほぼそのまま、n山のGrundy数と(n+1)山の必勝判定の関係に応用できる。
これまでは、山が3つ以下であったため、各山の石数の変数はx,y,zの3つで足りていたが、山数が増えるため変数が不足する。
そこで、今後、山1、・・・山n、山(n+1)の石数の変数をそれぞれ、x1、・・・xn、xmとする。x(n+1)と書くと読みにくいのでm=n+1とし、x(n+1)のことをxmと書く。アルファベットではm,nの順番なので、その逆になっていて少しややこしいが気にしないこととする。
具体的な値を表すときは、xn=xn'、xn=xn''のように「'」を付けることとする。具体的には、2つ山と3つ山の関係の議論におけるz0をxm'に、z1をxm''に、といった具合に置き換えていく。
n山のGrundy数と(n+1)山の必勝判定の関係（パスなしバージョン）
- xm=g(x1,$\cdots$,xn)ならば、g(x1,$\cdots$,xn,xm)=0
- xm≠g(x1,$\cdots$,xn)ならば、g(x1,$\cdots$,xn,xm)≠0
xm=g(x1,$\cdots$,xn)
⇒ g(x1,$\cdots$,xn)$\oplus$xm=0 ($\because$補題1)
⇒ x1$\oplus$$\cdots$$\oplus$xn$\oplus$xm=0
⇒ g(x1,$\cdots$,xn,xm)=0
xm≠g(x1,$\cdots$,xn)
⇒ g(x1,$\cdots$,xn)$\oplus$xm≠0 ($\because$補題2)
⇒ x1$\oplus$$\cdots$$\oplus$xn$\oplus$xm≠0
⇒ g(x1,$\cdots$,xn,xm)≠0
n山のGrundy数と(n+1)山の必勝判定の関係（パスありバージョン）
任意の非負整数x1、$\cdots$、xn、xmに対して以下が成り立つ。
- xm=g(p1,x1,$\cdots$,xn)ならば、g(p1,x1,$\cdots$,xn,xm)=0
- xm≠g(p1,x1,$\cdots$,xn)ならば、g(p1,x1,$\cdots$,xn,xm)≠0
命題7は以下の命題と同値である。
任意の非負整数x1',$\cdots$,xn'に対して、そのパスありGrundy数をxm'と置く。
g(p1,x1',$\cdots$,xn')=:xm'
この時、以下が成り立つ。
- 0$\notin$g(p1,x1',$\cdots$,xn',<xm')（以下、※1）
- g(p1,x1',$\cdots$,xn',xm')=0（以下、※2）
- 0$\notin$g(p1,x1',$\cdots$,xn',>xm')（以下、※3）
方針
- (p1,0,0)において命題7が成立する。（①）
- {(p1,≦x1,$\cdots$,≦xn)-(p1,x1,$\cdots$,xn)}おいて命題7が成立しているという仮定の下、(p1,x1,$\cdots$,xn)において命題7（又は命題8の※1、※2、※3）が成立する。（②）
の2つを証明できれば、任意の自然数a1,$\cdots$,anに対しても、
(p1,0,$\cdots$,0,0)$\cdots$(p1,0,$\cdots$,0,an),
(p1,0,$\cdots$,0,1,≦an)$\cdots$(p1,0,$\cdots$,0,a(n-1),≦an),
(p1,0,$\cdots$,0,1,≦a(n-1),≦an)$\cdots$(p1,0,$\cdots$,0,a(n-2),≦a(n-1),≦an),
$\cdots$
(p1,1,≦a2,$\cdots$,≦a(n-1),≦an)$\cdots$(p1,a1,≦a2,$\cdots$,≦a(n-1),≦an),
のようにドミノ倒し的に命題7が成り立つことが示せたことになる。
①の証明
n山の終了局面(p1,0,$\cdots$,0)及びm山の終了局面(p1,0,$\cdots$,0,0)のGrundy数は0であるため、g(p1,0,$\cdots$,0)=g(p1,0,$\cdots$,0,0)=0である。
xm=0のとき、命題7の1つ目、
『xm=g(p1,x1,$\cdots$,xn)ならば、g(p1,x1,$\cdots$,xn,xm)=0』
が成立している。
xm>0のとき、g(p1,0$\cdots$,0,0)=0より、Grundy数の決まり方から、
g(p1,0,$\cdots$,0,xm)≠0であるため、命題7の2つ目、
『xm≠g(p1,x1,$\cdots$,xn)ならば、g(p1,x1,$\cdots$,xn,xm)≠0』
が成立している。
②の証明
{(p1,≦x1',$\cdots$,≦xn')-(p1,x1',$\cdots$,xn')}の範囲の任意の(p1,x1,$\cdots$,xn)について、命題7が成立している、すなわち
- xm=g(p1,x1,$\cdots$,xn)ならば、g(p1,x1,$\cdots$,xn,xm)=0
- xm≠g(p1,x1,$\cdots$,xn)ならば、g(p1,x1,$\cdots$,xn,xm)≠0
が成り立っているものとし、（仮定★）
このとき、命題7と同値な命題8
- g(p1,x1',$\cdots$,xn')=xm'ならば、0$\notin$g(p1,x1',$\cdots$,xn',<xm')（※1）
- g(p1,x1',$\cdots$,xn')=xm'ならば、g(p1,x1',$\cdots$,xn',xm')=0（※2）
- g(p1,x1',$\cdots$,xn')=xm'ならば、0$\notin$g(p1,x1',$\cdots$,xn',>xm')（※3）
が成立することを示す。
g(p1,x1',$\cdots$,xn')=xm'ならば、0$\notin$g(p1,x1',$\cdots$,xn',<xm')（※1）の証明
g(p1,x1',$\cdots$,xn')=xm'より、Grundy数の決まり方から、
{<xm'} $\subset$ g{(p0,x1',$\cdots$,xn'),(p1,<x1',$\cdots$,xn'),$\cdots$,(p1,x1',$\cdots$,<xn')}
和集合の記号を使うと、
{<xm'} $\subset$ g{(p0,x1',$\cdots$,xn'),$\bigcup_{i = 1}^n$(p1,x1',$\cdots$,<xi',$\cdots$,xn')}
すなわち、xm'より小さい任意のxm''に対して、
xm'' $\in$ g{(p0,x1',$\cdots$,xn'),$\bigcup_{i = 1}^n$(p1,x1',$\cdots$,<xi',$\cdots$,xn')}
が言える。
xm''=g(p0,x1',$\cdots$,xn')の場合、
パスなしのn山と(n+1)山の関係より、g(p0,x1',$\cdots$,xn',xm'')=0であり、g(p1,x1',$\cdots$,xn',xm'')≠0が示せた。
以下、xm'' $\in$ g{$\bigcup_{i = 1}^n$(p1,x1',$\cdots$,<xi',$\cdots$,xn')}とする。
つまり、{$\bigcup_{i = 1}^n$(p1,x1',$\cdots$,<xi',$\cdots$,xn')}の範囲の、ある(p1,x1'',$\cdots$,xn'')にて、
xm''=g(p1,x1'',$\cdots$,xn'')となっている。
仮定★より{(p1,≦x1',$\cdots$,≦xn')-(p1,x1',$\cdots$,xn')}の範囲で命題7が成立しており、(p1,x1'',$\cdots$,xn'')はこの範囲内にあるため、
xm''=g(p1,x1'',$\cdots$,xn'')ということは、g(p1,x1'',$\cdots$,xn'',xm'')=0である。
上述のx1'',$\cdots$,xn''の取りうる範囲に注意して、
0$\in$g{$\bigcup_{i = 1}^n$(p1,x1',$\cdots$,<xi',$\cdots$,xn',xm'')}
Grundy数の決まり方より、g(p1,x1',$\cdots$,xn',xm'')≠0となる。
xm'より小さい任意のxm''について、これが成立するため、0$\notin$g(p1,x1',$\cdots$,xn',<xm')となる。
よって、（※1）が示せた。
g(p1,x1',$\cdots$,xn')=xm'ならば、g(p1,x1',$\cdots$,xn',xm')=0（※2）の証明
Grundy数の定義より、以下が成り立てば、g(p1,x1',$\cdots$,xn',xm')=0となる。
- g(p0,x1',$\cdots$,xn',xm')≠0
- 0 $\notin$ g(p1,x1',$\cdots$,xn',<xm')
- 0 $\notin$ g{$\bigcup_{i = 1}^n$(p1,x1',$\cdots$,<xi',$\cdots$,xn',xm')}
g(p0,x1',$\cdots$,xn',xm')≠0の証明
仮定よりg(p1,x1',$\cdots$,xn')=xm'であるから、g(p0,x1',$\cdots$,xn')≠xm'である。
パスなしのn山と(n+1)山の関係より、g(p0,x1',$\cdots$,xn',xm')≠0
0 $\notin$ g(p1,x1',$\cdots$,xn',<xm')の証明
(※1)にて証明済み。
0 $\notin$ g{$\bigcup_{i = 1}^n$(p1,x1',$\cdots$,<xi',$\cdots$,xn',xm')}の証明
仮定よりg(p1,x1',$\cdots$,xn')=xm'であるため、Grundy数の決まり方から、
xm' $\notin$ g{$\bigcup_{i = 1}^n$(p1,x1',$\cdots$,<xi',$\cdots$,xn')}
仮定★より、{$\bigcup_{i = 1}^n$(p1,x1',$\cdots$,<xi',$\cdots$,xn')}の範囲の任意の(p1,x1,$\cdots$,xn)について、命題7が成立しているので、
0 $\notin$ g{$\bigcup_{i = 1}^n$(p1,x1',$\cdots$,<xi',$\cdots$,xn',xm')}
よって、（※2）が示せた。
g(p1,x1',$\cdots$,xn')=xm'ならば、0$\notin$g(p1,x1',$\cdots$,xn',>xm')（※3）の証明
（※2）より、g(p1,x1',$\cdots$,xn',xm')=0であるから、Grundy数の決まり方より0$\notin$g(p1,x1',$\cdots$,xn',>xm')となる。
よって、（※3）が示せた。
（証明おわり）
更新履歴
- 2025年8月17日 初版投稿。
PCのプレビューでは問題ないが、スマホのプレビューでは数式の表示がうまくいっていない。ただ、解決しないので、そのまま投稿する。- 投稿したものを確認したところ、スマホでも正しく表示されていた。
- 2025年8月17日（2回目） 第2版投稿。
- 証明1-2を追加。
- 証明1-1の一部の誤記を修正。
- 2025年8月17日（3回目） 第3版投稿。
- 一部の誤記を修正。一部の表現を見直し。
- 2025年8月24日 第4版投稿。
- 参考文献の引用を追加。
- パスなしの項に、補題、定理の囲いを追加。
- パスありの命題の証明のうち、シンプルな証明1-2を残し、証明1-1を削除。
- 一部の誤記を修正。一部の表現を見直し。
- 2025年8月31日 第5版投稿。
- 複数の局面及びGrundy数の表記方法の章を追加。
- 証明において、(p1,x0,<y0,z0)と(p1,<x0,y0,z0)を場合分けせず、{(p1,x0,<y0,z0),(p1,<x0,y0,z0)}としてまとめて証明した。
- 表記方法にて空集合の取り扱いを明確にしたため、証明内の「x0=0又はy0=0又はz0=0の場合の証明は省略する。x0=0又はy0=0又はz0=0の場合は命題4が成立しているものとし、以降、x0≧1かつy0≧1かつz0≧1とする。」を削除。
- 証明の中に書いていた命題4と同値な命題(※1、2、3)を命題5として、命題4のすぐ下に並べた。
- 2025年9月14日 第6版投稿。
- 「n山のGrundy数と(n+1)山の必勝判定の関係」の章を追加。
参考文献
この記事を高評価した人
この記事に送られたバッジ
投稿者
