ノイズと高次手法の限界

前提知識：SPSA、勾配推定と摂動、ゲインスケジュール

このページの要点

• エンジン対局の目的関数は極端にノイジーであり、一次の SPSA ですら「運が大きく関与する」レベル
• 二次手法（2SPSA、Newton 法、BFGS）は Hessian 推定にさらに多くのサンプルを要求するため、ノイジーな環境では事実上使えない
• Fishtest は per-axis \(c_i\) パラメータを通じて暗黙的な対角準 Newton ステップを実現し、明示的な Hessian 計算を回避している
• 「真の収束」は現実のリソース制約では達成不可能であり、「最適解からの指定距離以内に指定確率で到達する」戦略が実用的

ノイズの本質

なぜエンジンチューニングは極端にノイジーなのか

通常の最適化問題と異なり、将棋やチェスのエンジンのパラメータチューニングでは、 目的関数の 1 回の「評価」が対局の勝敗という離散的で巨大な分散を持つ確率変数です。

通常の最適化問題:
  y = f(x) + ε,  ε ~ N(0, σ²)  ← ノイズは連続的で比較的小さい

エンジンチューニング:
  y ∈ {0, 0.5, 1}（負け/引き分け/勝ち） ← 3 値の離散出力
  Var[y] ≈ p(1-p) ≈ 0.25（勝率 50% 付近で最大）

1 局の結果から得られる勾配情報は極めて限られています。 SPSA では 2 局（\(\theta^+\) と \(\theta^-\)）の差分から \(p\) 次元の勾配を推定するため、 信号対雑音比（SNR）は本質的に低くなります。

Fishtest 開発者の見解

Fishtest（Stockfish テスティングフレームワーク）の主要開発者である vdbergh は、 2SPSA（二次 SPSA）の導入を提案した Issue #2126 に対して、以下のように明確に否定しています。¹

The Fishtest setting is extremely noisy. So noisy in fact that the regular 1SPSA algorithm barely works (a lot of luck is involved to get anything out of it). The noise would completely trash any second order algorithm.

— vdbergh, fishtest Issue #2126（2024年8月3日）

また、Issue #535 における MJZ1977（SPSA の実践経験者）のコメントも、ノイズ問題の深刻さを裏付けています。²

From my experience on SPSA, the main problem is the high level of noise in the results.

— MJZ1977, fishtest Issue #535（2020年2月11日）

MJZ1977 は反復あたり最低 100 局を推奨し、それ未満では収束が誤った方向に進む可能性があると警告しています。

ノイズの定量的理解

典型的なチェスエンジンの対局で、パラメータを \(\pm c\) だけ変化させたときの Elo 差が約 5 Elo だとすると、 勝率の差は約 0.7% です。

\[ \Delta W = \frac{5}{400 \ln 10} \approx 0.007 \]

一方、1 局の結果の標準偏差は約 0.5 です。 2 局ぶんの差分に対する SNR は次のようになります。

\[ \text{SNR} = \frac{\Delta W}{\sigma / \sqrt{n}} = \frac{0.007}{0.5 / \sqrt{2}} \approx 0.02 \]

信号はノイズの 50 分の 1 しかありません。 一次の SPSA が「運が大きく関与する」と言われるのは、この比の上で更新を積み重ねているからです。

なぜ二次手法が使えないのか

二次 SPSA（2SPSA）の理論

Spall（2000）が提案した 2SPSA は、勾配と同時に Hessian 行列も同時摂動で推定するアルゴリズムです。³

• 1SPSA（一次）：2 回の評価で \(p\) 次元の勾配を推定
• 2SPSA（二次）：4 回の評価で \(p\) 次元の勾配と \(p \times p\) の Hessian を推定

学術的には 2SPSA は 1SPSA の 5〜10 倍の効率を達成できるとされています。⁴

2SPSA provides a considerable reduction in the loss function value for the same number of measurements used in 1SPSA, with 1SPSA needing approximately five–ten times the number of function evaluations used by 2SPSA to reach the levels of accuracy shown.

— Zhu & Spall (2002)

エンジンチューニングで 2SPSA が破綻する理由

理論的な優位性にもかかわらず、エンジンチューニングでは以下の理由で 2SPSA は実用的ではありません。

1. Hessian 推定のノイズ感度

Hessian の推定には勾配推定よりもさらに高い精度が必要です。 勾配推定が既に「運が大きく関与する」レベルのノイズに晒されている状況では、 二次の情報（曲率）を信頼性高く推定することは不可能です。

一次情報（勾配）の推定:
  Var[ĝ_i] ∝ σ² / c_k²
  → 既にノイジーだが、反復平均で緩和可能

