パスワードを忘れた? アカウント作成
17651115 story
ゲーム

オセロが解決されたとする論文 69

ストーリー by nagazou
証明 部門より
nakka-man 曰く、

オセロが解決されたとする論文が出たようだ。arXiv
全ての手を解析した訳ではなく、双方のプレイヤーが最善手を打つと引き分けになることを証明したらしい。
arXivに掲載されている論文は査読前なのでまだマユツバだが、マイルストーンになると良いですね。

オセロゲームには「10の58乗通り」の棋譜と「10の28乗通り」の局面があり、未だに計算機的に解決されていない複雑なゲームなのだそう。プリファードネットワークスのHiroki Takizawa氏は、オセロが両プレイヤーが完璧にプレイした場合に引き分けになることが計算上証明されたとする論文を発表した。研究では証明をおこなうために、大規模なデータセットを使用、2587の仮説が正しいことが証明されたと述べられている。論文ではオセロゲームを解き明かすことは、コンピュータ・サイエンス分野における壮大な挑戦の一つであるとしている(arXiv/a>、 論文[PDF])。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • 引き分け (スコア:3, おもしろおかしい)

    by Anonymous Coward on 2023年11月09日 19時41分 (#4561300)

    オセロなのに白黒つけられないじゃないか!

    • by Anonymous Coward

      あなたが白とか黒とか思っているものは、白っぽいグレーと黒っぽいグレーです

      • by Anonymous Coward

        で、笑うポイントはどこなの?

        • by Anonymous Coward

          理解できないならムリしてわかろうとせんでもええんやで

    • by Anonymous Coward

      囲碁「待たせたな」

  • 25年くらい前、Mac用のフリーゲームに「マクベス」というソフトがあった。
    RPGのマップのように、オセロの盤面の上下左右の端が繋がっているというルール。あの頃はまだ小さかったのでよくわからず触れていたけど、あれはゲーム性としてどうだったんだろうか。
    類似のゲームを他に見たことないというのが答えなのだろうか。
    とりあえず、ネーミングセンスが好き。

    • 角や端が存在しなくなるので盤上のマス目はほぼ等価になる、
      ループの認識しづらさから思わぬ石(駒?)もひっくり返ることが起きやすい(ひっくり返しの見落としが発生しやすくなるためコンピュータに任せないとしんどい)

      ルール面での問題は、たとえば横一列に黒が7つ並んでいる時に残りの1マスに白を置くとどうなる?
      A. 黒の列の両端に白があることになるから横一列全部白になる
      B. 両端の白は同じものだから「挟んでいる」とは言えないから横一列の黒はひっくり返らない
      のどちらにするか決める必要があるな。

      --
      うじゃうじゃ
      親コメント
  • この手の完全情報ゲームは、ほとんどのケースで先手番有利になる。そして、上級者になればなるほど先手番有利の差が広がっていく。
    おそらく、全パターンを完全網羅してしまえば、チェスも将棋も先手番の勝率が100%になる可能性が高い。

    しかし、オセロの場合、へた同士だと後手番の方が勝率が高くて、上級者になればなるほど勝率が50:50に近づいていくらしい。
    今回の件が正しいとすると、突き詰めれば完全互角であると証明されたということになる。
    これは、ある種の奇跡と言えるのでは。

    --
    しもべは投稿を求める →スッポン放送局がくいつく →バンブラの新作が発売される
    • by Anonymous Coward on 2023年11月09日 22時04分 (#4561380)

      オセロの初手はどこに置いても同じなので、後手は実質的に先手ですよ

      親コメント
      • by Anonymous Coward

        は?
        # モデレータも良く考えてからにしてよ。

        • by Anonymous Coward on 2023年11月10日 9時43分 (#4561534)

          オセロは相手の石を挟むマスがある場合必ず石を必ず打つ(離れたマスへの空打ちや任意パスはNG)ルールがあるので

          ○●
          ●○
          この初手の状態から石を打てる場所は線対称・点対称を考えると実質すべて同じになる、というのは理解できるかね

          親コメント
        • by Anonymous Coward

          は?
          対称性を考えたら、初手はどこでも実質一緒でしょ。
          # モデレータはいい仕事してる。

      • by Anonymous Coward

        先手がどこに置いても対称性を考慮すれば一緒なので
        置く位置についての選択肢を最初に得るのは後手だというのは理解した

        でも「後手が実質的に先手である」という考え方を採用すると
        ゲームスタート時のコマの数が違うことになる

        #4561357は暗黙の前提として「ゲームスタート時のコマの配置が同じであれば」先手が有利とか引き分けになるという話をしていると思うのだけど
        そこにコメントをぶら下げて「後手は実質的に先手」というのはどうなの?

        • by Anonymous Coward

          まずは君の考える「暗黙の前提」とやらを全部書き出してみて。
          何を言っても後出しで条件付け加えてくる人の相手は誰もしてくれないよ。

    • ちなみにだけど、「オセロが奇跡のゲーム」ってのは私が言い出した話ではないです。

      こちら、2017年の記事
      人間VSコンピュータオセロ 衝撃の6戦全敗から20年、元世界チャンピオン村上健さんに聞いた「負けた後に見えてきたもの」 [itmedia.co.jp]

      ――世界チャンピオンを3度獲得した、村上さんが思う「オセロの魅力」とは?

      (中略)

      オセロは発明されたときから完成されたゲームです。囲碁将棋は長い歴史の中でマイナーチェンジを繰り返していますが、オセロは発明されてから一切ルールが変わっていません。ルールは簡単、尽きない奥深さ面白さがあって、しかも(先手の)黒と(後手の)白の勝率はほぼ互角。私は「奇跡のゲーム」だと思っています。

      このインタビュー記事には、オセロというゲームが持つ特徴だとか、もしオセロが完全解析されたらどうなるか、という事についても語られているので、今回の記事と合わせて読むとなかなか面白いと思いますよ。

      --
      しもべは投稿を求める →スッポン放送局がくいつく →バンブラの新作が発売される
      親コメント
    • by Anonymous Coward on 2023年11月09日 21時56分 (#4561375)

      他のコメントに既にあるけど、完全解析されたもので先手必勝が多いとは言えないです。
      サイズの小さいリバーシ(オセロ)は後手必勝だし、チェッカーは引き分け。

      チェスも将棋も人間のレベルでは先手番が有利ですが、強いAIでは引き分けが多くなっていきます。
      一昔前は完全解析の結果は先手勝ちだろうという意見で一致してましたが、今は引き分けかもしれないという意見もそこそこあります。

      親コメント
      • by Anonymous Coward

        完全解析したら引き分けだったからコミ6目半が廃止されたら人間の囲碁対局は先手取るゲームになりそうだな

    • by Anonymous Coward

      オセロは4x4も6x6も後手必勝だったし後手有利だと言われてたけどね。今回最善を尽くせば引き分けになることが証明されたけど、最善を尽くせない人間同士の対局ならやっぱり後手が有利らしい

      • by Anonymous Coward

        囲碁みたいに、先手に一目半とか半目の下駄を履かせたら、公平で引き分けのないゲームになる?

    • by Anonymous Coward

      3目並べも奇跡のゲームですか?

      • by Anonymous Coward

        核戦争を未然に防いだし、奇跡で良いのでは?

        # [映] WarGames (1983)

    • by Anonymous Coward

      昔聞いた話では、最後の石を置くことができる後手(初期配置からパスなしで進めばそうなる)が有利そうということだった。
      4x4、6x6が後手必勝(解明済)、8x8が引き分けとなると、より大きな盤面でも引き分けなのだろうか。

    • by Anonymous Coward

      すごい。
      最初から最後まで全部間違ってる。
      これは、ある種の奇跡と言えるのでは。

  • by Anonymous Coward on 2023年11月09日 19時00分 (#4561275)

    https://qiita.com/Nyanyan_Cube/items/a373da3157cdd117afcc [qiita.com]
    https://yaneuraou.yaneu.com/2023/11/06/the-surefire-winning-strategy-f... [yaneu.com]
    最近のAIはディープラーニングばかりですっかり影が薄くなったアルファ-ベータ法だけど、厳密さが必要な場面では威力を発揮するな

    • by Anonymous Coward

      α-β法はAIじゃないだろ

      • by Anonymous Coward

        もう、それっぽいのはAIだよ。
        エキスパートシステムも、ニューロファジー制御もぜーんぶAI。

        • by Anonymous Coward

          もうっていうか前世紀から「人工知能」というタイトルの大学講義や教科書の定番ネタでしょ

    • by Anonymous Coward

      これ読まないと「2587の仮説が正しい」とかいうnagazouの意味不明な供述の意味がわからんな。2,587は10手打った段階での調べるべき局面数。総局面数は2,958,551だが、弱解決なのでα-βカットによりわずか1000分の1以下を調べるだけで済むなど大幅に高速化できた。残り99.9%はコンピューターがわざと最適でない手を打たないと到達し得ない局面

  • by Anonymous Coward on 2023年11月09日 18時26分 (#4561254)

    ここが開発したとかいう人工知能専用ハードはいつになったらものになるんだろう…
    対内直接投資でものすごい資金調達してるから国内には出回らなそうではあるが…

    • by Anonymous Coward on 2023年11月09日 22時38分 (#4561394)

      > ここが開発したとかいう人工知能専用ハードはいつになったらものになるんだろう…

      MN-Core は2022年初め頃には実用が始まっていて
      今では自社でバリバリ使ってるのでは。
      今回のこのオセロの論文でも使ってるって書いてあるし。

      特殊なハードだから市販はしない気がしますが、
      パートナー企業になれば外部からの利用も可能になってるそうで。
      https://xtech.nikkei.com/atcl/nxt/column/18/00001/07509/ [nikkei.com]

      親コメント
    • by Anonymous Coward

      本文に書いてあるのになんで社名伏せたの?

  • by Anonymous Coward on 2023年11月09日 18時39分 (#4561260)

    完璧に打つAI相手の勝負では、人間は絶対に勝てないってことか。

    • by Anonymous Coward

      どんなに頑張っても引き分けにしかならないですね

      映画ウォー・ゲームでは最後三目並べに勝者がいないことを悟ったコンピューターがチェスをやろうと持ち掛けるが、チェス、将棋、囲碁だとどうなるのだろうか?
      一応ルール上は全部引き分けのパターンがあるみたいですが

      • by Anonymous Coward

        人間が最善ではない手も含めて打った時にそれでも勝てない証明はされてないのでは?

        • by Anonymous Crow (45505) on 2023年11月10日 8時54分 (#4561509)

          >人間が最善ではない手も含めて打った時にそれでも勝てない証明はされてないのでは?

          両者最善手を打つ場合(弱解決)、片方だけが最善手を打つ場合、共に考慮しているようです
          (両者が最善手を打たない場合は考慮されていない(強解決))

          (今回の論文の概略)
          https://gigazine.net/news/20231106-othello-is-solved/ [gigazine.net]
          https://yaneuraou.yaneu.com/2023/11/06/the-surefire-winning-strategy-f... [yaneu.com]

          (今回の論文の解説)
          https://qiita.com/Nyanyan_Cube/items/a373da3157cdd117afcc [qiita.com]

          (弱解決について)
          https://www.jstage.jst.go.jp/article/sugaku/65/1/65_0651093/_pdf/-char/ja [jst.go.jp]

          >最初の10手の進行について既存のプレイヤーの知識を元にあらかじめ評価値を与えたりすることで計算量を減らし

          最初の10手(実質11手?)は人力評価という事でしょうかね?

          フリーのAIオセロソフトでも32手目以降は完全読み切りするそうなので
          半分打ったところで勝敗が分かってしまうようです
          https://www.egaroucid.nyanyan.dev/ja/usage/ [nyanyan.dev]


          個人的に凄いと思ったのは、会社の20%ルール(20%の時間は好きな研究していいよ)の中で出した成果、だという事でしょうか

          親コメント
          • Re:ということは (スコア:2, 参考になる)

            by Anonymous Coward on 2023年11月10日 9時04分 (#4561514)

            1. 最初の10手をまず既存のオセロソフト(を改造したもの)の評価関数で見積もる。
            2. 残り50手を完全読みする(実際にはさらに14手-36手に分割してこの手順を再帰的に適用するようなことをしてるけど省略)
            3. 完全読みした評価値と1.の評価値が一致していたので(弱)解決
            4. もし一致していなかったら、完全読みした評価値をメモ化して改善された評価関数で1.からの手順を繰り返す

            最初から完全読みするのと何が違うのかと言うと、1.で評価しなかった局面(99.9%)については2.の完全読みをしなくて済むので計算量が大幅に節約できる。評価しなかった局面の評価値が違っていても結果に影響がないことはα-β法の原理により保証されている。

            親コメント
          • by Anonymous Coward

            両者最善手を打つ場合(弱解決)

            違う。初手以降、先手or後手が常に最善手を打ち続けた場合に結果が定まるのが弱解決。相手が最善手かどうかは関係ない。
            両者が最善手のときだけ結果が分かっている場合は超弱解決という。

            (両者が最善手を打たない場合は考慮されていない(強解決))

            これも違う。ゲーム上に現れうる全ての局面をスタート地点として、その後の先手後手どちらかが最善手を打ち続けた場合の結果がわかることを強解決という。

        • by Anonymous Coward

          文中の「両プレイヤーが完璧に〜」が誤解を招きやすいですが
          相手がミスをした時に正しく最善手を打てば負けない(勝ちか引き分け)、まで含みますよ
          (相手がミスをしなければ引き分けのみで、最善手を打ち続けても勝てない)

          • by Anonymous Coward

            >全ての手を解析した訳ではなく
            全ての手を解析していないのに最善手と言えるのか?
            最善手以外の手の優劣の順位を全部読み切ったわけでは無いけど、最善手が1番であることは証明できるということか?

            ※かつてのコンピュータ将棋プログラムで、
            「この手(簡単に咎められる手なので普通は差されない手)の対応は実装してないので指さないでください」というのが有って、
            でも対局したプロ棋士はしっかりとその手を指して勝ちをもぎとってた気がする。

            • by Anonymous Coward

              > 全ての手を解析していないのに最善手と言えるのか?

              自分の手番で「この手を打てば必勝」って確定してる時に、「でも自分が他の手を打っても勝てるだろうか」ってのは調べなくてもいいですよね
              なので全ての手を読む必要はないです

              > ※かつてのコンピュータ将棋プログラムで

              将棋は結構ルールが複雑ですし、オセロやチェスと違って終局が近づいてもプレイヤーの選択肢が狭まっていかないので、単純に比較できないです
              それに大会では「実装してない手があるけど、指されなければ負けない」でも勝負を挑めますけど、論文でそれは通らないでしょう

              • by Anonymous Coward on 2023年11月10日 12時34分 (#4561642)

                >自分の手番で「この手を打てば必勝」って確定してる時に

                勝ち負けだけを調べたい場合は、最大の差が付く最高の勝ち筋を読む必要はないので探索しきる必要もないわけですね。「少なくとも2目差で勝てる勝ち筋は見つけた(他の手を指せばもっと差を付けられるかもしれないが、再帰的に同じ議論でそれは探索していない)」と。

                でも、「勝ち筋を1個見つけた」なら良いんですが「引き分けにできる手を見つけた」の場合は、まだ未発見の勝ち筋が残ってる可能性が潰せてなさそうな。…ってああ! だから、先手、後手両方で試した、に繋がるわけですか。

                ・先手は確実に引き分けに持ち込める。なおそれが最善手かは不明。検討をすっ飛ばした手まで全て検討できれば必勝になる可能性もある
                ・後手は確実に引き分けに持ち込める。なおそれが最善手かは不明。検討をすっ飛ばした手まで全て検討できれば必勝になる可能性もある

                を両方とも独立に証明しておいて、その2つを組み合わせることで、

                ・先手後手共に引き分けが最善手

                と結論づけられた、と。

                もし、先手より後手の検討の方が無茶苦茶に重たくなるようなゲームだったとすると、後手が勝てないことまでは証明出来た、という途中段階で一端結論という展開もあり得るわけですね。

                親コメント
  • by Anonymous Coward on 2023年11月09日 20時11分 (#4561320)

    「人間が遊ぶのでなければ」オセロはひどくつまらないゲームだ。「引き分け」も予想されていたから結論もつまらない。「リーマン予想の解決への糸口があった」とかいうわけでもない。
    つまらなくないのは研究手法やそこから得られる洞察のほうだ。だから素人が口を挟むのは純粋な時間の無駄だ。

  • by Anonymous Coward on 2023年11月10日 1時44分 (#4561451)

    たいとるおんりー

typodupeerror

身近な人の偉大さは半減する -- あるアレゲ人

読み込み中...