モンテカルロ木探索のパフォーマンスを予測する Kaggleコンペ解説 〜生成AIによる未知のゲーム生成〜

Transcript

1. モンテカルロ木探索のパフォーマンスを予測する Kaggleコンペ解説 〜生成AIによる未知のゲーム生成〜 株式会社Rist
2. ©Rist Inc. 02 Kaggleコンペの解説では手法に焦点を当てることが多い。 今回は背景と問題設定が面白いコンペであったので、そちらを中心に紹介する。 1. コンペ概要と Ludii ゲーム記述言語の紹介 2. GAVEL (Generating Games Via Evolution and Language Models) の紹介 3. コンペの解法解説（おまけ） 目次
3. ©Rist Inc. 03 1. コンペ概要と Ludii ゲーム記述言語の紹介 2. GAVEL (Generating Games Via Evolution and Language Models) の紹介 3. コンペの解法解説（おまけ） 目次
4. ©Rist Inc. 04 タスク：未知のゲームの定義が与えられたとき、どのMCTSアルゴリズムが優位であるか予測する ゲームをプレイするMCTS（モンテカルロ木探索）アルゴリズムは、選択戦略やパラメータを変えた 72 種類か ら 2 つが選ばれる。プレイ対象のゲームは訓練事例に 1,377 種類が与えられる。テスト事例は訓練事例に含ま れない未知のゲームが与えられる。 UM - Game-Playing Strength of MCTS Variants コンペの概要 アルゴリズムB ゲーム定義 アルゴリズムAの 勝率は90% Input アルゴリズムA ※正確には予測するものは勝率ではなく utility value. すなわち (n_games_win - n_games_lost) / n_games. の数字 予測モデル 未知のゲームを含め、任意のゲームに対してアルゴリズムの優位性を評価できるモデルが求められる Output
5. ©Rist Inc. 05 アルゴリズムは以下のフォーマットで「文字列」として与えられる。 MCTSコンペ概要：アルゴリズムはどのような情報として与えられるか？ “MCTS-<SELECTION>-<EXPLORATION_CONST>-<PLAYOUT>-<SCORE_BOUNDS>” 選択戦略 探索定数 プレイアウト戦略 スコア制限 Source: “DKE Games Group - Seminar The Ludii General Game System” https://ludii.games/TalksWorkshop/Competition.pdf MCTSにおける各ステップの戦略とパラメータでアルゴリズムを定義する。
6. ©Rist Inc. 06 ゲームの特性を説明する情報は、数値情報とカテゴリカル情報に加えて、 • 自然言語によるルール説明 • Ludii ゲーム記述言語 (L-GDL) によるルール記述（S式による記述） が与えられる。 例：Hex というゲームの Luddi によるルール記述 MCTSコンペ概要：ゲーム定義はどのような情報として与えられるか？ Source: “Ludii as a Competition Platform” https://arxiv.org/abs/1907.00246
7. ©Rist Inc. 07 General Game-Playing (GGP) は何かしら特定のゲームではなく、様々なゲームをエキスパートレベルでプレイ する研究領域。その中でも Ludii (Piette et al. 2020) は 2019 年にリリースされた比較的新しいシステム。 Ludii は比較的新しいGGPのためのシステム。幅広いゲームに対応 • 先行研究のゲーム記述言語と比較して高速に実行できる • オープンソース (https://github.com/Ludeme/Ludii) • わかりやすく、シンプルで短いゲーム記述言語 (L-GDL) • 多様なゲームをモデリングできる ◦ 決定論的、確率的（Deterministic, Stochastic） ◦ パズル、複数プレイヤーゲーム（Puzzle, Multi-Player Games） ◦ 交互実行、同時実行（Alternating, Simultaneous） ◦ 有限非決定、不完全情報ゲームも記述できる (Soemers et al. 2024)
8. ©Rist Inc. 08 1,400 以上のゲームが登録されたライブラリ（https://ludii.games/library.php) Source: “DKE Games Group - Seminar The Ludii General Game System” https://ludii.games/TalksWorkshop/Competition.pdf
9. ©Rist Inc. 09 Luddi におけるゲームは ludemes と呼ばれるコンポーネントによって定義される： • ゲーム G を Players, Equipment, Rules という３つの ludemes (component) のタプルとして定義する • Rules は Start, Play, End を含むゲームの操作によって定義する ludemes (game meme) というゲーム情報の単位によって構成される → コンポーネントごとに特徴量を抽出することに 意味がある。 → マニュアルのコンポーネントや Ludii Library におけるゲームのコードを見て、重要そうなキー ワードを探して、その統計値を計算することで特 徴量を作れる。 (game “Amazons” (players 2) (equipment ( (board (square 10)) (piece “Queen” Each (move Slide (then (moveAgain)))) (piece “Dot” Neutral) )) (rules (start { (place “Queen1” {“A4” “D1” “G1” “J4”}) (place “Queen2” {“A7” “D10” “G10” “J7”}) }) (play (if (is Event (count Moves)) (forEach Piece) (move Shoot (piece “Dot0”)) ) ) (end (if (no Moves Next) (result Mover Win))) ) ) プレイヤー数 (Number of players) 設備 (Equipment) 開始時ルール（Starting Rules） 駒の配置、初期位置など プレイルール（Playing Rules） 各状態で可能な移動など 終了ルール（Ending Rules） 終了条件と結果
10. ©Rist Inc. 010 Ludii によるゲーム記述の具体例 (game “Tic-Tac-Toe” (players 2) (equipment ( (board (square 3)) (piece “Disc” P1) (piece “Cross” P2) )) (rules (play (move Add (to (sites Empty)))) (end (if (is Line 3) (result Mover Win))) ) ) (game “Shogi” (“TwoPlayersNorthSouth”) (equipment ( (board (square 9)) (piece “Osho” Each (“StepMove”)) (piece “Fuhyo” Each (“StepMove” Forward (then (if (“InPromotionZone” (last To)) (if (“InLastRank” (last To)) (“Promote”) (moveAgain) ) ) ) ... マルバツゲーム (Tic-Tac-Toe) 将棋 (Shogi) Source: “Ludii Portal” https://ludii.games/library.php ※ 類似したゲームの定義をまとめて 簡潔に記述できるよう、関数を用い てルールを定義している。これらを 展開すれば基礎となる構成は同じ
11. ©Rist Inc. 011 余談：Evolutionary Game Design (Browne & Maire, 2010) と Yavalath Ludii の先行研究かつ元ネタ的な論文。人間が面白いと感じる新しい組み合わせゲームを自動的に作成する課題 に取り組んでおり、この論文で提案されているフレームワーク (Ludi system) によって設計されたゲーム Yavalath は実際に市販されている。 Yavalath は変則4目並べ。4つ並べることを目指しつつ、3つを並べてはいけない 2~3 人用ボードゲームとなっ ている（とても面白い）。 Source: “ボードゲーム紹介：ヤバラス（Yavalath）” https://jellyjellycafe.com/games/yabalath
12. ©Rist Inc. 012 1. コンペ概要と Ludii ゲーム記述言語の紹介 2. GAVEL (Generating Games Via Evolution and Language Models) の紹介 3. コンペの解法解説（おまけ） 目次
13. ©Rist Inc. 013 LLMと進化計算における最近の研究から着想を得て、新しく独創的で興味深いゲームを自動的に生成する研究 (Automated Game Generation)。NeurIPS’24 採択論文。 • Model Training: Ludii のゲーム定義データセットから 500 以上のボードゲームを用いて、中間部分を当てる (fill-in-the-middle) ように Code LLM を fine-tuning する。 • Evolutionary Search: 学習した Code LLM + fill-in-the-middle によってランダムにゲームを変異させ、fitness 評価関数（後述）により評価して探索する。 GAVEL: Generating Games Via Evolution and Language Models (Todd et al. 2024) (game “Tic-Tac-Toe” (players 2) (equipment ( (board (square 3)) (piece “Disc” P1) (piece “Cross” P2) )) (rules (play (move Add (to (sites Empty)))) (end (if (is Line 3) (result Mover Win))) ) ) Target
14. ©Rist Inc. 014 生成されたゲームの評価関数は、プレイアウトによる結果から評価する。 GAVEL ゲーム評価関数：実行可能性とゲーム性を評価する ゲームが壊れていないかチェック： コンパイルできない場合は -3 コンパイル可能だがプレイできない場合は -2 ランダムポリシーエージェントでn=100のプレイアウト： プレイヤーの勝率の差が閾値以上だったり、行動可能でない ゲーム状態が多い場合（プレイヤーの主体性の欠如）は -1 探索ベースのエージェントで n=10 のプレイアウト： バランス（最大勝率差）、決着率（引き分けでない試合）、完 了率（終了状態に到達した割合）、主体性（行動可能な動きに あるターン割合）、網羅率（コマによって占有された盤面サイ トの割合）
15. ©Rist Inc. 015 生成されたゲーム例の中でも高評価なサンプル事例として Yavalath の変種 (YavaGo) を紹介している。これは囲碁の囲 みによる除去ルールが Yavalath に加わっている。 GAVEL の強みはコードセグメントとして表現されるゲーム のメカニズムを再結合して、その組み合わせが trivial なゲー ムにならないようにする点と言える。 「囲碁の囲みによる除去ルールの追加」が行われた例： Qualitative Results：どのようなゲームが生成されるのか？
16. ©Rist Inc. 016 1. コンペ概要と Ludii ゲーム記述言語の紹介 2. GAVEL (Generating Games Via Evolution and Language Models) の紹介 3. コンペの解法解説（おまけ） 目次
17. ©Rist Inc. 017 全体：特徴量エンジニアリングと、未知ゲームに適合するような CV と Public LB への最適化が重要であった。 特徴量抽出：ゲームルール記述の各コンポーネントからキーワードの出現頻度などの統計量やネストの深さ、正 規表現による特定キーワードのパラメータ抽出などを行い、特徴量を作成した。 基本は Best Public Code を参考にしつつ、有用そうなキーワードや ludemes を探索するために Ludii Library からゲームの定義を数十件読み、性質が共通部分や異なる部分を区別できるように特徴量を考えた。 特徴量選択：CV および Public LB 共に改善するか否かを判断基準とした。最終的には Top10 内の中でも特に上 位の Single Model を構築できた。 アンサンブル：ほぼ同じ 2 つの Catboost モデルの Bagging をした。最終的には Bagging の改善効果はあまり 無く、選択できなかった Single Model が Best Priv & Best Pub LB スコアであった。 余談ではあるが、Kaggle のための VSCode 拡張を開発して大いに活用した。VSCode からショートカットキーでコンペ投稿用の Notebook とコードベースをアップロードして投稿できるようにした。ご活用ください。 https://github.com/smly/vscode-fast-kaggle 8th place solution (Kohei) の解法概略 Source: “1st Place Solution” https://www.kaggle.com/competitions/um-game-playing-strength-of-mcts-variants/discussion/549801 ※ 詳細は kaggle discussion を参照ください。
18. ©Rist Inc. 018 アンサンブル：CatBoost と LightGBM (DART) と TabM (NN) の加重平均。 追加データセット：484 の追加のユニークなゲームルールと 14,365 行の追加の訓練データを生成して用いた。 生成したゲームルールは 2 つのアプローチによって生成。１つは GAVEL の独自バージョンによるもの。2 つ目 は Instruction-tuned LLMs (Llama 3.1 70b & Qwen 2.5 32b) による few-shot prompting。 • GAVEL によって生成されたゲームルールは、2つ目の LLMs で生成されたゲームルールと比較して遥かに 高品質である一方で、GAVEL はプレイ可能なゲームを生成するのが非常に遅かった。2 つ目の LLMs に よって生成される ~95% のゲームルールはコンパイルエラーやランタイムエラーなどで破棄されたが、そ れでもなお GAVEL の生成速度は遅い。 • CPU時間を節約するために、各エージェントのペアに対してルールセットごとに 4 試合のみゲームを実行 した。そのためラベルはコンペティションのデータセットと比較して低品質のデータではあるが、それで も CV, LB スコアの改善に寄与した。 その他解法の詳細については本解説の主題とは外れるため、元記事を参照ください。 https://www.kaggle.com/competitions/um-game-playing-strength-of-mcts-variants/discussion/549801 1st place solution の解法紹介（GAVEL に関する言及を中心に抜粋） Source: “1st Place Solution” https://www.kaggle.com/competitions/um-game-playing-strength-of-mcts-variants/discussion/549801
19. ©Rist Inc. 019 本スライドでは、UM - Game-Playing Strength of MCTS Variants コンペの興味深いタスクの背景と関連研究 に注目し、LLM と進化計算に着想を得た自動ゲーム生成アルゴリズムである GAVEL を紹介した。 • GAVEL は fine-tuning されたコード言語モデルを用いて部分的にゲームルールを変異させ、ゲームルー ルに特化してデザインされた評価関数によって、ゲームルール空間を効率的に探索する。 • GAVEL の強みはコードセグメントとして表現されるゲームのメカニズムを再結合して、その組み合わせ が trivial なゲームにならないようにする点であると言える。 • GAVEL の評価関数の定義から明らかなように、GAVEL によるゲーム生成はプレイアウトを必要とするた め、CPU時間を必要とする。既存 LLM の few-shot prompting と比較して得られるゲームの質が高い。 まとめ
20. ©Rist Inc. 020 (Piette et al. 2020) Éric Piette, Dennis J.N.J. Soemers, Matthew Stephenson, Chiara F. Sironi, Mark H.M. Winands, Cameron Browne, “Ludii -- The Ludemic General Game System”, ECAI 2020. (Soemers et al. 2024) Dennis J. N. J. Soemers, Éric Piette, Matthew Stephenson, Cameron Browne, “The Ludii Game Description Language is Universal”, IEEE Conference on Games, 2024. (Todd et al. 2024) Graham Todd, Alexander G Padula, Matthew Stephenson, Éric Piette, Dennis Soemers, Julian Togelius, “GAVEL: Generating Games via Evolution and Language Models”, NeurIPS 2024. (Browne & Maire, 2010) Cameron Browne, Federic Maire, “Evolutionary Game Design”, IEEE Transactions on Computational Intelligence and AI in Games 2 (1), 1-16, 2010. “Ludii Portal” https://ludii.games/ “Ludii Modeling, Playing and Evaluating Games” https://ludii.games/TalksWorkshop/Ludii.pdf “Ludii AI Competition” https://ludii.games/TalksWorkshop/Competition.pdf “1st Place Solution” https://www.kaggle.com/competitions/um-game-playing-strength-of-mcts-variants/discussion/549801 https://www.kaggle.com/competitions/um-game-playing-strength-of-mcts-variants/discussion/549801 参考文献