局面数の概算

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

---

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

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

472 256 sage 2006/04/15(土) 14:04:16 
>>462 
遅くなってすみません。 
中央４マスは常に石があるとして繋り割合を出してみました。 
結果はWikiに置いときました。 

http://www9.atwiki.jp/othello/pages/43.html

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年・・・。 
しかも１手につき最大 5.9E28の盤面を保持しないといけない。 
一体どのくらいの記憶容量が必要になるんでしょう。 

http://www9.atwiki.jp/othello/pages/44.html