Loading article…
ヘックス（ナッシュとも呼ばれる）は、六角形のマス目で構成された菱形の盤面の反対側の辺を繋げることを目指す、2人用の抽象戦略ボードゲームです。ヘックスは、1942年に数学者で詩人のピート・ハインによって考案され、後にジョン・ナッシュによって再発見され、広く知られるようになりました。
伝統的には11×11の菱形の盤でプレイされますが、13×13や19×19の盤も人気があります。また、六角形の罫線が引かれた方眼紙に紙と鉛筆でプレイすることもできます。盤はセルまたはヘックスと呼ばれる六角形で構成されています。各プレイヤーには盤の向かい合う2つの辺が割り当てられ、空いている六角形に自分の色の石を交互に置くことで、それらの辺をつなげようとします。一度置かれた石は、動かしたり取り除いたりすることはできません。隣接する石の連鎖によって自分の辺同士をうまくつなげたプレイヤーが勝ちです。ゲーム盤のトポロジーのため、ヘックスでは引き分けはありえません。
ルールは単純ながら、このゲームには奥深い戦略性と鋭い戦術が秘められている。また、ブロワーの不動点定理、マトロイド、グラフ連結性といった、高度な数学的基盤も備えている。
Hex は有限の 2 人完全情報ゲームであり、接続ゲームの一般的なカテゴリに属する抽象戦略ゲームです。[ 1 ]これは、特定のタイプの位置ゲームであるメーカー ブレーカー ゲームに分類できます。 [ 1 ] : 122このゲームは引き分けで終わることがないため、[ 1 ] : 99 Hex は決定ゲームでもあります。
Hexは、シャノンスイッチングゲームの「ノード」バージョンの特殊なケースです。[ 1 ] : 122 Hexは、ボードゲームとしても、紙と鉛筆のゲームとしてもプレイできます。
ヘックスは、通常11×11サイズの六角形の菱形グリッド上でプレイされますが、他のサイズも可能です。各プレイヤーには、慣習的に赤と青、または黒と白の色の割り当てがあります。 [ 2 ]各プレイヤーには、向かい合う2つのボードエッジも割り当てられます。4つの角の六角形は、隣接する両方のボードエッジに属します。
プレイヤーは順番に、自分の色の石を盤上の1マスに置きます。一般的には、赤または黒が先手となります。一度置かれた石は、移動、交換、または盤上から取り除くことはできません。各プレイヤーの目標は、自分の石で盤の両端を結ぶ線状の道を作ることです。この線状道を最初に完成させたプレイヤーがゲームに勝利します。
先手プレイヤーの有利さを相殺するために、通常はスワップルール（パイルールとも呼ばれる）が用いられる。このルールでは、先手プレイヤーが最初の手を打った後、後手プレイヤーが先手プレイヤーと位置を交換するかどうかを選択できる。
どちらのプレイヤーが勝つかが両プレイヤーにとって明らかになった場合、負けるプレイヤーが投了するのが慣例となっているが、必須ではない。実際には、ヘックスのゲームのほとんどはどちらかのプレイヤーが投了して終了する。
このゲームはデンマークの数学者ピート・ハインによって考案され、1942年にニールス・ボーア研究所で発表されました。ハインは後にこのゲームをコンタックスと改名しましたが、[ 3 ] [ 4 ]デンマークでは、 1942年12月26日付けのデンマークの新聞ポリティケンに掲載されたハインの記事（このゲームの最初の発表記事）でポリゴンという名前が使われたことから、このゲームはポリゴンという名前で知られるようになりました。
このゲームは、1948年か1949年にプリンストン大学の数学者ジョン・ナッシュによって再発見された。[ 2 ] [ 5 ] 1957年7月の「Mathematical Games」コラムでヘックスを取り上げたマーティン・ガードナーによると、ナッシュの仲間のプレイヤーたちはこのゲームをナッシュまたはジョンと呼んでおり、後者の名前は六角形の浴室タイルでプレイできることに由来している。[ 2 ]ナッシュはハインとは独立してこのゲームを発見したと主張したが、1940年代にプリンストンでヘックスをプレイしていたデンマーク人（アーゲ・ボーアを含む）がいたことが知られているため、ナッシュが無意識のうちにそのアイデアを取り入れた可能性があり、この点には疑問がある。ハインは1957年にガードナーに手紙を書き、ナッシュがヘックスを独立して発見したことに疑問を呈した。ガードナーはナッシュの主張を独自に検証することも反証することもできなかった。[ 6 ]ガードナーはハインに個人的にこう書き送った。「編集者と話し合った結果、ナッシュに疑いの余地を与えて寛大な態度をとるのが最善だと判断しました。…あなたが誰よりも先にこのゲームを発明したことは疑いの余地がありません。後から同じことを思いついたと言う人はいくらでもいますが、それはほとんど意味がなく、誰も気にしません。」[ 1 ] : 134後日、ガードナーはハインに宛てた手紙の中でこうも書いている。「ここだけの話ですが、ナッシュ氏がデンマークの情報源から『ひらめき』を得て、後にそれを忘れてしまったというあなたの指摘は的を射ていると思います。それが最も可能性の高い説明でしょう。」[ 1 ] : 136
このゲームは、1942年12月26日にデンマークの新聞「ポリティケン」にハインによって「ポリゴン」という名前で初めて掲載されました。50枚のシートからなるゲームパッドの形で配布されました。各シートには、鉛筆やペンでプレイできる11×11の空白のボードが含まれていました。[ 1 ]
1952年、パーカー・ブラザーズは「Hex」という名前でこのゲームのバージョンを販売し、その名前が定着した。[ 2 ]パーカー・ブラザーズは1968年に「Con-tac-tix」という名前でもバージョンを販売した。[ 3 ] Hexは1974年の3Mペーパーゲームシリーズのゲームの一つとしても発売された。このゲームには、5 + 1/2インチ× 8 + 1/2インチ（140mm × 220mm）の罫線入り六角形グリッド50枚綴りのパッドが含まれていた。
Hexは現在、Nestorgames社から11×11、14×14、19×19のサイズで発売されている。[ 7 ]
1950 年頃、クロード・シャノンとE.F. ムーアはアナログの Hex プレイマシンを構築しました。これは基本的に抵抗器をエッジ、電球を頂点とする抵抗ネットワークでした。[ 8 ]行うべき手は、ネットワーク内の特定の指定された鞍点に対応していました。このマシンは Hex をかなりうまくプレイしました。その後、ゲームを解いて Hex をプレイするコンピュータアルゴリズムを開発しようとした研究者たちは、シャノンのネットワークを模倣して強力なコンピュータプレイヤーを作成しました。[ 9 ]
1942年の時点で、ハインはヘックスが引き分けで終わることはないことを知っていた。実際、彼がこのゲームを設計した際の基準の一つは、「2人のプレイヤーのうち、ちょうど1人が自分の2つの辺をつなげることができる」というものだった。[ 1 ]： 29
ハインはまた、先手プレイヤーには理論上の必勝戦略があることも知っていた。[ 1 ]： 42
1952年、ジョン・ナッシュは、対称盤面において先手プレイヤーが必勝戦略を持つという存在証明を発表した。[ 1 ]： 97
1964年、数学者のアルフレッド・レーマンは、ヘックスはバイナリマトロイドとして表現できないことを示したため、正方格子上のシャノンスイッチングゲームのような確定的な必勝戦略は存在しなかった。[ 10 ]
1981年、ステファン・ライシュはHexがPSPACE完全であることを示した。[ 11 ]
2002年、7×7盤面における初の明確な必勝戦略（削減型戦略）が記述された。
2000年代には、総当たり探索のコンピュータアルゴリズムを用いることで、9×9サイズ（2016年時点）までの六角形盤が完全に解かれた。
2006年頃から、コンピュータHexの分野は、 Goの成功したコンピュータ実装から借用したモンテカルロ木探索法によって支配されるようになった。これらは、シャノンのHexプレイヒューリスティックとアルファベータ探索を組み合わせた以前の実装に取って代わった。初期のコンピュータHexについて言えば、注目すべき初期の実装には、1980年代初頭にAtari 8ビットコンピュータ向けに公開されたDolphin MicrowareのHexmasterがある。 [ 12 ]
2019 年までは、少なくとも 19x19 のような大きな盤面では人間がコンピュータよりも優れていましたが、2019 年 10 月 30 日に、プログラム Mootwo が LittleGolem で最高の Elo ランクを持つ人間プレイヤーに勝利しました。このプレイヤーはさまざまなトーナメントでも優勝しています (ゲームはこちらでご覧いただけます)。このプログラムは、Polygames [ 13 ] (当初はFacebook 人工知能研究といくつかの大学[ 14 ]によって開発されたオープンソース プロジェクト)をベースに、以下の要素を組み合わせて使用しています。 [ 15 ]
最初のプレイヤーの勝利戦略の証明から、ヘックス盤はこれまで解決されていない複雑なタイプの接続性を持つ必要があることがわかっています。ゲームは、「安全に接続された」と呼ばれるより単純なタイプの接続性を持つ小さなパターンを作成し、それらを「パス」を形成するシーケンスに結合します。最終的に、プレイヤーの1人がボードの両側の間に石とスペースの安全に接続されたパスを形成することに成功し、勝利します。必要に応じて、ゲームの最終段階は、パスの空いているスペースを埋めることです。[ 17 ]
「安全に接続された」パターンは、プレイヤーの色の石と、相手のプレイ方法に関わらず、辺で隣接する石の途切れない連続であるチェーンに連結できる空きスペースで構成されています。[ 18 ]このようなパターンの中で最も単純なものの1つはブリッジで、これは同じ色の2つの石のダイヤモンドと、2つの石が接触しない2つの空きスペースで構成されています。[ 19 ]相手がどちらかのスペースに石を置くと、プレイヤーはもう一方のスペースに石を置くことで、連続したチェーンが形成されます。石を辺に接続する安全に接続されたパターンもあります。[ 20 ]安全に接続されたパターンは他にもたくさんあり、中には図のような単純なパターンから構成される非常に複雑なものもあります。パターンやパスは完成する前に相手によって中断される可能性があるため、実際のゲーム中の盤面の構成は、計画または設計されたものというよりは、パッチワークのように見えることがよくあります。[ 17 ]
石同士の間、または複数の隙間がある安全に繋がったパターン間には、「安全に接続された」よりも弱いタイプの接続が存在する。[ 21 ]ゲームの中盤は、そのような弱く接続された石とパターンのネットワークを作成することである。[ 21 ]これにより、プレイヤーは弱いリンクを埋めることで、ゲームが進むにつれて、サイド間に安全に接続された1つのパスを構築できるようになることが期待される。[ 21 ]
Hexで成功するには、複雑なパターンの合成をヒューリスティックな方法で視覚化し、そのようなパターンが最終的に勝利を可能にするほど「十分に強く」接続されているかどうかを推定する特別な能力が必要です。[ 17 ]このスキルは、チェスにおけるパターンの視覚化、動きの順序付け、および局面の評価といくらか似ています。[ 22 ]
ヘックスは引き分けで終わることはない、という「ヘックス定理」は説明によって容易に納得できる。つまり、盤面が石でどのように埋め尽くされていても、必ず1人だけ自分の辺をつなげているプレイヤーが存在する。この事実は1942年にピート・ハインに知られており、彼はオリジナルのポリティケン誌の記事でヘックスの設計基準の1つとして言及している。[ 1 ] : 29 ハインはまた、この事実を「相手にとっての障壁は、自分にとってのつながりである」と述べている。[ 1 ] : 35ジョン・ナッシュは1949年頃にこの事実の証明をまとめたが、[ 23 ]どうやらその証明は公表しなかったようだ。その最初の説明は1952年の社内技術報告書に登場し、[ 24 ]ナッシュは「つながりと相手のブロックは同等の行為である」と述べている。より厳密な証明は、ジョン・R・ピアースが1961年の著書『シンボル、シグナル、ノイズ』で発表した。[ 25 ]
Hex の引き分け禁止特性の非公式な証明は、次のように概略的に説明できます。完全に埋まった Hex 盤で、赤い辺の 1 つを連結成分、つまりその赤い辺に直接的または間接的に接続されているすべての赤い六角形を考えます。連結成分の概念は明確に定義されています。なぜなら、六角形のグリッドでは、2 つのセルは辺でしか接しないか、全く接しないかのどちらかであり、セルが 1 点で重なることは不可能だからです。この連結成分は、反対側の赤い辺を含むか、含まないかのどちらかです。後者の場合、連結成分の境界に沿った青い石が、青の勝利経路を形成します。
1979年、デイビッド・ゲイルは、 Hexの決定性が2次元のBrouwerの不動点定理と同等であり、高次元のnプレイヤー変種の決定性が一般的に不動点定理を証明するという証明を発表した。[ 26 ]
交換ルールのないヘックスでは、 n x nの盤面であれば、先手プレイヤーは理論上の必勝戦略を持つ。この事実は、ハインが1943年の講義ノートで言及している。「他のほとんどのゲームとは対照的に、先手プレイヤーは理論上常に勝つことができることが証明できる。つまり、あらゆる可能なプレイの展開を最後まで見通すことができれば、必ず勝つことができる」[ 1 ]： 42
この事実に関する既知の証明はすべて非構成的であり、つまり、証明は実際の勝利戦略が何であるかを示唆していません。以下は、1949 年頃のジョン・ナッシュに帰属される証明の要約版です。[ 2 ]この証明は、ヘックスを含む多くのゲームで有効であり、戦略窃盗論証と呼ばれるようになりました。
1976年、Shimon EvenとRobert Tarjanは、任意のグラフ上でプレイされる一般化Hexゲームの局面が勝ち局面であるかどうかを判定することがPSPACE完全であることを証明した。[ 27 ] この結果の強化は、Reischが連言標準形における量化ブール式問題をHexに還元することによって証明された。[ 28 ]この結果は、すべてのPSPACE問題に対する効率的なアルゴリズムが存在しない限り、任意のHex局面を解くための効率的な（盤面サイズに対して多項式時間）アルゴリズムは存在しないことを意味するが、これは広くそうではないと考えられている。[ 29 ]ただし、これは初期局面（任意のサイズの盤面）に対する単純な勝ち戦略、または特定のサイズの盤面上のすべての局面に対する単純な勝ち戦略の可能性を排除するものではない。
11×11 Hex では、状態空間の複雑さは約 2.4×10 56 ; [ 30 ]であり、チェスでは 4.6×10 46 です。[ 31 ]ゲームツリーの複雑さは約 10 98 [ 32 ]であり、チェスでは10 123です。[ 33 ]
2002年、Jing Yang、Simon Liao、Mirek Pawlakは、再利用可能なローカルパターンのセットを用いた分解法を用いて、7×7サイズの六角形盤上で先手プレイヤーの明確な必勝戦略を発見した。[ 34 ]彼らはこの方法を拡張し、2002年に8×8盤上の位相的に一致するオープニングの中央ペアを弱く解決し、2003年には9×9盤上の中央オープニングを解決した。 [ 35 ] 2009年、Philip Henderson、Broderick Arneson、Ryan B. Haywardは、コンピュータ探索によって8×8盤の解析を完了し、可能なすべてのオープニングを解決した。[ 36 ] 2013年、Jakub PawlewiczとRyan B. Haywardは、9×9盤上のすべてのオープニングと、10×10盤上の1つ（最も中央の）オープニングムーブを解決した。[ 37 ]ガードナーが1957年にサイエンティフィック・アメリカン のコラムで、一見もっともらしくはあるものの、短い対角線上の最初のプレイはすべて勝ちのプレイであると初めて提唱して以来、[ 38 ] n=9までのすべての解決済みゲーム盤では、実際にその通りであった。さらに、n=2とn=4を除くすべての盤では、多数の追加の勝ちの最初の動きがあり、勝ちの最初の動きの数は一般的に≥ n²/2である。
目的は似ているが構造が異なる他のコネクションゲームには、シャノン・スイッチング・ゲーム（ゲイル、ブリッジイットとも呼ばれる）やトゥイックスTなどがある。これらはどちらも、古代中国のゲームである囲碁とある程度の類似性を持っている。
このゲームは、チェス盤、チェッカー盤、囲碁盤のような長方形のグリッド上でプレイできます。その際、マス目（囲碁の場合は交点）は対角線上の一方向には繋がっていますが、もう一方向には繋がっていないという点に着目します。また、紙と鉛筆を使って、長方形のドット配列や方眼紙上で、2色の鉛筆を使ってプレイすることもできます。
標準的な11×11の他に、13×13や19×19といったサイズもよく用いられますが、これは囲碁という古いゲームとの関連性によるものです。『ビューティフル・マインド』という本によると、ジョン・ナッシュ（このゲームの発明者の一人）は14×14が最適なサイズだと提唱していました。
ヘックスのミゼール版は「レックス」と呼ばれ、各プレイヤーは相手に連鎖を作らせようとします。レックスはヘックスよりも遅く、同じ寸法の空のボードでは、負けているプレイヤーはボード全体が埋まるまで負けを遅らせることができます。[ 39 ] 寸法が異なるボードでは、どちらが先にプレイしても、より遠く離れているプレイヤーが勝つことができます。[ 40 ] 寸法が同じボードでは、各辺のセルの数が偶数のボードでは最初のプレイヤーが勝つことができ、奇数のボードでは2番目のプレイヤーが勝つことができます。[ 41 ] [ 42 ] 偶数のボードでは、最初のプレイヤーの勝利の1つは常に鋭角の角に石を置くことです。[ 39 ]
Hexは、テレビゲーム番組「Blockbusters」のクイズボードとして登場したことがある。プレイヤーは「ムーブ」を行うために、クイズに正解する必要があった。ボードには4つの六角形が交互に並んだ5列があり、ソロプレイヤーは上から下まで4ムーブでつなげることができ、2人1組のチームは左から右まで5ムーブでつなげることができた。
Yゲームは、六角形の三角形グリッド上でプレイするヘックスゲームです。目的は、どちらかのプレイヤーが三角形の3辺すべてを接続することです。Yはヘックスの一般化であり、ヘックス盤上のどの位置も、より大きなY盤上の同等の位置として表現できます。
ハバナはヘックスをベースにしたゲームです。[ 43 ]ボードスペースは六角形のタイルで構成されていますが、ボード自体が大きな六角形の形をしており、3つのパターンのいずれかを形成することで勝利となります。
Projexは、実射影平面上でプレイされるHexの変種で、プレイヤーは非縮約ループを作成することを目標とする。[ 44 ] Hexと同様に、引き分けはなく、両方のプレイヤーが勝ちとなる接続を持つ局面はない。
ダークヘックス（ファントムヘックスとも呼ばれる）は、ヘックスの不完全情報版です。[ 45 ]プレイヤーは、先に発見しない限り、ゲーム中のどの時点でも互いの石を見ることはありません。ゲームは審判の立ち会いのもとで行われ、各プレイヤーはまず、その動きが衝突するかどうかを確認します。この点の継続に基づいて、ゲームにはさまざまなバージョンがあります。
2016年現在、ブラジル、チェコ共和国、デンマーク、フランス、ドイツ、イタリア、オランダ、ノルウェー、ポーランド、ポルトガル、スペイン、イギリス、アメリカ合衆国で、対面式のトーナメントが開催されていると報告されている。最大規模のHex競技会の1つは、フランスのパリで国際数学ゲーム委員会によって主催されており、2013年から毎年開催されている。Hexはコンピュータオリンピックの一部でもある。[ 46 ]この競技会ではパイルールが使用される。
{{cite book}}ISBN /日付の不一致（ヘルプ）{{cite web}}: CS1 maint: bot: 元の URL の状態が不明です (リンク)