二次情報（Hessian）の推定:
  Var[Ĥ_ij] ∝ σ⁴ / c_k⁴
  → ノイズが勾配の 2 乗で増幅される
  → エンジンチューニングの σ² では壊滅的

2. ill-conditioned Hessian の問題

2SPSA では Hessian の逆行列 \(\hat{H}^{-1}_k\) を計算しますが、 推定 Hessian がわずかに真の Hessian からずれただけで、 逆行列の誤差は条件数に比例して増幅されます。⁴

\[ \frac{|\hat{H}^{-1} - H^{-1}|}{|H^{-1}|} \approx \kappa(H) \cdot \frac{|\hat{H} - H|}{|H|} \]

エンジンのパラメータ空間では、感度が大きく異なるパラメータが混在する （ピース評価値 vs 枝刈り閾値など）ため、Hessian の条件数は大きくなりがちです。

3. 計算コストの問題

4 回の評価は、ノイジーな環境で Hessian を推定するにはまったく不十分です。

他の二次手法も同様

Newton 法や BFGS などの準 Newton 法は、正確な勾配（またはそれに近い推定）を前提としています。 SPSA 環境ではこの前提が成り立ちません。

Adam は深層学習で広く成功していますが、 深層学習のミニバッチ勾配と SPSA の 2 局からの勾配推定では、ノイズのレベルが根本的に異なります。

深層学習: ミニバッチサイズ 32〜256 サンプルから勾配を推定 → SNR は比較的高い
SPSA: 2 ゲーム（実質 1 サンプル）から p 次元の勾配を推定 → SNR ≈ 0.02

実際、チェスエンジン開発コミュニティでは以下の区別が明確にされています。⁶

• Texel Tuning（棋譜データベースからの教師あり学習）：解析的勾配が計算可能 → Adam、Adagrad が有効
• ゲームプレイベースの SPSA：勾配は対局結果からのみ推定 → 適応的学習率は勾配推定の根本的問題を解決しない

Arasan uses ADAM and Ethereal uses Adagrad with standard gradient descent implementation, not SPSA.

— jdart, TalkChess

つまり、Adam が成功しているのは SPSA の勾配推定と組み合わせた場合ではなく、 バックプロパゲーション的に正確な勾配が得られる場合のみです。

Fishtest の暗黙的な対角準 Newton

per-axis \(c_i\) による曲率の吸収

Fishtest は明示的な Hessian 計算の代わりに、パラメータごとの摂動スケール \(c_i\) を ユーザーが設定することで、暗黙的に曲率情報を組み込む設計を採用しています。

Fishtest の公式ドキュメントでは、この設計の理論的根拠を以下のように説明しています。⁷

Per-axis \(c_i\) encodes axis scale/curvature, yielding diagonal quasi-Newton steps in \(\theta\) even while tuning with a global learning rate.

— Fishtest Mathematics Documentation

仕組みは 3 段階です。

1. ユーザーが \(c_i\) を「\(\theta_i \pm c_i \Delta_i\) が数 Elo の差を生む」ように設定する
2. 正規化パラメータ \(\varphi_i = \theta_i / c_i\) では、すべてのパラメータが同じスケールになる
3. \(\theta\) 空間に戻すと \(\Delta\theta_i = r_i \cdot c_i \cdot g_{\varphi_i}\) となり、平坦な軸では大きな更新、急峻な軸では小さな更新になる

        二次手法の本来の目的:
        Δθ = -H⁻¹ ∇L   ← 曲率に応じてステップを調整

        Fishtest の暗黙的実現:
        Δθ_i = r · c_i · g_φ_i
              ≈ r · (1/√H_ii) · ∂L/∂θ_i   ← 対角近似

曲率を推定ではなく設定として与えるので、二次手法が破綻した三つの理由がそのまま裏返ります。

• 追加の対局が不要：Hessian 推定用の対局を実行しない
• ノイズ耐性：ユーザーの事前知識で曲率を「一度だけ」設定するため、ノイジーな推定に依存しない
• 計算オーバーヘッドなし：\(O(p^2)\) の行列演算が不要

ShogiArena での対応

ShogiArena では、ParamEntry の step と delta パラメータがこの役割を果たしています。

step: 摂動の大きさ（Fishtest の c_i に相当）
  → パラメータの感度に応じて設定

delta: 学習率スケール
  → パラメータごとの更新速度を調整

これらを適切に設定することで、暗黙的に曲率情報を組み込める

収束の限界

チューニングを止めるべき時点

ゲインスケジュールは無限回の反復を前提に設計されていますが、実際のチューニングは有限回で打ち切ります。 Stockfish のチューニング手法の原案者である Joona Kiiski（zamar）は、 収束の限界について以下のように述べています。⁸

