モンテカルロツリー検索の改善点

Question

私はゲームにMCTSアルゴリズムを実装しようとしています。私は移動あたり約0.33秒しか使用できません。この時点では、約500の子ノードを含む開始状態から、1つの子供につき1つまたは2つのゲームを生成することができます。私のシミュレーションはランダムではありませんが、もちろん、1つまたは2つのシミュレーションに基づいて正しい選択をすることはできません。さらにゲームではツリーが小さくなり、私の選択はより多くのシミュレーションに基づいています。

私の問題は、最初のいくつかの動きにあります。より多くのゲームをシミュレートできるようにMCTSアルゴリズムを改善する方法はありますか、別のアルゴリズムを使用すべきですか？

Answer 1

状態のヒューリスティックな評価関数を考え出すことは可能でしょうか？私は、MCTSの主な利点の1つは、理論上はこれを必要としないと考えていますが、とにかくやや妥当な評価関数を作成できれば、端末のゲーム状態に達する前に早期にシミュレーションを停止できます。次に、勝ち負けではなく、そのような非終端のゲーム状態の評価をバックアップすることができます。このように早期にシミュレーションを停止すると、より多くのシミュレーションを実行できます（個々のシミュレーションごとに時間がかからないため）。

それ以外は、「一般化」する方法を見つけようとします。 1つのシミュレーションを実行する場合は、通過しなかったツリー内の他のノードのシミュレーションから有用な情報を抽出できるかどうかを確認する必要があります。この精神の中で考慮したいかもしれない拡張の例は、AMAF、RAVE、プログレッシブヒストリー、Nグラム選択技法です。

パフォーマンスのボトルネックはどこにあるのか分かりませんか？これはプロファイラを使用して調べることができます。処理時間の大部分がゲームに関連する機能（世代の移動、ある州から次の州への進出など）に費やされている場合は、実行可能なシミュレーションの数に制限があることを確実に認識しています。次に、個々のシミュレーションを可能な限り有益なものにする拡張機能を実装するようにしてください。これは、例えば、計算上高価な評価関数を使用することを意味します。ゲームコード自体がすでに非常に最適化され、高速であれば、余分な計算時間を評価関数のようなものに移すことは、あなたのシミュレーションカウントにとってより有害であり、おそらくそれほど償わないでしょう。

私がMCTS-based agent in General Video Game AIに書いたいくつかのものを見てみると興味深いかもしれません。これは非常に計算コストの高いゲームのリアルタイム環境でもあり、シミュレーションのカウントが厳しく制限されています（しかし、分岐ファクタは、あなたの場合のようにはるかに小さくなります）。これに関する私の出版物のPDFファイルもオンラインで入手できます。