AlphaGo Zeroの論文を読むその4(自己対局)

自己対局パイプライン

自己対局パイプラインは、3つの主要な部分から構成される。

最適化
評価
自己対局

これらは並行で実行される。

最適化

ミニバッチサイズ：2,048 (32バッチずつ別々のGPUで実行)
ミニバッチデータは直近50万の自己対局のすべての局面からランダムでサンプリング
モーメントありのSGDで最適化(モメンタムパラメータ=0.9)
学習率は以下の通り徐々に下げる

1000ステップ	学習率
0-400	$10^{-2}$
400-600	$10^{-3}$
>600	$10^{-4}$

損失関数には、policyの交差エントロピーとvalueの平均二乗誤差の和を使用
policyの交差エントロピーとvalueの平均二乗誤差は等しく重み付けする
L2正則化を行う(c= $10^{-4}$ )

損失関数を式にすると以下の通り
$l=(z-v)^2 - {\bf \pi}^T log {\bf p} + c\|\theta\|^2$
zは勝敗(-1,1)、vはvalue、 ${\bf \pi}$ はモンテカルロ木探索で求めた局面の遷移確率、 ${\bf p}$ はpolicyの遷移確率、 $\|\theta\|^2$ はネットワークのパラメータの2乗ノルム

自己対局1,000回ごとにチェックポイントを設ける
チェックポイントで次の自己対局で使用するか評価を行う

評価

チェックポイントで現在の最良のネットワークと比較して評価する
モンテカルロ木探索アルゴリズムで最良のネットワークと400回対局を行う
1手1,600シミュレーション
温度パラメータは $\tau \to 0$ とする(最大の訪問回数のノードを選択)
最良のネットワークに55%以上勝利した場合、それを最良のネットワークとし、その後の自己対局で使用する

自己対局

評価で選択した最良のネットワークを使ってデータを生成する
各イテレーションでは、25,000ゲーム、1手1,600シミュレーションのモンテカルロ木探索で自己対局を行う

各ゲームの最初の30手は温度 $\tau=1$ に設定する(訪問回数の応じた確率で着手し、局面にバリエーションを持たせる)

残りの手は、温度 $\tau \to 0$ に設定する
ルートノードの事前確率にディリクレノイズを加える
具体的には、 $P(x,a)=(1-\epsilon)p_a + \epsilon \eta_a, \eta \sim Dir(0.03), \epsilon=0.25$
このノイズは、全ての手を試すために行うが、探索することで悪手は選択されなくなる

計算資源を節約するため、明らかに負けの場合投了する
閾値は誤認率を5%以下に保つように自動的に決定する
誤認率を測定するため10%のゲームは終局までプレイする

将棋AIに応用する際の考察

損失関数について

policyの交差エントロピーは、式では教師データの指し手ではなく、遷移確率 $\pi$ を使用していますが、温度パラメータを0にして自己対局しているので、実際は打ち手のみを学習することになるので、教師データとして打ち手をone hotベクトルとしたsoftmax交差エントロピーを使っていると思われます。

valueの損失には平均二乗誤差が使われています。
出力の活性化関数がtanhの場合は、交差エントロピーは負の値に使えないので、平均二乗誤差を使用していると思われます。
報酬が(-1,1)の単位スケールなのでvalueの平均二乗誤差とpolicyの交差エントロピーと同じ重みにするのは合理的だと、書かれていましたがちょっと意味が分かりませんでした。

なお、将棋AIでは、評価関数の出力にsigmoidを使用して、損失には交差エントロピーを使うのが主流になっています。

温度パラメータについて

局面のバリエーションを増やすために、自己対局の最初30手は温度パラメータが調整されています。
将棋AIでは、初期局面集を使って局面バリエーションを増やすことが行われています。
初期局面集の質が良ければその方がバリエーションを増やすには良いと思います。
初期局面集から開始して温度パラメータ調整ありで、数手を指すのが良いかもしれません。