After a while important variables stop approaching optimal values and "random walk" takes over and the strength starts to decrease. So the method doesn't converge and it needs to be stopped at "suitable moment".

— Joona Kiiski, Stockfish's Tuning Method（TalkChess, 2011年）

この現象は以下のメカニズムで発生します。

チューニング初期:
  ├─ 感度の高いパラメータ → 最適値に近づく ✓
  └─ 感度の低いパラメータ → ランダムウォーク ×

チューニング中期:
  ├─ 感度の高いパラメータ → 最適値付近で安定
  └─ 感度の低いパラメータ → まだランダムウォーク

チューニング後期:
  ├─ 感度の高いパラメータ → ランダムウォークに転落
  └─ 感度の低いパラメータ → ランダムウォーク継続
  全体 → 強度低下！停止すべきタイミング

精度と信頼度による目標設定

vdbergh の SPSA シミュレータ（spsa_simul）は、この問題に対して 「収束を目指さない」アプローチを提案しています。⁹

Due to resource constraints in chess tuning, no reasonable form of convergence is ever achievable, so the best approach is to plan for ending up within a specified distance from the optimum with a specified probability.

— vdbergh, spsa_simul README

• 精度（precision）：最適解からの目標 Elo 距離（デフォルト: 0.5 Elo）
• 信頼度（confidence）：目標達成の確率（デフォルト: 95%）

このフレームワークでは、固定ゲイン（\(\alpha = \gamma = 0\)）を使用し、 漸近的収束ではなく有限サンプルでの性能を最適化します。 ShogiArena の既定は Spall の推奨減衰（\(\alpha = 0.602,\ \gamma = 0.101\)）ですが、 algorithm.alpha と algorithm.gamma を 0 にすればこの固定ゲイン方針も選べます （ゲインスケジュール の「探索的」パターン）。

パラメータ数とスケーリング

パラメータ数が増えると、必要な計算量は急激に増大します。

vondele（Stockfish メンテナー）は nevergrad4sf で以下のように述べています。

Count on O(1M) games for convergence, even with few parameters.

— vondele, nevergrad4sf README

変数選択の重要性

パラメータ数の問題に対する Kiiski の解決策は「メタパラメータ」の導入でした。

Variable selection extremely important. Tuning each piece-square value separately doomed to fail — changing single value changes strength minimally. Instead using ampli-bias knobs proved successful.

— Joona Kiiski, TalkChess

個々のパラメータを直接チューニングする代わりに、 複数のパラメータに影響を与える少数の「制御ノブ」（ampli-bias 変換）を使うことで、 効果的にパラメータ空間の次元を削減しています。

代替手法との比較

Rémi Coulom（CLOP 開発者）の評価

SPSA has potential close to CLOP in performance, but main weakness is difficulty choosing good meta-parameters. In practice, impossible finding optimal SPSA meta-parameters.

— Rémi Coulom, TalkChess（2013年）

手法の位置付け

表のとおり、SPSA はノイズ耐性でもメタパラメータの扱いやすさでも他手法に劣ります。 それでも実運用で選ばれ続けているのは、分散テスティング環境との親和性があるからです。 Fishtest のように多数のワーカーが非同期で並列実行する環境では、 中央でモデルを保持する必要がなく、各ワーカーが独立に摂動対局を実行できる SPSA の単純さが効きます。

実践的な教訓

ck の大きさ

If after a few thousand games the values are barely changing at all, the tuning run is useless and should be stopped. This usually happens when the ck value is too low for the parameter changes to influence the tuning result more than random noise.

— Fishtest Wiki, Creating my first test

• ck が小さすぎる場合：パラメータ変化がノイズに埋もれ、更新がランダムウォークになる
• ck が大きすぎる場合：線形近似が破綻し、勾配推定にバイアスが生じる

チューニングの実用的な進め方

Fishtest コミュニティでの経験則をまとめると、次の 5 点になります。²

1. 少数の重要パラメータから始める：全パラメータを一度にチューニングしない
2. ck は「数 Elo の差を生む」レベルに設定：小さすぎるとノイズに埋もれる
3. 進捗を監視する：数千局を終えてもパラメータが動いていなければ、ck を上げるか中止する
4. LTC 回帰テストで検証：STC でのチューニング結果が LTC でも有効か確認する
5. 「適切なタイミング」で停止する：収束を待たず、強度のピークで停止する

参考文献

次に読む

→ LTC 回帰テスト：「適切なタイミング」の判定を自動化する手法。STC でのチューニング結果が LTC で劣化していないかの定期検証。