ワイソフのゲームのソースを表示

[[画像:Wythoff.svg|180px|thumb|ワイソフのゲームを[[チェスボード|チェス盤]]で表した図。[[クイーン (チェス)|クイーン]]の位置が青丸だと、後手が最善手を行えば必ず勝つ。]]
'''ワイソフのゲーム'''（{{lang-en-short|Wythoff's game}}）は2人用の[[ゲーム]]で、2つの山からコイン（または石など）を好きな数だけ交互に取り合っていき、最後に取った者を勝者とする。ただし、1回での取り出し方は、片方の山からまたは、両方の山から同数ずつとする。

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

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

[[オランダ]]の[[数学者]]である[[ウィレム・アブラハム・ワイソフ]]が[[1907年]]にこのゲームの数学的分析を発表した<ref>{{Citation |last=Wythoff |first=W. A. |authorlink=ウィレム・アブラハム・ワイソフ |title=A modification of the game of nim |url=https://archive.org/details/nieuwarchiefvoo02genogoog/page/n219/mode/2up |journal=Nieuw Archief voor Wiskunde |volume=7 |issue=2 |pages=199-202 |year=1907}}</ref>。最善手を行うならば、どちらが勝つかは最初の個数の組で決まる（後述）。歴史的には、[[ニム]]に次いで2番目に（必勝法が数学的に）解決したゲームである<ref>Richard J. Nowakowski ([[ダルハウジー大学|Dalhousie University]]) {{Wayback |url=http://www.mathstat.dal.ca/~rjn/papers/HistoryCGT.pdf |title=The History of Combinatorial Game Theory |date=20120118130119}} 2009年1月24日。p.4</ref>。

== 必勝形の原理 ==
[[画像:Wythoff's Nim.svg|thumb|upright=1.6|ワイソフのゲームの必勝形。一番左下の四角は位置 (1, 1) で、赤い四角は後手必勝形である。]]
後手必勝形のリストは、以下のようにして帰納的に見出せる。

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

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

(0, 0) は〇である。

{{math2|(''x'', ''y'') ≠ (0, 0)}} が〇であるとは、任意の自然数 {{mvar|a}} に対して {{math2|(''x'' &minus; ''a'', ''y''), (''x'', ''y'' &minus; ''a''), (''x'' &minus; ''a'', ''y'' &minus; ''a'')}} が×であることである。{{math2|(''x'', ''y'') ≠ (0, 0)}} が×であるとは、ある自然数 {{mvar|a}} を取ると {{math2|(''x'' &minus; ''a'', ''y''), (''x'', ''y'' &minus; ''a''), (''x'' &minus; ''a'', ''y'' &minus; ''a'')}} のどれかは〇であることである。

故に、(0, 0) は〇より、{{math2|1=''x'' = 0}} または {{math2|1=''y'' = 0}} または {{math2|1=''y'' &minus; ''x'' = 0}} は×である。

残りは {{math2|(''x'', ''y'' ≠ 0), ''y'' &minus; ''x'' > 0}} で、この中で {{math2|''x'', ''y'', ''y'' &minus; ''x''}} がいずれも最小である (1, 2) は〇である。

(1, 2) は〇より、残りの内 {{math2|1=''x'', ''y'' = 1, 2}} または {{math2|1=''y'' &minus; ''x'' = 1}} は×である。

残りは加えて {{math2|(''x'', ''y'' ≠ 1, 2), ''y'' &minus; ''x'' ≥ 2}} で、この中で {{math2|''x'', ''y'', ''y'' &minus; ''x''}} がいずれも最小である (3, 5) は〇である。

(3, 5) は〇より、残りの内 {{math2|1=''x'', ''y'' = 3, 5}} または {{math2|1=''y'' &minus; ''x'' = 2}} は×である。

残りは加えて {{math2|(''x'', ''y'' ≠ 3, 5), ''y'' &minus; ''x'' ≥ 3}} で、この中で {{math2|''x'', ''y'', ''y'' &minus; ''x''}} がいずれも最小である (4, 7) は〇である。

これを繰り返すと、〇である {{math2|(''x'', ''y'')}} は次の表のようになる：
{|class="wikitable" style="text-align:right"
|+ワイソフのゲームの後手必勝形 {{math2|(''x'' ≤ ''y'')}}
!{{mvar|n}}
|0||1||2||3||4||5||6||7||8||9||10||11||12||13||14||15||16||17||18||19||20||…
|-
!{{mvar|x}}
|0||1||3||4||6||8||9||11||12||14||16||17||19||21||22||24||25||27||29||30||32||…
|-
!{{mvar|y}}
|0||2||5||7||10||13||15||18||20||23||26||28||31||34||36||39||41||44||47||49||52||…
|}
:（{{mvar|x}} の列は{{OEIS|id=A066096}}を参照）
:（{{mvar|y}} の列は{{OEIS|id=A090909}}を参照）
:（{{math2|(''x'', ''y'')}} を1列にしたものは{{OEIS|id=A072061}}を参照）

== 必勝形の床関数表示 ==
ワイソフのゲームの後手必勝形は次のように表される：
* <math>( \lfloor n \varphi \rfloor , \lfloor n \varphi^2 \rfloor )</math>（{{mvar|n}} は 0 以上の整数、{{mvar|φ}} は[[黄金比]]）
ここで &#8970; &#8971; は[[床関数と天井関数|床関数]]を表す。

これは、[[レイリーの定理]]と
* {{math2|1=''φ''{{sup|2}} &minus; ''φ'' = 1}}
* <math>\frac{1}{\varphi} + \frac{1}{\varphi^2} =1</math>
より従う。

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

〇である {{math2|(''x'', ''y'') ≠ (0, 0) (''x'' ≤ ''y'')}} は、{{math2|''y'' &minus; ''x''}} のゼッケンドルフ表現を
:<math>y-x=: F_{n_1 -1} + F_{n_2 -1} + \cdots + F_{n_k -1}</math>（{{math2|''n''{{sub|1}} < ''n''{{sub|2}} < … < ''n{{sub|k}}''}} はどの2つも連続しない正整数）
とすると、
:<math>x= F_{n_1} + F_{n_2} + \cdots + F_{n_k}</math>
:<math>y= F_{n_1 +1} + F_{n_2 +1} + \cdots + F_{n_k +1}</math>
となる。

== 逆型ルール ==
ワイソフのゲームを含む組合せゲームにおいて、最後に石を取った者を勝ちとするルールは'''正規形'''、最後に石を取った者を負けとする方のルールは「逆形」<ref>[https://dev.classmethod.jp/articles/combinational-game-and-game-tree/ {{Nowiki|[組み合わせゲーム理論] 組み合わせゲームとゲーム木について {{!}} DevelopersIO}}]（クラスメソッド株式会社）2018.03.23</ref>「逆型」「双対ゲーム」などと呼ばれている。

逆形のワイソフのゲームの後手必勝形 {{math2|(''x'', ''y'') (''x'' ≤ ''y'')}} は次の通りである：
* <math>(0,1),(2,2),( \lfloor n \varphi \rfloor , \lfloor n \varphi^2 \rfloor ) \ (n \geq 2)</math>

== 脚注 ==
{{Reflist}}

== 参考文献 ==
* {{Cite web|和書 |title=Wythoff の石取りゲーム |url=https://sugakuyugi.web.fc2.com/Wythoff_setumei.pdf |format=pdf |work=数学パズル・ゲームの広場 |accessdate=2024-03-08}}
* {{Cite web|和書 |author=廣津孝 |title=問題《レイリー=ビーティの定理》 |url=https://wkmath.org/floor-f.html#q-ray-thm |work=有名問題・定理から学ぶ数学 |accessdate=2024-03-08}}

== 関連項目 ==
* [[不偏ゲーム]]
** [[ニム]]
** {{仮リンク|グランディのゲーム|en|Grundy's game}}
* [[レイリーの定理]]
* [[ビーティ数列]]
* [[フィボナッチ数]]
* [[ゼッケンドルフの定理]]

== 外部リンク ==
* {{MathWorld|urlname=WythoffsGame|title=Wythoff's Game}}

{{DEFAULTSORT:わいそふのけーむ}}
[[Category:組合せゲーム理論]]
[[Category:数学ゲーム]]
[[Category:ゲーム]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]