一つの仕事を複数のコンピュータで分けて行おうとする試み
「オセロの試合結果は何通りか？」の問題を解くにあたって一番の問題は時間であるとされる。
Ｎ台のコンピュータで同時に処理をすると、１台の時と比べ、Ｎ倍の速度で処理をすることとなり、
時間を大幅に短縮できる。
しかし、我々にとって大幅な短縮となっても敵は腐っても超大な数、なかなかうまくいかない。
また、分散処理の分野となると、話題に上がれる人が少なくなってくるのも痛恨である。
しかし、このシステムが出来上がれば、さらに今の数手先の棋譜数の出力はいけそうである。
156 名無しさん＠３周年 2005/07/03(日) 06:01:27
あるソフトをネットを通してバラまく。このソフトは、
一つの局面から一手すすんだ全ての局面を計算する簡単なソフト。
まず１台のPCからスタートする。一手目はルール上黒f5と決まっているらしいから。
一局目は初期状態からf5に黒をおいた一通りの棋譜となる。
んでこの棋譜を同じソフトが入っている別の任意の一台のPCに送る。
棋譜を送ったら棋譜の情報を消す。
受け取ったPCは受け取った棋譜から二局目を弾きだす。
実際二局目は三通りある。
んでこの三通りの棋譜を今度は三台のPCに一通りづつ送る。
送ったら、棋譜の情報を消す。
以下続ける。
終局の棋譜を受け取ったPCは、この終局の棋譜はソフトネットワーク上
唯一無二なので、「終局の棋譜が来た」
という情報だけで棋譜の情報を消してもいい。
んで何回終局の棋譜が来たかを
代表のサーバーに送って
それを足していけば答えがでるんじゃん？
157 名無しさん＠３周年 sage 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 年 -- すべての恒星が燃え尽きるまでの時間
だそうです。
175 名無しさん＠３周年 2005/08/24(水) 00:57:39
あ～!!!!!!!!!!!
時間さえあれば!!!!!!!!!!!!
UDみたいに分散コンピューティングは使う事は出来ないの？
176 名無しさん＠３周年 sage 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 [年]
(´･ω･`)ﾑﾘﾎﾟ
179 名無しさん＠３周年 2005/08/24(水) 09:37:29
こんなんあるよ。
分散すれば何とかなるかも。
ttp://oshiete1.goo.ne.jp/kotaeru.php3?q=1091338
6000 (年) * 365 = 2190000 (日)
約200000台のPCが集まれば、10日か...
この専門家の根拠は不明だが。
既出だったらごめんよ。
426 256 sage 2006/03/24(金) 21:56:39
http://boinc.oocp.org/indexj.php
以前↑こんなのを見つけたんですが、誰か知ってる人居ます？
前からこれで何かの分散処理やってみたいなと思ってたんですけど、
苦手なのでまだよく理解してなくて。
こっち方面の得意な方居ますか？
429 名無しさん＠５周年 sage 2006/03/25(土) 14:24:46
>>426
分散処理って全探索の場合はN台でやってもコストが1/Nにしかならないのよね。
全探索はいまの段階では使ってもまだまだ無理かなぁ。
あともうちょっと！ってところ、つまりあと10000倍くらい計算機が速いと
何かが解けるんだけどなぁという段階になったらいいかもね。
確率的概算値を求めるんなら、確率的分散がいまよりどれくらい抑えられるかな？
430 256 sage 2006/03/25(土) 15:44:11
>>429
ふむふむ。参考になります。
僕は序盤の全探索があと4手くらいは多くできるかなくらいで考えてました。
>>406では大型コンピュータを使って何をするつもりなのかも気になりますね。
453 409 (=200) sage 2006/04/09(日) 12:43:21
以前話されていたグリッドコンピューティングなんだけど、
総手数を「数える」のは１００万台マシンをそろえても本質的な解決にならないよね
ってうちの分散処理の教授がいってました(泣
理由は１００万台では１００万倍にしかならないからです(結果をまとめない限り)
１００万倍位じゃ数え上げるの無理ですね
757 ：名無しさん＠５周年 ：2009/05/03(日) 06:29:17
>>520 氏の othello_counter3.cpp をなんちゃって並列化してみますた
http://www9.atwiki.jp/othello?cmd=upload&act=open&pageid=28&file=othello_counter3_multi.cpp
(http://www9.atwiki.jp/othello/pages/28.html)
といっても単に初期状態を引数指定できるようにしただけ。
ex. ２手目結果から18手まで探索する場合 (２手結果 = 12盤面/回転対称4 = ３問題に分割、あとで結果を４倍しる)
./othello_counter3_multi 00000008 10080000 00000010 08040000 18 > result/02-0000.txt
./othello_counter3_multi 00000008 08080000 00000010 10100000 18 > result/02-0001.txt
./othello_counter3_multi 00000000 18080000 0000001C 00000000 18 > result/02-0002.txt
758 ：名無しさん＠５周年 ：2009/05/03(日) 06:32:11
ex. ３手目結果から18手まで探索する場合 (３手結果 = 56盤面/回転対称4 = 14問題に分割、あとで結果を４倍しる)
./othello_counter3_multi 00000010 08000000 00000008 100E0000 18 > result/03-0000.txt
./othello_counter3_multi 00000010 00040000 00000008 1C080000 18 > result/03-0001.txt
./othello_counter3_multi 00000000 08040000 00000038 10080000 18 > result/03-0002.txt
./othello_counter3_multi 00000000 08040000 00001018 10080000 18 > result/03-0003.txt
./othello_counter3_multi 00000010 10000000 00000008 08182000 18 > result/03-0004.txt
./othello_counter3_multi 00000010 00000000 00000008 18380000 18 > result/03-0005.txt
./othello_counter3_multi 00000010 00100000 00000008 38080000 18 > result/03-0006.txt
./othello_counter3_multi 00000000 00100000 00000038 18080000 18 > result/03-0007.txt
./othello_counter3_multi 00000000 10100000 00002018 08080000 18 > result/03-0008.txt
./othello_counter3_multi 00000018 00000000 00000204 18080000 18 > result/03-0009.txt
./othello_counter3_multi 00000014 00000000 00000408 18080000 18 > result/03-0010.txt
./othello_counter3_multi 00000014 00000000 00000808 18080000 18 > result/03-0011.txt
./othello_counter3_multi 0000000C 00000000 00001010 18080000 18 > result/03-0012.txt
./othello_counter3_multi 0000000C 00000000 00002010 18080000 18 > result/03-0013.txt
& 付けてひとりで Quad 実行するもよし、
計算を別の日に分けるもよし、
みんなで分割統治するもよし。
おまいら２ｃｈのちからを見せてくれ
759 ：757 ：2009/05/03(日) 07:11:22
ちなみに３手目から13手目までの探索をテストしてみた結果
(Core2Quad Q6600 2.4GHz)
othello_counter3:
13手目全棋譜数 18429768516, パス19204, 終了16384
計算時間 74.39秒
othello_counter3_multi x14:
13手目全棋譜数 18429768516, パス19204, 終了16384
計算時間(14 jobs @ 1 CPU) 74.62秒
計算時間(14 jobs @ 4 CPU) 17.63秒
なかなかいい感じ。
760 ：757 ：2009/05/03(日) 08:35:40
説明ミスりました。
ex. ２手目結果から18手まで探索する場合 (２手結果 = 12盤面/回転対称4 = ３問題に分割、あとで結果を４倍しる)
./othello_counter3_multi 00000008 10080000 00000010 08040000 17 > result/02-0000.txt
./othello_counter3_multi 00000008 08080000 00000010 10100000 17 > result/02-0001.txt
./othello_counter3_multi 00000000 18080000 0000001C 00000000 17 > result/02-0002.txt
ex. ３手目結果から18手まで探索する場合 (３手結果 = 56盤面/回転対称4 = 14問題に分割、あとで結果を４倍しる)
./othello_counter3_multi 00000010 08000000 00000008 100E0000 16 > result/03-0000.txt
./(以下略)
Ｎ手目結果からＭ手後棋譜を求めたいときは M-N+1 を引数に与える。
>>757>>758 そのままやると19手,20手まで求めようとして止まらなくなるｗ
最終更新：2009年11月23日 23:24
