Hexの勝利条件が逆転していることに注意してください。

Rexという名前はReverse Hexを縮めて名付けられたものです。

他にも逆形Hex(Misère Hex)と呼ばれることもあります。

ここからはもう少し一般化して，\(\,N \times N\,\)のボードで行われるRexについて考察していきたいと思います。

定理

この記事の目的は上の定理1を証明することです。

この定理1を完全な形で初めて出版したLagariasさんとSleatorさんの論文\(\,[1]\,\)を参考にしつつ解説します。

\([1]\,\)はSleatorさんのホームぺージから閲覧可能です。

まず前提として，Hexと全く同様にして

Rexに引き分けはなく，先手必勝もしくは後手必勝のどちらかであることが言えます。

※このことはHexの記事にて証明が確認できます。

そのためRexのプレイヤーは勝者(必勝戦略を持つ者)と敗者(必勝戦略を持たない者)に分かれます。

その敗者について次の定理2が成り立ちます。

この定理2は逆に，マスを交互に塗った時，最後のマスを塗るプレイヤーが敗者だということを保証しています。

そのためマスの総数\(\,N^2\,\)の偶奇によって，最後の手番のプレイヤーが切り替わり，定理1が成り立つことを保証します。

つまり問題は定理2を証明することに帰着されました。

ここからは記述の簡略化のために，勝者を\(\,W\,\)(winner)，敗者を\(\,L\,\)(Loser)と表すことにします。

単調性補題(monotonicity property)

定理2を証明するために，次の単調性補題を確認しましょう。

Rexでは自分の色の対辺をつないで，橋を作ってしまうと負けです。

この橋は単調性補題の順序に従って，一部のマスを塗り替えても崩れはしないので，上の補題が成り立ちます。

一見，明らかに見えますが，定理2の証明の核心となる面白い補題です。

余談ですが「単調性補題」という言葉は私が元論文のmonotonicity propertyを直訳しただけです。

個人的にしっくりこないので，良い訳語を思いついた方は教えていただけると嬉しいです。

証明

それでは定理2を証明を完成させましょう。

戦略拝借論証と似た議論で進みますが，こちらの方がやや難しいと思うので，慣れていない方は，まずはそちらの証明を見ることをおススメします。

背理法により示すために，定理2が成り立たないと仮定します。

2つに場合分けして考えます。

\([1]\,L\,\)が先攻のとき

\(L\,\)は次の戦略を用いることにします。

まず\(\,L\,\)は仮想のRexを用意します。

元のRexのボードの隣に，別のボードを用意するイメージで考えると分かりやすいです。

元のRexにおける\(\,L\,\)の初手はどこか適当なマスを塗ります。

そしてどちらのRexもそのマスに印を付けておきます。

しかし仮想Rexは\(\,L\,\)の初手は無視し，なにも塗られていない状態から始まります(印が付いているだけ)。

以後，元のRexで一マス塗られる度，仮想Rexも同じマスを同じ色で塗るようにします。

この仮想Rexにおいて，\(\,L\,\)の初手は無視されているので，\(\,L\,\)は後攻として扱われます。

そのため\(\,L\,\)は仮想Rexにおいて，\(\,W\,\)の必勝戦略を模倣(拝借)することができます。

そこで\(\,L\,\)は仮想Rexにおいて必勝戦略に従うように，元のRexの手を進めて行きます。

しかしこのとき，初手のマスの違いが，必勝戦略の遂行に影響を及ぼさないかが問題になります。

もし\(\,L\,\)の必勝戦略において，元のRexでは既に塗られてしまっている初手のマスを仮想Rexで塗る必要が出たときは，

まず元のRexの任意の空きマスを\(\,1\,\)つ塗り，そこに印を付け直します。

そうして今度は印を付け直したマスを仮想Rexで塗られていないものとみなし，仮想Rexでは代わりに初手のマスを塗ります。

こうすることで，仮想Rexにおいては必勝戦略に従い続けることができます。

さらに印を付け直したマスを塗る必要が出てきたときは，同様に印を付け直す作業をすることで

仮想Rexにおいて，空きマスが残り\(\,1\,\)つになるまで，必勝戦略を実行し続けます。

