Kaggleコンペ「UM - Game-Playing Strength of MCTS Variants 」3位入賞解法徹底解説

### はじめに
DataRobotシニアデータサイエンティスト、Kaggle Competition Grandmasterの詹金（センキン）です。本侯では、個人で3位入賞したKaggleコンペ「UM - Game-Playing Strength of MCTS Variants 」[[1](https://www.kaggle.com/competitions/um-game-playing-strength-of-mcts-variants)]の解法をご紹介します。

### UMコンペの概要
このコンペティションの目的は、モンテカルロ木探索（MCTS）[[2](https://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%B3%E3%83%86%E3%82%AB%E3%83%AB%E3%83%AD%E6%9C%A8%E6%8E%A2%E7%B4%A2)]のパフォーマンスを予測することにありました。具体的には、1000種類以上のボードゲームにおいて、モンテカルロ木探索を使用する2種類のエージェント（72体）を対戦させた場合の勝率を予測するタスクでした。（最初のエージェントが相手に対してどの程度の優位性を持つかを予測する）

評価指標は回帰分析でよく用いられるRMSE[[3](https://docs.datarobot.com/ja/docs/modeling/reference/model-detail/opt-metric.html#rmse-weighted-rmse-rmsle-weighted-rmsle)]でした。伝統的なテーブルデータ、サイズが小さい（学習データが約23万行）ため、初心者にやりやすいコンペティションでした。

### データについて
このコンペティションでは、1000種類以上の異なるボードゲームにおいて、さまざまなバリエーションのモンテカルロ木探索（MCTS）エージェントが対戦した結果のデータセットを生成しました。800以上のゲームルール特性やゲーム動作に関する連続値特徴量があり、エージェントとゲームルールの説明文章もあり、特徴量エンジニアリングで改善できることが多いです。ほとんどのターゲットは15回のゲームシミュレーションの結果ですが、1%のケースでは30回または45回のゲームが行われました、対戦回数がすくないため若干ランダム性があります。

**連続値**
![senkin1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3864834/08e28595-7d1a-4738-81fc-7e8c7672ec7b.png)

**テキスト**
![senkin2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3864834/77519390-4cc0-4901-8a4f-b50f5293f447.png)

**予測ターゲット**
![senkin3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3864834/1a575f6a-69f0-430a-a339-027bac6a99b8.png)

### パーティション戦略
Kaggleには Public Leaderboard（公開リーダーボード）とPrivate Leaderboard（最終評価の非公開リーダーボード）が存在します。これらで上位に入るためには、汎化性能の高いモデルを構築するためのパーティション戦略が非常に重要です。

このコンペティションの訓練データとテストデータの対戦ゲーム自体は完全に異なります。
また、Publicテストに含まれるゲームはPrivateテストのゲームの一部であり、Privateテストには新しいゲームも含まれています。これらの未知データに強いモデルを作ることが大切です。


※ゲーム分割
![senkin4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3864834/560d92ab-c297-446f-a902-654943fa9a9e.png)

同じゲームのデータが訓練データと検証データの両方に入るのを防ぐためにはGroupKFoldを使うのが適切ですが、さらにゲームクラス不均衡を防ぐためGroupKFoldとStratifiedKFoldを組み合わせたStratifiedGroupKFold[[4](https://www.datarobot.com/jp/blog/summary-of-ml-partitioning-part-2/)]を採用して、同ゲームグループのデータが同じ側に割り当てられ、かつ正解ラベルの分布が訓練と検証で等しくなるように分割するパーティション戦略をとりました。これで検証データの精度とPublicテストデータの精度の相関性が高くなりました。

### 特徴量エンジニアリング
特徴量の作成は、テーブルデータを使った機械学習モデルの構築プロセスの中で最も手間がかかる部分であり、異なる特徴量の組み合わせを試す「実験」に膨大な時間を費やすことも少なくありません。しかし、データの本質を理解し、業務知識を反映できる特徴量を抽出できれば、少数の特徴量でも高精度なモデルを構築することが可能です。
今回のコンペでは、元データの特徴量が多く、情報量の少ないものが多数含まれていたため、それらを削除することで計算コストを削減できました。また、コンペ中に学んだドメイン知識を活用して主に以下の 3 種類の特徴量を作成しました。これらの特徴量は、予測精度改善に大きく貢献しました。

#### 1. カテゴリー特徴量
ゲームエージェントの文字列からカテゴリー情報を抽出します。例えば、「MCTS-UCB1-0.1-NST-true」からは、以下の4つの特徴量を生成します：
- UCB1（選択フェーズ戦略）
- 0.1（探索定数）
- NST（プレイアウトフェーズ戦略）
- true（スコア制限）

#### 2. 交互作用（組み合わせ）特徴量
強い元特徴量の組み合わせで新しい特徴量を作成します。例えば、以下のような特徴量です：
- PlayoutsPerSecond: 1秒間に行うプレイアウト（シミュレーションの回数）を示す指標です。
- MovesPerSecond: 1秒間に実行されるゲームの「手」の数を示す指標で、実際にAIがゲーム内でどれだけ多くの手を決定できるかを示します。

さらに上記から1回の手を決定するためにどれだけ多くのプレイアウト（シミュレーション）を行っているか、または計算リソースがどれだけ効率的に使われているかを示す「PlayoutsPerSecond / MovesPerSecond」という特徴量も作成しました。

#### 3. テキスト特徴量
ゲームルールテキスト(EnglishRules)のTF-IDF[[5](https://ja.wikipedia.org/wiki/Tf-idf)]行列を作って、特異値分解 (SVD[[6](https://ja.wikipedia.org/wiki/%E7%89%B9%E7%95%B0%E5%80%A4%E5%88%86%E8%A7%A3)])で次元を削減し、新たな特徴量を作成しました。最も重要なパラメーターはTF-IDFのmax_featuresで、これはTF-IDFの単語辞書の最大サイズを制限するものですが、過学習を防ぐために有効なパラメーターでもあります。最終的に、頻度が高い上位300単語を使用することで、予測精度が最も高くなりました。

### データ拡張（Data Augmentation）
データ拡張[[7](https://en.wikipedia.org/wiki/Data_augmentation)]は画像処理でよく使われる主要な改善手法ですが、テーブルデータにはほとんど利用されていないようです。しかし、スポーツやゲームのような対戦競技のデータにおいては効果があります。例えば、毎年開催されるKaggleのアメリカ大学バスケコンペ(NCAA)[[8](https://www.kaggle.com/competitions/march-machine-learning-mania-2024)]では、一試合の両チームを反転させてデータ拡張を行うことで精度が向上します。
今回のゲーム対戦のコンペにおいても、データ反転拡張（Flip Augmentation）の効果が大きかったです（下表）。ただし、エージェントとターゲットの反転だけでは不十分で、他の関連性のある特徴量の変換も必要でした。ちなみにデータ反転拡張を試みた他のチームがうまくいかなかった原因は、おそらく他の関連特徴量の変換を工夫しなかったことにあると思われます。

※元データ
![senkin_5.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3864834/ad21c6ca-e2bf-4377-ab74-f9da2c270a1d.png)

※反転データ
![senkin_6.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3864834/f009d2a0-2dd0-4ca3-bf01-e71c0c61e3a4.png)

具体的に実施したデータ反転処理は下記の通りです。
1. agent
(agent1,agent2)を反転させ、(agent2,agent1)に変更。

2. AdvantageP1
最も重要な特徴量AdvantageP1（100回対戦シミュレーションしたagent1の勝率）に対して、反転後1-AdvantageP1に変更。

3. Utility_agent1
ターゲットのutility_agent1を-utility_agent1に変更。

4. その他の特徴量
変更なし。

### Two-Stage Modeling
[Two-Stage Modeling（二段階モデリング）](https://www.datarobot.com/jp/blog/thorough-explanation-of-the-winning-solution-of-the-recommendation-competition-1/) とは、機械学習や統計モデリングにおいて、2 つの異なるステップでモデルを構築し、最終的な予測や分類を行う手法です。特に、分類や回帰の問題において、複雑な関係を分解して学習することで、精度や解釈性の向上を目指します。
拡張したデータの構造は元の学習データと同じですが、必ずしも同じ分布とはいえません。最初のエージェントが相手に対して優位性を持つため、データを反転すると、その性質が「優位」から「劣位」へと変わり、異質なデータになる可能性があります。
同質データの場合、データを統合して 一段階モデリング を行うのが最適ですが、異質データの場合、二段階モデリング を採用することで精度が向上するケースが多く見られます。今回のコンペでも二段階モデリングアプローチを採用した結果、他の上位チームとの差別化を図ることができ、精度向上に最も大きく貢献した手法の 1 つとなりました。

#### 1. 第一段階
拡張したデータを学習データとして使用し、元の学習データとテストデータに対して勝率を予測します。その予測値を特徴量として抽出し、第二段階のモデルで利用します。
また、多様性を持たせるためにXGBoost[[9](https://xgboost.readthedocs.io/en/stable/)]、LightGBM[[10](https://lightgbm.readthedocs.io/en/stable/)]、CatBoost[[11](https://catboost.ai/docs/en/)] の 3 つの異なるモデルを使用し、それぞれから特徴量を生成しました。

#### 2. 第二段階
元の学習データのみを使用し、テストデータに対して勝率を予測しました。精度が最も高かった 2 つのモデル（LightGBM と CatBoost）を採用しました。

#### 3. アンサンブル
第二段階の 2 つのモデルの予測値を加重平均し、最終的な予測値を算出しました。CatBoost の精度が高いため、重みを 70%、LightGBM の重みを 30% に設定しました。

![senkin7.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3864834/5b5b74bb-a914-4415-b41b-0a6f5bc159f0.png)

### 後処理
今回のコンペの予測ターゲットは対戦の勝率であり、正解ラベルは -1 から 1 までの範囲です。また、最初のエージェントは相手に対して優位性があるため、正解ラベルには負の値よりも正の値が多く含まれています。この性質に基づき、2 つの後処理アプローチを実施しました。

#### 1. 予測値が範囲外の値になっている場合の処理
予測値が正解（-1～1）の範囲外になる場合、値を-1～1の範囲内に制限します。

#### 2. モデルが全体的に過小予測している場合の処理
正解ラベルでは負の値よりも正の値が多いですが、予測値は負の値と正の値がほぼ同じ割合になっています。そのため、学習データの分布に合わせるためにスケーリングを行う必要があります。具体的には、予測値に補正係数（α > 1）を掛けます。

Kaggle のコンペでは最終提出を 2 回行えるため、最適な係数を検定データと Public Leaderboard の両方に対してそれぞれ決定しました。一方、実際のプロジェクトでは通常、検定データに基づいて最適な係数を決定します。

※予測値と実測値の比較
![senkin8.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3864834/da3b523a-0c06-4c8a-ae2c-a2f986bd34c9.png)

### 実験管理
筆者はシンプルな実験管理を好み、提出した学習＆予測用の Notebook にバージョン番号を付けて保存します。そして、Notebook実験の記録を表形式で残します。Kaggleコンペを含む機械学習プロジェクトにおける実験管理が重要な理由は、以下のようなポイントにあります。

#### 1. 再現性の確保
機械学習モデルの開発では、データの前処理、特徴量エンジニアリング、ハイパーパラメータの調整など、多くの要素で実験（試行錯誤）が必要になります。実験管理をしないと、後から「どの設定が最も良かったのか」や「なぜスコアが向上したのか」が分からなくなります。ログを適切に記録することで、再現性を確保できます。

#### 2. 効率的なハイパーパラメータ探索
Kaggleのコンペでは、ハイパーパラメータの最適化がモデルの性能に大きく影響します。同じような設定の実験を何度も繰り返すことを防ぎ、効率的に最適な組み合わせを見つけるために、実験管理が必要です。

#### 3. チームでの協力
Kaggleコンペではチームで参加することも多いです。適切に実験管理を行えば、チームメンバーが別々に行った試行結果を簡単に共有し、成功したパターンや失敗したパターンを効率よく学ぶことができます。

#### 4. 過去の知見の活用
以前のコンペやプロジェクトで得た知見を次に活かすためにも、実験の記録を残しておくことが重要です。同じ課題に取り組む際に、ゼロから試行錯誤するのではなく、過去の成功・失敗を踏まえたアプローチが可能になります。

#### 5. モデルの確認や実運用のため
コンペ終了後、主催者が結果を確認し、最終的な順位や賞金の確定を行うプロセスがあります。適切な実験管理を行っていれば、最も良い結果を出したモデルを正しく再現し、実運用へスムーズに移行できます。
※メジャーバージョン管理ログ
![senkin09.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3864834/d45a9a64-7fa3-4f84-970b-1d1423339904.png)

### まとめ
本稿では、Kaggleコンペ「UM - Game-Playing Strength of MCTS Variants」において筆者が採用したパーティション戦略、特徴量エンジニアリング、テーブルデータの拡張手法、Two-Stage Modeling手法、後処理、実験管理について解説しました。実際のコンペの分析課題にこれらを適用した結果、短期間で高パフォーマンスなモデルを構築でき、上位にランクインすることができましたが、一つ一つの手法はAI予測分析の実務でも応用できるものばかりです。ぜひ、皆様の業務でご活用いただければ幸いです。

最後に、本コンペティションを通じて得たデータの分析に関する知見をKaggleコミュニティに還元するとともに、弊社のソリューションにも活かし、ビジネスへの実装を進めていきたいと考えています。

#### References
[1]https://www.kaggle.com/competitions/um-game-playing-strength-of-mcts-variants
[2]https://ja.wikipedia.org/wiki/モンテカルロ木探索
[3]https://docs.datarobot.com/ja/docs/modeling/reference/model-detail/opt-metric.html#rmse-weighted-rmse-rmsle-weighted-rmsle
[4]https://www.datarobot.com/jp/blog/summary-of-ml-partitioning-part-2/
[5]https://ja.wikipedia.org/wiki/Tf-idf
[6]https://ja.wikipedia.org/wiki/特異値分解
[7]https://en.wikipedia.org/wiki/Data_augmentation
[8]https://www.kaggle.com/competitions/march-machine-learning-mania-2024
[9]https://xgboost.readthedocs.io/en/stable/
[10]https://lightgbm.readthedocs.io/en/stable/
[11]https://catboost.ai/docs/en/