すごいニュースが飛び込んできた。オセロの必勝法が見つかったのだ。正確に言うとオセロが弱解決された。まずはその論文を紹介する。

Othello is Solved : https://arxiv.org/abs/2310.19387

「弱解決(weakly solved)」を簡単に言うと、初期局面からの双方最善手を打つ時の結論(勝敗)がわかったと言う意味である。8×8のオセロの結論は引き分けなのだそうだ。「必勝法が見つかった」と本記事のタイトルで書いたが、その結果として双方最善を尽くした時のオセロの結論が引き分けだったことが判明したので正しくは「必勝法(必ず勝てる方法)が存在しないことが証明された」とでも言うべきか。

今回は、初期局面から到達できるあらゆる局面についての結論(勝敗)がわかったわけではない。こちらは「強解決(strongly solved)」と呼ばれる。

弱解決と強解決とでは、必要となる局面数が桁違いである。詳しくは、にゃにゃんさんの記事を見て欲しい。

Othello is Solved 論文解説 (私見) : https://qiita.com/Nyanyan_Cube/items/a373da3157cdd117afcc

このブログでこのアルゴリズム的な解説をしようかと思ったのだが、にゃにゃんさんが上の記事でだいたい書いているので、私のほうは、上の記事に書いてないことだけいくつか補足的に書いていくことにする。

まず、この論文の著者は、PFN(Preferred Networks社)に勤務している人なのだが、PFNの20%ルール(勤務時間の20%の時間を好きな研究をして良いというルール。おそらくGoogleの同ルールを取り入れたもの)で行った研究なのだそうだ。言わば、(業務の)片手間でオセロの必勝法を解明してしまったと言うわけだ。「あれ？ボクなんかやっちゃいました？ｗｗｗ」どころの騒ぎではない。

また、今回、オセロの結論は引き分けだと判明したわけだが、このこと自体はオセロ愛好家の中では、以前から半ば常識となっていた。オセロの序盤は、それほど手が広いわけでもなく、また、残り36升ぐらいの局面からは時間をかければEdax(オセロAI)で完全に読み切れていたので、オセロ愛好家はこの結論を知っていたわけである。とは言え、そのすべての変化を人間が覚えきれるものではないので、結論だけ知っていても実戦でほとんど何の役にも立たないわけだが…。

あと、(強解決ではなく)「弱解決」であれば、計算量はかなり減って現実的な計算オーダーになることは私も気づいていた。

この件について、私は5年前にツイートしている。

6×6のオセロの完全解析はいまどきのPCなら100時間かからずに行える。8×8の完全解析は、(合法局面数の比からすると)その10^12倍程度の計算時間が必要だが、AWSのスポットインスタンスを借りるとして、(色々工夫すれば)1000万円程度に収まると思う。これクラウドファンディングでお金集まらんかな…。

— やねうら王 (@yaneuraou) August 20, 2018

ただ、厳密な解を得るために探索する必要である局面の数が、以前の研究(※)で予測された数よりもはるかに少なかったことは本論文の著者には予想外であったようだ。

※　L. V. Allis. Searching for Solutions in Games and Artificial Intelligence. PhD thesis, Department of Computer Science, University of Limburg, 1994.

また、今回の論文のインパクトは大変大きいので、AI界隈の人たちがかなりツイッター(X)で言及してたりするのだが、αβ探索なんてAI界隈の人たちは普段使ってなくて(彼らはDeep Learningばかりやっているから)、拡散力の大きなアカウントからのかなり誤解を招くツイートも散見される。

内容的に誤ったツイートの例と何故それが間違いなのかを説明しておく。

オセロで「完璧な手を打ち続けた結果は引き分けである」ことを証明する研究が発表されました。
AI研究の長年にわたる課題の一部解決であり、ゲーム理論の分野における進展を示しています。
ただし、本発表の解釈にあたっては注意点があります。… pic.twitter.com/jxTOuRYt21

— AIDB (@ai_database) November 5, 2023

この人⇑は、「弱解決」を正しく理解できていない。

最終的な局面だけが証明されているのではなく、相手がどう打っても引き分けに持ち込める作戦までは求まっている。(EdaxというオセロAIで36升空きの局面から読み切った部分は、その読み筋までは残ってないかも知れないが)

この⇓ツイートもわりとバズっている。

某オセロ論文の弱解決証明は不完全（近似的）だと思う

まず、恣意的な閾値によるalpha-beta刈り込みを行っているので、探索に漏れがないという保証がない（Sec.3.4~3.5）。
それと、任意のデータセットで反例が観測されなかったことは、仮説の正しさを確率的にしか示さない（Sec.4.1）。

— Kyo (@kyo_takano) November 5, 2023

この人⇑は、alpha-beta探索を誤解している。(と思う)

naiveなalpha-beta探索は、minimax探索と同じ探索結果になることは保証されている。だから、「枝刈りをやっているゆえに漏れがないという保証がない」という主張の仕方はおかしい。結果がminimax探索の結果と変わらないような安全な枝刈り(naiveなalpha-beta探索の枝刈りはそう)であれば枝刈りしても良いのだから。

「恣意的な閾値」(すなわちaspiration windowと呼ばれるwindowを設定した)alpha-beta探索の場合、fail low/fail highにならなければ、それは探索中に安全な枝刈りしかしなかったということを意味しているので、aspiration windowなしの、すなわち区間alpha = -∞ , beta = +∞ の普通のalpha-beta探索の結果と同じであり、それはすなわちminimax探索の結果と変わらないことが保証される。(はず)

このへん、にゃにゃんさんがわかりやすい解説を書いてくれることを期待しつつ、このあたりで筆を置くのであった。(何か間違ったこと書いてたら、コメント欄で教えて)

[2023/11/06 23:00追記]

「弱解決」についてすごく良い資料を教えてもらったので、ぺたぺた。

資料 田中哲朗、ゲームの解決、「数学」65巻1号(2013) (PDF注意) https://www.jstage.jst.go.jp/article/sugaku/65/1/65_0651093/_pdf/-char/ja

[2023/11/06 23:10追記]

今回、オセロの結論が引き分けだと判明したが、後手勝ちの局面数の方が圧倒的に多いはずで(昔から人間同士の対局だと後手の方が勝率が高い)、6×6のオセロが後手必勝であることが証明されていたことからも、8×8も後手が必勝だと予測していた人がたくさんおられた。確かに最善を尽くせば引き分けではあるものの、(人間同士だと)最善を尽くせないから後手有利だとは言えるのかも知れない。