対戦ゲームは「解かれる」

対戦ゲームには、「お互いが最善を尽くしたら、結局どうなるか」という問いがあります。先に打つ人が必ず勝つのか、必ず引き分けなのか。コンピュータを使ってこれが完全にわかったゲームは「解かれた」といいます。 このページでは、このサイトの8つの対戦ゲームについて、わかっていることと、まだはっきりしないことを分けて紹介します。

「解かれた」にも段階があります。最初の局面から、どちらかが負けない打ち方がわかれば「弱く解かれた」といいます。どの局面からでも最善手がわかるのが「強く解かれた」です。 なお、解かれていても、人間同士の対戦がつまらなくなるわけではありません。完璧に打てる人はほとんどいないからです。

三目並べ

3×3のマスに○と×を交互に置いて、縦・横・斜めに3つ並べたら勝ちです。お互いが最善を打てば、必ず引き分けになります。 盤が小さいので、考えられるすべての場合を調べつくすことができ、そのとおりだとわかっています。

似た遊びは、古代ローマにもあったとされています（駒を動かすルールで、いまの三目並べとは別のものです）。古代エジプトの屋根瓦にあった、という話もありますが、根拠は弱いので、ここでは触れません。 また、1952年にケンブリッジ大学のコンピュータ用に作られた三目並べは、最初期のコンピュータゲームのひとつだといわれています。

このサイトのプログラムで、勝負がついたらそこで止めるとして、途中の盤面は全部で5478通りあり、引き分けで終わる盤面は16通りあることを確かめました。 さらに、最初の局面は最善手同士なら引き分けであること、「強い」コンピュータは先手でも後手でも負けないことも確かめました（tic-tac-toe/engine.test.ts）。

点と箱

点と点のあいだに交互に線を引き、箱の4本目の線を引いた人がその箱をもらいます。箱を取ったら、もう一度続けて打てます。このサイトの盤は3×3＝9個の箱で、線は全部で24本です。

フランスの数学者エドゥアール・リュカが19世紀に紹介した遊びで、「ピポピペット」という名前でした。年は、19世紀末ごろとしておきます。 この遊びのコツは、箱が長くつながった「鎖」です。鎖の最初の1本を引くと、相手に続けて箱を取られてしまいます。そのため、鎖を先に開かされたほうが不利になりやすいのです。

このサイトのプログラムで、線が24本、箱が9個あり、内側の12本は隣り合う2つの箱に共有されていること、4本目で箱を取っても手番が変わらないこと、鎖の数え方、最後にどの箱もちょうど1回ずつ誰かのものになることを確かめました（dots-and-boxes/engine.test.ts）。

重力四目並べ

縦に7列、6段の盤に、上から石を落とします。石は列の下から積まれ、縦・横・斜めに4つ並べたら勝ちです。1970年代に商品として世界に広まった遊びで、その商品名はここでは使いません。

この遊びは1988年に解かれました。ジェームズ・アレンが10月1日に、ヴィクター・アリスがそれとは別に、およそ15日後に解いています。ふつうの7×6の盤では、先手が正しく打てば必ず勝てます。 これは「弱く解かれた」の例です。必勝の打ち方はわかりましたが、そのあとに、すべての局面を調べる研究も続きました。

このサイトのプログラムで、4つ並べて勝ちになる並びがちょうど69通りあること（盤の外にはみ出したり、行をまたいだりしないこと）、列が埋まったら置けないこと、勝てる手とふせぐ手をコンピュータが選ぶことを確かめました（gravity-four/engine.test.ts）。

六角つなぎ

六角形のマスの盤で、赤は上と下、青は左と右を、自分の石でつなげたら勝ちです。デンマークのピート・ハインが1942年に新聞で紹介しました。 数学者のジョン・ナッシュも、1948年ごろにこの遊びにたどり着いたと語られています。ただ、どちらが先かには、意見が分かれる話もあります。ここでは、別々の場所で同じ遊びに行き着いた、とだけ書いておきます。

この遊びの大きな特徴は、引き分けがないことです。盤がすべて埋まったとき、赤か青の、必ずどちらか一方だけが、つながっています。 このサイトのプログラムで、3×3の盤の全512通りの埋め方と、7×7・9×9の盤の無作為な2000通りで、つながっているのはちょうど片方の色だけであることを確かめました（hex-game/engine.test.ts）。

引き分けがないと、先手が必勝だということがわかります。理屈はこうです。 もし後手に必勝法があるなら、先手はまず1手を適当に置き、あとは「後手のふりをして」その必勝法をまねすればよいはずです（その1手が邪魔になることはありません。余分な石は、持っていて損にならないからです）。 すると先手も勝てることになり、両方が必ず勝つという矛盾が起きます。だから、勝てるのは先手のほうです。これを「戦略の盗用」といいます。

