January 26, 2008

Othelloプログラム(強化学習による実装)

少し前に、昔Ruby書いたオセロのプログラムをC++に書き直した、という記事を書きましたが、その続きを書きたいと思います。ようやくコンピュータ側のルーチンの実装が完了、ないし、メモリが漏れるバグ取りが完了しました(苦笑)。

とりあえず現時点のソースはこの辺りに散らかっています。

コンピュータ側のルーチンの実装にあたっては、とある目的で今後本格的に使いたいと考えている『強化学習』の入門書を1冊読んだ上で行いました。前回のRuby実装では少しこのテーマをかじった程度で実装したので、後から見直してみると何がなんだかわからない実装になっていますね。それでもある程度コンピュータプログラムができていると錯覚できたのは、学習のケースを積めば積むほど、最適な手筋に近い手筋に収束していくという効果(があるらしい)のお陰であったようです。

読んでみた本は、ずばり『強化学習』というタイトル。

この本は、非常に読みやすい一冊でした。思い返してみると、本を読みはじめる前に適用したい目標が定まっていたのが非常に良かったのだと思います。特に本を読むにあたって、この方法はあの目標に使えそうだ、この方法とあの方法の違いはこういうところがあるらしい、等のことに着目して読み進められたことが、理解に繋がったのだと思います。なおこの本の原本(『Reinforcement Learning』、英語)はネット上で読めるようです。

読んだ本に基づいていうと、今回の実装は方策オン型のTD(1) Sarsa学習で、学習中の方策にはソフトマックス関数を利用したepsilon-greedy戦略を用いています。また行動価値推定(オセロ盤面の評価関数)については、数手先の盤面の縦・横・斜めのタイリングを行い、テーブルを引くことによって最終局面における黒石と白石の差を推定しています。
これらの設定の下、現在プログラムを鍛えている最中ですが、おおよそ30分100試合程度こなしているようです。予定では1週間後には数万試合を消化し、行動価値、つまりこの局面は有利か不利か、の推定精度が上がっていることを期待していますが、どうなることやら。非常に楽しみです。

23:44 fenrir が投稿 : 固定リンク | | | トラックバック
このエントリーのトラックバックURL: https://fenrir.naruoka.org/mt/mt-tb.cgi/616