オセロの解析
いちです。おはようございます。今回のエピソードは、オセロは解かれたというお話についてお届けします。
このポッドキャストは、僕が毎週お送りしているニュースレター、スティームニュースの音声版です。
スティームニュースでは、科学、技術、工学、アート、数学に関する話題をお届けしています。
スティームニュースは、スティームボートの取り組みのご協力でお送りしています。
改めまして、いちです。このエピソードは、2023年11月10日に収録しています。
このエピソードでは、スティームニュース第154号から、オセロは解かれたについてお届けします。
今週、佐読前の論文を投稿するサイト、archive.orgに、
オセロ is solved という衝撃的なタイトルの論文が投稿されました。
佐読前なので、論文としての信憑性は、佐読後の論文に比べてワンランク落ちることは落ちるのですが、
実際に使われたプログラムが公開されており、そのプログラムを読んだ専門家による解説もて始めているので、
まず、信頼しても良いのではないかと、個人的な印象は持っています。
それにしてもですよ、今年は2023年なのですが、AI、これ凄まじい進化ですね。
1990年代初頭のインターネット普及から30年、世界を変えたiPhone登場から15年なので、
ICT業界は15年に一度革命が起こるのかもしれません。
この15年に一度革命説は昔から唱えられてはいたのですが、
例えばインターネット登場の15年前、世界初のパーソナルコンピューター向け表計算ソフト、VisiCalcが発表されています。
これは1979年のことで、スティーブ・ジョブズもこの年をパーソナルコンピューティングの原点と主張していました。
というわけで、今年2023年は再び節目の年になるのかもしれません。
というわけで、われわれコンピューター・サイエンティストが衝撃を受けたアーカイブ論文、
オセロは解かれたについてできるだけわかりやすくお話をしていこうと思います。
今週も25分間どうぞお付き合いください。
人気のカレー屋さんココ一番屋で、ビーフカレー829キロカロリーにトッピングやサイドメニューを加えて、
合計1000キロカロリーを食べたいとします。
一番安くなる組み合わせは何でしょうか。
お店にあるもののカロリー数はココ一番屋公式ホームページに掲載されています。
あと171キロカロリーどうやって埋めると一番安くなるでしょうか。
このような問題はコンピューター・サイエンスの典型的な対象とされています。
ココ一の場合はメニューの組み合わせを変えるたびに即座に値段とカロリー数がわかりますが、
それでも組み合わせ数が膨大なために計算が大変になることがわかると思います。
ココ一ではオプションの重複を許さないとしても、
10の24乗1乗どおりほどの組み合わせがあります。
重複を許すとさらに組み合わせ爆発が起こります。
コンピューター・サイエンスにはより難しい問題もあります。
それがボードゲームを解く問題。
ココ一の場合と違ってある局面の価値、つまりカロリー数がすぐにはわからないので、
次の一手を選ぶことは非常に難しいんですね。
将棋AIは数学的に厳密な計算をすることなく、
盤面の価値を求めてしまうから驚異的なんです。
言い換えると、現在の将棋AIは将棋を解いているわけではありません。
オセロの結果と将棋AI
藤井総太八官が時々AI語彙をするのは、将棋がまだ解かれていないからなんですね。
そしてこの10月30日に、オセロは解かれたという論文が発表されました。
論文といっても正確に言うと学術論文ではなく、プレプリントという、
信憑性で言うとワンランク下がるものなのですが、
実際に使えるプログラムも公開され、同業者による肯定的な評価も始まっていますので、
もちろん信用して良いかと思います。
またネットニュースなんかでも紹介され始めているので、
お聞きになった方もいらっしゃるかもしれません。
結論を言うと、オセロで先手後手とも最前種を指し続けた場合、
引き分けになることが分かったということです。
これはトッププレイヤーの直感、体感だったり、
オセロAIが人間相手に無双できるという話とは一線を隠したものです。
オセロが数学的に解かれたんです。
ボードゲームの場合、完全に解かれるということは滅多にありません。
解かれるというのは、数学的に解析がされたということです。
例えば、マルペケゲーム、英語ではTikTokですね、あるいは三目並べ、
こちらはかなり早い段階で数学的に解析がされています。
また、6×6マスのオセロであれば、後手が必ず勝つことが分かっています。
しかし、一般的な8×8マス、64マスのオセロは、
これまでなんとなく最前種を指し続ければ引き分けるのではないかとだけ言われていました。
今、オセロの盤面を脳内に思い描いていただきたいのですが、
最初、白2枚、黒2枚置いてありますよね。
黒が先手盤ということになっていますから、まず黒の人が1枚置きます。
この時に何箇所か置く場所がありますよね。
これ、手が広がっていくわけですね。
最初1つ置きました。次、白がまた置きます。
次、黒の番になりました。
何通りも5本があります。
つまり、手が進む度に枝分かれしていくわけですね。
局面が枝分かれしていきます。
これが非常に組み合わせが多いことになっていきます。
もちろん、ルール上、打ってはいけない場所というのがあるので、
64マス全ての可能性を考える必要はないのですが、
それでも非常に膨大な組み合わせがあることを直感的に
ご理解いただけるのではないかと思います。
オセロの解析とは、この広がっていく枝の先を
最終盤まで追いかけるということです。
64マス全部埋めるまで追いかけるということなんですね。
すべてを追いかけることは現代のコンピューターではできないので、
遠沢オセロの解析は無理だろうと思われていました。
オセロの局面数とトッピング
オセロは解かれた論文では、先手後手とも最前種を指し続けた場合には
引き分けるということがちゃんとわかったと主張しています。
オセロにしても他のボードゲームにしても、
終盤は手が狭い、つまり有効なうち手が少なくなってくるために、
コンピューターによってすべての手筋を読み切ることができます。
またオセロに関して言うと、序盤もこれ意外だったんですが手が狭いそうなんですね。
トッププレーヤーや既存のAIが最前種を打てると信じられています。
ということは序盤と終盤をつなぐ中盤を解析することが、
オセロを解く鍵になるわけですね。
公開された論文では序盤の実定は既存AIによって
お互い最前種を指した場合の局面を用意したそうです。
オセロの盤面は8×8の64マスがあり、最初に4マス埋まっていますから、
オセロは残り60マスを埋めるゲームです。
序盤の実定が経過した後は50マスが残っていることになります。
本論文では終盤の36マス残った状態からは全ての局面を読み切っています。
というわけで残りは50マスから36マスの間14点ということになりますね。
本論文は盤面の仮の評価値、
仮のカロリー数を決め打ちしておいて、
その後最終的に全ての読みを厳密に解析して結果を比較する手法を発明しています。
これは僕の理解なので間違っているかもしれません。
もし間違っていたら後日訂正のポッドキャストをお届けします。
最初から全ての読みを解析すればいいんじゃないのかなって僕も素人で思ったんですが、
ある読みの中で別の読みが必要になるんですね。
その時にとりあえずの値があると計算速度が爆速になるそうなんです。
これも非常に雑な僕の理解なので、
もし間違っていたら後日訂正のエピソードを上げさせていただきたいと思います。
ともかくですね、オセロは解かれたと言っても良いのでしょうね。
オセロの局面の数、先ほどから爆発的という大雑把な表現しかしてきませんでしたが、
実際には10の28乗通り、ここ1の1乗の組み合わせのさらに1万倍の1乗通りあると言われています。
なお将棋はさらに大きい10の62乗から10の69乗通り、
囲碁に至っては10の169通りの局面があるとされていますから、
将棋や囲碁が数学的に解析されるのはまだまだ先になりそうです。
さて、ここ1のあと171キロカロリーのトッピング料金ですが、答えはなんと0円。
福神漬けが1グラムあたり0.19キロカロリーなので、福神漬け900グラム、まあ0.9キログラムですね。
こちらをビーフカレーにトッピングすると1000キロカロリーになります。
福神漬け0.9キログラム、これテーブルの上にあるのかとかそもそも食えるのかとか、
いろいろ突っ込みの頃はありますが、数学的な回答は福神漬け0.9キログラムになります。
まあ世の中にはですね、信じられないぐらいこう食べられるユーチューバー、大食いユーチューバーとかもいらっしゃいますから、
まあ無理ではないんでしょうね。
というわけで、オセロは解かれたという論文のご紹介でした。
いやー、あの組み合わせ爆発の例としてね、トッピングがまあいっぱい選べるメニュー何かなと思って、
ココイチがねパッと思いついたんですけれども、
メニュー表を見たらびっくりしましてね、思ったよりもめちゃくちゃ種類が多かったんですよ。
なんかね80個以上ありました、トッピングとサイドメニューが。
おせいろの起源と名前の由来
で、これあの組み合わせがね、従来からココイチの組み合わせはもう何か100兆超えるとかね、そういう話は聞いてたんですけれども、
計算したらそれどころじゃなかったですね。
10の24畳とか数え方によっては、キッズメニューとかも組み合わせたりとかしたら、
10の28畳とかも本当ね、おせいろの局面の数ぐらいまで爆発するということが分かりました。
まあちょっと適切な例やったかどうかっていうのは、
今振り返ってみると疑問やったんですけれども、
まあココイチで始めてしまったからしゃーないかというので、ココイチでお話をね続けさせてもらいました。
で、このエピソードの中で、それからね、メールで送りさせてもらっているニュースレターの中で、
おせいろ、おせいろという風にね、おせいろの名前何回も使わせてもらってますけれども、
おせいろというゲームの名前、こちらはですね、登録商標なんです。
なので、正しい呼び方、例えば登録商標を避ける呼び方として、かつてはね、リバーシというゲームの名前が使われていました。
一般的にはリバーシというのが、おせいろの一般名というようなね、ジェネリックですね、という風な考え方をされていたんですが、
現在ではリバーシとおせいろは実は別物じゃないかというようなことも言われていて、
あえてね、おせいろという表現をさせてもらいました。また論文のタイトルにもおせいろが入っていますので、
これはおせいろに限った話、おせいろとリバーシは違うゲームやという話で進めさせてもらっています。
おせいろの興味深さと功績
で、このおせいろなんですが、これ生まれがすごい興味深くて、またちょっと謎にも包まれています。
これ日本人の発明家、長谷川五郎さんが発明して、おせいろという名前をつけた、それをつくだオリジナルさんに売却して、現在はですね、メガハウスというメーカーさんの商標になっています。
メガハウスというと、Amazonなんかで調べてもらうとね、ルービックキューブの公式販売サイトをやったりもします。
おせいろなんですが、これはシェイクスピアのおせいろというね、劇局にちなんで名前をつけたそうなんですが、この長谷川五郎さんがもともとね、当時知られていたリバーシというゲームを元にちょっとアレンジしておせいろをつくったという説と、
ゼロから発明したという説と両方あってですね、ご本人が両方言ってあるんですね。なのでどっちが本当なのかというのはわからないんですが、そう考えて、そう言われてみるとリバーシとおせいろはそっくりなので、初期配置とかが若干違うぐらいなので、僕はリバーシの影響をだいぶ受けたんじゃないかなと思っています。
ただ、今回のね、おせいろイズソルブドという論文で、最前級を指し続けても引き分けるというのは、これもすごいことで、絶妙なバランスを組み上げた初期配置、それから数年の数、ルールの整備、そういう意味では長谷川五郎さんの功績もあったんではないかなと。
で、それのリスペクトも込みでおせいろは説かれたという論文のタイトルになったんじゃないかなというふうな感想も僕は持っています。
で、この長谷川五郎さんがなんでこのシェイクスピアのおせいろから名前をもらったのかというのは、白が黒になり黒が白になりというね、変わっていく様子から取ったのかもしれません。
おせいろ、シェイクスピアの方のおせいろ、これはね、シェイクスピア四大悲劇とも言われていまして、1602年やそうですね。
1602年、関ヶ原が1600年ですから、えらい昔ですよね。400年ちょい前ということなんですが、今でも読めるんですよ。
これね、改めて僕もおせいろの話を書かせていただくので、図書館で借りて読んでみました。
今でも読める、これすごいですよね。日本やったら1680年前後ですかね。
近松門左衛門の公職一代男というね、これも今漫画化されてるんですよ。
そういうふうに現代風にアレンジすると読めるというのはやっぱりプロットの力というのがね。
公職一代男はちょっと大人向けのちょっとアダルティーな内容ですが、これもまたね、面白く読めるという意味では、文学ってすごいな。400年読まれるってすごいですよね。
ちょっとなんかこう、憧れというかですね。いやーすごいなーっていう、もうちょっともう語彙力が全然なくて申し訳ないんですけれども、そんな感想を持ちました。
番組後半は自由に喋らせていただいたのですが、ここでね、また落ち着いた話し方に戻ろうかと思います。
15年おきに革命が起こるとしたら、次は2038年頃ということになりますかね。どんな革命が来ているんでしょうか。
ひょっとしたら量子コンピューティング、量子コンピューターというものが実用化されているかもしれません。
そうしたら将棋の解析なんかも終わっているのかもしれませんね。
今週も最後まで聞いてくださってありがとうございました。
今週はメイリンのインダスターズを聞きながらのお別れとなります。
最後にね、曲紹介しているのは僕、この曲を聴きながら次のポッドキャストとか過去のエピソードを探す時間が欲しくて、自分のためにやってるんですけれどもね。
お相手はsteam.fmのイチでした。良い週末をお迎えください。
次のポッドキャストを探しています。
次のポッドキャストを探しています。
次のポッドキャストを探しています。
次のポッドキャストを探しています。
次のポッドキャストを探しています。
次のポッドキャストを探しています。
次のポッドキャストを探しています。
次のポッドキャストを探しています。
次のポッドキャストを探しています。
次のポッドキャストを探しています。
次のポッドキャストを探しています。
次のポッドキャストを探しています。
次のポッドキャストを探しています。
次のポッドキャストを探しています。
次のポッドキャストを探しています。
次のポッドキャストを探しています。
次のポッドキャストを探しています。
次のポッドキャストを探しています。
次のポッドキャストを探しています。
次のポッドキャストを探しています。
次のポッドキャストを探しています。
次のポッドキャストを探しています。
