■

はてなダイアリー、開設カンタンでいいなあ。
貧乏性なので、カスタマイズしてタイトル部分の高さを節約してみた。

ブログのタイトルは「雷雲の変奏曲」
今日は雷鳴がすごかったので・・・。

プログラミングの話題を中心に書き進めていきたいと思います。

最近コツコツ取り組んでいるのがコンピューターオセロ。
世界で最初に8x8オセロを解けたらいいな。
まあムリだろうけど。
6x6は解かれているらしい。

同一局面数（鏡像・回転も統合）を数えてみた

着手	盤面数	終局盤面数	増率
-	1	0	-
1手目	1	0	1.00
2手目	3	0	3.00
3手目	14	0	4.67
4手目	60	0	4.29
5手目	322	0	5.37
6手目	1,773	0	5.51
7手目	10,649	0	6.01
8手目	67,245	0	6.31
9手目	434,029	36	6.45
10手目	2,958,586	28	6.82
11手目	19,786,652	925	6.69
12手目	137,642,678	1,321	6.96
13手目	912,004,217	26,938	6.63
14手目	6,158,977,944	46,489	6.75
15手目	38,755,255,016	578,729	6.29
16手目	244,248,103,534	?	6.41

今のところ数えることが出来たのはここまで。(2010/07/17 更新) (2013/07/27 表だけ更新14手→16手)
普通に考えると、同一局面を纏めるためには、纏められる可能性のある局面をすべてメモリにキャッシュしておかなければならない。
1盤面あたり16byte程度必要なので、6,158,977,944通りでは約96GBのメモリが必要になる。
そんなにメモリを積んだマシンは持っていないので、メモリを節約する工夫をしている。

盤面に対してハッシュ値を計算したのである。例えばハッシュ値を0〜40とすることで、ハッシュ値が0のものだけ保存して同一盤面かチェック、残りは捨てる。次はハッシュ値が1のもの、2のもの・・・と41回繰り返すことで、処理時間は約41倍になるが、メモリの使用量は約1/41にすることができた。こうして4GBのメモリで足りるようになった。
実際の処理時間はおよそ36時間だった。

オセロってあまりやらないけど、10手目で約300万ものバリエーションがあるものなのかと感心してしまう。

この実験では、石が四辺に到達することで、着手の分岐数が少なくなり、同一局面数の増加が次第に穏やかになるのではないか？という仮説を検証したかった。
しかし、14手目まででは、まだちょっとよく分からない。
15手目まで求めるには、このやり方では約7*7=49倍の時間がかかる。あまり現実的ではない。