またこのとき，印の付いた空きマスを\(\,L\,\)の色にするだけで，仮想Rexから元のRexの局面を再現できることに注意しておきましょう。

※仮想Rexの空きマスが\(\,1\,\)つのときに必勝戦略を行うと，この再現方法が少し異なってしまいます。
後のなぜ戦略拝借論証は使えないのか？を読むと，このズレが決して小さなものではないことが分かります。

こうして\(\,L\,\)は空きマスが残り\(\,1\,\)つになる，もしくは仮想Rexで決着が付くまでゲームを進行します。

すると仮想Rexにおいて\(\,L\,\)は必勝戦略に従っているので，次の\(\,2\,\)パターンに落ち着きます。

\((\,\mathrm{i}\,)\,\)仮想Rexのボードが全て塗られる前に決着が付く。

\((\mathrm{ii})\,\)仮想Rexで空きマスが残り\(\,1\,\)つになるが，決着が付いていない。

※このとき元のRexにおける勝敗は気にしなくて良いです。後で\(\,L\,\)が勝っていたと判明するからです。

\((\,\mathrm{i}\,)\,\)の場合について考えます。

仮想Rexは\(\,L\,\)の勝ちで，印を付けた空きマスを\(\,L\,\)の色に変えることで，元のRexの局面が得られます。

これは単調性補題から，元のRexにおいても\(\,L\,\)が勝っていることを意味します。

すなわち\(\,L\,\)は必勝戦略を持つことになり矛盾です。

\((\mathrm{ii})\,\)の場合についてはどうでしょう。

\(L\,\)は\(\,W\,\)の必勝戦略に従っていて，定理2が成り立たないと仮定しているので，この空きマスが残り\(\,1\,\)つの状態では\(\,L\,\)は勝利していないといけません。

そうでないと\(\,L\,\)はこれまでの仮想Rexの\(\,W\,\)の手順をマネすることで，\(\,W\,\)の必勝戦略に対し，決着をボードのすべてのマスが塗られるまで遅らせることができるからです。

よって\(\,L\,\)は仮想Rexにおいて勝利していることになり，再び単調性補題から元のRexにおいても\(\,L\,\)が勝利し矛盾です。

\([2]\,L\,\)が後攻のとき

\([1]\,\)と同様に仮想Rexを用意します。

ただし今度は\(\,W\,\)が先攻なので，少し異なります。

まず\(\,W\,\)の初手のマス\(\,p_0\,\)に印を付け，そのマスを仮想Rexでは空きマスとみなします。

そうすることで，\(\,L\,\)は先攻とみなせ，仮想Rexにおいて\(\,W\,\)の必勝戦略を，空きマスが残り\(\,1\,\)つになるまで実行し続けます。

今度も同様に，もし元のRexで既に塗られているマスを仮想Rexで塗る必要が出たとき，印を付け直すことで対応します。

そうすることで\(\,L\,\)は\(\,[1]\,\)の場合と同様に，空きマスが残り\(\,1\,\)つになるまで必勝戦略に従い続けることができます。

しかし今度は仮想Rexから元のRexの盤面を再現するには，一回でも印を付け直すと，

初手のマス\(\,p_0\,\)を\(\,L\,\)の色から\(\,W\,\)の色に，

印を付けた\(\,1\,\)マスを空きマスから\(\,L\,\)の色にすれば良いです。

印を一切付け直さなかった場合は，初手のマス\(\,p_0\,\)を空きマスから\(\,W\,\)の色にするだけで十分です。

こうして同様に\(\,2\,\)パターンに落ち着きますが，\(\,[1]\,\)の場合と異なるのは，仮想Rexから元のRexへの再現方法だけなので，

\((\,\mathrm{i}\,)\,\)仮想Rexのボードが全て塗られる前に決着が付く

場合のみを議論すれば良いです。

この仮想Rexで決着が付いた盤面から元のRexの盤面を再現するには，上で述べたようにすれば良く，さらにこれは単調性補題に従っています。

よって元のRexにおいても\(\,L\,\)が勝っていることを意味し，矛盾が生じます。

