Xion's Programming Notes

リバーシ，つまり，オセロの盤面は，普通8x8の64マスですが，今回の対象は，4x4の16マスという小さなリバーシです．
初期の盤面で，黒2つ白2つを置いた状態から始まるので，パスを無視して考えれば，12手でゲームが終了します．

ビットボードを用いた 4x4 オセロ完全解析．こちらのページを参考にさせていただきました．

16bitのビットボードで，NegaMax法，NegaAlpha法，NegaScout法の3つを実装しました．
ハッシュテーブル（トランスポジションテーブル）は，単純にルートノード（初期局面）から数えた深さが一定値以下の時にだけ，登録と参照を行うこととしました．

探索の結果は，上のページにもあるように，黒の8石負けとなりました．
先手が負けるっていうのもなんだか不思議な感じがします．

各アルゴリズムを100回実行した時間の合計値をプロットしています．

実験環境はこんな感じ．

CPU	Intel Core i7 2700K@3.5GHz
OS	Ubuntu 12.04 32bit

時間が最小となったのは，NegaAlpha法で，深さ5までハッシュテーブルを使ったもの．
100回の試行にかかった時間が，0.002259秒，つまり，1回の探索に，22.59マイクロ秒．
思った以上に速いですね．

初期局面における黒の合法手は4つ．その全ては対称性を考慮すると等価です．
なので，テーブルを使う深さが1から2になったときに，だいたい4分の1の探索時間になります．
しかし，NegaAlpha法の場合は，20分の1くらいになっています．バグでしょうか...

ここでいう末端局面とは，黒白両方がパスしかできない盤面のことです．

NegaAlpha法で，テーブルを使う深さを14以上にした場合では，たったの84回しか評価しません．
これで本当にあっているのか不安ですが...

(少なくとも4x4のリバーシでは，バグがなければ，)

プログラミングの勉強や囲碁プログラムの開発について書いていきます。