【論文】Othello is Solved(weakly solved)【オセロは引き分け】【弱解決】

なかなかびっくりするようなタイトルですが、

Othello is Solved
...

え?オセロが解かれたの?ついに60手(59手)完全読みか完全解析された!?

と思っちゃいますが、60手(59手)完全読みをしたという論文ではないようです。

※査読前の論文が沢山載ってるサイトらしいです。

arXivについて教えてください。
...

Google翻訳を参考にして読んでみました。

論文の概要

We developed an algorithm that requires predictive scores for all positions with 50 empty squares and returns a subset…

私たちは、50 個の空の正方形を持つすべてのポジションの予測スコアを要求し、サブセットを返すアルゴリズムを開発しました…

50個空きの局面の予測スコアが分かるアルゴリズムを開発

We implemented an algorithm 5 that requires a position with 50 empty squares and data about position(s) with 36 empty…

50 個の空の四角形を持つ位置と 36 個の空の四角形を持つ位置に関するデータを必要とするアルゴリズム 5 を実装しました…

50個空きと36個空きに関するデータを必要とする「アルゴリズム5」(1~4も当然ある)

We solved the positions with 36 empty squares which were obtained from the above algorithm 5, using a computer
cluster and Edax software…

上記のアルゴリズム 5 で得られた 36 個の空の正方形の位置をコンピューターを使用して解決しました。
クラスターと Edax ソフトウェア…

終盤36手はEdaxで完全読みしたのかな?

First of all, we enumerated and shortly evaluated the all positions with 50 empty squares. We only enumerated positions
with at least one legal move and considered symmetrical positions to be identical. As a result, 2,958,551 positions were
enumerated…

まず最初に、50 個の空きマスがあるすべてのポジションを列挙し、簡単に評価しました。ポジションを列挙しただけです 少なくとも 1 つの正当な手を伴い、対称的な位置は同一とみなされます。その結果、2,958,551 のポジションが獲得されました。 列挙した…

50個空きの局面を全部列挙したら、2,958,551通りあったわけですね。

Next, we selected 2,587 positions out of the aforementioned 2,958,551 positions and formulated hypotheses regarding…

次に、前述の 2,958,551 職種の中から 2,587 職種を選択し、以下の仮説を立てました…

で、2,958,551通りの局面のうち、2,587通りを選択しました、と。その2,587通りの終盤36手をEdaxで完全読みしたのかな?(50手読まなくていいのかな?)

We chose them such that if all these hypotheses were proven correct, it would prove that the initial
position results in a draw…

これらの仮説がすべて正しいことが証明されれば、最初の仮説が正しいことが証明されるように、それらを選択しました。
順位により引き分けとなります…

その2,587通りの選択方法なのですが、「その2,587通りが引き分けならオセロは引き分け」になるように選択した、という解釈で合ってるのかな?どうやって?というのがちょっと良く分からなくて「WTHORのデータべース」・・・うーん???

We conclude that our study has weakly solved Othello, although we recognize that our achievement is just above the
criteria of weakly solving…

私たちの研究はオセロを弱く解決したと結論付けていますが、私たちの達成度はわずかに上であると認識しています。
弱解法の基準…

これは「Discussion and Conclusions」に書いてあって、論文というのは「Results」~「Discussion and Conclusions」が「結局何を言ってるのか」と端的に分かる部分です。「weakly solved」(弱く解決された)と主張しているわけですね。

つまり、タイトルにはweaklyとは書いてなかったけど、ある程度読めば「Othello is (weakly) Solved」と分かるという仕組み。

※追記:
ゲームの理論で、「弱解決」という概念があるようです。論文の筆者は、「弱解決」できたと主張しています。つまり、初期盤面の勝敗は引き分けで確定した、という論文です。

初期盤面の勝敗のみがわかることを超弱解決、初期盤面の勝敗がわかっていてそれを証明するのに必要な各局面の最善手もわかることを弱解決、すべての局面について勝敗も最善手もわかることを強解決と呼んで区別することもあります。

ゲームを解く!Educational DP Contest K, L 問題の解説 - Qiita
...

私の意見

オセロ界隈でEdax等のソフトを触って解析していた人が最低何十人かはいて、「引き分けだよな」「引き分けだよね」「引き分けっすね」・・・と、最近10年か20年くらいの間に、「引き分けだよね」という雰囲気が濃くなって行ったように感じています。

特にEdaxは、book(定石)を育てて行くと、引き分けの手順(その手順で打てば、終盤解析すれば引き分けになる)がどんどん分かって来て、「初手から相手がどう打っても勝ち(相手は負け)」という手順はみつからなくて、「あー、これはその前の段階でここに打てば引き分け」と・・・そんな感じで、私などは、「双方最善を尽くせばオセロは99.999999%引き分け」くらいに思っています(桁は適当ですが、昔なら「99.9%」と言ってたところを、桁を増やしました)

そういう、オセロ界隈の(多分)多くの人が持っていた感覚を、論文にしてちゃんと発表していただけた、と思います。

※そうじゃなくて数学的にもう完全読みと全く同じなんだよ、という話であれば、私の論文解釈の誤りです。

追記:私の論文解釈の誤りでした。論文筆者は「弱解決」したと主張していて、それだと、「オセロは初期盤面から双方最善で引き分けで確定して、それを証明するのに必要な各局面の最善手もわかる」という意味です。

私だったら、50個空きの2,958,551通りの局面のうち、まず1つを完全読みしてみたいところです。家庭用PCだと、50手完全読みはできるのかどうかに疑問符が付く段階で、もしかしたら世界で何人かは、何ヵ月とか何年もかけて達成した?うーん、どうかなという感じです。

40手改善読みは前にシングルスレッドで1ヵ月以上くらいかかったことがあって、今なら32スレッドとか普通にあって、シングルコア性能も上がたので、数時間~1日で終わるのかな?という感じ(やってみることも可能)

その辺が家庭用PCの常識的な限界で、50手だと1000倍の時間がかかるかな?(合ってるかどうかは知らない)と考えても、1時間→1000時間(42日)、1日→1000日で、そろそろ家庭用PCでは非常識な時間になってしまいます。これが1000倍でなく100万倍だったりすると、もうお手上げです。

スーパーコンピュータを使えるのであれば、実際に40手完全読み→42手→44手→・・・とやって時間を計ってみれば、50手完全読みが可能かどうか大体想像がつくと思います。

追記:もっと良く分かってそうな方の詳しい解説はこちら

Othello is Solved 論文解説 (私見) - Qiita
...

私は、これで「弱解決」になる…というのはどうしてなのかな?というのを、もう少し勉強しなければならないようです。

コメント

  1. 論文を読みましたが、著者の主張としては「双方最善を尽くせば100%引き分け」です。
    weakly solvedというのは(ややこしいことに)専門用語なので「解析が不完全で穴があるかもしれない」という意味ではありません

  2. もう少し調べたところ、ゲームの理論で「弱解決」という概念があって、それを証明した(つまり初期盤面で引き分けなのが確定した)という話のようですね。「弱解決」という概念をほぼ考えたことがなくて、この内容で証明したことになる…というのを理解するため、私はもっと勉強する必要がありそうです。

タイトルとURLをコピーしました