探索パラメーターを自動調整したい。

従来は、一つ一つのパラメーターを少し動かし、自己対局をさせて勝率を見ていた。

2015年当時、あの有名なPonanzaですら、それは同様であった。しかしやねうら王では、もっと雑に、すべてのパラメーターを同時にランダムに少しだけ動かして、それでそれぞれのパラメーターについて集計して、それぞれのパラメーターについて勝率が改善する方向に少しずつ動かすということをしていた。

当時、Ponanzaの作者の山本君からパラメーター調整はどうやってるの？と尋ねられた時に「すべてのパラメーターを同時にランダムに少し動かして、SGD(確率的勾配降下法)みたいなことをしている」と私は答えた。いまにして思うと、動かす方向を決める部分はSGDっぽいが、アルゴリズムの呼び名としては、SGDはちょっと違うかもしれない。

その後、チェスAIの世界ではパラメーターの自動調整は、SPSA（Simultaneous Perturbation Stochastic Approximation）という手法が主流になった。

いまやStockfishのfishtest(テスティングフレームワーク = 改良したあと強くなっているかを計測するためのフレームワーク)でもSPSAによるチューニングができるようになっており、また、OpenBenchというチェスAI用のフレームワークでは、SPSAによるチューニングが簡単に実施できるので、ほとんどのチェスAIは、このOpenBenchを利用して調整しているという状況らしい。

OpenBench
https://github.com/AndyGrant/OpenBench

それからすると、将棋AIは、そのような調整を簡単にできる標準的なフレームワークがなく、各々の開発者がそれぞれ自作しているような状況である。

・やねうら王では、パラメーターを少しずつランダムに動かした状態で対局させて、その結果の勝率を集計するスクリプトを自作して半自動で調整。(2015年)
・tanuki-シリーズの開発者の野田さんは、Hyperoptを使って調整するスクリプトを自作。(2017年)
・dlshogiの山岡さんは、dlshogiのためにOptunaで調整するスクリプトを自作。(2019年)

HyperoptもOptunaも、TPE(Tree-structured Parzen Estimator)というアルゴリズムを用いている。確率密度推定ベースのベイズ最適化で、理論的なことはわりと難しい。

難しすぎてこのブログでは、「ぜんぜんわからない俺たちは雰囲気でベイズ最適化をやっている」という雑コラを貼り付けてお茶を濁すぐらいのことしかできそうにない。

それはさておき、そのように、ベイズ最適化の中身を何一つ理解してなくとも、簡単に呼び出して使えるのがOptunaなのであるが、将棋AIの世界ではさほど取り入れられてはいない。

と言うのも、ベイズ最適化は、チェスAIや将棋AI(NNUE系)の探索パラメーターの調整とはあまり相性がよろしくないから…ではないかと個人的には思う。将棋AI(NNUE系)は、高次元で(パラメーターが多くて)、非連続でかつ、条件付き依存関係があるので、ベイズ最適化は不向きだろう。

チェスAIで使われているSPSAは、この問題を克服する。

それで、今回はこのSPSAのアルゴリズムについて、簡単に説明する。というか、アルゴリズム自体は1分で説明が終わるレベルの簡単さである

まず、現在のパラメーターをθとする。θは複数のパラメーターで構成されているので、ベクトルである。θ = (θ1 , θ2, …)とする。

θから、ちょっとだけ動かした状態で対局させる。

どう動かすかなのだが、ランダムに動かす。各次元ごとに+1か-1する。

つまり、 Δ = (+1, -1 , +1, +1, …)みたいに、ランダムな +1か -1 の要素からなる微小な方向を用意する。(このような+1と-1を1/2の確率でとる分布をRademacher(ラーデマッヘル)分布と言うらしい。)

そうは言っても、パラメーターごとにスケールが違うので、実際は、摂動幅 s = (5, 1, 2 , ..) みたいなパラメーターごとに動かす初期幅を用意する。これをΔに要素ごとに掛け算しておく。いま、要素ごとの掛け算は、アダマール積(⊙)を用いてs⊙Δ と書くことにする。

それで、θから +s⊙Δ と、その逆方向である -s⊙Δに動かして対局させる。摂動幅だけ動かせば勝率にわずかに影響することが前提としてある。逆に言うと勝率に影響する程度の大きさにsを調整しておかなければならない。

そして、仮に、+s⊙Δだけに動かしたら勝って、逆方向である-s⊙Δだけ動かしたら負けたとしたら、θを+s⊙Δ方向にほんの少し動かす。ここで動かす量を決めなければならないが、sが各パラメーターのスケールを表現しているので、これを掛け算しておきたい。そこで、ε = 0.0002 ぐらいとして、ε・s⊙Δ / 2だけ動かす。

たったこれだけである。

※ 分母を2で割っているのは、1変数のときにf'(θ) = { f(θ+ε) – f(θ-ε) } / 2ε と勾配を近似する(中心差分近似)ことがあるけど、今回やっているのは、これの多変数版だから同様に分母に2が出てきている。

※ ソースコード上はint(整数)のパラメーターであっても、SPSAフレームワーク上ではfloat(浮動小数点数)を用いて管理していることに注意すること。これにより、対局させるごとに少しずつ(1未満で)パラメーターが移動していき、大量に対局させた時に最適値付近に移動する。

実際は、パラメーター調整の初期段階では摂動幅は大きめにして、そこから徐々に(焼なまし法の指数冷却のように)下げていくのが好ましい。εも最初はもう少し大きく(10倍～100倍ぐらいで)しておき、そこから徐々に下げていくのが好ましい。

詳しい計算式はStockfishのfishtestの説明に書いてあるのでそちらも参考にして欲しい。

https://official-stockfish.github.io/docs/fishtest-wiki/Creating-my-first-test.html#tuning-with-spsa

やねうら王プロジェクトでは、今回、SPSAフレームワークを自作した。fishtestやOpenBenchを将棋AI向けに書き換えるぐらいなら、自作してやるわいと思い、ちゃちゃっと自作した。おかげでかなり使い勝手がいいものができた。これについては、また別の記事で詳しく書く。

この自作したSPSAフレームワークによって、やねうら王の探索パラメーターの全体的な最適化ができて、+R50ぐらい強くなったっぽい。これは、今日発行するやねうら王News Letterでやねうら王の支援者向けに配布する。

ともかく、SPSAという、誰でも思いつきそうなすごく単純なアルゴリズムで、(今回のような条件であるなら)ベイズ最適化よりうまく機能するというのだから驚きだ。

簡単に実装でき、他のゲームAIでもパラメーターの調整に使えるものなので、是非活用していただきたい。