ワイソフのゲーム

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

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

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

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

必勝形の原理

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

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

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

(0, 0) は〇である。

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

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

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

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

残りは加えて $(x, y \neq 1, 2), y - x \geq 2$ で、この中で $x, y, y - x$ がいずれも最小である (3, 5) は〇である。

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

残りは加えて $(x, y \neq 3, 5), y - x \geq 3$ で、この中で $x, y, y - x$ がいずれも最小である (4, 7) は〇である。

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

ワイソフのゲームの後手必勝形 $(x \leq y)$
$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	…
$x$	1	3	4	6	8	9	11	12	14	16	17	19	21	22	24	25	27	29	30	32	…
$y$	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を参照）

必勝形の床関数表示

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

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

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

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

$φ 2 - φ = 1$
${\frac {1}{\varphi }}+{\frac {1}{\varphi ^{2}}}=1$

より従う。

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

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

〇である $(x, y) \neq (0, 0) (x \leq y)$ は、 $y - x$ のゼッケンドルフ表現を

y-x=:F_{n_{1}-1}+F_{n_{2}-1}+\cdots +F_{n_{k}-1}

（

n 1 < n 2 < \dots < n k

はどの2つも連続しない正整数）

とすると、

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

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

となる。

逆型ルール

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

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

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

脚注

^ Wythoff, W. A. (1907), “A modification of the game of nim”, Nieuw Archief voor Wiskunde 7 (2): 199-202
^ Richard J. Nowakowski (Dalhousie University) The History of Combinatorial Game Theory - ウェイバックマシン（2012年1月18日アーカイブ分） 2009年1月24日。p.4
^ [組み合わせゲーム理論] 組み合わせゲームとゲーム木について | DevelopersIO（クラスメソッド株式会社）2018.03.23

参考文献

“Wythoff の石取りゲーム” (pdf). 数学パズル・ゲームの広場. 2024年3月8日閲覧。
廣津孝. “問題《レイリー=ビーティの定理》”. 有名問題・定理から学ぶ数学. 2024年3月8日閲覧。

外部リンク

Weisstein, Eric W. "Wythoff's Game". mathworld.wolfram.com (英語).

[1] Wythoff, W. A. (1907), “A modification of the game of nim”, Nieuw Archief voor Wiskunde 7 (2): 199-202

[2] Richard J. Nowakowski (Dalhousie University) The History of Combinatorial Game Theory - ウェイバックマシン（2012年1月18日アーカイブ分） 2009年1月24日。p.4

[3] [組み合わせゲーム理論] 組み合わせゲームとゲーム木について | DevelopersIO（クラスメソッド株式会社）2018.03.23

[1]

[2]

[3]