February 09, 2006

OthelloAI その2

オセロをコンピュータで解く課題ですが、前の記事のルールの実装に続き、コンピュータが自分の手筋を決定するためのアルゴリズムの作りこみを行いました。
アルゴリズムとしては、盤面の状態が自分にとって有利かどうかを判断するための評価関数算出法としてベイズ推定を採用しました。また、その算出法ができるだけ確からしい値になるように経験をつませるため、強化学習(ぽいもの)を組み合わせました。
ソースを置いておきます。Rubyで書いてあります。

課題の対象は6x6のオセロ、現在学習中。

経験を積ませる過程で問題となったのがRubyの実行速度です。プログラムが高速に動けば動くほど、経験を多く積むことができ、賢くなるはずです。
ところが、Rubyは公式ページのチュートリアルにもあるように『RubyはCなどに比べて開発速度は速く，実行速度は遅い．』ので、Rubyに実行速度を求めるのはかなり問題があります。今回は課題の期限の関係で仕方なくRubyを選択したわけですが、こういった事情なので色々悪あがきをして高速に動くようチューニングしてみました。

チューニングのポイントとなるのが、あたり前ですが『時間がかかる部分を早くする』ことにあります。時間がかからない部分をいくらチューニングしたところであまり早くなりません。この時間がかかる部分をいかに見極めるかが重要で、この作業をプロファイルと呼びます。
Rubyではこの作業を簡単に実現することが可能です。

をしてみてください。実行が終わるとどの部分でどれだけ時間がかかったのかが表示されます。あとはその遅い部分をチューニングしていけば、プログラムが早くなります。

今回チューニングした点は、時間がかかる部分に対して

• evalをしない
• ループの入れ子を作らない
• newをしない、できるだけ一度作ったものを再利用する

この3点でかなり実行速度が改善されました。