オセロはいつ解けるのか

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

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

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

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

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

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

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

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

その研究は認められない2

今日先生に今年度の研究計画について訂正した案を出したのだが、
またも却下された。
原因は私が過去(修士1年夏まで)やってきたアイデアをばっさり切捨てて新しい案を出したから

従来の方法では、これ以上は目立った成果がえられなさそうなので(理由は説明した)
新しい案を考えます。
そのためにいくつかの試験的な実験を行いたいです。
４月いっぱい時間をくださいと言ったが通らなかった。

どうも修士2年で
今までの蓄積がない案を出すのは好ましくないようだ。
修士論文が控えているのでそれが妥当だろう。

その研究は認められない

一昨日の話だが今年度の研究計画を先生に出したら却下された。
理由を端的に言うと博打だったから。

この「博打」とは成功する可能性が低いことを言っているわけではない。
成功すればよいが、失敗したらそれまでの努力が水泡に帰すことを意味する。

世の中の多くの研究は既存研究を発展させるという内容である。
発展とは高速化であったり、省メモリ化であったりする。
それは今まで遊んでいた回路に着目したりだとか、
今まで固定だったパラメータをトレードオフを
考えて最適値になるよう自動調整するようにしたりとかである。

これらはたとえ当初の目論見が外れても
それまでに得た理解や知識から
ある程度柔軟に「ごまかす」ことが可能である。

それに対して私の行おうとする研究はある一つの答を見つけ出すことである。
その答えが見つかれば万々歳。
見つからなければそれまで遊んでいたことになる。

これの成功はかなりの学術的価値、注目されると予測しているが、
そのメリットがあってもなお、
 博打をはることは 主にリスク管理の観点から許されない。

納得。