五目並べのAIを作ってみる[PHPでニューラルネット]

こんにちはみなさん

機械学習の理解のため、PHPでニューラルネットを書いてみることをしてみましたが、ここらで強化学習にでも手を出しておきましょう。
とは言っても、実際にはそれほど強いものができませんでしたのが、とりあえず現状できているところまで晒し上げようと思います。

今回五目並べを選択したのは、これを研修課題として出したところ、２ヶ月たってもできなかったというので、そんなことはないだろうと思ってたら、２時間位でできてしまったので、それなら機械学習の例題にしてしまおうと考えただけです。

# 強化学習

強化学習の詳しい解説については、先人がおりますので、そちらに丸投げしてサボります。
http://qiita.com/icoxfog417/items/242439ecd1a477ece312

大雑把に強化学習は現在の状況に対して、次の行動を機械が自発的に選択できるようになる学習方法で、以下のような過程を辿ります。

1. はじめはある状況に対してランダムに行動する
2. ある行動を取ると報酬が得られることがある
3. 報酬が得られる行動を取るようになる

これもはある程度人間の行動も近いところがあります。
例えば、１０ｍ先で不良がたむろしていたら、別の道を選ぶでしょうが、これは現在の状況を視覚で取得し、それに対して行動を選択しているわけです。

## 行動価値関数

現在の状況に対して、どういう行動を取ると、どれだけの価値が得られるかを表す関数を行動価値観数と呼び、現在の状況を$s$、行動を$a$とすると、行動価値関数は$F(s, a)$と表せます。
そして、この行動価値関数$F(s, a)$が最大化するように$a$を選ぶようにします。

しかしながら、当然行動価値関数がどういう形をしているかなんかわかりません。
そこで、「とりあえず」適当に行動価値関数を決めてみて、入力を現在の状況、出力をそれに伴う行動を「とりあえず」実行してみて、その結果発生する報酬から、今取った行動がその報酬に応じた価値を持つように$F(s, a)$を修正していきます。

今回は、この行動価値関数をニューラルネットで近似することにします。

## 過去の行動に対する報酬

何事も積み重ねが大事、とはよく言いますが、ある状況に対して取った行動により、即報酬がもらえるとは限りません。通勤時間中、一歩一歩１００円が落ちていることなんてありえないわけです。
大抵は報酬を得るために事前に準備を行い、満を持して報酬を得るわけです。
逆に、何か失敗をした場合、まさに失敗に至った行動だけではなく、それに至るまでに取ってきた行動もまた、失敗につながる行動であるとみなして良いでしょう。

今回は超簡略化して、ある時刻に報酬$R$を取得したとき、その時の行動価値関数$F_t(s, a)$を

```math
F_t(s, a) = R
```
であるとしましょう。で、報酬確定した際の一つ前の報酬を

```math
F_{t-1}(s', a') = \gamma F_t(s, a) = \gamma R
```
とします。ここで、$\gamma $は1に近い値であるとします。
すると、$n$回前の行動価値関数の値を

```math
F_{t-n} (s, a) = \gamma ^ n R
```
と考えることができます。
こうして報酬が発生した時点で、過去の行動に対する報酬を決めてやります。

# 五目並べAIの教育

今回のソースコード全体は以下のとおりです。
https://github.com/niisan-tokyo/gomokunarabe

## 五目並べのルール

今回の五目並べですが、ルールは縦横斜めのいずれかに石を５個並べられたほうが勝ち、という単純なもので、禁じ手とか一切なしです。
先攻超有利なルールですね。
その他は以下のとおりです。

- 盤面のサイズは7X7
- 先攻は白、後攻は黒 ( 普通逆だった。。。 )

## 報酬

報酬は以下のとおりです

|  | 白 ( 先攻 ) | 黒 ( 後攻 ) |
|:-:|:-:|:-:|
| 白が勝つ | 2 | -2 |
| 黒が勝つ | -2 | 2 |
| 引き分け | 1 | 1.5 |

引き分け次に黒のほうが報酬が大きいのは、黒がそもそも勝ちにくいので、ちょっと報酬を高めに設定しています。
これがうまい手段かどうかはわからないですが。

## 行動価値関数

