オセロはいつ解けるのか

先日箱根で開催されたゲームプログラミングワークショップに行ってきた。
ゲームプログラミングワークショップとは
簡単に言うと将棋や囲碁などのゲームに関する学会と考えてよい。

論文を書こう書こうと言いながら結局断念してしまったことは非常に残念だったが
やる気はあるので卒業してからでもコツコツ書こうと思う。
(基本的な理論は完成していて、あとは実験と論文を書くのみ)

それに関連して自分の研究分野の話を少々。

最近チェッカーが解かれたので(双方最善を尽くすと引き分け)
オセロはいつ頃解けるのかについて。
現在最速と言われているZebraを用いて
最終40手を読みきるのに大体1日かかる。
(これは運が良ければの話で局面によってはもっともっとかかる)

オセロは全部で60手なので
単純に分担させれば20手目の総手数の日数で解ける。

オセロの試合結果は何通りかスレによると、16手目で
2×10^13なのでざっくり言って20手目だと10^17手程度だとする。
αβ探索法という方法を使えば最も良い場合で計算量がおよそ平方根になるので
10^8程度。

つまり1000台で分担すれば273年程度で解けることになる。
intelが予定しているサーバー用128コアCPUでHTをかければ
1000台使って1年程度だろう。

1000台規模のグリッドコンピューティングが用意できなければ
あと十数年程度ではとてもではないが無理という結論になる。