オセロは解かれた【第154号】

人気のカレー屋さん「CoCo壱番屋」で，ビーフカレー（829キロカロリー）にトッピングやサイドメニューを加えて合計で1,000キロカロリーを食べたいとします．一番安くなる組み合わせは何でしょうか？

お店にあるもののカロリー数はこちらの表にあります．あと171キロカロリー，どうやって埋めると一番安くなるでしょうか？

このような問題はコンピューターサイエンスの対象としてよく出てきます．

「ココイチ」の場合はメニューの組み合わせを変えるたびに即座に値段とカロリー数がわかりますが，それでも組み合わせ数が膨大なため計算が大変なことがわかると思います．ココイチではオプションの重複を許さないとしても1𥝱（じょ）（10²⁴）通りほどの組み合わせがあります．重複を許すとさらなる組合せ爆発が起こります．

コンピューターサイエンスには，より難しい問題もあります．それがボードゲームを解く問題．ココイチの場合と違って，ある局面の「価値」つまり「カロリー数」がすぐにはわからないので，次の一手を選ぶことは非常に難しいのです．

将棋AIは，数学的に厳密な計算をすることなく盤面の価値を求めてしまうから驚異的なのですよね．言い換えると，現在の将棋AIは将棋を「解いている」わけではありません．藤井聡太八冠がときどき「AI超え」をするのは，将棋がまだ解かれていないからなのです．

この10月30日に「オセロは解かれた（Othello is Solved）」という論文が発表されました．論文と言っても，正確に言うと「学術論文」ではなく「プレプリント」という，信ぴょう性でいうとワンランク下がるものなのですが，実験に使えるプログラムも公開され，同業者による肯定的な評価（その1，その2）も始まっていますので，まず信用しても良いかと思います．また，同論文を紹介するニュース記事も出ています．

結論を言うと，オセロで先手，後手とも最善手を指し続けた場合，引き分けになることがわかったということです．これはトッププレイヤーの「直感」「体感」だったり，オセロAIが人間相手に無双できるという話とは一線を画したものです．オセロが数学的に解かれたのです（＊）．

（＊厳密に言うと「弱解決」です．初期局面から最終局面までのルートはわかっていますが，任意の局面について解決されたわけではありません．）

ボードゲームの場合，完全に解かれるということはめったにありません．解かれるというのは，数学的に解析されたということです．たとえば6x6マスのオセロであれば，後手が必ず勝つことがわかっていますが，一般的な8x8マスのオセロはこれまでなんとなく「最善手を指し続けれは引き分けるのではないか」とだけ言われていました．

上の図はオセロを1手進めるたびに，可能性が枝分かれしていく様子です．1手目はどこに打っても「対称的」なので実質的な枝分かれはありませんが，2手目からは手つまり枝が広がっていきます．

オセロの解析とは，この広がっていく枝の先を最終盤まで追いかけるということです．すべてを追いかけることは現代のコンピューターではできないので，当座はオセロの解析は無理だろうと思われていました．

「オセロは解かれた」論文では，先手，後手とも最善手を指し続けた場合には引き分けるということがちゃんとわかったと主張しています．オセロにしても，他のボードゲームにしても，終盤は「手が狭い」つまり有効な打ち手が少なくなってくるために，コンピューターによってすべての手筋を読み切ることができます．またオセロに関して言うと，序盤も手が狭く，トッププレイヤーや既存のAIが最善手を打てるそうです．ということは，序盤と終盤をつなぐ中盤を解析する妙手があれば良いということですね．

公開された論文では，序盤の10手は既存AIによってお互い最善手を指した場合の局面を用意したそうです．オセロの盤面は8x8の64マスがあり，最初に4マス埋まっていますから，オセロは残り60マスを埋めるゲームです．序盤の10手が経過したあとは50マスが残っていることになります．

本論文では，終盤の36マス残った状態からはすべての局面を読み切っています．というわけで，鍵は残り50マスから残り36マスまでの14手ということですね．本論文は，盤面の仮の評価値，言うなればカロリー数を決め打ちしておいて，その後，最終的にすべての読みを厳密に解析して，結果を比較する手法を発明しています（僕の理解では）．最初からすべての読みを解析しないのは，ある読みの中で別の読みが必要になるため，とりあえずの値があると計算速度が稼げるためのようです（非常に雑な僕の理解では）．

ともかく，オセロは「解かれた」と言っても良いのでしょう．オセロの局面の数は10²⁸通り，1𥝱（じょ）の1万倍にあたる1穣（じょう）通りあると言われています．なお将棋はさらに大きい10⁶²から10⁶⁹通り，囲碁に至っては10¹⁶⁹通りの局面があるとされていますから，将棋や囲碁が数学的に解析されるのはまだまだ先になりそうです（＊）．

（＊本誌「棋士『藤井聡太』が戦う世界【第60号】」でオセロの局面数を10⁶⁰通りとしていますが，これは数え方が異なるためです．詳しくは別冊で解説したいと思います．）