ただ、この論法は「必勝法がある」とだけ教えてくれて、具体的にどう打てばよいかは教えてくれません。実際に全部解かれている盤は、小さなものに限られます。 先手がずるいほど強いので、最初の1手を打ったあとで先手と後手を入れ替えてよい、というルールを足すこともあります。

リバーシ

相手の石をはさむと、色が返ります。1880年代のイギリスで、ルイス・ウォーターマンとジョン・モーレットが、それぞれ自分が考えたと主張しました。発明者ははっきりしません。 日本では、石の初期配置を決めた版が1970年代に商品になり、いまの標準になりました。その商品名はここでは使いません。

ふつうの8×8の盤は、2023年に論文で、お互いが最善なら引き分けになると示されました。約140年遊ばれてきたゲームですから、これは大きな話題でした。ただ、これは研究者が公表した論文で、ここでは「示された」と書くにとどめます。

このサイトのプログラムで、石の返し方（複数の方向を同時に返すことも含めて）、打てる場所がないときのパス、どちらも打てないときの終局、引き分けの判定を確かめました（reversi/engine.test.ts）。

マンカラ

穴に入った種を、1つずつ反時計回りにまいていきます。最後の1個が自分の大きな穴に入れば、もう一度打てます。最後が自分の空の穴なら、向かいの穴の種をもらえます。

「マンカラ」は1つのゲームの名前ではなく、種まきの遊びをまとめた呼び名です。伝統的な名前は800以上あるとされます。 遺跡や盤の発見がたくさんありますが、どれがいちばん古いのかは、研究者のあいだでも意見が分かれています。「何千年も前から」とは言い切れません。 アフリカで広く遊ばれていることははっきりしていますが、生まれた場所はわかっていません。

このサイトのプログラムで、種の総数が最後まで変わらないこと、最後の1個が自分の大きな穴に入るともう一度打てること、向かいの穴を取る条件を確かめました（mancala/engine.test.ts）。 マンカラの仲間には、先手が必ず勝つと調べられたものもありますが、ルールの細かな違いで結果が変わるので、このサイトのルールについては、ここでは何も言えません。

五目並べ

石を先に5つ並べたほうの勝ちです。記録をたどれる範囲では、江戸時代の日本にさかのぼれるとされていて、19世紀には「ゴーバン」という名前でイギリスに伝わったとされます。中国の五子棋、韓国のオモクなど、仲間もたくさんあります。

日本の強い人たちは、昔から「先手が有利」と言ってきました。それが1990年代に、コンピュータでも確かめられました。 15×15の盤で、6つ以上並べても勝ちとするルール（禁じ手なし）では、先手が必ず勝てると示されたのです。ただし、これは論文が扱った限られたルールの話です。 禁じ手のある「連珠」や、ほかの変種には、そのままは当てはまりません。プロの対局では、先手の有利をおさえる、特別な開き方のルールが使われています。

このサイトの五目並べは、6つ以上並んでも勝ちで、禁じ手はありません。プログラムで、縦・横・2種類の斜めで5つ並ぶと勝ちになること、4つだけでは勝ちでないこと、盤の端で反対側につながらないことを確かめました（gomoku/engine.test.ts）。

ナイン・メンズ・モリス

ひとりが9個の駒を持ち、交互に盤の点に置いてから、線に沿って動かします。直線に3つ並べると「ミル」になり、相手の駒を1つ取れます。駒が3つになると、どこにでも飛べます。

盤は、中世のヨーロッパで盛んに遊ばれ、イングランドの教会の回廊の座席などにも彫られている、とされています。古代エジプトの神殿に刻まれた盤が紀元前1400年ごろのものだという説もありますが、年代に疑いが出ているので、ここでは取り上げません。

このゲームは1990年代にラルフ・ガッサーが解き、お互いが最善なら引き分けになると示しました。人間同士なら勝負がつきますが、完璧に打てば引き分けになる、という意味です。ルールのこまかな違いで結果が変わりうる点には、注意が必要です。

このサイトのプログラムで、盤に24の点と、ミルになる並びが16通りあること、ミルの駒は、ほかに取れる駒があれば取れないこと、3つのとき（4つではなく）だけ飛べること、同じ局面が3回出たら引き分けになることを確かめました（nine-mens-morris/engine.test.ts）。

ちがいを見る

• 三目並べ：最善なら引き分け。小さいので、人間が完全に読める。
• 六角つなぎ：引き分けがないから、先手必勝と理屈でわかる。でも勝ち方は、小さな盤でしかわかっていない。
• 重力四目並べ・五目並べ：ふつうの大きさの盤で、先手が必ず勝てると、コンピュータで示された。
• リバーシ・ナイン・メンズ・モリス：最善なら引き分け。
• 点と箱・マンカラ：ルールの細かな違いで答えが変わるので、このサイトの盤についてはここでは言い切らない。

「解かれた」ことと「勝てる」ことは別です。三目並べで引き分けにする方法を知っていても、相手にまちがえてもらえなければ、勝てません。勝ち負けの読み合いを、遊びの中でためしてみましょう。