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

今朝起きたら、とんでもない論文を見つけました。 Othello is Solved ゲームの オセロが"解かれた(弱解決)" というのです。飛び起きました。それで、16時まで二度寝してから読みました。 注意すべきは、この論文が査読を経て公開されているわけではないこと、つまり形式上特にチェックを受けたものではないことです。ただ、タイトルからして非常に衝撃的ですので、個人的に読んでみました。この記事では、私がこの論文(およびソースコード)を読んでわかったことを、なるべくわかりやすくまとめます。随時更新します。 余談ですが、このタイトルはどうやら、チェッカーというゲームが以前弱解決された際の論文"Checkers Is Solved"のオマージュだろうという話です。 この記事には専門用語が出てくるので、最後の方に基礎知識として重要な用語や知識をまとめました。 お詫びと訂正 この記事の内容は、私が

[khtokage]

とてもわかりやすい、凄いなーと思ってたら学部2回生でビックリ、さらに3回目の2回生で二度ビックリしました笑

[shunkeen]

“今朝起きたら、とんでもない論文を見つけました。”／今朝起きたら、とんでもない解説記事を見つけました。

[unfallen_castle]

分かりやすくて面白かった。こういう野生の専門家の方が解説記事を書いてくれるのはありがたい

[lostnamer]

オセロは先手必勝の手筋だかが読み切られていたんじゃなかったっけ？とうろ覚えしていたが、弱解決(わざと悪手打たない限りは必ず引き分け、駒の除去が無いから千日手も起きない)に至るのか。

[ogijun]

むちゃくちゃアツい。解説から楽しさと悔しさがにじみ出る感じがいい

[Helfard]

オセロですら全部の組み合わせを力技で計算するとか無理なんだな。

[xlc]

80年代の「ASCIIマイクロセロリーグ」の頃は当時のPCで終盤20手読み切りだったような気がするので、随分深く読めるようになったんだな。

[ngsw]

この方もすごい

[mohno]

「オセロは長らく、引き分けが答えだろうと言われてきました」「分散メモリ環境で独立して探索できるタスクを非常に多く用意したこと」「私自身、オセロの弱解決の一番乗りを狙っていた経緯があり、正直悔しいです」

[pholxia]

オセロは後手必勝って得意になってひけらかしていました。（推定の正解を後から証明するってやり方応用できるとよいと思いました）

[call_me_nots]

ゲームの解決 田中哲朗 https://www.jstage.jst.go.jp/article/sugaku/65/1/65_0651093/_pdf/-char/ja

[shidho]

序盤で黒が選ばない「最善分岐」ってなんだろう？　/ 個人的には後手有利だと思ってた。研究的には20年前の常識だったのね。(じっさい20年前からアップデートしてない)

[sonots]

:eyes:

[altar]

αβ探索で全探索せずに「最善手」「悪手」を判断できる理由、あるいは弱解決に推測ベースの評価値(の上界)を使っていい理由がいまだによくわからない／相手に選択肢を与えるだけの下位互換の分岐を切るためかな

[mumei-0]

“注意すべきは、この論文が査読を経て公開されているわけではないこと、つまり形式上特にチェックを受けたものではないことです。”

[nekoluna]

なるほど。ドメイン知識って重要だな。　譜の解説もまあそうだよねって

[camellow]

オセロのように一手ごとにマスが減っていくようなゲームなら時間をかければ全パターンを探索してすべてが判明してるのかと思ってたわ。そんな事もなかったのね。

[ptolemychan]

学部2年生なのですね！！ 素晴らしい解説記事です。

[udofukui]

まじで何言ってるのかわからんくて、悲しみ。

[zakinco]

これは詳しい。

[currypurin]

解説ありがたい。

[rogertroutman]

ところで、量子コンピュータを使ったらこういう（天文学的な計算量を必要とする）問題もチャチャッと解決できちゃう感じなのでしょうか

[tiamointer]

“2年”

[azzr]

人間同士のオセロは終わってないけど、これでAIオセロは完成形か。五目並べから連珠ができたように、オセロもルールを変えて別な競技に発展したりするんだろうか？

[yarumato]

“オセロAI開発者。弱解決であるのが注意点。簡単に言えば、相手のどんな手にも厳密な最善で返せるが、自分がミスをした(悪手を打った)結果発生した局面について、厳密な最善手がどれなのかは求めていない”

[pekee-nuee-nuee]

スゴイ

[barlog]

うわ、そういうことか（うわべりかい）。

[softstone]

アルゴリズムの解説はなんとかついていけたのに、実際のリバーシ譜の解説になったとたん何も理解できなくなった。コンボス？ストナー（爆発）？中割り？ライン（切れ）？

[buhoho]

序盤、中盤、終盤、スキがないよね。

[richard_raw]

たった64マスでもなかなか読み切れないんですな。

[Akech_ergo]

たかだか６０手のゲームでも、完全解析はできていないのだな（60手の組み合わせが膨大なのはわかるが。）

[agrisearch]

「弱解決」

[odakaho]

“自分がミスをした(悪手を打った)結果発生した局面について、厳密な最善手がどれなのかは求めていない”

[nemoba]

序/中/終の分解は、それこそ収束問題ならゲーム限らず応用できそう。分かりやすい解説ですばらしい

[snow8-yuki]

盤面縦横範囲の切り分けじゃなくて残手数による切り分けか

[omega314]

なるほど、事前知識をそう使うのか。

[mazmot]

うん。わからん。けど、おもろい