私は質問に出くわし、最終結果を予測できるかどうか疑問に思っていました.
これは、グラフ (有向非巡回グラフ) 上の 1 対 1 (交互移動) ゲームです。
開始点またはノードから、プレーヤー 1 はノード v1 へのエッジを選択します。ノード v1 から、プレーヤー 2 はノード v3 へのエッジを選択します。
勝つ方法: アウトエッジのないノードに到達したプレーヤーが負けます。
他のプレイヤーが何をしても勝利を保証できるアルゴリズムを考え出すことは可能ですか?
したがって、開始ノードは s です。プレーヤー 1 は C または A のいずれかを選択できます。つまり、基本的に、勝利を保証できる何らかのアルゴリズムに基づいて決定を下す方法はありますか?
この場合、私がノード D または B にいて、ノード E に向かうエッジを選択すると、プレイヤー 2 がノード E で立ち往生する場合に勝ちます。
*距離は関係ない
グラフのノードを、勝者ノードと敗者ノードの 2 つのタイプに分類する必要があります。勝利ノードは、現在のプレイヤーがそのノードにいる場合に勝利戦略を持っているノードであり、敗北ノードは、現在のプレイヤーがどのようにプレイしても負けるノードです (対戦相手が正しくプレイすると仮定します)。これは有向非巡回グラフであるため、すべてのノードが勝つか負けるかのいずれかになります (最終的には出力エッジのないノードに到達するため)。
発信エッジのないノードは、明らかにノードを失います。別のノード N の場合:
すべてのノードを分類するには、ノードを逆位相順序で調べます。上記のルールに従って各ノードを分類します。逆トポロジ順序は、N を分類する前に、N から到達できるすべてのノードを分類したことを保証します。
終了したら、開始ノードが勝利ノードである場合、勝利戦略があります。常に敗北ノードへのエッジを選択します。
一般的に、いいえ。グラフによって異なります。奇数のノード（= n個のノードとn-1個のエッジのグラフ）の単純なツリー/チェーンがあるとします。そうすれば、強制的に勝つことはできないので、プレーヤー2は常に勝ちます。
ゲーム戦略を導くために、いくつかの最小-最大アルゴリズムを見ることができます。それらを使用すると、最後から始めて戻って、DAGの各サブDAGの勝者を決定することで、誰が再帰的に勝つかを決定できます。