私はゲーム ソルバーの作成に約 1 か月間取り組んでおり、さまざまな戦略を試していますが、そのほとんどはブルート フォースに重点を置いています。これは、ゲームの単純なケースでは機能しますが、より複雑なケース (ゲーム ツリーの深さが高い) では失敗します。以下は、ゲームの抽象的な定式化です。
1) 実行可能な一連のアクションがあります。A.
2) 状態にアクションを適用すると、可能な状態の確率分布が生成されます。apply(A, s) = [[s1, p1], [s2, p2], [s3, p3]]
3) ゴール状態に到達するとゲームは終了します。
4) 各状態には、それに関連付けられたスコアがあります。
3) 目標状態には、状態のスコアが前の状態のスコアである「成功」状態と、スコアが 0 である「失敗」状態の 2 種類があります。
5) 目標は、ゲーム終了時の平均スコアを最大化する戦略を作成することです。
6) サイクルはありません。すべてのパスには有限の長さがあります。
私はこのゲームを可能な限り抽象的な意味で定式化しました。私の現在の戦略は、作業の重複を防ぐために一意の状態をキャッシュする単純な深さ優先検索です。これは、メモリが不足する約 2 億の一意の状態まで機能します。最適化を見つけるために下位レベルの詳細を分解する前に、ゲームの一般的なケースに適した巧妙なアルゴリズムがあるかどうかを知りたい. 状態遷移がどのように生成されるかの詳細に興味がある場合は、提供できます。問題を既知の問題に減らすいくつかの方法を次に示します。
1) 状態報酬関数が非ゴール状態の場合は 0 であり、それ以外の場合はゴール状態のスコアである確率的マルコフ決定プロセス。MDP の一般的なアルゴリズムがあまり効率的でないことはわかっていますが、MDP の特定のクラスには効率的なソリューションがあります。この問題は、これらの特定のクラスのいずれかに当てはまりますか?
2) 辺の重みが負の有向非巡回グラフにおける確率的最長経路問題。