TadaoYamaokaの開発日記

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

PUCTの定数のベイズ最適化

AlphaZeroの論文では、PUCTの定数C_{PUCT}を以下の式で、親ノードの訪問回数に応じて動的に調整を行っている。

U(s,a)=C(s)P(s,a)\frac{\sqrt{N(s)}}{1+N(s,a)} \\
C(s)=\log{\frac{1+N(s) + C_{base}}{C_{base}}}+C_{init}
この式で現れる定数C_{base}C_{init}は、疑似コードでは以下のように定義されている。

    # UCB formula
    self.pb_c_base = 19652
    self.pb_c_init = 1.25

私が実験しているdlshogiでも上記の式を適用することで効果があるか試してみた。

報酬によるスケーリング

AlphaZeroは、報酬(負けと勝ち)を-1、1で与えているが、dlshogiでは、0、1で与えているため、スケールを変更する必要がある。
定数C_{PUCT}の理論値は、報酬が[-1,1]の場合は2で、[0,1]の場合は1となる。
したがって、およそ半分になるように調整すればよい。

測定結果

以下の通り、手動でいくつかの組み合わせで、GPSfishと1手3秒で100回対局した勝率を測定した。

c_base c_init 勝率
変更前(C_PUCT=1) 54%
25000 0.8 65%
20000 0.7 62%
30000 0.85 56%
20000 0.8 57%
30000 0.8 66%

考察

いずれの組み合わせでも、変更前のC_{PUCT}が固定値1の場合より、勝率が高くなっている。
勝率が最大の組み合わせは、c_base=30000、c_init=0.8であった。
C(s)をグラフにすると以下のようになる。
f:id:TadaoYamaoka:20181213001907p:plain

自己対局でモデルの学習を長時間行っても勝率は少しずつしか変わらなかったが、探索のパラメータを変えるだけで10%以上勝率が上がることがわかった。
今までは探索パラメータを手動で適当に決めていたが、強くするには探索のパラメータの調整も重要であると気づかされた。

そこで、ベイズ最適化を使って、探索パラメータをちゃんと調整することにした。

ベイズ最適化

ベイズ最適化を使うことで、既知の説明変数と目的変数から、確率的に目的変数が最大となる説明変数の組み合わせ候補を求めることができる。
ベイズ最適化の理論を正確に理解して実装するのは大変なので、こちらのページにあったPythonのコードを使用させてもらった。

以下のようにして、次の実験候補を求めることができる。

import numpy as np

from bayesianoptimization import bayesianoptimization

X = np.random.rand(100, 2) * [1, 3] + [0.5, 1]
X_train = np.array([[0.8, 2.5], [0.7, 2.0], [0.85, 3.0], [0.8, 2.0], [0.8, 3.0]])
y_train = np.array([0.65, 0.62, 0.56, 0.57, 0.66])

selected_candidate_number, selected_X_candidate, cumulative_variance = bayesianoptimization(X_train, y_train, X, 2)

selected_X_candidateに説明変数の候補が格納される。

array([0.70598003, 2.04039803])

候補となった条件で、実験を行い、その結果を追加して、同様に次の候補を求めて実験すればよい。

変数の正規化

c_baseの値の桁がc_initに比べて大きいため、適切に正規化しておく必要がある。
上記のコードでは、c_baseを1/10000にしている。勝率も%ではなく、[0,1]の範囲で与えている。
Xは、ランダムにサンプリングした仮想的な候補だが、サンプリングの範囲は、c_baseを[1.0,4.0]、c_initを[0.5,1.5]の範囲でサンプリングしている。

ベイズ最適化で求めた候補の実験結果

実験した結果は以下の通りとなった。

c_base c_init 勝率
20403.9803 0.70598003 59%

予測はしていたが、1回の実験では最大にはならなかった。
そもそも100回の対局では誤差も大きく、確率的な事象であるため、1回で最適な値は求まらない。

繰り返し実験を行う必要があるが、今後は自動的に調整できるような仕組みを構築したい。