英米で親しまれている盤上ゲーム「チェッカー」は、2007年にコンピューターで「解かれた」ゲームです。双方が一度も間違えずに指し続けると、勝負は必ず引き分けになる。カナダのアルバータ大学のチームが、18年がかりでそれを証明しました。海外掲示板では、三目並べの思い出話から、史上最強と言われる人間のプレイヤーの逸話まで話が広がりました。 ※注：チェッカーは、8×8マスの盤の濃い色のマスだけを使い、12個ずつの丸い駒を斜め前へ1マスずつ進めて、相手の駒を飛び越えて取り合うゲームです。取れる駒があるときは必ず取らなければならず、相手側のいちばん奥の列まで進んだ駒は「キング」になって、後ろにも動けるようになります。イギリスでは「ドラフツ」と呼ばれます。名前の似た「チャイニーズチェッカー」（日本でいうダイヤモンドゲーム）とは別のゲームです。 今日の知ってた？ 🏁 8×8の盤で指す英米式のチェッカーは、2007年にコンピューターで「解かれた」。双方が最善を尽くすと、結果は必ず引き分けになる。 🧮 盤上に現れうる局面は約5×10の20乗（5垓）通り。カナダのアルバータ大学のジョナサン・シェーファーらが1989年に取り組みを始め、米科学誌『サイエンス』に証明を発表した。 🤖 証明に使われたのは、同じチームが開発したチェッカー用プログラム「チヌーク」。1994年には人間対機械の世界選手権で王者になり、人間を相手にした世界選手権のタイトルを取った最初のコンピュータープログラムになった。 🎓 論文の共著者8人には、当時公立はこだて未来大学に勤めていた岸本章宏さんも名を連ねている。 背景：「解かれたゲーム」とは ゲームを「解く」とは、双方が一度もミスをしなかった場合に、勝負がどう決着するかを突き止めることです。シェーファーらの論文は、これを3つの段階に分けています。いちばん弱い段階は、結果だけが分かっていて、そこへたどり着く指し方は分からない状態です。たとえば「ヘックス」という盤ゲームは先手必勝だと分かっていますが、大きな盤での勝ち方は分かっていません。その上が、最初の配置から最善の結果を出す指し方まで分かっている状態で、チェッカーはここに当たります。いちばん強いのは、ゲームの途中に現れうるすべての局面について結果が分かっている状態です。 チェッカーについて今回示されたのは、黒と白のどちらを持っても、どんな相手に対しても少なくとも引き分けに持ち込める、具体的な指し方です。逆に言えば「必勝法」が見つかったわけではありません。相手が間違えない限り、行き着く先は引き分けです。引き分けという結論そのものは意外なものではなく、トップ選手たちは何十年も前からそう予想していた、と論文も書いています。 いちばん強い意味で解く、つまりすべての局面の結果を記録するのは、まだ現実的ではありません。論文の見積もりでは、約5垓通りの局面をすべて保存すると、よく圧縮しても10の18乗バイト、つまり100万テラバイトほどになります。 チェッカーとコンピューターの縁は古く、1950〜60年代には、IBMの研究者アーサー・サミュエルが、自分で対局を重ねて強くなるチェッカーのプログラムを作りました。1960年代の初めには腕の立つ人間の指し手から1局を勝ち取り、人工知能の勝利として話題になります。この話はやがて誇張され、「チェッカーはもう解かれた」とまで言われるようになりましたが、実際に解かれたのは、それから40年以上あとのことでした。 もう少し詳しく 人間最強の王者、マリオン・ティンズリー。チヌークの開発は1989年、チェッカーの世界王者に挑めるプログラムを作ることを目標に始まりました。当時の王者は、アメリカの大学で数学を教えていたマリオン・ティンズリーです。選手権から長く離れていた時期をはさみながら、1955〜58年と1975〜91年に世界王者の座にあり、論文によれば1950年から1991年までに負けたのはわずか3局でした。 チヌークは1990年に世界選手権の挑戦権を勝ち取りますが、チェッカーの団体はコンピューターがタイトルを争うことを認めませんでした。するとティンズリーはタイトルを返上してまでチヌークとの対戦を望み、1992年の対戦では4勝2敗（引き分け33局）で勝ちます。1994年の再戦では、6局続けて引き分けたところで、ティンズリーが体調不良のため棄権しました。直後に膵臓がんと診断され、翌1995年4月に68歳で亡くなっています。チヌークはこの再戦で王者となり、1995年にもう一度タイトルを守ったあと、大会からは退きました。 ティンズリーとの勝負は、どちらが強いのか分からないまま終わりました。論文は、チェッカーが引き分けだと証明できれば、完璧なチヌークは決して負けないことになる、と書いています。チームはその後、チェッカーそのものを解く計算に力を注いでいきます。 どうやって解いたのか。証明は、2つの方向からの計算を組み合わせています。ひとつは、ゲームの終わりから逆向きにたどる計算です。盤上の駒が10個以下になった局面をすべて調べ上げ、約39兆通りの局面の結果をデータベースにまとめました。圧縮すると237ギガバイトになります。駒8個までのデータベースを作るのに1989年から1996年まで7年かかりましたが、コンピューターの性能が上がった2001年には、同じ計算が1か月で済みました。10個までのデータベースは2005年に完成しています。 もうひとつは、最初の配置から先へ読み進める計算です。こちらで調べた局面は、論文の見積もりでおよそ10の14乗（100兆）通り。最初の配置の結果を決めるのに必要な19通りの序盤を、ひとつずつ証明していきました。計算は途中で止まった時期をはさみながら続きました。1992年のピーク時には200台を超えるプロセッサーを同時に使い、最後の1年間も平均50台のコンピューターが動き続けました。論文はチェッカーを、これまでに解かれた広く遊ばれているゲームの中でいちばん難しく、縦に立てた盤に駒を落として4つ並べるゲーム「コネクトフォー」の、およそ100万倍の複雑さだとしています。 大会では最初の3手をくじで決める。チェッカーの大会では、ふつうの初期配置から始めると「退屈」だとされ、最初の3手をくじで決めて指し始めるのが一般的です。引き分けを減らすための工夫で、チェッカーが解かれるずっと前から使われてきました。今回の証明が示したのは、ふつうの初期配置から始めた場合の結果です。 ほかのゲームはどこまで解かれたか。三目並べは、双方が間違えなければ引き分けになることが早くから知られています。コネクトフォーは1988年に、先手が必ず勝てると解かれました。日本生まれのオセロについては、2023年に東京のAI企業プリファードネットワークスの研究者が、双方が最善を尽くすと引き分けになるとする論文をネット上で公開しました。ただ、この論文は査読を経る前のもので、結論に異論を唱える声もあります。 チェスは、駒が7個以下になった終盤ならすべての局面の結果が計算済みですが、ゲーム全体はまだ解かれていません。19路盤の囲碁と将棋も同じです。小さなゲームでは、3×4マスの盤で指す子ども向けの将棋「どうぶつしょうぎ」を、東京大学の田中哲朗さんが2009年に完全に解析し、双方が最善を尽くすと後手が勝つという結果を発表しています。 海外の反応 1. 海外の名無しさん 先手と後手があるのに、お互いに最善を尽くせば必ず引き分けって、ゲームとしてはものすごくバランスが取れてるってことだよな。 2. 海外の名無しさん（>>1への返信） じゃあ2人同時に指せばいいじゃん。なんでわざわざ交代で指してるんだ。バカなのか？ 3. 海外の名無しさん（>>2への返信） ふざけた質問に真面目に答えると、全員が同時に動くゲームは実在する。『ディプロマシー』っていうボードゲームで、全員が自分の命令を紙に書いて、一斉に公開するんだ。相手が何をしてくるか読み合って、さらにその裏をかく。あの駆け引きがたまらない。 4. 海外の名無しさん 完璧に指すと引き分けになるボードゲームって、なぜか多いよな。チェッカー、チェス、オセロ、たぶん囲碁も。どれも、そんなことを証明できるようになるずっと前に生まれたゲームなのに。 5. 海外の名無しさん（>>4への返信） 生存者バイアスだと思う。先手が勝ちすぎるような、バランスの悪いゲームもたくさんあったはず。そういうのはつまらなくて誰も遊ばなくなり、消えていったんだろう。 6. 海外の名無しさん（>>4への返信） チェスと囲碁は、数学的にはまだ解かれてないよ。それに囲碁は、引き分けにならないように作り直されてきたゲームだ。先手の黒が有利すぎるから、後手の白に最初から点を足す「コミ」が20世紀になって取り入れられて、その値も何度か引き上げられてきた。日本のルールなら今は6目半。半目が付いているのは、同点の引き分けを出さないためなんだ。 7. 海外の名無しさん このゲームを解いたチームが、史上最強のチェッカー選手マリオン・ティンズリーと指していたころの話が好きだ。1990年のある対局で、チヌークが10手目を指した瞬間、ティンズリーは「それは後悔することになるよ」と言った。チヌークは36手目で投了。開発者のシェーファーが後で振り返ると、ティンズリーはその時点で、もう勝ちまでの道筋を見通していたらしい。チヌークの側がその10手目の失敗に気づくには、何十手も先まで読む必要があったそうだ。 8. 海外の名無しさん（>>7への返信） ティンズリーは、人間と指すのに飽きてたらしいね。若いころから負け知らずで、相手はみんな最初から引き分け狙いで来る。そこへ現れたチヌークは、勝つためならリスクも平気で取ってきた。チヌークと指していると若いころに戻ったような気分になる、とティンズリーが話していたと、シェーファーが書き残してる。 9. 海外の名無しさん（>>7への返信） それだけ先が読めるなら、なんでチェスに移らなかったんだろう。チェスなら複雑さに底がないから、退屈することもなかっただろうに。 10. 海外の名無しさん（>>9への返信） シェーファーの著書『One Jump Ahead』には、ティンズリーの言葉としてこんな一節が載ってる。「チェスを指すのは、果てしない海を眺めるようなもの。チェッカーを指すのは、底なしの井戸をのぞき込むようなものだ」。広さより深さのほうに惹かれていたんだろうね。 11. 海外の名無しさん みんなが「解かれた」とか言ってる横で、俺はいまだに三目並べで引き分けに持ち込めないことがある……。 12. 海外の名無しさん（>>11への返信） 上の娘が5歳くらいのころ、妻が「三目並べはどんなに上手くなっても、分かってる相手には引き分けが精一杯なのよ」と教えようとしたことがある。ところが途中で妻の気がそれて、娘が勝ってしまった。娘は22歳になった今でも、不可能なことなんてないと信じてる。 13. 海外の名無しさん（>>12への返信） 相手のミスを待って仕留めるのも、立派な戦略だからね。オーストラリアのスティーブン・ブラッドバリーに聞いてみるといい。 ※注：2002年のソルトレークシティー冬季五輪、ショートトラック男子1000メートルの決勝で、最後尾を滑っていたブラッドバリー選手は、最終コーナーで前の4人がまとめて転倒したため、そのまま1着でゴールして金メダルを取りました。 14. 海外の名無しさん 完璧に指したら必ず引き分けなんだろ？ってことは、唯一の勝ち筋は「最初から指さないこと」だな。 15. 海外の名無しさん（>>14への返信） 映画『ウォー・ゲーム』（1983年）だな。核ミサイルの発射を任されたコンピューターが、三目並べを自分相手に延々と繰り返したあと、「勝つ唯一の方法は、プレイしないことだ」と悟って発射をやめる。そのあとのセリフが「それより、チェスでもどうだい？」。この元ネタが通じない人が増えてきて、年を感じるよ。 16. 海外の名無しさん ならルールを足して、駒の種類も増やした『チェッカー2』を作ればいい。駒ごとに動き方を変えて、キングだけじゃなく女王も用意して……あ、それチェスだわ。 17. 海外の名無しさん（>>16への返信） 競技のチェッカーは、今は細々と続いてる程度だけど、最初の3手をくじで決めて、少し進んだ盤面から指し始めるんだ。初期配置からだと引き分けばかりで退屈だから、って理由で、解かれるずっと前からそうしてる。 18. 海外の名無しさん 解説を読んでみたけど、どう指せば勝てるのか結局どこにも書いてなかった。俺がバカなだけかもしれないけど、誰か教えてくれ。 19. 海外の名無しさん（>>18への返信） 相手次第だよ。「解かれた」っていうのは、どう指されても負けない手順が分かったって意味で、必勝法が見つかったわけじゃない。相手が間違えない限り、行き着く先は引き分け。しかも三目並べと違って局面は5垓通りもあるから、人間が覚えられる量じゃない。コンピューターでもない限り、地道に上手くなるしかないね。 20. 海外の名無しさん そんなの簡単に勝てるだろ。いちばん後ろの列の駒を……絶対に動かさなければいいんだよ！ 21. 海外の名無しさん（>>20への返信） 英米式のチェッカーは、取れる駒があったら必ず取らなきゃいけないルールなんだよ。だから、わざと自分の駒を取らせる位置に置けば、後ろの列に居座ってる駒も引っぱり出せる。 22. 海外の名無しさん 解かれたのは8×8の盤の話だからね。国際ドラフツ（国際式のチェッカー）は10×10の盤で指すし、ヨーロッパやアフリカで盛んなのはこっち。同じ8×8でも、ロシア式みたいにルールが違えばまた別のゲームだ。ロシア式を指す人から見ると、英米式は物足りないらしい。 23. 海外の名無しさん チェスのほうが好きな理由を分かってもらおうとして、チェッカーでわざと毎回引き分けに持ち込んでみせたことがある。 24. 海外の名無しさん（>>23への返信） でも、チェスだって最善同士で指せば、ほぼ確実に引き分けだと言われてるよ。それに、チェッカーを完璧に近く指して毎回引き分けに持ち込める人間なんて、ほとんどいない。チェスのほうが奥が深いのは確かで、チェスをそこまで完璧に指せる人間は、この先も出てこないと思う。 25. 海外の名無しさん 「機会さえあれば、プレイヤーは効率を突き詰めて、ゲームから楽しさを消してしまう」。『シヴィライゼーションIV』でリードデザイナーを務めたソーレン・ジョンソンの言葉だ。それを最後までやり切ったのが、チェッカーとコンピューターなんだろうな。 まとめ チェッカーは、双方が最善を尽くせば必ず引き分けになることが、2007年に証明されたゲームです。研究の背景には、人間の王者ティンズリーとの、決着がつかないまま終わった勝負もありました。コメント欄では、ティンズリーの読みの深さに驚く声と、「解かれた」は人間が勝てなくなったという意味ではない、という声が並び、話は三目並べや囲碁、映画『ウォー・ゲーム』にまで広がりました。 元ソース: チェッカーが20年近く前から「解かれた」ゲームだと知った。最善の手を指せば負けることはなく、双方が最善を尽くすと必ず引き分けになる The post 「それは後悔することになるよ」コンピューターの10手目を見て人間最強の王者が言った…チェッカーが“解かれる”までの話 appeared first on みんな知ってた？【海外の反応】.…