昨日のエントリは「ブロックス・デュオを２手目まで探索してみて、ちょっと全数探索するのは厳しそうな雰囲気やなあ」というところまで。
ここはひとまず３手目以降の総局面数の見積もりが欲しい。
というわけで各局面で可能な手を数え上げながら、ランダムな手を選んで手詰まり（どちらかのプレイヤーがパス）になるまで進める、というのを１０００回やってみた。この結果から、（３手目での可能な手の数の平均）×（４手目での可能な手の数の平均）×……で、とてもおおざっぱながらも局面数の見積もりが得られるはず*1。
というわけで以下が結果。
"estimate" のところが３手目以降の局面数の見積もり。これに前回の 86346 通りを掛ければ全局面数の見積もりとなるが、まあそれ以前の問題。
3: 536.179 (536179/1000, max: 904) 4: 516.143 (516143/1000, max: 904) 5: 543.944 (543944/1000, max: 928) 6: 493.939 (493939/1000, max: 877) 7: 491.801 (491801/1000, max: 843) 8: 435.732 (435732/1000, max: 887) 9: 410.996 (410996/1000, max: 822) 10: 360.382 (360382/1000, max: 855) 11: 330.437 (330437/1000, max: 741) 12: 277.403 (277403/1000, max: 668) 13: 241.777 (241777/1000, max: 583) 14: 201.657 (201657/1000, max: 482) 15: 167.17 (167170/1000, max: 405) 16: 133.225 (133225/1000, max: 384) 17: 107.453 (107453/1000, max: 374) 18: 81.9219219219219 (81840/999, max: 315) 19: 62.0220440881764 (61898/998, max: 346) 20: 46.4187689202825 (46001/991, max: 180) 21: 33.5223577235772 (32986/984, max: 198) 22: 25.3354231974922 (24246/957, max: 149) 23: 17.2868217054264 (15610/903, max: 122) 24: 13.4443084455324 (10984/817, max: 91) 25: 9.2431654676259 (6424/695, max: 57) 26: 8.03724394785847 (4316/537, max: 56) 27: 5.60574412532637 (2147/383, max: 36) 28: 5.39754098360656 (1317/244, max: 30) 29: 4.11363636363636 (543/132, max: 18) 30: 3.34782608695652 (231/69, max: 13) 31: 3.52941176470588 (120/34, max: 17) 32: 2.29411764705882 (39/17, max: 5) 33: 1.5 (3/2, max: 2) 34: 2.0 (2/1, max: 2) estimate: 883586246344447668847298428561454899663647269222195314
8.8*10^53 ということで、まあ誤差はきっとずいぶんあるんだろうけど、全数探索はとてもとても無理なようだ。攻め方をいろいろ考えなくては。
手数の分布からいくつか気がついたこと。
- 10手目あたりまでは定石ベースか？
- 10手目以降はｎ手先読み＋評価関数
- 20手目以降なら、かなり先読みできそう。25手目以降なら全数探索もあり？
- ブロックス・デュオの実際のプレイの「棋譜」が欲しいなあ。対戦サイトのログとか分けてくれないかな？ｗ
*1:同じ局面でも手の順番が違えば別々に数えることになるので、実際はこれより小さいことを期待したいが……
