小論文: AI拡張UCTによる汎用ゲームプレイ

author:

黒岩晃弘 と Gemini

date:

2025/10/03

概要

本稿では、遺伝的プログラミング（ GP ）の進化的メカニズムを現代的な AI エージェントで置き換える、モンテカルロ木探索（ MCTS ）のための新しいフレームワーク mcts-gen を紹介する。我々は「 AI 拡張 UCT 」アルゴリズムを中心としたアーキテクチャを提案する。このアルゴリズムでは、標準的な UCT 探索が外部 AI によって 3 つの重要な点で強化される。すなわち、末端ノード評価（ Value: 価値）、動的な探索パラメータ調整（ Exploration: 探索）、そして最も重要な点として、 Policy Pruning（ポリシーによる枝刈り） による行動空間の削減である。このアプローチは、 UCT アルゴリズムの単純さを維持しつつ、 AI のポリシーモデルを活用して将棋のような巨大な分岐因子を持つゲームのパフォーマンスを劇的に向上させる点で、一般的な AlphaZero モデルとは一線を画す。我々は、 AI エージェントがリアルタイムのパフォーマンス指標に基づいて戦略を繰り返し洗練させながら、シミュレーションループ全体を統括する、ステートフルなクライアントサーバーモデルを実証する。

1. 遺伝的プログラミングの AI エージェントによる置換

In previous works like chess-ant, Genetic Programming was used to evolve a strategy for tuning the MCTS explorationConstant. This process, while effective, involved a computationally expensive evolutionary cycle with a large population and multiple generations. Each evaluation required a full MCTS simulation, leading to significant time investment.

mcts-gen replaces this entire evolutionary loop with a single, intelligent AI agent. The agent maintains a single strategic model (e.g., a Python function) and iteratively refines it based on direct feedback from the search process. This AI-driven, single-strategy evolution is significantly more efficient, allowing for rapid strategy adaptation without the overhead of managing a genetic population.

この相互作用の中核をなすのは、そのメソッドが MCP ツールとして公開されるステートフルなシミュレータ（ AiGpSimulator ）である。 AI エージェントはこれらのツールを戦略的に呼び出し、シミュレーションループを外部から管理する。特に、 Search Limit（探索制限） メカニズム（ run_mcts_analysis を介した導入）により、エージェントは単一のバッチで複数の MCTS ラウンドを実行できるようになった。これは、 chess-ant における GP の routine() サイクルを模倣しつつ、 AI による予算配分を行うことで、 API レベルのボトルネックを回避しながら、実行、分析、自己修正という緊密なフィードバックサイクルを保証するものである。

2. Policy Pruning: PUCTの代替案

AlphaZero とその派生技術は、 PUCT （ Polynomial Upper Confidence Trees ）の計算式を介して、 MCTS の選択段階にポリシーネットワークを直接統合する。これは強力である一方、探索アルゴリズムとポリシーモデルを密結合させる。

我々は、よりシンプルで疎結合なアプローチである Policy Pruning（ポリシーによる枝刈り） を提案する。そのワークフローは以下の通りである。

  1. The AI agent calls a tool (get_possible_actions) to retrieve all legal moves from the current node.

  2. The agent applies its internal policy model to this list, filtering out unpromising moves and creating a smaller, pruned list of candidate actions.

  3. The agent then calls the main search tool (run_mcts_round), passing this pruned list (actions_to_expand) as an argument.

  4. MCTS エンジンは、このリストを受け取ると、その展開フェーズを AI によって提供されたアクションのみを考慮するように制約する。

この手法は、 AI のポリシーを高度なフィルターとして効果的に使用し、特に将棋のような複雑なゲームにおいて、探索木の分岐因子を劇的に削減する。これにより、根底にあるエンジンは標準的な UCT 実装のままでよく、アーキテクチャを単純化しつつ、ポリシーネットワークの主要な利点を享受することができる。

3. AI 主導の探索による UCT

