はじめに
有名なチェスプログラム "Stockfish" では性能の比較テスト手法として SPRT (Sequential Probability Ratio Test) が導入されています。
この記事では、筆者がその技術をコンピューター将棋へ応用するために調べた内容をまとめます。
注意点
この記事では SPRT を活用するために必要な知識を浅く扱っています。
筆者は AI の力を借りながら計算部分の実装をしているものの、理論の数学的な土台部分を詳しく解説できるほどの理解がありません。深く理解をしたい方は参考文献に記載している論文を参照してください。
また、記事中に細かい部分も含めて間違いがあればコメントで指摘をお願いします。
モチベーション
ソフトウェアの性能を上げるために変更を加えたとき、改善することが自明でないのなら、実験をして性能を評価する必要があります。例えば、処理時間を計測するケースやマシンリソースの消費量を計測するケースが考えられます。どのような観点に着目するかはソフトウェアの性質によって異なります。
コンピューターチェスやコンピュータ将棋の場合、最も重要な性能指標は対局における強さです。
副作用の無い高速化なら処理時間を計測するだけで済みますが、多くの場合に思考ルーチンの変更は副作用を伴います。特にチェスや将棋は序盤から終盤まで全ての局面で高い精度が求められ、特定の局面の思考結果だけでは強さを測ることができません。
したがって、変更前後のバージョンどうしで対局を何千、何万と繰り返して結果を見る必要があります。そして、改良できたかどうかは統計的な有意性を評価しなければなりません。
この作業は頻繁に行われるにも関わらず、毎回非常に多くの計算資源を必要とします。そこで、検査の正確さを保ちながら少しでも効率の良い方法を確立する必要があります。
古典的な検定の例とその課題
古典的な検定方法では最初にサンプル数を決めます。例えば 5000 局の対局を行うとします。
その結果に対して 2 項検定に基づいて優位に勝ち越したと言えるかどうかを判断します。よく使われるのは有意水準 5% あるいは 1% です。例えば有意水準 5% であれば、「互角のプレイヤーどうしでこれだけ結果が偏る確率は 5% しかない → 故に強くなったとみなす」という意味です。
また、どれくらい強くなったのかを判断する参考値として、例えば Elo rating の差の 95% 信頼区間を計算します。
上の例では 5000 局と書きましたが、実力差が小さいと 5000 局では有意に勝ち越したと言える結果が出ない場合もあります。逆に実力差が大きければ 1000 局でも十分な評価ができる場合もあります。
この手法ではサンプル数を事前に決めてしまうため、計算資源を最適化できません。有意水準を満たしたところで停止すれば良いのでは？と思われるかもしれませんが、途中結果を見て恣意的にサンプル数を変えてしまうと正しい評価とは言えません。
また、引き分けが多かったり手番による勝ちやすさの偏りがあると結果が五分に近づきやすく、より多くの対局数を必要としてしまいます。
SPRT (GSPRT)
SPRT (Sequential Probability Ratio Test) はサンプル数を固定しない検定手法の一種です。チェスプログラム Stockfish のテストフレームワークである Fishtest で採用されています。
なお、 Fishtest が採用しているものは正確には SPRT の中でも GSPRT (Generalized Sequential Probability Ratio Test) と呼ばれるものです。この記事ではその詳細には触れないので単に SPRT と記載しています。
SPRT を用いると対局が進むごとに逐次的に評価を行い、その時点までの結果で基準を満たした（あるいは満たさない）と判断できれば検証を終了することができます。
ちなみに、SPRT はもともとゲーム情報学の分野ではなく製造業の品質管理を目的に研究されたそうです。
Fishtest
Fishtest のサイトでは過去の実験結果を閲覧することが可能です。
例えば Pull Request #6467 に対する実験結果は次のページで見ることができます。
このページの情報のうち SPRT に関係が強い部分を抜粋したものが次の表です。
| 項目 | 値 |
|---|---|
| SPRT | elo0: -1.75 alpha: 0.05 elo1: 0.25 beta: 0.05 (normalized) |
| Pentanomial | [55, 11390, 30659, 11490, 70] |
| LLR | 2.94 [-2.94,2.94] (accepted) |
まず、 LLR の末尾に (accepted) と書かれており、この変更が検査をパスしたことを意味します。
SPRT の elo0 と elo1 はそれぞれ帰無仮説と対立仮説に該当するレート差です。つまり、レート差 -1.75 と +0.25 の尤もらしさを比較して評価します。
alpha と beta はそれぞれの仮説の誤り率を表しています。通常は 0.05 が用いられるようです。
SPRT の末尾に (normalized) と書かれています。これは古典的な Logistic Elo ではなく Normalized Elo を用いていることを意味します。
Pentanomial が対局の結果を表していますが、単純な勝ち数や負け数ではありません。白番と黒番を入れ替えた 2 つの対局をペアにして、その結果を [負負, 負分, 分分 + 負勝, 分勝, 勝勝] の 5 項で集計します。したがって、全ての値を足して 2 倍にすると総対局数になります。
LLR (Log-Likelihood Ratio) が elo0 と elo1 の尤度（尤もらしさ）比の対数であり、大きいほど elo1 以上であることが尤もらしいと言えます。 [-2.94,2.94] は alpha と beta から算出した値域であり、 2.94 に到達したため採用という結果になっています。
Elo0, Elo1
elo0 や elo1 の値はケースによって使い分けます。
先ほどの Pull Request の例だと内容が単純なコードの除去であるため、悪化していないことを説明できれば問題ありません。そのため [-1.75, 0.25] という低めの値でした。
逆に新しいアルゴリズムを導入してその効果を説明するには [0, 2] や [0.5, 2.5] など正の方向に寄った値が使われます。
Stockfish では時間の長い対局ルール (LTC) と時間の短い対局ルール (STC) でも使い分けているようです。詳しくは Chess Programming Wiki を参照してください。
Pentanomial (5-nomial)
前述の通り、対局ペアを 5 項 [負負, 負分, 分分 + 負勝, 分勝, 勝勝] で集計します。対局実験は定跡や局面集を使うことで開始局面にバリエーションを持たせますが、同じ局面に対して表裏（手番を入れ替えた 2 局）を実施しそれをペアとして扱います。
対局をペアで扱わずに 3 項 [負, 分, 勝] で扱う場合と比べて表現力が上がっています。例えば先手が勝ちやすい局面で定跡を抜けて表裏ともに先手が勝った場合、 3 項では 勝 と 負 がそれぞれ +1 加算されます。一方で 5 項の場合には 分分 + 負勝 に分類されます。それに対して 勝勝 や 分勝 は定跡に関係なく実力で勝ったことを示唆していると言えます。
LLR
LLR (Log-Likelihood Ratio) はどちらの仮説が尤もらしいかを示す値で、 elo0, elo1, pentanomial から算出されます。
この値は対数尤度比の合計であり、実力に差があれば対局が増えるごとに正か負のどちらかへ徐々に進んでいきます。実際の計算では対数尤度比の平均を出してから、対局ペアの数を乗じることで得られます。
LLR がいくつになったら accept あるいは reject するかは alpha や beta で決まります。ほとんどの場合に alpha = beta = 0.05 が用いられ、範囲はおよそ [-2.94, 2.94] (正確には log((1-0.05)/0.05) = 2.944438979...)となります。
必要対局数
結果が出るまでに必要な対局数は elo0 や elo1 の値、それから実力差や引き分けの発生率、定跡の影響などで変わります。
実力差が大きい場合は数百局で結果が出る場合もあるし、差が小さい場合は数万局に及ぶ場合もあります。そのため最大対局数は 10 万から数十万程度に設定する必要があります。
実際にどれくらいの対局数が必要になるかは Fishtest の SPRT Calculator で計算することが可能です。
参考文献
- Wikipedia
- Chess Programming Wiki
- 論文
- Xiaoou Li, Jingchen Liu, and Zhiliang Ying
- MICHEL VAN DEN BERGH
- Stockfish (Fishtest)