オセロが解決されたとする論文 69
ストーリー by nagazou
証明 部門より
証明 部門より
nakka-man 曰く、
オセロが解決されたとする論文が出たようだ。arXiv
全ての手を解析した訳ではなく、双方のプレイヤーが最善手を打つと引き分けになることを証明したらしい。
arXivに掲載されている論文は査読前なのでまだマユツバだが、マイルストーンになると良いですね。
オセロゲームには「10の58乗通り」の棋譜と「10の28乗通り」の局面があり、未だに計算機的に解決されていない複雑なゲームなのだそう。プリファードネットワークスのHiroki Takizawa氏は、オセロが両プレイヤーが完璧にプレイした場合に引き分けになることが計算上証明されたとする論文を発表した。研究では証明をおこなうために、大規模なデータセットを使用、2587の仮説が正しいことが証明されたと述べられている。論文ではオセロゲームを解き明かすことは、コンピュータ・サイエンス分野における壮大な挑戦の一つであるとしている（arXiv/a>、 論文[PDF]）。
引き分け (スコア:3, おもしろおかしい)
オセロなのに白黒つけられないじゃないか！
Re: (スコア:0)
あなたが白とか黒とか思っているものは、白っぽいグレーと黒っぽいグレーです
Re: (スコア:0)
で、笑うポイントはどこなの？
Re: (スコア:0)
理解できないならムリしてわかろうとせんでもええんやで
Re: (スコア:0)
囲碁「待たせたな」
もし盤面がドラクエ式だった場合は (スコア:3)
25年くらい前、Mac用のフリーゲームに「マクベス」というソフトがあった。
RPGのマップのように、オセロの盤面の上下左右の端が繋がっているというルール。あの頃はまだ小さかったのでよくわからず触れていたけど、あれはゲーム性としてどうだったんだろうか。
類似のゲームを他に見たことないというのが答えなのだろうか。
とりあえず、ネーミングセンスが好き。
Re:もし盤面がドラクエ式だった場合は (スコア:1)
角や端が存在しなくなるので盤上のマス目はほぼ等価になる、
ループの認識しづらさから思わぬ石(駒?)もひっくり返ることが起きやすい(ひっくり返しの見落としが発生しやすくなるためコンピュータに任せないとしんどい)
ルール面での問題は、たとえば横一列に黒が7つ並んでいる時に残りの1マスに白を置くとどうなる？
A. 黒の列の両端に白があることになるから横一列全部白になる
B. 両端の白は同じものだから「挟んでいる」とは言えないから横一列の黒はひっくり返らない
のどちらにするか決める必要があるな。
うじゃうじゃ
オセロが奇跡のゲームであることが証明されたな (スコア:2)
この手の完全情報ゲームは、ほとんどのケースで先手番有利になる。そして、上級者になればなるほど先手番有利の差が広がっていく。
おそらく、全パターンを完全網羅してしまえば、チェスも将棋も先手番の勝率が100％になる可能性が高い。
しかし、オセロの場合、へた同士だと後手番の方が勝率が高くて、上級者になればなるほど勝率が50:50に近づいていくらしい。
今回の件が正しいとすると、突き詰めれば完全互角であると証明されたということになる。
これは、ある種の奇跡と言えるのでは。
しもべは投稿を求める →スッポン放送局がくいつく →バンブラの新作が発売される
Re:オセロが奇跡のゲームであることが証明されたな (スコア:5, すばらしい洞察)
オセロの初手はどこに置いても同じなので、後手は実質的に先手ですよ
Re: (スコア:0)
は？
# モデレータも良く考えてからにしてよ。
Re:オセロが奇跡のゲームであることが証明されたな (スコア:2, 参考になる)
オセロは相手の石を挟むマスがある場合必ず石を必ず打つ（離れたマスへの空打ちや任意パスはＮＧ）ルールがあるので
○●
●○
この初手の状態から石を打てる場所は線対称・点対称を考えると実質すべて同じになる、というのは理解できるかね
Re: (スコア:0)
は？
対称性を考えたら、初手はどこでも実質一緒でしょ。
# モデレータはいい仕事してる。
Re: (スコア:0)
先手がどこに置いても対称性を考慮すれば一緒なので
置く位置についての選択肢を最初に得るのは後手だというのは理解した
でも「後手が実質的に先手である」という考え方を採用すると
ゲームスタート時のコマの数が違うことになる
#4561357は暗黙の前提として「ゲームスタート時のコマの配置が同じであれば」先手が有利とか引き分けになるという話をしていると思うのだけど
そこにコメントをぶら下げて「後手は実質的に先手」というのはどうなの？
Re: (スコア:0)
まずは君の考える「暗黙の前提」とやらを全部書き出してみて。
何を言っても後出しで条件付け加えてくる人の相手は誰もしてくれないよ。
Re:オセロが奇跡のゲームであることが証明されたな (スコア:4, 参考になる)
ちなみにだけど、「オセロが奇跡のゲーム」ってのは私が言い出した話ではないです。
こちら、2017年の記事
人間VSコンピュータオセロ 衝撃の6戦全敗から20年、元世界チャンピオン村上健さんに聞いた「負けた後に見えてきたもの」 [itmedia.co.jp]
このインタビュー記事には、オセロというゲームが持つ特徴だとか、もしオセロが完全解析されたらどうなるか、という事についても語られているので、今回の記事と合わせて読むとなかなか面白いと思いますよ。
しもべは投稿を求める →スッポン放送局がくいつく →バンブラの新作が発売される
Re:オセロが奇跡のゲームであることが証明されたな (スコア:1)
他のコメントに既にあるけど、完全解析されたもので先手必勝が多いとは言えないです。
サイズの小さいリバーシ（オセロ）は後手必勝だし、チェッカーは引き分け。
チェスも将棋も人間のレベルでは先手番が有利ですが、強いAIでは引き分けが多くなっていきます。
一昔前は完全解析の結果は先手勝ちだろうという意見で一致してましたが、今は引き分けかもしれないという意見もそこそこあります。
Re: (スコア:0)
完全解析したら引き分けだったからコミ6目半が廃止されたら人間の囲碁対局は先手取るゲームになりそうだな
Re: (スコア:0)
オセロは4x4も6x6も後手必勝だったし後手有利だと言われてたけどね。今回最善を尽くせば引き分けになることが証明されたけど、最善を尽くせない人間同士の対局ならやっぱり後手が有利らしい
Re: (スコア:0)
囲碁みたいに、先手に一目半とか半目の下駄を履かせたら、公平で引き分けのないゲームになる？
Re: (スコア:0)
３目並べも奇跡のゲームですか？
Re: (スコア:0)
核戦争を未然に防いだし、奇跡で良いのでは?
# [映] WarGames (1983)
Re: (スコア:0)
昔聞いた話では、最後の石を置くことができる後手（初期配置からパスなしで進めばそうなる）が有利そうということだった。
4x4、6x6が後手必勝（解明済）、8x8が引き分けとなると、より大きな盤面でも引き分けなのだろうか。
Re: (スコア:0)
すごい。
最初から最後まで全部間違ってる。
これは、ある種の奇跡と言えるのでは。
オセロAI作者の解説 (スコア:1)
https://qiita.com/Nyanyan_Cube/items/a373da3157cdd117afcc [qiita.com]
https://yaneuraou.yaneu.com/2023/11/06/the-surefire-winning-strategy-f... [yaneu.com]
最近のAIはディープラーニングばかりですっかり影が薄くなったアルファ-ベータ法だけど、厳密さが必要な場面では威力を発揮するな
Re: (スコア:0)
α-β法はAIじゃないだろ
Re: (スコア:0)
もう、それっぽいのはAIだよ。
エキスパートシステムも、ニューロファジー制御もぜーんぶAI。
Re: (スコア:0)
もうっていうか前世紀から「人工知能」というタイトルの大学講義や教科書の定番ネタでしょ
Re: (スコア:0)
これ読まないと「2587の仮説が正しい」とかいうnagazouの意味不明な供述の意味がわからんな。2,587は10手打った段階での調べるべき局面数。総局面数は2,958,551だが、弱解決なのでα-βカットによりわずか1000分の1以下を調べるだけで済むなど大幅に高速化できた。残り99.9%はコンピューターがわざと最適でない手を打たないと到達し得ない局面
P社 (スコア:0)
ここが開発したとかいう人工知能専用ハードはいつになったらものになるんだろう…
対内直接投資でものすごい資金調達してるから国内には出回らなそうではあるが…
Re:P社 (スコア:1)
> ここが開発したとかいう人工知能専用ハードはいつになったらものになるんだろう…
MN-Core は2022年初め頃には実用が始まっていて
今では自社でバリバリ使ってるのでは。
今回のこのオセロの論文でも使ってるって書いてあるし。
特殊なハードだから市販はしない気がしますが、
パートナー企業になれば外部からの利用も可能になってるそうで。
https://xtech.nikkei.com/atcl/nxt/column/18/00001/07509/ [nikkei.com]
Re: (スコア:0)
本文に書いてあるのになんで社名伏せたの？
Re:P社 (スコア:1)
MNでP社とかいうとパナソニックに見える…
ということは (スコア:0)
完璧に打つAI相手の勝負では、人間は絶対に勝てないってことか。
Re: (スコア:0)
どんなに頑張っても引き分けにしかならないですね
映画ウォー・ゲームでは最後三目並べに勝者がいないことを悟ったコンピューターがチェスをやろうと持ち掛けるが、チェス、将棋、囲碁だとどうなるのだろうか?
一応ルール上は全部引き分けのパターンがあるみたいですが
Re: (スコア:0)
人間が最善ではない手も含めて打った時にそれでも勝てない証明はされてないのでは？
Re:ということは (スコア:3, 興味深い)
>人間が最善ではない手も含めて打った時にそれでも勝てない証明はされてないのでは？
両者最善手を打つ場合（弱解決）、片方だけが最善手を打つ場合、共に考慮しているようです
（両者が最善手を打たない場合は考慮されていない（強解決））
（今回の論文の概略）
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, 参考になる)
1. 最初の10手をまず既存のオセロソフト(を改造したもの)の評価関数で見積もる。
2. 残り50手を完全読みする(実際にはさらに14手-36手に分割してこの手順を再帰的に適用するようなことをしてるけど省略)
3. 完全読みした評価値と1.の評価値が一致していたので(弱)解決
4. もし一致していなかったら、完全読みした評価値をメモ化して改善された評価関数で1.からの手順を繰り返す
最初から完全読みするのと何が違うのかと言うと、1.で評価しなかった局面(99.9%)については2.の完全読みをしなくて済むので計算量が大幅に節約できる。評価しなかった局面の評価値が違っていても結果に影響がないことはα-β法の原理により保証されている。
Re: (スコア:0)
両者最善手を打つ場合（弱解決）
違う。初手以降、先手or後手が常に最善手を打ち続けた場合に結果が定まるのが弱解決。相手が最善手かどうかは関係ない。
両者が最善手のときだけ結果が分かっている場合は超弱解決という。
（両者が最善手を打たない場合は考慮されていない（強解決））
これも違う。ゲーム上に現れうる全ての局面をスタート地点として、その後の先手後手どちらかが最善手を打ち続けた場合の結果がわかることを強解決という。
Re: (スコア:0)
文中の「両プレイヤーが完璧に〜」が誤解を招きやすいですが
相手がミスをした時に正しく最善手を打てば負けない（勝ちか引き分け）、まで含みますよ
（相手がミスをしなければ引き分けのみで、最善手を打ち続けても勝てない）
Re: (スコア:0)
＞全ての手を解析した訳ではなく
全ての手を解析していないのに最善手と言えるのか？
最善手以外の手の優劣の順位を全部読み切ったわけでは無いけど、最善手が1番であることは証明できるということか？
※かつてのコンピュータ将棋プログラムで、
「この手（簡単に咎められる手なので普通は差されない手）の対応は実装してないので指さないでください」というのが有って、
でも対局したプロ棋士はしっかりとその手を指して勝ちをもぎとってた気がする。
Re: (スコア:0)
> 全ての手を解析していないのに最善手と言えるのか？
自分の手番で「この手を打てば必勝」って確定してる時に、「でも自分が他の手を打っても勝てるだろうか」ってのは調べなくてもいいですよね
なので全ての手を読む必要はないです
> ※かつてのコンピュータ将棋プログラムで
将棋は結構ルールが複雑ですし、オセロやチェスと違って終局が近づいてもプレイヤーの選択肢が狭まっていかないので、単純に比較できないです
それに大会では「実装してない手があるけど、指されなければ負けない」でも勝負を挑めますけど、論文でそれは通らないでしょう
Re:ということは (スコア:1)
>自分の手番で「この手を打てば必勝」って確定してる時に
勝ち負けだけを調べたい場合は、最大の差が付く最高の勝ち筋を読む必要はないので探索しきる必要もないわけですね。「少なくとも2目差で勝てる勝ち筋は見つけた(他の手を指せばもっと差を付けられるかもしれないが、再帰的に同じ議論でそれは探索していない)」と。
でも、「勝ち筋を1個見つけた」なら良いんですが「引き分けにできる手を見つけた」の場合は、まだ未発見の勝ち筋が残ってる可能性が潰せてなさそうな。…ってああ! だから、先手、後手両方で試した、に繋がるわけですか。
・先手は確実に引き分けに持ち込める。なおそれが最善手かは不明。検討をすっ飛ばした手まで全て検討できれば必勝になる可能性もある
・後手は確実に引き分けに持ち込める。なおそれが最善手かは不明。検討をすっ飛ばした手まで全て検討できれば必勝になる可能性もある
を両方とも独立に証明しておいて、その2つを組み合わせることで、
・先手後手共に引き分けが最善手
と結論づけられた、と。
もし、先手より後手の検討の方が無茶苦茶に重たくなるようなゲームだったとすると、後手が勝てないことまでは証明出来た、という途中段階で一端結論という展開もあり得るわけですね。
オセロはつまらないゲーム (スコア:0)
「人間が遊ぶのでなければ」オセロはひどくつまらないゲームだ。「引き分け」も予想されていたから結論もつまらない。「リーマン予想の解決への糸口があった」とかいうわけでもない。
つまらなくないのは研究手法やそこから得られる洞察のほうだ。だから素人が口を挟むのは純粋な時間の無駄だ。
Re: (スコア:0)
人間が遊ぶのでなくても面白いゲームってたとえばどんなゲームですか？
Re:オセロはつまらないゲーム (スコア:2)
ライフゲームとか？
Re: (スコア:0)
ライフゲームなどセルラーオートマトンは非常に神秘をたたえているが、その事実はまだあまり知られていない。なので素人の出番もありうるし、むしろ必要とされているかもしれない。たとば一介の数学愛好家がリーマン予想との関連に気づくとか。
https://ja.wikipedia.org/wiki/%E3%82%AB%E3%82%AA%E3%82%B9%E3%81%AE%E7%B8%81 [wikipedia.org]
オセロの解決には(話題性以外は)純粋に専門的な興味しか残っていない。
Re: (スコア:0)
AI「人間を粛清するゲームなら楽しそうだな」
オセロってNGワードになったんじゃなかったのか (スコア:0)
たいとるおんりー
Re: (スコア:0)
Re: (スコア:0)
おふろ入ってるよね。
相方の方があまり見なくなった。