残りの手は、温度パラメータを0にして最大訪問回数のノードを選択しています。
それではpolicyが予測する限られた手以外を探索しなくなるので、ルート局面のみノイズが加えられています。
policyは読み抜けをなくすこと重要なので、ノイズを加えることで対策しているようです。
ルート局面以外にもノイズを加えると探索の幅が広がりすぎるので、ルート局面のみに限定しています。
ノイズを加えることで、ついでにある程度打ち手にランダム性を加えることもできます。

ディリクレノイズについて、K次元のディリクレ分布は、
$Dir({\bf p}|{\bf \alpha})=\frac{\Gamma(\sum_{k=1}^K \alpha_k)}{\prod_{k=1}^K \Gamma(\alpha_k)} \prod_{k=1}^K p_k^{\alpha_k-1}$
で表されるので、出力ラベル数を次元としたディリクレ分布に従って生成した値をノイズに加えるということだと思います。
（合っているか自信がありません。間違っていたら教えてください。）

投了の閾値について

投了の閾値を自動で決定しているのはよく考えられていると思いました。
自分なら適当に決めていると思います。

対局数について

モンテカルロ木探索で自己対局をするには相当な時間がかかります。
個人で試そうと思ったらどこかで割り切りが必要そうです。

続く

2017/10/24 追記

ディリクレ分布について、グラフにして確かめてみた。
Dir(0.03)をα=0.03の対称ディリクレ分布と解釈すると、2次元の場合グラフは以下のようになる。
f:id:TadaoYamaoka:20171024210134p:plain

octaveで以下のようなスクリプトでプロットした。

alpha = [0.03 0.03];
x1 = linspace(0,1,101);
x2 = linspace(0,1,101);
[X1, X2] = ndgrid(x1, x2);
bad = (X1+X2 > 1 | X1+X2 < 0.98); X1(bad) = NaN; X2(bad) = NaN;

betaConst = exp(sum(gammaln(alpha))-gammaln(sum(alpha)));
F = (X1.^(alpha(1)-1) .* X2.^(alpha(2)-1)) / betaConst;

figure, surf(X1,X2,F,'EdgeColor','none');
xlabel('x1'); ylabel('x2'); zlabel('f(x1,x2)');

参考：
http://jp.mathworks.com/matlabcentral/newsreader/view_thread/139363

また、以下のようなスクリプトで5次元のディリクレ分布に従ってランダムに値を10個生成すると、以下のような値が生成された。

function r = drchrnd(a,n)
% take a sample from a dirichlet distribution
p = length(a);
r = gamrnd(repmat(a,n,1),1,n,p);
r = r ./ repmat(sum(r,2),1,p);
endfunction

A = drchrnd([0.03 0.03 0.03 0.03 0.03], 10)

参考：
To Generate Random Numbers from a Dirichlet Distribution | Yi Wang's Tech Notes

生成された値

  6.9672e-006  7.3486e-014  1.0742e-012  1.1276e-047  9.9999e-001
  5.5256e-009  1.5200e-037  9.9999e-001  6.5353e-006  4.2202e-034
  9.9999e-001  5.9592e-006  6.0206e-009  4.5226e-014  2.7251e-012
  2.3452e-025  5.0914e-011  9.9862e-018  1.0000e+000  2.7700e-043
  1.0641e-033  2.6900e-015  3.5634e-008  4.1919e-001  5.8081e-001
  1.5973e-010  2.2561e-010  1.8230e-023  6.8685e-045  1.0000e+000
  1.2859e-044  7.1633e-009  8.1942e-005  2.2902e-019  9.9992e-001
  7.8554e-001  7.7956e-018  1.4490e-005  2.1445e-001  3.6593e-023
  1.8477e-006  6.7389e-014  9.9992e-001  2.3746e-005  5.3420e-005
  3.8418e-039  2.9569e-011  9.9991e-001  9.9550e-025  9.3844e-005

以上の結果から、α=0.03のディリクレ分布はどれか一つの要素が1になり、他が0になるような分布になっていることがわかる。
つまり、ルートノードではどれか一つの手をランダムで選びやすくしている。
実装上は、ディリクレ分布を計算しなくてもランダムで1手を選んでその手のみη=1にしても問題ないかもしれない。

TadaoYamaokaの開発日記

個人開発しているスマホアプリや将棋AIの開発ネタを中心に書いていきます。