タグ

アルゴリズムとHiroki Takizawaに関するmohnoのブックマーク (2)

  • オセロの必勝法が見つかった件 | やねうら王 公式サイト

    すごいニュースが飛び込んできた。オセロの必勝法が見つかったのだ。正確に言うとオセロが弱解決された。まずはその論文を紹介する。 Othello is Solved : https://arxiv.org/abs/2310.19387 「弱解決(weakly solved)」を簡単に言うと、初期局面からの双方最善手を打つ時の結論(勝敗)がわかったと言う意味である。8×8のオセロの結論は引き分けなのだそうだ。「必勝法が見つかった」と記事のタイトルで書いたが、その結果として双方最善を尽くした時のオセロの結論が引き分けだったことが判明したので正しくは「必勝法(必ず勝てる方法)が存在しないことが証明された」とでも言うべきか。 今回は、初期局面から到達できるあらゆる局面についての結論(勝敗)がわかったわけではない。こちらは「強解決(strongly solved)」と呼ばれる。 弱解決と強解決とでは、

    mohno
    mohno 2023/11/07
    AIじゃないだろ、というのは分かる。「今回、オセロの結論が引き分けだと判明したが、後手勝ちの局面数の方が圧倒的に多いはずで(昔から人間同士の対局だと後手の方が勝率が高い」←そういうことか。
  • Othello is Solved 論文解説 (私見) - Qiita

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

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