遅い遅い遅い！

オセロの完全読みルーチンを二通りやっと完成。ひとつはオーソドックスなα-β法。こっちは、単純ミスに気付かなくてしばらく動かなかった以外はまあ一本道。もうひとつが、ゲーム木展開法とでも呼ぶべきアルゴリズム。各局面を節点として、そこから次に出現しうる局面（子）、またそこに来うる局面（親）へリンクを張って木構造にしたものを作っていきます。複数の手順で同じ局面にたどり着くことがあるので、木は枝同士が交わることもある構造をとります。つまり節点は複数の親を持ち得る。
展開していって終局にたどり着いたら自分の評価点（石差）を親に伝えます。すべての子の評価点を受け取った節点は自身も評価点を持ち、さらに親に伝える、という具合で最終的に初期配置の評価点が（そしてその石差に至るための経路が）判明するという具合。
4×4オセロで動かしてみると、α-β法は一瞬。ちなみに、白の8石勝ちが最善手とでます。次にゲーム木展開法。遅い！　ペンティアム4マシンでも10秒ぐらいかけて同じ答えを出します。
読んだ手の数を数えると、α-βで24000手くらい、ゲーム木では12000手くらいと、手の数自体は少ないのに（ゲーム木展開法では、点対称・線対称な盤面は同じ局面としてまとめてしまうので読む手が節約される）。これは、木構造を作るのにインスタンス生成などのメモリ操作がかさんでいるからかと推測。
さて面白いこと。オセロの第一手は、４通りあるようでもすべて対称なので一通りしか実はないことになります。では、最初の黒番を打ち終わったところから探索するとどうなるか。
α-βでそれをやると、1800手ぐらいで読めてしまいました。単純に1/4にならない。もう少し検証が必要だと思うのですが、最初の４択は同じことになると言っても、盤面の方向が変わることになるので先読みする時に打つ手の候補の順番が変わってしまい、枝刈りの効率が全然変わってくるせいかなと思っています。