TadaoYamaokaの日記

山岡忠夫Homeで公開しているプログラムの開発ネタを中心に書いていきます。

学習中と並列で自己対局

先日の日記で、学習中にも自己対局を行うようにしたことを書いたが、現在dlshogiでは自己対局で生成した局面は過去10サイクル分をすべて学習に使うようにしている。
(AlphaZeroのようにサンプリングしないですべての局面を使うのは、Actor-Criticで敗着となった手(学習したい手)を学習する機会が減りそうという理由からだが、どっちがよいかは分かっていない。)

そのため、学習時間に依存して生成する局面が増えるので、次のサイクルで学習する局面が増えて、それにより学習時間も増える。
そうすると生成する局面も増えるので、どんどん学習時間伸びていくのではないかという素朴な疑問が起きる。

学習する局面に対して、学習中に自己対局で生成する局面は相対的に少ないので、直感的に収束しそうだが、念のため計算してみた。

以下、数学の問題です。高校数学を復習したい方はどうぞ。

収束判定問題

純化のために、過去2サイクル分だけ学習に使うとした場合、Tサイクル目の学習時間t_Tと学習中に生成する局面x_Tは、
 \displaystyle
t_T=a(x_{T-1}+c) \\
x_T=bt_T
となる。ここで、aは学習速度(時間/局面)、bは局面生成速度(局面/時間)、cは1サイクルの学習中以外で生成する局面数(固定値)。

x_{T-1}=bt_{T-1}を、上式のt_{t-1}に代入すると、
 \displaystyle
t_T=a(bt_{T-1}+c)
となる。

よって、T=0のとき、
 \displaystyle
t_0=ac

T=1のとき、
 \displaystyle
\begin{eqnarray}
t_1&=&a(bt_0+c) \\
&=& ac(ab+1)
\end{eqnarray}

T=2のとき、
 \displaystyle
\begin{eqnarray}
t_1&=&a(bt_1+c) \\
&=& ac(ab(ab+1)+1) \\
&=& ac((ab)^2+ab+1)
\end{eqnarray}

T=3のとき、
 \displaystyle
\begin{eqnarray}
t_3&=&a(bt_2+c) \\
&=& ac(ab(ab(ab+1)+1)+1) \\
&=& ac((ab)^3+(ab)^2+ab+1)
\end{eqnarray}

となる。
つまり、
T=nのとき、
 \displaystyle
\begin{eqnarray}
t_n&=&a(bt_{n-1}+c) \\
&=& ac((ab)^n+(ab)^{n-1}+\cdots+ab+1)
\end{eqnarray}
となり、等比級数和の形になっている。

等比級数の和は、高校の数学で習った通り(忘れてたけど)、
 \displaystyle
\frac{1-(ab)^n}{1-ab}
となるので、|ab|<1のときに、
 \displaystyle
\frac{1}{1-ab}
となり、収束する。

dlshogiでは、学習速度aは、3.9 \times 10^{-4}(秒/局面)、学習中の局面生成速度bは、39.6(局面/秒)なので、
 \displaystyle
ab\simeq0.015<1
となり収束する。

10サイクルにした場合も、基本的に同じ問題に落とし込めるので省略する。