5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

オセロの試合結果は全部で何通りか

1 :名無しさん@3周年:04/07/23 11:16
白黒それぞれが先攻の場合を合計して
何通りあるのだろうか。

154 :名無しさん@3周年:2005/07/01(金) 22:01:46
>>148-149
ものすごいプリミティブな発想が出てきたことに(良い意味で)感銘を受けた

155 :名無しさん@3周年:2005/07/02(土) 08:56:38
プリミティブ?原始的なってこと?
どうせ俺は素人だよ!!(`ε´)

>>153
を訂正。2組→1組。3^60→2^60。


また閃いた。
全て埋まっている状態の終局面の全通りの予想値なんだけど
まずランダムに面を白黒埋める。んで開始の四マス白黒の状態になるように逆に局を進める。この方法は縦探索でね。
おそらく探索をかけても最初の状態にならないのが存在する。
んで例えば10パターン実行して1パターン…

ん?まてよ…
ごめん何でもなかった。。

156 :名無しさん@3周年:2005/07/03(日) 06:01:27
あるソフトをネットを通してバラまく。このソフトは、一つの局面から一手すすんだ全ての局面を計算する簡単なソフト。
まず1台のPCからスタートする。一手目はルール上黒f5と決まっているらしいから。一局目は初期状態からf5に黒をおいた一通りの棋譜となる。
んでこの棋譜を同じソフトが入っている別の任意の一台のPCに送る。
棋譜を送ったら棋譜の情報を消す。
受け取ったPCは受け取った棋譜から二局目を弾きだす。
実際二局目は三通りある。
んでこの三通りの棋譜を今度は三台のPCに一通りづつ送る。
送ったら、棋譜の情報を消す。
以下続ける。

終局の棋譜を受け取ったPCは、この終局の棋譜はソフトネットワーク上唯一無二なので、「終局の棋譜が来た」という情報だけで棋譜の情報を消してもいい。

んで何回終局の棋譜が来たかを
代表のサーバーに送って
それを足していけば答えがでるんじゃん?

157 :名無しさん@3周年:2005/07/03(日) 07:13:28
>156
既に指摘されているようだが、やっぱり時間が足りないと思われ。適当に概算してみよう。
この場合、木をそのまま辿っていくから可能な状態は >37 によると 10^58。
超大雑把に IPv4 アドレス全域に属するノードが使えるとして 2^32 ≒ 4*10^9。
どんどんノードが増加していくから処理が進む、というのは典型的なネズミ講発想で残念ながら頭打ちする。
つまりノード全域に盤面が行き渡ってしまえば他に渡せるやつがいなくなるので単位処理あたりに進む
手数はノード数と等しくなると考えて良かろう。結局、探索空間をノード数で分割しただけと考えて良い。
1ノードで 1μs で1手進むとして、1年間に 60*60*24*365*1000*1000 ≒ 3*10^13 進む。
結局全体で 1 年間で 4*10^9 * 3*10^13 = 12 * 10^22。
10^58 を割ってやると 8 * 10^34 年程度ということになる。

ttp://ja.wikipedia.org/wiki/宇宙の終焉
によると
> 10^14 年 -- すべての恒星が燃え尽きるまでの時間
だそうです。

158 :名無しさん@3周年:2005/07/03(日) 15:10:30
レス有難う。
そっかあ。駄目かあ。うーんどうしょう。
感情的にだが10^58は予測値として多すぎると思う。
よし減らそう

159 :名無しさん@3周年:2005/07/04(月) 00:00:13
漁師アルゴリズムを考えたらどうだろう?
んで漁師コンピューター開発までスレ保存

漁港の人にがんばってもらうしか

160 :名無しさん@3周年:2005/07/09(土) 01:27:15
自分は素人ですが、真ん中に線を引いて対象的に動かしたら(鏡に写す様に)、もう一通りの結果がわかりますよね?これってみなさんの計算のプラスになりませんでしょうか?
無知の自分がレスってすみませんです。。。

161 :名無しさん@3周年:2005/07/09(土) 03:06:19
最終盤面のみを考えて、
絶対にありえない形のパターン化ができれば
ありえない形の数を計算できて、最終盤面の通り数がでるのではないでしょうか。
(ただし投了の場合除く)

ありえないパターン@
真ん中らへんの4つのどれかが無地 

あーーつかれた。あとは他の人に任せよう

162 :名無しさん@3周年:2005/07/09(土) 20:42:05
>>160
そうすれば探索範囲が半分になりますね
ほかにも盤面を回転させると同じになる分を省いたりします。
殆どの人が割りとすぐ思いつくようなアイデアだけど
貴方が自分で思いついたならそれは貴方のアイデアです。
どうせみんなもう知ってるんだ、と考えるのをやめるのはもったいない。
めげずにアイデアを考えつづけていれば、
その内まだ誰も思いついてないアイデアが浮かぶかも知れません。

163 :名無しさん@3周年:2005/07/26(火) 15:22:31
hosyu

164 :名無しさん@3周年:2005/08/05(金) 22:59:36
補習

165 :名無しさん@3周年:2005/08/11(木) 07:19:31
予測値の出し方なんだけど
まず何本か(多ければ多いほどいい)終局までの棋譜を適当につくる。
つぎに一本一本に対して局ごとの手の数を出す。
そして局ごとに何通りあるかの平均を出す。
その値を掛けて予測値を出す。
っていうのはどう?

166 :名無しさん2周年 :2005/08/12(金) 19:54:02
いいサイトない?
って、Aちゃんに・・・・。(:::)


167 :名無しさん@3周年:2005/08/13(土) 14:09:32
反応がない。。
とりあえずこの方法で計算した予測値を近々載っけますね。

168 :名無しさん@3周年:2005/08/13(土) 18:48:52
ワクワクテカテカ(AA略

169 :名無しさん@3周年:2005/08/17(水) 16:24:13
試しに動かしたら
7.29E+53
とか出た。頼むから論理エラーであってくれ

170 :167:2005/08/17(水) 20:52:23
百本、千本の棋譜で試した所、共に予測値の桁が48桁になりました

やっぱだみだこりゃ

171 :名無しさん@3周年:2005/08/18(木) 21:14:29
>>167
K3乙
48桁という目星がついただけでも(少なくとも俺は)すごいと思うよ

172 :名無しさん@3周年:2005/08/19(金) 14:41:39
>>170
GJ!
これはまったく新しいアプローチでしたね。

173 :167:2005/08/19(金) 18:36:37
すんません。間違えました。
10^52ぐらいです。
個人的にこれでほぼ確定と思っています。
調べる棋譜数としてはあまりにも貧弱ですが。。。

ttp://49uper.com:8080/html/img-s/72569.zip
↑結果です。説明が全くなくてすみません。

174 :名無しさん@3周年:2005/08/22(月) 18:50:17
>>173
Page Not Found って出るのは
俺だけ?

175 :名無しさん@3周年:2005/08/24(水) 00:57:39
あ〜!!!!!!!!!!!
時間さえあれば!!!!!!!!!!!!

UDみたいに分散コンピューティングは使う事は出来ないの?

176 :名無しさん@3周年:2005/08/24(水) 02:18:16
分散コンピューティングでの予想経過時間
仮定1 コンピュータの速さは平均3GHzとする
仮定2 1クロックで1手探索できるとする
仮定3 >>173 の慨算が正しいとする
仮定4 コンピュータは常時100億台使えるものとする

結構非現実的な仮定もあるけど、これで計算すると
10^52 / (3*10^9 * 10^10) ≒ 3.3*10^32 [sec] ≒ 1.05*10^25 [年]
(´・ω・`)ムリポ

