とりあえずなんでもいいからやってみようということで Tesauro の論文(*)からヒントを得て TD(λ) + バックプロパゲーションという構成で実装してみました。

(*) http://www.research.ibm.com/massive/tdl.html

ソースは svn で見ることができますが、ドキュメントが皆無なのであまり意味ないかもしれません。

% svn co https://kserver.panicode.com/panicode/reversi/trunk reversi

まずは構造の説明から。 TD(λ) は経験からモデルを学習するモンテカルロ法とエピソードの終わりを待つことなく既存の推定価値から推定価値を更新するダイナミックプログラミングを組みあわせた手法です。何万エピソードもゲームを経験し、逐一推定価値を更新していくことによって、知識なしの状態から適切な推定価値関数を見いだすのが今回の目標です。推定価値の更新は現在の推定価値と行動 a のあとの状態の推定価値の誤差と行動 a による報酬を用いて行います。誤差計算はバックプロパゲーションで行います。

ニューラルネットワークはフィードフォワード型で、 input に 192 ユニット、 hidden に 128 ユニット、 output に 2 ユニットになっており、それぞれ、 input は empty に 1, 0, 0 、 black に 0, 1, 0 、 white に 0, 0, 1 と忠実に表現した 3 ユニット * 64 で、 hidden は適当、 output は black の勝率と white の勝率になっています。目標出力（報酬）は black が勝った場合に 1, 0 、 white が勝った場合に 0, 1 、 引き分けの場合に 0.5, 0.5 を与え、それ以外の場合はなしです。方策は ε グリーディーです。

とりあえず基本的な基盤ができた状態で 10 万エピソード学習させたやつが以下。リバーシのルールやニューラルネットワークの計算部分を JavaScript で実装しました。強化学習によって得られた学習結果は全てニューラルネットワークの weights に帰結するので、それを別ファイルに記録して .js 形式に変換して読みこませています。グリーディー方策ですが、探索は一切していません。 KnightCap という td chess は minmax 等を行ってある程度強くしているみたいですが、それは強化学習的でないのとあまりヒューリスティックな手を期待できないのに加えて、そもそもニューラルネットワークの計算を evaluate として minmax するとめちゃくちゃ重いので使っていない次第です。とはいっても単なるニューロンの計算とは思えぬほどちゃんとした手を打ってきます（序盤は）。

http://www.panicode.com/software/reversi/js/js-reversi-r1.html

Firefox 2.0 で動作確認しています。

で、今現在おそらく問題になっているのが、汎化能力とか過学習とか局所解。おそらく勾配法や方策を改良すればまだまだ改良できると思うので、このまま研究を続けます。