さて，ココイチのあと171キロカロリーのトッピング料金ですが，答えはなんと0円．福神漬けが1グラムあたり0.19キロカロリー（＊）なので，福神漬900グラムをビーフカレーにトッピングすると1,000キロカロリーになります．

（＊メニュー表では0.2キロカロリーとなっていますが，通販のデータで計算し直しました．）

福神漬け900グラムがテーブルの上にあるのかとか，そもそも食えるのかとか，色々突っ込みどころはありますが，数学的な回答は「福神漬900グラム」になります．まあ，信じられないぐらい食べられるユーチューバーもいらっしゃることですから，不可能ではないということで．

シェイクスピア，菅泰男訳：オセロウ

ボードゲーム「オセロ」はシェイクスピアの戯曲「オセロ」から名前を受け継ぎました．

原点を参照することは大切ですよね．

というわけで，読みました．

本作は1602年の作品です．1602年と言えば，ガリレオ・ガリレイが38歳，地動説を信じ始めた頃，日本では関ヶ原の戦いから2年を経て徳川家康がまさに江戸幕府を開こうとしていた時期にあたります．80年ほど遅れますが「好色一代男」が1682年の作なので，日本もそこまで遅れを取ったわけではないのでしょう．

で，好色一代男もそうなのですが，オセロも現代の視点で読んでも「読める」作品です．いや，天下のシェイクスピアに失礼な言い方をしてしまいましたが，それでも400年の時を超えて「読める」というのは，恐るべき筆力ではないでしょうか．

古典ていいものですね．

アレックス・ローゼンタール：パズル大会「パズルハント」――楽しくも，頭を悩ませる世界（日本語字幕）

パズル愛にあふれるトークです．楽しいので御覧くださいね．

匿名質問サイト「マシュマロ」および質問サイト「Quora」で質問を受け付けています．普段はツイッターでお返事を書いていますが「ニュースレター読んでます」と入れていただければ，こちらのニュースレターでより長めの回答を書かせていただきます．

今週はこちらの質問から．

生肉が好きです（でした）．

普段はブラッディ・レア（血のしたたる生肉）を頼むのですが，カリフォルニアのとあるステーキ店に入ったとき，焼き具合の指標に

• ウェルダン（よく焼く）

• ミディアム

• レア（軽く焼く）

• ブラッディ・レア（血のしたたる生肉）

• ピッツバーグ・レア（ピッツバーグの生肉！？）

とあるのを見かけた事があります．「ピッツバーグ・レア」とはなんだろうと思って説明を読んでみると「中心部がまだ凍っている」と書かれていました．さすがに凍っているのは遠慮しました．

英語圏では「ブルー・レア」とか「タタキ」とかもあるのですね．ここらへんはかなりお肉を選びそうですが，いつか試してみたいと思います．

このレターの最後に匿名質問サイトへのリンクを貼っています．質問をお待ちしております．

1週間とは早いものですね．先週戦友であり親友を見送ってきたところなのですが，あっというまに1週間が過ぎました．時の流れを早く感じると歳をとったと言われますので，僕もひとつやふたつは歳をとったということでしょうか．

TEDxDejima Womenから2本の動画が公開されました．どうかブログでご確認ください．とても素敵なトークです．

先週末は3連休でしたが，読者の皆様はいかがお過ごしになったでしょうか？　僕も3連休を見込んでいたのですが，タイ向けのオンライン講義が入ったためしっかりと働きました．ああ．とはいえ，日曜日だけは地元で開かれた「ラブフェス」に参加してきました．いやあ，メディアアートってどれだけ頑張っても，インパクトでは一発の花火に負けますな……と，思った週末でした．

🍓

今週も最後までお読みいただきありがとうございます．メールでお読み頂いた皆様は，よろしければボタンを押して行ってくださいませ．（ボタンは匿名化されています．集計したデータはこのニュースレターの内容改善以外には用いません．）

このニュースレターは下のボタンからSNSで共有できます．もし気に入っていただけたら，共有ボタンも押していってくださいませ．

では，また来週，お目にかかりましょう．

【謝辞】本ニュースレターは「STEAMボート」乗組員（STEAM NEWSサポートメンバー様）のご支援でお届けしております．乗組員の皆様に感謝申し上げます．

ニュースレター「STEAM NEWS」

金谷一朗（いち）

TEDxDejima Studioファウンダー・パイナップルコンピューター代表・長崎大学情報データ科学部教授

📚バックナンバーはこちらから👉 https://steam.theletter.jp/

🎙️ポッドキャストはこちらから👉 https://steam.fm/

📝文字起こしはこちらから👉 https://listen.style/p/steam

💭匿名質問・コメントはこちらから👉 https://marshmallow-qa.com/kanaya

🐘つぶやきはこちらから👉 https://mstdn.jp/@kanaya

🐤DMはこちらから👉 https://twitter.com/kanaya

📬メールはこちらから👉 steam.newsroom@gmail.com

☕️コーヒーの差し入れ（400円のご支援）はこちらから👉 https://ko-fi.com/steamnews

ご意見，ご感想はこのメールに直接ご返信頂けます．