177 :名無しさん@3周年:2005/08/24(水) 02:34:53
>>176
オセロの勝敗を計算する事って
たんぱく質とかガンの特効薬の開発よりも時間がかかる事tなんだ・・・

すごい事にチャレンジしているな・・・

178 :名無しさん@3周年:2005/08/24(水) 04:59:32
このままではどんなにコンピュータが発達しても答えが出ないことになってしまう。
目玉が飛び出るぐらい画期的な計算方法を発案しないと…

52桁まで有効な予測値を出すとかw

179 :名無しさん@3周年:2005/08/24(水) 09:37:29
いつの間にかオセロの総手数を求めることが、
必勝解を求めることになっている気がするが...

こんなんあるよ。
分散すれば何とかなるかも。

ttp://oshiete1.goo.ne.jp/kotaeru.php3?q=1091338

6000 (年) * 365 = 2190000 (日)
約200000台のPCが集まれば、10日か...

この専門家の根拠は不明だが。
既出だったらごめんよ。

180 :名無しさん@3周年:2005/08/24(水) 10:27:26
原始的な方法かもしれないけれど、
現在あるアルゴリズムと、分散コンピューティングを使って、
それぞれのPCでオセロを1試合ずつやらせる。
その試合結果をひたすら中央のサーバに集積していって
かぶらないものだけを抽出していく。
こうすることによって、過去の戦いの経験値を増やしていくと同時に
計算する事ではなくて実際的なカウントをしていく事ができるのでは?

