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

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

概要

現代の将棋AIには、

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

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

グリッドサーチ
Hyperopt
Optuna
SPSA

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

グリッドサーチ

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

利点:

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

欠点:

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

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

Hyperopt

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

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

Optuna

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

将棋AIの実験でも、

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

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

SPSA

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

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

実装例

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

実務上の注意

長時間条件と短時間条件で最適値がずれる
探索パラメータ単体ではなく、評価関数との相性を見る必要がある
ノイズが大きいので、最終候補は別条件で再検証した方がよい

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