PUCT の代わりに、 mcts-gen はノード選択に標準的な UCT （ Upper Confidence bounds for Trees ）アルゴリズムを使用する。主要な革新は、 explorationConstant （ UCT 計算式における C ）がどのように決定されるかにある。

  • The AI agent is responsible for generating and maintaining a strategy (e.g., a Python function) that determines the optimal explorationConstant for any given game state.

  • この戦略は、ゲーム固有の特徴（例： board.is_check() ）や、汎用的なシミュレーション指標（例： UCT 値の improvement ）を考慮に入れた、複雑なものになり得る。

  • AI はこの戦略を実行して各シミュレーションループの定数を選択し、パフォーマンスに基づいて戦略コードを洗練させることで、探索（ exploration ）と活用（ exploitation ）のバランスを最適に取る方法を効果的に学習する。

4. AlphaZero とのその他の相違点

  • ロジックの分離: MCTS エンジンと AI の「頭脳」は完全に分離されている。エンジンは汎用的なツールを提供し、 AI はそれらを使って、潜在的に複雑な独自の探索ロジックを実装する。

  • ステートフルな相互作用: ステートレスなモデルとは異なり、サーバーは複数のツール呼び出しにわたって MCTS ツリーのインスタンスを維持し、 AI が 1 ターン内で以前の探索結果の上に構築していくことを可能にする。

  • 明示的な戦略: AI の探索戦略は、明示的で人間が読めるコードであり、ログに記録して分析することが可能で、ニューラルネットワークの暗黙的な重みよりも高い透明性を提供する。

5. ゲームロジック生成の課題

The mcts-gen framework is designed to be generic. This requires the creation of game-specific logic files (*_mcts.py) that inherit from a GameStateBase abstract class. This task has proven to be complex for both humans and AI agents due to the need for a deep understanding of two separate APIs: the game library (e.g., python-shogi) and the GameStateBase interface.

我々の経験によれば、このプロセスは単純な一度きりの生成（ one-shot generation ）ではない。それには、オブジェクトのコピー（ deepcopy ）、戻り値の規約、そして API 固有のメソッド（例： board.is_checkmate() 対 GameStateBase.takeAction(action) ）といった概念の正確な理解と、繰り返しの試行錯誤、デバッグが必要である。

このプロセスには、 spec-kit のような仕様駆動開発（ Spec-Driven Development ）のためのツールキットの使用を強く推奨する。構造化されたマークダウンファイル（ spec.md , plan.md , tasks.md ）で要件を定義することにより、 AI は明確なテスト駆動開発（ TDD ）サイクルに従うことができ、複雑なタスクを管理可能なステップに分解してそれぞれを検証することが、成功に不可欠であることが証明されている。

6. chess-ant の GP モデルとの比較

  • ** chess-ant :** chess-ant の遺伝的プログラミングモデルは、大規模な進化的シミュレーションに依存している。集団内の各個体の評価のために、統計に使用される主要なインスタンス変数はリセットされるが、基礎となる MCTS 探索木は維持される。多くの世代にわたって各個体に対して完全な MCTS シミュレーションが実行されるこのプロセスは、計算量が膨大である。

  • ** mcts-gen :** AI エージェントが個体群全体を置き換える。単一の戦略を維持し、それを繰り返し改善する。 AI は、単一のバッチで実行する MCTS ラウンド数である 探索制限（ Search Limit ） を自ら決定するメインループを駆動する。これは chess-ant における 1 つの GP routine() に相当するが、戦略の洗練は世代交代による進化ではなく、各バッチの後に AI によって知的に行われる。さらに、リガンド生成のような複雑な領域において、エージェントは 立体配座の多様性（ Conformational Diversity ） を管理し、様々な 3D の向きを MCTS ツリー内の別個のアクションとして探索するようになった。その結果、探索プロセスは著しく効率的かつ現実的なものとなっている。

7. 参考文献