遊び方

※ルールによっては\(\,13\times 13\,\)のボードなどで遊ぶ場合もあります。
今回の記事の内容は\(\,n\times n\,\)まで一般化できるので，最初からその場合で考えても良いです。

余談ですがHexの名前の由来はhexagon(六角形)らしいです。

例えばゲームを進めて下の図のようになったとすると，赤の勝ちになります。

ここからはこのHexについて解析していきましょう！

Hexは引き分けなし・先手必勝

まずは次のことを証明していきましょう。

厳密な証明は少しグラフ理論の知識を用いるので，まずは簡単に直感的な説明をしたいと思います。

引き分けの場合とは，ゲームを進めて
全てのマスが赤か青で塗られているのに，ボードの向かい合った赤・青のどちらの辺もつながっていない状態です。

ここからが直感的ですが，赤で塗られた領域を「陸」，青で塗られた領域を「海」と考えると

海がつながっているか，陸がつながっているかのどちらか一方が必ず成り立ちそうなことが理解できるでしょう(下の図を見て想像してください)。

そのため\(\,2\,\)人のプレイヤーの片方は必ず勝利するはずなので，引き分けとはならないことが分かります。

それでは厳密な証明に移りたいと思います。

命題1を示すには

後半の「ボードの全てのマスを色で塗り分けたとき(Hexの手順どおりに塗り分けなくてもよい)，どちらか片方の色の辺のみがつながる」を示せば十分です。

引き分け状態も，ボードの全てのマスを色で塗分けた状態の一つだからです。

そこで後半部分を示していきましょう。

まず六角形のコマの頂点の一部を利用して，赤と青の領域の境界を表すグラフ\(\,G\,\)を構成しましょう。

例えば先ほど上で用いた図からグラフ\(\,G\,\)を構成すると，下の図の黒点と黒太線からなるグラフとなります。

このときグラフ\(\,G\,\)の頂点の次数は次のようになることが分かります。

ひし形の\(\,4\,\)頂点以外の点\(\,\cdots\,\)次数\(\,2\,\)

ひし形の\(\,4\,\)頂点\(\,\cdots\,\)次数\(\,1\,\)。

以下その理由を記します。

まずひし形の\(\,4\,\)頂点に隣接する点は，そもそも私たちが操作できる六角形のコマから離れたところにあるので，その次数はボードの形状によって\(\,1\,\)となります。

次にひし形の\(\,4\,\)頂点以外の点について考えましょう。

ひし形の\(\,4\,\)頂点以外の点は，下図のように\(\,3\,\)つの六角形のマスに挟まれた点\(\,p\,\)のような状況とみなせます。

※\(\,4\,\)頂点以外の赤や青の辺上の点は\(\,3\,\)つの六角形のマスに挟まれていませんが，赤・青の辺をそれぞれ赤・青の六角形と「みなす」ことで上図のように考えられます。以降ではこの考え方で\(\,4\,\)頂点以外の辺上の点を捉えます。

点\(\,p\,\)は赤と青の領域の境界上の点なので，
この\(\,3\,\)つの六角形の色は「赤・赤・青」，「青・青・赤」のどちらかになります。

後でどちらにせよ議論は同様であることが分かるので，「赤・赤・青」として考えます。

必要があれば回転させることで，点\(\,p\,\)は下の図のような状況になっていると考えても良いです。

このときグラフ\(\,G\,\)の構成法から上図のように点\(\,p\,\)から\(\,2\,\)つの辺が延びるので，次数は\(\,2\,\)であることが分かりました。

よってグラフ\(\,G\,\)は点の次数\(\,1\,\)か\(\,2\,\)であるので，各連結成分は道か閉路になり，特に次数\(\,1\,\)の点を含む連結成分は道になります。

グラフ\(\,G\,\)の次数\(\,1\,\)の点はひし形の\(\,4\,\)頂点のみで，一つの道に対して始点・終点の\(\,2\,\)つの次数\(\,1\,\)の点が対応するので，

これらの\(\,4\,\)頂点はどの道の端点に属するかによって\(\,2\,\)つのペアに分けられます。

ここからは議論を分かりやすくするため，この\(\,4\,\)頂点それぞれを右・左・上・下で指定することにします。

この内，左右の\(\,2\,\)の頂点が同じ道の端点になったとしましょう。

その道に右から左の頂点に向かうように向きを付けます。

上図から見て分かるように，

右の点では進行方向の右側に青の領域がありましたが，左の点では進行方向の左側に青の領域があります。

このような“ねじれ”が起こることはあり得ないので，左右の\(\,2\,\)頂点が同じ道の端点にならないことが分かります。

つまり右の点を端点として含む道のもう一方の端点は上下の点のどちらかです。

もしもう一方の端点が上の点だとすると，それは赤の辺がつながっていることになります。

反対に下の点だとすると，それは青の辺がつながっていることになります。

したがって，どちらか片方の色の辺のみがつながることが言えたので，証明終了です。\(\quad\square\)

この「Hexは引き分けにならない」ことと，戦略拝借論証で示した「Hexは後手必勝でない」を合わせると次の命題が得られます。

必勝法の詳細は分からないのに，必勝法の存在だけは分かるのは面白いですね。

Hexのどの局面も先手必勝か後手必勝になる

前節では，Hexの最初の局面では先手必勝になることが分かりました。

「数手進んだ局面や，ハンデのためにいくつかのマスが色で塗られているような局面の場合はどうなるのか？」という疑問に答えるのが次の命題です。

証明はとても簡単です^※1。

Hexのボードで色で塗られていないマスの個数を\(\,n\,\)として，\(\,n\,\)に関する数学的帰納法で示していきます。