以上の\(\,[1],[2]\,\)より矛盾が示されたので，定理2は成り立ちます。\(\quad\square\)

なぜ戦略拝借論証は使えないのか？

前節を見れば分かるように，証明が戦略拝借論証に似ています。

特に \(\,[1]\,L\,\)が先攻のとき は特に似ているように見えます。

定理2の証明が戦略拝借論証に似ているのにも関わらず，

Hexでは使えた戦略拝借論証はなぜRexでは使えないのでしょうか？

先行を\(\,A\,\)，後攻を\(\,B\,\)とおいて考えましょう。

戦略拝借論証を進めると，場合\(\,[1]\,\)と同様に仮想のボードを用意し，

元のボードは，印を付けたマスを先攻\(\,A\,\)の色で塗るという余分な一手を仮想ボードに付け足すことで構成できますね。

一言で言えば，この余分な一手が\(\,A\,\)にとって有利か不利かが，戦略拝借論法が使えるかに影響しています。

普通のHexでは明らかに有利に働きますが，勝利条件が逆のRexでは不利に働くという違いが影響しているということですね。

さらに踏み込んで，その違いが論証のどこに影響するのか，もう少し詳しく見ていきましょう。

HexもRexもこのまま論証を進めると，先ほどの証明と同様に次の\(\,2\,\)パターンに落ち着きます。

\((\,\mathrm{i}\,)\,\)仮想のボードが全て塗られる前に決着が付く。

\((\mathrm{ii})\,\)仮想のボードで空きマスが残り\(\,1\,\)つになるが，決着が付いていない。

このうち\(\,(\,\mathrm{i}\,)\,\)は\(\,A\,\)が必勝法を持つことになり矛盾するので却下されます。

HexとRexの戦略拝借論証の違いが出るのは，この\(\,(\mathrm{ii})\,\)のときです。

残り\(\,1\,\)マスを必勝戦略に従って\(\,A,B\,\)のどちらかの色で塗ったとします。

必勝戦略なので，これにより仮想上では\(\,A\,\)の勝利が確定します。

ここから元に戻すときに違いが生じます。

仮想から元に戻すには，このマスを\(\,A\,\)の色でぬりかえる必要がありますね。

ところでHexでも，Rexと同様の単調性補題が成り立ち，\(\,A\,\)が勝ちのとき，順序は空きマス\(\,\to {\color{#1e7bba}B}\to {\color{#f2541d}A}\,\)となります。

そのためHexでは，塗り替えの作業は単調性補題の順序に沿っています。

しかしRexでは，順序が空きマス\(\,\to {\color{#f2541d}A}\to {\color{#1e7bba}B}\,\)でHexと比べ逆転しており，例えば残りの\(\,1\,\)マスが\(\,B\,\)で塗られていたとき，それを\(\,A\,\)で塗り替えてしまうと，この順序に逆行してしまいます。

つまり仮想Rexにおける\(\,A\,\)の勝利を元のRexへと翻訳できないということです。

まとめると，余分な一手が単調性補題の順序の最上位に属するか属さないかの違いが，戦略拝借論証を使えるか使えないかに影響するということですね。

また定理2の場合\(\,[1]\,\)の証明はこの問題を，定理2が成り立たないという背理法による仮定で代用したため，筋が通っていることも分かるでしょう。

今回の記事ではRexを解説いたしました。

ボードの偶奇によって先手・後手必勝が入れ替わるという面白さもさることながら，その証明法もなかなかトリッキーで奥深かったですね。

戦略拝借論証が使えない例になっていることも個人的には面白かったです。

もし「説明がわかりにくい」などご要望・ご感想がありましたら，
X（旧:Twitter）で#サイエンティクスでつぶやいていただけると，できる限り対応します。

ここまで読んでいただき，ありがとうございました。

• \([1]\) Jeffrey Lagarias and Daniel Sleator. Who Wins Misère Hex appears as a chapter in The Mathemagician and Pied Puzzler: A Collection in Tribute to Martin Gardner. Elwyn Berlekamp and Tom Rodgers Ed., A, K. Peters, 1999

著者であるSleatorさんのホームページ(2025-09-11閲覧)から閲覧可能です。