局面数の概算


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

オセロゲームが到達しうる盤面がだいたいこのくらいあるであろうという概算。





462 284 sage 2006/04/11(火) 16:52:42 
256氏にお願いなんだけどいいかな? 
>>310のソースまだある?もしあるならそれに中央4マスは
常に石があるとして繋り割合出せないかな。 
乱数発生後に中央4マスは石有りでマスクして1島状の確認をする。 
これが出ればn手目の局面数の概算が出せると思うんだけど。 
n手目の盤面数(60!/(60-n)!/n!)に繋り割合を掛けて、
それに白黒分布(2^(4+n))を掛ければ局面数になる。 
各n手目の局面数の累加がトランスポジションを考慮した時の計算量になると思う。 

本当は繋り以外にもありえない局面を除外出来ればいいんだけどね。 
あと、一様な試行が出来れば良いかな、と思って>>288の方法も考えてるんだけど
上手いハッシュ関数が思いつかないorz 

472 256 sage 2006/04/15(土) 14:04:16 
>>462 
遅くなってすみません。 
中央4マスは常に石があるとして繋り割合を出してみました。 
結果はWikiに置いときました。 
473 284 sage 2006/04/15(土) 22:01:53 
>>472 
私の勝手なお願いでお手数をおかけしました。 
すみませんでした。そしてありがとうございます。 
早速、繋り割合を使って概算の局面数を出してみました。 
http://www9.atwiki.jp/othello/pages/44.html 

結果は5.10E29でした。これは推定の棋譜数6.45E54に比べると格段に小さい数値ですが 
カウントするにはまだまだ大きすぎる数値ですねorz 
>>430の16手検索は、ノード数2.03E13で183.8時間ですから4.62E18時間=5.3E14年・・・。 
しかも1手につき最大 5.9E28の盤面を保持しないといけない。 
一体どのくらいの記憶容量が必要になるんでしょう。 
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。