でも時間もかかるし、実際的じゃないか・・・
素人考えでゴメン・・・

181 :名無しさん@3周年:2005/08/24(水) 11:39:54
>>180
計算する事ではない実際的なカウント

って何?
詳細キボンヌ

182 :名無しさん@3周年:2005/08/24(水) 14:10:11
>>180がいいたかった事って
一つ一つ実際の戦局を打ち出すことによってありえない盤面を省く事が出来るってことでは?

人間の脳ってすごいよな

183 :名無しさん@3周年:2005/08/24(水) 18:29:26
>>180
>>182

なるほど、もすこし具体的に言うと
盤面をデータベースに蓄えていって、
そのデータベースからコンピュータが自動的に
法則性を見つけ出し、
あらゆる盤面の可能性(3^64)の中から
ありえない盤面を削ってゆく。

そしてしばらくして盤面が減らなくなったら
のこった盤面数がオセロの試合結果ということになる。

ってことか。なるほど。
ルールを覚えるのなら記憶容量そんなに増えないかもしれないしな。

問題はルールの自動抽出の部分か...

184 :183:2005/08/24(水) 18:31:50
>>183

記憶容量そんなに増えない -> 記憶容量そんなに食わない

すまん

185 :名無しさん@3周年:2005/08/24(水) 19:00:16
いっちょやってみっか
┏━━━━━━━━━━━━━━━━━┓
┃┌─┬─┬─┬─┬─┬─┬─┬─┐┃
┃│  │  │  │  │  │  │  │  │┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│  │  │  │  │  │  │  │  │┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│  │  │  │  │  │  │  │  │┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│  │  │  │○│●│  │  │  │┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│  │  │  │●│○│  │  │  │┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│  │  │  │  │  │  │  │  │┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│  │  │  │  │  │  │  │  │┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│  │  │  │  │  │  │  │  │┃
┃└─┴─┴─┴─┴─┴─┴─┴─┘┃
┗━━━━━━━━━━━━━━━━━┛


186 :名無しさん@3周年:2005/08/24(水) 23:14:36
↑もうええっちゅに

187 :名無しさん@3周年:2005/08/25(木) 22:58:32
>>183
そこんところ、自分素人なんでわからんのだけどでかくなっちゃうの?

188 :名無しさん@3周年:2005/08/26(金) 10:52:22
>>187
覚えなければならない量のこと?
覚えなくてもいいけど、覚えたほうがいいってこと。

すべての盤面を一つ一つ数えるときに
何も覚えないと10^52すべてを数えないといけない。
もし仮にメモリが無尽蔵にあるとすれば、
一度出現したことのある盤面を覚えておくことができ、
最大でも3^64(= 約10^30)回数えればいいってことになる。

ただしそんな馬鹿でかい記憶装置はないんだよね。
1 テラ = 10^12
だからもっと効率のよい方法はないかなってなっちゃうのよ。

189 :名無しさん@3周年:2005/08/26(金) 23:15:51
┏━━━━━━━━━━━━━━━━━┓
┃┌─┬─┬─┬─┬─┬─┬─┬─┐┃
┃│  │  │  │  │  │  │  │  │┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│  │  │  │  │  │  │  │  │┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│  │  │  │  │  │  │  │  │┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│  │  │  │○│●│  │  │  │┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│  │  │  │●│●│●│  │  │┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│  │  │  │  │  │  │  │  │┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│  │  │  │  │  │  │  │  │┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│  │  │  │  │  │  │  │  │┃
┃└─┴─┴─┴─┴─┴─┴─┴─┘┃
┗━━━━━━━━━━━━━━━━━┛




190 :名無しさん@3周年:2005/08/27(土) 21:49:19
↑そやからもうええっちゅうねん

