分散削減テクニック

前提知識：SPRT、SPSA

対局スコアのばらつきを抑えると、Elo 推定の信頼区間を狭め、SPRT の判定や SPSA の勾配推定に必要な対局を減らせます。 共通乱数法（CRN）、先後を入れ替えるペアゲーム、複数の結果をまとめるバッチ処理を扱います。

分散が問題になる理由

エンジン対局の結果は本質的に確率的です。 同じエンジンペアでも、対局ごとに勝ち、引き分け、負けのいずれにもなります。

このばらつきは、次の推定や判定に影響します。

  • SPRT：判定に到達するまでの対局数が増加する
  • SPSA：勾配推定がノイズに埋もれ、最適化が不安定になる
  • Elo 推定：信頼区間が広くなり、実用的な判断が困難になる

CRN（共通乱数法）

原理

2 つのシステムを比べるとき、結果の差にはシステムの違いだけでなく、実験条件の当たり外れも混ざります。 Common Random Numbers（CRN） は、両者に同じ乱数列（ここでは同じ開始局面）を与えて、この共通の変動要因を相殺する手法です。

CRN なし:
  θ⁺ → 局面 A で対局 → スコア s⁺
  θ⁻ → 局面 B で対局 → スコア s⁻
  → 局面 A と B の難易度の差がノイズに加算

CRN あり:
  θ⁺ → 局面 A で対局 → スコア s⁺
  θ⁻ → 局面 A で対局 → スコア s⁻
  → 局面の影響がキャンセルされ、純粋なパラメータの差を測定

数学的背景

2 つのスコアの差の分散は、次のように分解できます。

\[ \text{Var}[s^+ - s^-] = \text{Var}[s^+] + \text{Var}[s^-] - 2\text{Cov}[s^+, s^-] \]

同じ局面を使えば、局面自体の難易度が両者のスコアを同じ向きに動かすため \(\text{Cov}[s^+, s^-] > 0\) となります。 共分散の項が引かれるぶんだけ、差の分散が小さくなります。

ShogiArena の実装

現在のSPSAは、plusとminusを直接対戦させます。 各ペアの開始局面を更新ごとの決定的な乱数で抽選し、同じ局面でplus/minusの先後を入れ替えて2局対戦します。 局面は入力ファイル全体から復元抽出するため、重複する場合があります。 更新間で同じ局面列に固定する必要はありません。

割当の再現条件は、sealed run seed、run ID、更新番号、ペア番号、局面ファイルの内容と順序、割当規則の版が同じことです。 並列実行順や中断・resumeによって割当は変わりません。 variants.crnは旧設定の互換入力として受け付けますが、値によってこの動作を切り替えることはありません。

ペアゲーム（先後入れ替え）

原理

将棋（およびチェス）では先手が有利です。この先後バイアスは、エンジンの実力差とは無関係のノイズです。

ペアゲームでは、同じ開始局面で先後を入れ替えた 2 局をセットにします。

ペア:
  Game 1: Engine A (先手) vs Engine B (後手) → 結果 r₁
  Game 2: Engine A (後手) vs Engine B (先手) → 結果 r₂

ペアスコア = r₁ + r₂  (先後バイアスが相殺)

分散削減効果

先手勝率を \(p_b\)（先手有利バイアス）、Engine A の実力による勝率を \(p_a\) とすると、次のようになります。

  • 独立した 2 局：\(\text{Var} \propto p_b(1-p_b) + p_a(1-p_a)\)
  • ペアゲーム：\(\text{Var} \propto p_a(1-p_a)\)（\(p_b\) の項が消える）

ペアの中で先手番が両エンジンに 1 回ずつ割り当てられるため、先後バイアス由来の分散が残りません。

五項分布との関係

ペアゲームの結果は 五項分布 でモデル化できます。 5 カテゴリ（0.0, 0.5, 1.0, 1.5, 2.0）による分析は、三項分布（勝/引/負）よりも情報量が多く、 SPRT の判定に必要な対局数を 20-40% 削減できます。

バッチ処理

原理

SPSA の 1 回の更新で、同じ摂動に対して複数の対局を実行し、スコアを平均します。

\[ \bar{s}^+ = \frac{1}{B} \sum_{b=1}^{B} s^+_b \qquad \bar{s}^- = \frac{1}{B} \sum_{b=1}^{B} s^-_b \]

分散削減効果

\[ \text{Var}[\bar{s}^+ - \bar{s}^-] = \frac{1}{B} \text{Var}[s^+ - s^-] \]

バッチサイズ \(B\) に反比例して分散が減少します。

実装

現在の実装はplus/minusの直接対戦を先後反転して行い、全対局の「plus勝ち数−plus負け数」を合計します。 上の平均スコアの式は分散削減の説明用であり、runtimeでは平均しません。 pairs_per_updateを増やす場合は、更新幅も変わるためr_endの再調整が必要です。

コストと利益のトレードオフ

バッチサイズを \(B\) にすると、次のようになります。

  • 分散：\(1/B\) に削減
  • 1 更新あたりの対局数：\(2B\) に増加
  • 総対局数：\(N \cdot 2B\)（更新回数 \(N\) が同じ場合）

総対局数を固定するなら、バッチサイズを上げたぶんだけ更新回数 \(N\) は減ります。 1 回の更新は安定しますが、パラメータを更新できる回数は減ります。

手法の組み合わせ

これらの手法は直交しており、すべて同時に使用できます。

1 回の SPSA 更新:
  ┌─────────────────────────────────────────────┐
  │ CRN: 同じ SFEN を θ⁺ と θ⁻ に使用          │
  │   ┌────────────────────────────────────────┐ │
  │   │ ペアゲーム: 先後入れ替え 2 局           │ │
  │   │   ┌───────────────────────────────────┐│ │
  │   │   │ バッチ: B ペアのスコアを集計         ││ │
  │   │   └───────────────────────────────────┘│ │
  │   └────────────────────────────────────────┘ │
  └─────────────────────────────────────────────┘

現在の直接対戦方式では、1回の更新あたりの対局数は2B局です。

推奨設定

spsa:
  pairs_per_update: 4        # 1 回の更新に使うペア数（バッチサイズ）
  inflight_factor: 8         # 同時進行させる対局数の乗数

効果の比較

以下は概念的な比較です（実際の効果は問題に依存します）。

手法分散削減率追加コスト実装の複雑さ
CRN30-50%なし低い
ペアゲーム20-40%2倍低い
バッチ (B=4)75%4倍低い
全手法併用80-90%8倍中

現在のplus_minusではペア内の局面共有が常時行われます。crnの指定は不要です。

実装リファレンス

ファイル設定キー/関数役割
config_spsa_models.pyvariants.crn旧設定の互換入力
config_spsa_models.pypairs_per_update1 回の更新に使うペア数
orchestrator.pySpsaOrchestratorペアゲームの実行制御
pentanomial.pycompute_pentanomial()五項分布の計算

参考文献

  • Asmussen, S. and Glynn, P. (2007). Stochastic Simulation: Algorithms and Analysis. Springer. — CRN を含むモンテカルロ法の分散削減手法の体系的な解説
  • Spall, J. C. (2003). Introduction to Stochastic Search and Optimization. Wiley. — SPSA におけるバッチ処理と分散削減の理論

次に読む

設定や実行手順は、次のページを参照してください。