オセロの厳密解
オセロは将棋に比べてパターンが少なく、必勝法なる物を
コンピューターで計算できると思うんだけど、
必勝法をうつもの同士が対戦したら
先手、後手どちらが勝つの？
コンピューターで計算できると思うんだけど、
必勝法をうつもの同士が対戦したら
先手、後手どちらが勝つの？
|
|
|
2 ：名無し名人：02/05/12 11:58 ID:ZreOc/MY
先手だ思う。
3 ：名無し名人：02/05/12 12:13 ID:U0TYUs36
３ゲト・・・でもクソスレに３ゲトしてもしょうがないか・・・・。
4 ：名無し名人：02/05/12 12:20 ID:qaAJsn96
た
5 ：名無し名人：02/05/12 12:28 ID:.b3Ayqmo
後手 1手目は選択枝なく2手目で決まる
6 ：名無し名人：02/05/12 12:57 ID:gjpL7XHs
連珠は先手
7 ：名無し名人：02/05/12 13:05 ID:UgpQNB4c
五目並べは先手
連珠は理論的には仮後か
連珠は理論的には仮後か
8 ：名無し名人：02/05/12 13:16 ID:UgpQNB4c
連珠は、引き分けの珠型があれば
仮先はそれをえらぶから引き分けかも
仮先はそれをえらぶから引き分けかも
9 ：名無し名人：02/05/12 13:20 ID:fDIgXwKI
ところでいつになったらオセロは解析されるの？
もうされてもいい頃だと思うけど。
もうされてもいい頃だと思うけど。
>>9
それそれ、まだ解析されてないのかョ。
それそれ、まだ解析されてないのかョ。
11 ：名無し名人：02/05/12 14:32 ID:jzKl1VCQ
パソコンだと
終盤三十数手読みきりレベル
スーパーコンピューターでは・・・？
終盤三十数手読みきりレベル
スーパーコンピューターでは・・・？
12 ：名無し名人：02/05/12 14:41 ID:zHCESjS.
とりあえずオセロはCOMが人間よりは圧倒的に強いみたいだね・・・
解析されたってのは聞いたこと無いけど。
ディープブルーの読みきりはどのくらいなんだろう。
解析されたってのは聞いたこと無いけど。
ディープブルーの読みきりはどのくらいなんだろう。
13 ：名無し名人：02/05/12 14:50 ID:PqSlePJU
ファミコンの時代でも、頭がイタクなるほどつよかったもんね。
終盤も強いけど、序盤の定跡も抜かりなかったね。
終盤も強いけど、序盤の定跡も抜かりなかったね。
14 ：名無し名人：02/05/12 15:23 ID:yG1Wvms2
もうできてるよ
15 ： ：02/05/12 15:27 ID:m5weOPbs
オセロは後手必勝で解析されてます。
16 ：名無し名人：02/05/12 15:27 ID:LyfOlu2w
↑
６×６はね
６×６はね
17 ：名無し名人：02/05/12 15:35 ID:OAFlYfo2
コンピューター将棋スレッド ３
http://game.2ch.net/test/read.cgi/bgame/1018373365/l50
だったかその前スレだったかで「1/3は解析されている」という書き込みがあった。
黒の1手目は1通り。その後の白の置方は3通り。
もし「1/3は解析されている」の意味が白の1手目どれかについて完全に探索されてるなら
そのなかに必勝手順が入っててもおかしくないと思うんだけど。
http://game.2ch.net/test/read.cgi/bgame/1018373365/l50
だったかその前スレだったかで「1/3は解析されている」という書き込みがあった。
黒の1手目は1通り。その後の白の置方は3通り。
もし「1/3は解析されている」の意味が白の1手目どれかについて完全に探索されてるなら
そのなかに必勝手順が入っててもおかしくないと思うんだけど。
18 ：17：02/05/12 15:45 ID:OAFlYfo2
2番目のスレ
http://game.2ch.net/bgame/kako/1004/10043/1004344371.html
の272だった。
272 名前： 名無し名人 投稿日： 02/01/10 23:52 ID:kLYQ/R3X
8×8オセロは既に、1/3ほど解が出てると聞きました。
将棋に例えると、ハブに飛車引く程かしらん。
http://game.2ch.net/bgame/kako/1004/10043/1004344371.html
の272だった。
272 名前： 名無し名人 投稿日： 02/01/10 23:52 ID:kLYQ/R3X
8×8オセロは既に、1/3ほど解が出てると聞きました。
将棋に例えると、ハブに飛車引く程かしらん。
19 ：名無し名人：02/05/12 16:05 ID:hX9NFQF6
終盤５８手
完全読み？？
完全読み？？
20 ：オセロ三段：02/05/12 16:09 ID:Qn7us0Zg
双方最善で引き分けというのが現在の結論。
まだ終盤30数手ほどまでしか解析されてないが、おそらく
それでも充分であろう。
まだ終盤30数手ほどまでしか解析されてないが、おそらく
それでも充分であろう。
21 ：名無し名人：02/05/12 16:18 ID:fDIgXwKI
スパコン使っても解析できないの！？？
24 ：名無し名人：02/05/12 16:28 ID:OAFlYfo2
1手の選択肢が6つあるとして6^4=1296だから
並列型スーパーコンでプロセッサ1024台だとしたら
4手深く読める程度かな。（個々のプロセッサはパソコンと同程度として）
いや、効率良く枝刈りできればもっと読めるかな。それでも8手くらい？
SETI@Home方式で100万台でも
6^8=1679616
8手くらい？ 枝刈りで16手？
並列型スーパーコンでプロセッサ1024台だとしたら
4手深く読める程度かな。（個々のプロセッサはパソコンと同程度として）
いや、効率良く枝刈りできればもっと読めるかな。それでも8手くらい？
SETI@Home方式で100万台でも
6^8=1679616
8手くらい？ 枝刈りで16手？
25 ：名無し名人：02/05/12 16:44 ID:eTKZyYd.
パンダのオセロでパンダパパに勝てません。
勝つ方法押せ−手。
勝つ方法押せ−手。
ちょっと組んでみたけど計算時間1分で終盤23手読み程度だ。
>11
>終盤三十数手読みきりレベル
これはデータベース持ってるのかな？
>11
>終盤三十数手読みきりレベル
これはデータベース持ってるのかな？
探索中の手で明らかに変な手があったらそこを人間が直してやる
（別な手を先に探索させる）ようにするとかなり早くなりそうな気がする。
（別な手を先に探索させる）ようにするとかなり早くなりそうな気がする。
28 ：名無し名人：02/05/12 19:44 ID:gjpL7XHs
だから後手
753は後手必勝です。
30 ：名無し名人：02/05/12 21:44 ID:qaAJsn96
オセロの世界戦てあるの？そういう対局では先後の勝率はどないなんやろ？
>>30
人間同士だと微妙に白の勝率が良い。正確にはわからないが
感覚的には白勝ち51:49黒勝ちくらいか？
なぜなら微妙な形勢のまま終盤に突入した場合、
白には偶数理論があり、黒はそれを偶数理論を壊すか
あるいは偶数理論込みでも勝てる手順を探すか、いずれにしろ
高度に創造的な手法を編み出すことを要求されることになる。
その作業はPCにはなんてことはない作業だが人間の脳では難しい。
ってこと。
用語わからなかったら検索で調べてね。
人間同士だと微妙に白の勝率が良い。正確にはわからないが
感覚的には白勝ち51:49黒勝ちくらいか？
なぜなら微妙な形勢のまま終盤に突入した場合、
白には偶数理論があり、黒はそれを偶数理論を壊すか
あるいは偶数理論込みでも勝てる手順を探すか、いずれにしろ
高度に創造的な手法を編み出すことを要求されることになる。
その作業はPCにはなんてことはない作業だが人間の脳では難しい。
ってこと。
用語わからなかったら検索で調べてね。
>>27
漏れも一時同じこと考えたが甘いかも。
今の優秀なソフトはMPCで
明らかに変な手は4手読みくらいでかなりの確率で
カットされる。
その作業に人間の高段者が絡んでも、
かなり速くなるということはないんじゃないかな。
少しくらい速くはなると思う。
漏れも一時同じこと考えたが甘いかも。
今の優秀なソフトはMPCで
明らかに変な手は4手読みくらいでかなりの確率で
カットされる。
その作業に人間の高段者が絡んでも、
かなり速くなるということはないんじゃないかな。
少しくらい速くはなると思う。
>>24
枝刈りというのは2種類の概念があって、
一つはいわゆるαβ
もうひとつはMPC（前向き枝刈り）
前者はミニマックスの最適化だからいくら使っても問題ない。
っていうより採用しないソフトはアフォのレベル。
これを効率的にやるには如何に最善ぽい枝から読み始めるか
そこにかかってる。ここには高度なソフト的手法の入る余地がある。
でも後者は浅い読みで可能性の低そうな枝をカットするから、
深く読んで初めて良い手だってことに気づく、そういう手を
カットしてしまう。
だから後者の枝刈りをやってしまうと、それは完全読みとはいえない。
でも後者の枝刈りをやらない限り、深読みの必要時間を劇的に短縮する
効果は無い。
αβの初期枝の順位付けの手法はゼブラあたりでほぼ究極の
ところまで行ってると思う。だから枝刈り技術の今後の向上は
あまり期待しない方がいい。
枝刈りというのは2種類の概念があって、
一つはいわゆるαβ
もうひとつはMPC（前向き枝刈り）
前者はミニマックスの最適化だからいくら使っても問題ない。
っていうより採用しないソフトはアフォのレベル。
これを効率的にやるには如何に最善ぽい枝から読み始めるか
そこにかかってる。ここには高度なソフト的手法の入る余地がある。
でも後者は浅い読みで可能性の低そうな枝をカットするから、
深く読んで初めて良い手だってことに気づく、そういう手を
カットしてしまう。
だから後者の枝刈りをやってしまうと、それは完全読みとはいえない。
でも後者の枝刈りをやらない限り、深読みの必要時間を劇的に短縮する
効果は無い。
αβの初期枝の順位付けの手法はゼブラあたりでほぼ究極の
ところまで行ってると思う。だから枝刈り技術の今後の向上は
あまり期待しない方がいい。
というわけで、厳密解を一般人が正確に知るまでには
あと20年くらいはかかるでしょう。
でも、現在Public Drawと呼ばれてる手順の中に、
その厳密解の手順は既に存在している可能性はかなり高い。
かもしれない。
議論吹っかけのために一言余計なことを言うと、
どのゲームも時間の問題。22世紀くらいには囲碁も将棋も
人間はソフトにはまったく歯が立たなくなるでしょう。
ただし、ソフトと延々引き分け続ける実力の持ち主の出現は
あるかもしれない。ゲーム自体がルール的に引き分けを含む
ものであるならば。
あと20年くらいはかかるでしょう。
でも、現在Public Drawと呼ばれてる手順の中に、
その厳密解の手順は既に存在している可能性はかなり高い。
かもしれない。
議論吹っかけのために一言余計なことを言うと、
どのゲームも時間の問題。22世紀くらいには囲碁も将棋も
人間はソフトにはまったく歯が立たなくなるでしょう。
ただし、ソフトと延々引き分け続ける実力の持ち主の出現は
あるかもしれない。ゲーム自体がルール的に引き分けを含む
ものであるならば。
35 ：名無し名人：02/05/13 03:26 ID:wggj9dw.
まだオセロに結論が出てなかったのか・・・。ちょとビックリ。
初手23手は10^16通りくらいかな。
10^8〜10^16、間をとって10^12通りの枝を読めば解が求まるとすると
今の1万(10^4)倍速いスーパーコンを1万(10^4)台、1年(10^4 hour)回せば解が出る程度かな。
かなりいい加減な価ですが。
10^8〜10^16、間をとって10^12通りの枝を読めば解が求まるとすると
今の1万(10^4)倍速いスーパーコンを1万(10^4)台、1年(10^4 hour)回せば解が出る程度かな。
かなりいい加減な価ですが。
38 ：名無し名人：02/05/13 11:21 ID:3BuZCWwk
>>38
それ、あんまり信用してはいけない。
それ、あんまり信用してはいけない。
31がいいこといった
>39
(部分的な)完全解じゃなかったみたいですね。
>40
>でも4〜5手でこりゃもういかんっていう進行は腐るほどある。
すご。
それはさておき、オセロ専用プロセッサなんて作れないですかね。
オセロのロジックをハードウエアで処理してしまう。
1つの局面を1本のレジスタに保存できて
1クロックで盤面が全部ひっくり返り
1GHz版なら1秒間に10億局面読めたりとか．．
盤面用のレジスタは61本用意しておけばスタック退避とかいらないかな。
(部分的な)完全解じゃなかったみたいですね。
>40
>でも4〜5手でこりゃもういかんっていう進行は腐るほどある。
すご。
それはさておき、オセロ専用プロセッサなんて作れないですかね。
オセロのロジックをハードウエアで処理してしまう。
1つの局面を1本のレジスタに保存できて
1クロックで盤面が全部ひっくり返り
1GHz版なら1秒間に10億局面読めたりとか．．
盤面用のレジスタは61本用意しておけばスタック退避とかいらないかな。
43 ：名無し名人：02/05/15 03:24 ID:iMOVJLF6
オセロは後手が2石差で勝ちになるって聞いたけど
44 ：名無し名人：02/05/16 03:19 ID:njAp3Qy.
チャンピョン
チャンピオン
チャンピヨン
チャンピオン
チャンピヨン
46 ：名無し名人：02/05/23 01:50 ID:sFXXK3Sw
オセロは藤井
>>42
サクセスという会社がオセロ専用PCIボードを発売の噂
サクセスという会社がオセロ専用PCIボードを発売の噂
48 ：名無し名人：02/05/24 12:39 ID:zWtAuW4E
引き分け
>>47
ソフト会社なのに・・・
ソフト会社なのに・・・