ワイソフのゲーム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/05/18 00:43 UTC 版)
ワイソフのゲーム（英: Wythoff's game）は2人用のゲームで、2つの山からコイン（または石など）を好きな数だけ交互に取り合っていき、最後に取った者を勝者とする。ただし、1回での取り出し方は、片方の山からまたは、両方の山から同数ずつとする。
このゲームは、チェスにおけるクイーンによっても同等な説明ができる。碁盤上にあるクイーンを、各プレイヤーが碁盤上の南、西、南西のどれかの向きに好きな歩数だけ移動させていったとき、クイーンを左下隅に移動させた者を勝者とする、というものである。クイーンがあるマスのx座標、y座標は2山にあるコインの数に対応する。
マーティン・ガードナーは1977年3月に、科学雑誌『サイエンティフィック・アメリカン』での「数学ゲーム コラム」の中で、このゲームは中国で捡石子（jiǎn shízǐ（チャヌシッチ）、石取りの意）の名前でプレイされていたと主張している。
オランダの数学者であるウィレム・アブラハム・ワイソフが1907年にこのゲームの数学的分析を発表した[1]。最善手を行うならば、どちらが勝つかは最初の個数の組で決まる（後述）。歴史的には、ニムに次いで2番目に（必勝法が数学的に）解決したゲームである[2]。
必勝形の原理
後手必勝形のリストは、以下のようにして帰納的に見出せる。
後手必勝形、後手必敗形を表記の簡略化のためそれぞれ〇, ×で表す。
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) は次の表のようになる：
| 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を参照）
必勝形の床関数表示
ワイソフのゲームの後手必勝形は次のように表される：
- ワイソフのゲームのページへのリンク
