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

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

## 概要

現代の将棋AIには、

- [Null Move Pruning](/shogi/shogiwiki/search/null-move-pruning/)
- [Late Move Reductions](/shogi/shogiwiki/search/late-move-reductions/)
- [Aspiration Windows](/shogi/shogiwiki/search/aspiration-windows/)
- [時間管理](/shogi/shogiwiki/search/time-management/)

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

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

- グリッドサーチ
- Hyperopt
- Optuna
- SPSA

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

## グリッドサーチ

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

利点:

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

欠点:

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

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

## Hyperopt

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

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

## Optuna

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

将棋AIの実験でも、

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

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

## SPSA

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

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

## 実装例

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

```python
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 の最小イメージは次のようになる。

```python
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
```

## 実務上の注意

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

## 関連項目

- [探索](/shogi/shogiwiki/search/)
- [時間管理](/shogi/shogiwiki/search/time-management/)
- [Null Move Pruning](/shogi/shogiwiki/search/null-move-pruning/)
- [Late Move Reductions](/shogi/shogiwiki/search/late-move-reductions/)
- [定跡自動生成](/shogi/shogiwiki/search/joseki-automatic-generation/)

## 参考にしたホームページ

- [scikit-learn.org: Sklearn.Model Selection.Gridsearchcv.Html](https://scikit-learn.org/stable/modules/generated/sklearn.model_selection.GridSearchCV.html)
- [hyperopt.github.io: Hyperopt](https://hyperopt.github.io/hyperopt/)
- [optuna.org: Optuna.Org](https://optuna.org/)
- [Stockfish Docs](https://official-stockfish.github.io/docs/stockfish-wiki/Regression-Tests.html)
- [やねうら王公式サイト: %E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF%E3%83%BC%E5%B0%86%E6%A3%8B%E5%85%A8%E8%88%AC](https://yaneuraou.yaneu.com/category/%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF%E3%83%BC%E5%B0%86%E6%A3%8B%E5%85%A8%E8%88%AC/)