191 :名無しさん@3周年:2005/08/28(日) 09:28:53
┏━━━━━━━━━━━━━━━━━┓
┃┌─┬─┬─┬─┬─┬─┬─┬─┐┃
┃│  │  │  │  │  │  │  │  │┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│  │  │  │  │  │  │  │  │┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│  │  │  │  │  │  │  │  │┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│  │  │●│●│●│  │  │  │┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│  │  │  │●│●│●│  │  │┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│  │  │  │  │  │  │  │  │┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│  │  │  │  │  │  │  │  │┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│  │  │  │  │  │  │  │  │┃
┃└─┴─┴─┴─┴─┴─┴─┴─┘┃
┗━━━━━━━━━━━━━━━━━┛

192 :名無しさん@3周年:2005/08/28(日) 20:58:12
問題を簡単にしようぜ。

黒ゴマ白ゴマあわせて10^52個ほどある。
効率よく何粒あるか数えるにはどの様な手法がいいでしょう?

193 :183:2005/08/28(日) 21:20:32
>>192
ゴマで惑星がいくつかできそうな気がするが...

ゴマを一面にまいて、遠くから見て何色に見えるか
白→白ゴマ多い。
黒→黒ゴマ多い。
灰色→明度によって判断。
とか。

それだけの数のゴマを一面にまける平面がこの宇宙にあるのかは
知らないが。

194 :名無しさん@3周年:2005/08/29(月) 00:14:22
要は「カウント」の限界だよね。正確に数を数えるには「カウント」以外ないのだが…


195 :名無しさん@3周年:2005/08/29(月) 01:10:47
カウントしなければいい方法かぁ・・・

逆転の発想!
演算時間や計算結果のメモリ消費量からカウント数を割り出す

ナニ言ってんだ・・・俺・・・

196 :名無しさん@3周年:2005/08/29(月) 11:12:41
>>194
たしかに。

オセロは
ある局面の次の局面数はその盤面の状態に依存してしまう。
○×ゲームみたいに次の局面数がみんな同じじゃないからなぁ。

○×ゲームも正確には 9! ではなくて、途中で終わることも
考慮しなければならないが。

197 :名無しさん@3周年:2005/08/29(月) 16:47:21
○×ゲームの試合結果の通り。
カウントではなく数式で答えを出すのはこの問題でさえむずかくね?
やべー

198 :名無しさん@3周年:2005/08/29(月) 23:23:58
○×ゲーム程度のサイズなら全探索でOKじゃね?

199 :名無しさん@3周年:2005/08/29(月) 23:41:11
>>197
○×ゲームでは
理論上、最も早く勝負がつくのは5手目だから
それまでの9*8*7*6*5までは正確に分かる。
問題は残りの4ターンがどういう振る舞いをするかだな。

これをカウントせずに正確に算出できれば、
オセロの総手数算出の足掛かりになるかもしれないな。

200 :名無しさん@3周年:2005/08/30(火) 00:22:18
○×ゲームの全探索してみた。
数式での計算の答えあわせに利用してくれ。

引き分けは問題を簡単にするために全部埋まった時点でということにしておく。
つまり勝負が決まる以外での枝刈りはなし。

1ターン目の局面数: 9
2ターン目の局面数: 72
3ターン目の局面数: 504
4ターン目の局面数: 3024
5ターン目の局面数: 15120
6ターン目の局面数: 54720
7ターン目の局面数:148176
8ターン目の局面数:200448
9ターン目の局面数:127872

全ての局面数: 549946
先手の勝ち数: 131184
後手の勝ち数: 77904

バクの可能性もあるだろうから
信頼性向上のため誰か他にも作って確認してくれ。

201 :名無しさん@3周年:2005/08/30(火) 05:07:27
>>198
うん。でも探索はオセロでは使えないことが
今までのレスでほぼきまったと俺は思うのよ。
方法としてあとは計算で出すしかないかと。
>>199が言ってくれたように○×はその練習問題として
いいんじゃない?

>>200
おつかれどす。
これで正解はでた。この数字に行き着く計算式を考えよっと。
つーかやっぱり後手超不利だなw


202 :名無しさん@3周年:2005/08/30(火) 19:29:43
6ターン目以降が全て144で割り切れるのは偶然?

203 :名無しさん@3周年:2005/08/30(火) 21:01:41
age

55 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.02 2018/11/22 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)