さて、行動価値関数$F(s, a)$がどのようなものなのかですが、ここに現在の状態を入力してみます。すると、$G(a) = F(s, a)$みたいな感じになって、行動$a$だけの関数になります。
行動$a$とは、要するに盤面に自分の意志を置く行為ですので、色んな所に石をおいたと仮定したとき、$G(a)$が最大になる行動$a$が取るべき手段だと判断させます。

そんな$F(s, a)$をニューラルネットで近似してみます。
各層のパラメータを以下のようにしてみました。

|  | 出力次元数 | 使用関数 |
|:-:|:-:|:-:|
| 第0層 ( 入力 ) | 50 | - |
| 第１層 | 64 | ReLU |
| 第2層 | 128 | ReLU |
| 第3層 | 64 | ReLU |
| 第4層 ( 出力 ) | 49 | HyperboricTangent |

まず、入力の次元数が49( = 7 x 7)ではなく、50になっています。
これは、盤面の状態の数49に加え、自分が先攻なのか後攻なのかを表す状態を加えているからです。
出力は各盤面の位置に石を置くとしたときにどれだけの価値があるかを表しています。
間の層の次元層や使用関数は、**勘**です。

## 報酬と損失関数

さて、強化学習中にゲームが終了すると、その状況に応じて報酬$R$が付与されます。
報酬が付与されたときの状態と行動を$s_n, a_n$としたときの行動価値が報酬と同一であるべきだとしますと、損失関数$L$は

```math
L = \frac {1}{2} (F(s_n, a_n) - R)^2
```
こんな感じで置くことができます。
$a_n$以外の行動を取ったとした場合の誤差も欲しいところですが、あくまで今回取った行動のみに焦点を当てるため、今回は無視します。
微分値に関しては以下のとおりです。

```math
\frac{\partial L}{\partial a} = \begin{cases}
F(s_n, a_n) - R & (a = a_n)\\
0 & (a \neq a_n)
\end{cases}
```
これをもとに、各報酬が発生するごとに、$F(s, a)$を修正していきます。

## ソースコード

ソースは先に提示したgithubのリポジトリに全部あります。
操作の方法は簡単で、`$ php train.php`というコマンドを打つと、学習が始まります。
あとは待つだけです。

適当に層数を変えたり、次元数を変えたりすると、学習効率が変わるかもしれませんが、時間がないので試していません。
というより、私のMacが轟音を上げ始めるため、あまり酷使したくないというのが本音です。
いろいろな小細工があ入りますが、ポイントは以下のとおりです。

- 実際に学習を行うエージェントは先攻・後攻で同一のものを使用している
- 報酬の付与回数で学習を切っている　( 学習終了までの行動数は不定 )
- ある程度の公平性を保つため、ランダムに幾つか石をおいてから開始している
- 学習終了後、ニューラルネットの各層の重み情報は/dest 配下に格納される

# 結果

とりあえず、学習終了後に先攻後攻ともに機械にやらしてみて、経緯を見てみましたが。。。

![game.gif](https://qiita-image-store.s3.amazonaws.com/0/102182/4e30c6a0-a153-4283-6f6b-30ac3895b4ff.gif)


とりあえず並べようという方向に向かって入るようですが、いかんせんお互いひたすら並べようとするだけになっています。
まだ、相手を邪魔するという概念を取得していない模様です。
ちなみにこのデモは、学習後に`$ php battle.php`と入れてやれば動きます。

# まとめ

とにかく大変だったのは以下の問題です

- 関数は何を選べばいいのか
- 層数はいくつくらいがいいのか
- 次元数はいくつくらいがいいのか
- 勝敗は何回発生すればいいのか
- etc...

これらは全てパラメータの調整部分になります。
ロジックを組むだけならそんなに難しくはないのですが、なんせパラメータ一つで収束したりしなかったりします。
機械学習って、こういう地味なパラメータ調整をちゃんとやっているんだなぁとなんとなく感動したりしています。

それにしても機械学習系の記事って、書くの大変ですね。。。
今回は以上となります。

# 参考

[強化学習で考えるギャンブラーの最適行動](http://kivantium.hateblo.jp/entry/2015/09/29/181954)
[強化学習](http://www.sist.ac.jp/~kanakubo/research/reinforcement_learning.html)