探索パラメータの確率的最適化

探索パラメータの確率的最適化とは、枝刈り閾値、reduction 量、時間管理係数などの探索パラメータを、自己対局や対戦結果を使って自動調整する考え方である。

概要

現代の将棋AIには、

など、多数の探索パラメータがある。

これらは相互作用が強いため、人手の微調整だけで最適値を見つけるのは難しい。そのため、対局結果を評価関数として

グリッドサーチ
Hyperopt
Optuna
SPSA

などの手法で自動調整することがある。

グリッドサーチ

グリッドサーチは、候補値の組を総当たりで試す方法である。

利点:

実装が簡単
結果の再現性が高い

欠点:

次元が増えると試行数が爆発する
離散化の粒度に結果が依存する

少数パラメータの当たりを付ける用途には向くが、大規模調整には重くなりやすい。

Hyperopt

Hyperopt はベイズ最適化系のハイパーパラメータ探索ライブラリで、 TPE による探索がよく使われる。

総当たりより少ない試行で良い候補へ寄りやすく、探索パラメータの自動調整とも相性が良い。

Optuna

Optuna は Python から扱いやすい最適化フレームワークで、試行管理、枝刈り、可視化を含めた運用がしやすい。

将棋AIの実験でも、

対局ジョブを objective にする
短時間テストで粗く絞る
有望領域だけ長時間対局で再評価する

という使い方がしやすい。

SPSA

SPSA は Simultaneous Perturbation Stochastic Approximation の略で、多数のパラメータを少ない評価回数で動かせる最適化法である。

通常の有限差分で p 個のパラメータの勾配を近似しようとすると、1 回の更新におおむね 2p 回の評価が必要になる。SPSA では全パラメータを同時に + 方向と - 方向へランダムに揺らし、その 2 点の評価差から勾配を近似するため、パラメータ数に依存せず基本的に 2 回の評価で 1 回の更新ができる。

チェス界隈では Fishtest と結び付いて広く使われ、将棋AI界隈でも 2020 年代に導入が進んだとやねうら王公式サイトで言及されている。

将棋ソフトでは、評価関数の値を直接最小化するというより、候補設定 A と候補設定 B を同じ条件で対局させ、勝敗差を目的関数の noisy な観測値として使う ことが多い。開始局面、先後反転、持ち時間、引き分け規則を揃えないと、SPSA の更新が対局条件の偏りを拾いやすくなる。

dlshogi での利用

DeepLearningShogi には dlshogi/utils/spsa_usi_tuner.py があり、USI エンジンのパラメータを SPSA で調整するための補助スクリプトになっている。

このスクリプトでは、--params で

name:min~max:start[:c_end][:r_end][:type]

の形で調整対象の USI オプションを指定する。たとえば C_init、C_base、C_fpu_reduction、Softmax_Temperature のような PUCT 周辺パラメータや温度パラメータが対象になり得る。

対局は --openings で指定した SFEN 開始局面から行われ、候補設定の theta+、theta-、baseline との対局を集計する。スクリプト内では、alpha = 0.602、gamma = 0.101、A_ratio、sets_per_iter、repeat_per_pair などで SPSA の更新幅や評価局数を制御している。

これは、dlshogi における MCTS/USI パラメータ調整が、単発の手動チューニングではなく、開始局面付きの大量対局と確率的更新で行えることを示す例である。

実装例

Optuna を使った概念例は次のようになる。

import optuna

def objective(trial):
    null_r = trial.suggest_int("null_r", 2, 4)
    lmr_base = trial.suggest_float("lmr_base", 0.5, 2.5)
    fut_margin = trial.suggest_int("futility_margin", 50, 300)

    config = {
        "null_r": null_r,
        "lmr_base": lmr_base,
        "futility_margin": fut_margin,
    }
    return run_match_and_return_elo(config)

study = optuna.create_study(direction="maximize")
study.optimize(objective, n_trials=200)

SPSA の最小イメージは次のようになる。

theta = initial_params()
for k in range(1, 500):
    delta = random_sign_vector(len(theta))
    plus = evaluate(theta + ck(k) * delta)
    minus = evaluate(theta - ck(k) * delta)
    ghat = (plus - minus) / (2.0 * ck(k)) * delta
    theta = theta + ak(k) * ghat

実務上の注意

長時間条件と短時間条件で最適値がずれる
探索パラメータ単体ではなく、評価関数や方策・価値ネットワークとの相性を見る必要がある
ノイズが大きいので、最終候補は別条件で再検証した方がよい
開始局面、先後反転、持ち時間、スレッド数、GPU 数、定跡、引き分け規則を揃える必要がある
短時間・少局数の SPSA で得た値は、最後に固定局数テストや SPRT 形式の比較で確認した方がよい

探索パラメータの確率的最適化 search-parameter-optimization