\([1]\,n=0\,\)のとき，
命題1「Hexで引き分けとなることはない。さらにボードの全てのマスを色で塗り分けたとき(Hexの手順どおりに塗り分けなくてもよい)，どちらか片方の色の辺のみがつながる。」より，

既に先手か後手のどちらか一方のみが勝利しているので，命題が成り立つことが分かります。

\([2]\,n= k\in \mathbb{N}\cup \{0\}\,\)のとき成り立つと仮定して，\(\,n=k+1\,\)である局面\(\,G\,\)について考えましょう。

先手(赤とする)が一手だけ進めた局面\(\,G^{N}\,\)の残りのマスはもちろん\(\,k\,\)です。

局面\(\,G^{N}\,\)に帰納法の仮定を用いることで，
局面\(\,G^{N}\,\)では赤か青のどちらか一方のプレイヤーが必勝の状態になってます。

仮にどの局面\(\,G^{N}\,\)においても青にとって必勝の状態だったとすると，これは局面\(\,G\,\)の時点でもともと青が必勝であったことを意味します。

逆にある局面\(\,G^{N}\,\)において青にとって必勝でない，つまり赤にとって必勝であったとすると，

局面\(\,G\,\)の時点で赤がその必勝局面\(\,G^{N}\,\)に移るように着手することで，赤は勝つことができるので，これは局面\(\,G\,\)では赤が必勝であることを意味します。

よって\(\,n=k+1\,\)のときも命題が成り立つことが分かりました。

したがって\(\,[1],[2]\,\)より，題意は示されました\(\quad\square\)

※1 本質的には組み合わせゲーム理論の基本定理の証明と同様です。

Hexは正規形のゲームでないので，組み合わせゲーム理論の基本定理をそのまま適用することはできませんが，

正規の条件を命題1「Hexで引き分けになることはない」という条件で代用すれば良いだけですね。

二つの証明を実際に見比べると，Hexの残りのマスの個数が組み合わせゲームの後続局面数に対応していることが分かるでしょう。

先攻の初手はボードの鋭角の先端を塗ってはいけない

前々節ではHexの初期の局面では先手必勝になることが示されました。

一方前節では，Hexのどの局面も必ず先手必勝か後手必勝になることが示されました。

二つの命題を合わせて考えると，
先攻が「下手な手」を打ってしまうと，後攻が必勝戦略をもつ局面に変わってしまう可能性があることになります。

実際どのような手が「悪手」なのかを示すのが，次の命題になります。

この命題の証明も戦略拝借論証を用いますが，やや工夫が必要です。

しかし証明は簡単なので，身構えなくて良いです。

戦略拝借論証を使うので，まず先攻(赤)が初手において，ボードの鋭角の先端のマスを塗った状態で必勝戦略を持つと仮定します。

つまり下の図は先攻(赤)が必勝の状態です。

※一般性は失わないので左の鋭角のマスで考えています。

次にハンデで後攻(青)に鋭角のマスをあげた状態を考えましょう。

このとき青が鋭角のマスを初手に塗ったとみなすことで，青が先攻とみなせます。

そのため先ほどの図が先攻必勝であったことから，今度は青が必勝の状態であることが分かります。

さらにハンデで青に下のように\(\,1\,\)マスあげても，もちろん青必勝の状態ですね。

このことから次の状態も青必勝の状態であることを示します。

まず最後の図で鋭角の赤のマスが青のマスに変わった状態では青は必勝戦略を持つのでした。

そこで最後の図の鋭角の赤のマスを青のマスと「思い込み」，青は必勝戦略を行います。

この「思い込み」の状態で必勝戦略を進めると，仮想的に青の勝ち状態に持っていけます。

この仮想的な勝ち状態を現実に引き戻したときに，「思い込み」は青の勝ち状態に影響しません。

なぜなら影響するときとして考えられるのは，仮想的な青の対辺を結ぶ道に「思い込み」のマスが含まれているときですが，

下図のように黒太線で囲った青のマスにより，道に「思い込み」のマスが含まれていないように取り換えることができるからです。

そのため下の状態は青必勝の状態となります。

そのため赤が鋭角のマスを初手で塗ったとしても，後攻の青が上図になるように打てば青必勝の形になります。

これは先攻(赤)が初手において，ボードの鋭角の先端のマスを塗った状態で必勝戦略を持つと仮定したことに矛盾します。

引き分けはないので，これは赤が初手でボードの鋭角の先端のマスを塗ってしまった状態では青が必勝戦略を持つことを意味します。

したがって題意は示されました。\(\,\quad\square\,\)

余談ですが，ボードの上下の鈍角のマスだと「思い込み」のマスが，仮想的な勝ちの状態を現実に引き戻すときに影響が出てしまいます。

そのためボードの鋭角に限ったということです。

その他の話題

ここまで紹介してきた話題以外にも，Hexでは以下のたくさんのことが知られています。

• Hexとブラウワーの不動点定理の関係
• 逆形Hex(Rex)について
• Hexの亜種Yについて

流石にボリュームが多くなりすぎるので，この記事では解説しませんが，希望があれば調べて別記事にしたいと考えています。

この他Hexについて面白い話題を知っている方は教えていただけると嬉しいです。

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

Hexの図をTeXで作成するのがめちゃくちゃ大変でした。その苦労に見合うだけの感動を読者に与えられていたら何よりです。

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

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

• \([1]\) 安田健彦.“ゲームで大学数学入門　―スプラウトからオイラー・ゲッターまで―”.初版.共立出版.2018出版.p.17-26
• \([2]\) .David Gale.“Topological games at Princeton, a mathematical memoir”.Games and Economic Behavior.2009Published.Volume 66.p.647-656