Hex(1942) — 新聞の片隅の六角形が、引き分けを許さなかった年

はじめに

これは1942年、デンマークの新聞の片隅に載った、小さなパズル欄の話である。まだ名前も定まっていない盤が、そこで初めて紙に印刷された。

遊び方は驚くほど単純だ。ひし形に並んだ六角形の盤で、自分の色の駒を置いていき、盤の向かい合う二辺を自分の駒の鎖でつなげば勝ち。ルールはこれだけである。

だがこの単純な盤は、のちに「絶対に引き分けが起きない」ことが数学的に証明され、さらに「解くこと自体がとてつもなく難しい」ことも証明されることになる。今日Hexと呼ばれるこのゲームが、たった一行のルールからどこまで歩いたのかを、今日は掘り起こしたい。

紙面の片隅に載った六角形の盤、というイメージ（イメージ・AI生成）

その時代の文脈

発表は1942年12月26日、デンマークの新聞Politiken紙。考案者は詩人にして数学者のピエト・ハイン(Piet Hein、1905-1996)で、当時は「Polygon」という名で紹介された。当時のデンマークは1940年4月からドイツの占領下にあり、そういう時代の新聞に載ったパズルだという事実だけが、資料として残っている。

6年後、大西洋を越えたアメリカ・プリンストン大学。1948年から49年にかけて、数学科の大学院生だったジョン・ナッシュ(John Nash)が、ハインとはまったく別に同じ盤へたどり着く。学生たちはこのゲームを「Nash」、あるいは六角形のタイルが敷かれた浴室の床でも遊べることから「John」と呼んだ。

ナッシュが本当にハインの存在を知らなかったのかは、実は今も議論が残っている。当時プリンストンにはデンマーク人の留学生もいたからだ。それでも、占領下のコペンハーゲンと戦後まもないプリンストンという、まったく違う二つの場所で同じ盤が独立に生まれたという事実は動かない。

1952年、玩具会社パーカー・ブラザーズがこのゲームを商品化する。名前は「Hex」。この名前が、そのまま今日まで定着した。

占領下の新聞の一段と、六角形のタイル。二つの場所から同じ盤が生まれた（イメージ・AI生成）

メカニクス

盤はひし形に並んだ六角形の集まりである。対辺の片方を白、もう片方を黒に割り当てる。プレイヤーは交互に自分の色の駒を置き、自分の対辺どうしを駒の鎖でつなげば勝ちになる。

このゲームには「引き分け」がない。盤が全部埋まれば、必ずどちらか一方の鎖が反対側まで届く形になる。これは位相幾何学的な性質による。さらに「後出しの手を真似すれば損をしない」という模倣の理屈から、先手には必ず勝てる手順が存在することも示された(ジョン・ナッシュ、1949年ごろの議論)。ただし、その手順が具体的にどんな手なのかまでは、証明は教えてくれない。

「必勝法がある」と「解ける」は別の話だ。1981年、シュテファン・ライシュ(Stefan Reisch)は、Hexが計算複雑性の分類でいう「PSPACE完全」であることを証明した。盤が大きくなるほど、最善手を計算し尽くすことは実質的に不可能になっていく。ルールは一行で書けるのに、解くのは途方もなく難しい。これがHexの正体である。

対辺どうしを駒の鎖でつなげば勝ち、という構造の図解（イメージ・AI生成）

現代への系譜

1957年7月、数学コラムニストのマーティン・ガードナーが『サイエンティフィック・アメリカン』誌の連載でHexを取り上げた。コラムの題は「浴室の床タイルでも遊べるHexというゲームについて」。ナッシュの逸話をそのまま引いたような題で、Hexは一気に広く知られることになる。

このHexは、のちに「コネクションゲーム」と呼ばれるジャンルの起点になった。ゲーム研究者カメロン・ブラウンは著書『Connection Games』で、Hexを「最初のコネクションゲーム」と位置づけている。TwixT(1962年)、Y、Havannah、そして2016年に発表されたTak(考案:James Ernest、Patrick Rothfuss。盤は正方形だが「対辺をつなげば勝ち」という文法はHexと同じ系譜にある)まで、この一行のルールは今も新作を生み続けている。

1950年ごろ、情報理論で知られるクロード・シャノンと数学者E・F・ムーアは、Hexだけを指す専用のアナログ計算機を作った。辺には抵抗、頂点には豆電球を配した電気回路そのものが、対戦相手になったのである。ゲームを「読ませる」コンピュータの、ごく初期の試みの一つだった。

2009年、コンピュータHexの世界でモンテカルロ木探索(MCTS)という探索手法が主流になる転換点が訪れた。この探索手法は、2016年に囲碁の世界トップ棋士を破ったAlphaGoの中核技術と同じ系譜にある。今日、Steamで遊べる多くのボードゲーム系デジタル作品のAI対戦相手も、この系譜の延長線上で作られている。占領下の新聞に載った小さな盤が、遠く回って今の画面の中まで届いているわけだ。

一つの盤から、ジャンルと計算技術へ枝分かれしていく系譜のイメージ（イメージ・AI生成）

参考文献

本記事で参照した情報源:

・Wikipedia: Hex (board game)

・Wikipedia: Connection game

・Wikipedia: Piet Hein (scientist)

・HexWiki: History of Hex

・Chess Programming Wiki: Hex

・Stefan Reisch, "Hex ist PSPACE-vollständig", Acta Informatica 15 (1981) — Springer

・Scientific American: Martin Gardner, "Mathematical Games" (1957年7月号)

・Wikipedia: Tak (game)

おわりに

Hexが歴史的に示したのは、ルールの単純さと解くことの難しさは、反比例しないという一点である。ひし形の盤と「つなげば勝ち」という一行のルールから、引き分けなしの証明も、計算の難しさの証明も、そして新しいジャンルも生まれた。

占領下の新聞の片隅から、プリンストンの浴室タイルへ。ハインとナッシュ、二人が別々の場所でたどり着いた盤は、80年以上たった今も、新しい接続を待っている。

静かに置かれた、一つの六角形（イメージ・AI生成）