ワイソフのゲーム

ワイソフのゲーム（英: Wythoff's game）は2人用のゲームで、2つの山からコイン（または石など）を好きな数だけ交互に取り合っていき、最後に取った者を勝者とする。ただし、1回での取り出し方は、片方の山からまたは、両方の山から同数ずつとする。

ワイソフのゲームをチェス盤で表した図。クイーンの位置が青丸だと、後手が最善手を行えば必ず勝つ。

このゲームは、チェスにおけるクイーンによっても同等な説明ができる。碁盤上にあるクイーンを、各プレイヤーが碁盤上の南、西、南西のどれかの向きに好きな歩数だけ移動させていったとき、クイーンを左下隅に移動させた者を勝者とする、というものである。クイーンがあるマスのx座標、y座標は2山にあるコインの数に対応する。

マーティン・ガードナーは1977年3月に、科学雑誌『サイエンティフィック・アメリカン』での「数学ゲーム コラム」の中で、このゲームは中国で捡石子（jiǎn shízǐ（チャヌシッチ）、石取りの意）の名前でプレイされていたと主張している。

オランダの数学者であるウィレム・アブラハム・ワイソフが1907年にこのゲームの数学的分析を発表した^[1]。最善手を行うならば、どちらが勝つかは最初の個数の組で決まる（後述）。歴史的には、ニムに次いで2番目に（必勝法が数学的に）解決したゲームである^[2]。

必勝形の原理

ワイソフのゲームの必勝形。一番左下の四角は位置 (1, 1) で、赤い四角は後手必勝形である。

後手必勝形のリストは、以下のようにして帰納的に見出せる。

後手必勝形、後手必敗形を表記の簡略化のためそれぞれ〇, ×で表す。

2山のコインの数を (x, y) (x ≤ y) とする。各点は〇, ×のどちらかである。

(0, 0) は〇である。

(x, y) ≠ (0, 0) が〇であるとは、任意の自然数 a に対して (x − a, y), (x, y − a), (x − a, y − a) が×であることである。(x, y) ≠ (0, 0) が×であるとは、ある自然数 a を取ると (x − a, y), (x, y − a), (x − a, y − a) のどれかは〇であることである。

故に、(0, 0) は〇より、x = 0 または y = 0 または y − x = 0 は×である。

残りは (x, y ≠ 0), y − x > 0 で、この中で x, y, y − x がいずれも最小である (1, 2) は〇である。

(1, 2) は〇より、残りの内 x, y = 1, 2 または y − x = 1 は×である。

残りは加えて (x, y ≠ 1, 2), y − x ≥ 2 で、この中で x, y, y − x がいずれも最小である (3, 5) は〇である。

(3, 5) は〇より、残りの内 x, y = 3, 5 または y − x = 2 は×である。

残りは加えて (x, y ≠ 3, 5), y − x ≥ 3 で、この中で x, y, y − x がいずれも最小である (4, 7) は〇である。

これを繰り返すと、〇である (x, y) は次の表のようになる：

ワイソフのゲームの後手必勝形 (x ≤ y)

n	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	…
x	0	1	3	4	6	8	9	11	12	14	16	17	19	21	22	24	25	27	29	30	32	…
y	0	2	5	7	10	13	15	18	20	23	26	28	31	34	36	39	41	44	47	49	52	…

（x の列はオンライン整数列大辞典の数列 A066096を参照）

（y の列はオンライン整数列大辞典の数列 A090909を参照）

（(x, y) を1列にしたものはオンライン整数列大辞典の数列 A072061を参照）

必勝形の床関数表示

ワイソフのゲームの後手必勝形は次のように表される：

• ${\displaystyle (\lfloor n\varphi \rfloor ,\lfloor n\varphi ^{2}\rfloor )}$（n は 0 以上の整数、φ は黄金比）

ここで ⌊ ⌋ は床関数を表す。

これは、レイリーの定理と

• φ² − φ = 1
• ${\displaystyle {\frac {1}{\varphi }}+{\frac {1}{\varphi ^{2}}}=1}$

より従う。

必勝形のゼッケンドルフ表現

ワイソフのゲームの (0, 0) 以外の後手必勝形は、次のようにゼッケンドルフ表現することができる。F_n は n番目のフィボナッチ数とする。

〇である (x, y) ≠ (0, 0) (x ≤ y) は、y − x のゼッケンドルフ表現を

${\displaystyle y-x=:F_{n_{1}-1}+F_{n_{2}-1}+\cdots +F_{n_{k}-1}}$（n₁ < n₂ < … < n_k はどの2つも連続しない正整数）

とすると、

${\displaystyle x=F_{n_{1}}+F_{n_{2}}+\cdots +F_{n_{k}}}$

${\displaystyle y=F_{n_{1}+1}+F_{n_{2}+1}+\cdots +F_{n_{k}+1}}$

となる。

逆型ルール

ワイソフのゲームを含む組合せゲームにおいて、最後に石を取った者を勝ちとするルールは正規形、最後に石を取った者を負けとする方のルールは「逆形」^[3]「逆型」「双対ゲーム」などと呼ばれている。

逆形のワイソフのゲームの後手必勝形 (x, y) (x ≤ y) は次の通りである：

• ${\displaystyle (0,1),(2,2),(\lfloor n\varphi \rfloor ,\lfloor n\varphi ^{2}\rfloor )\ (n\geq 2)}$