循環局面の後退解析とminimax距離

概要

終了局面から逆辺を辿り、終了側が一手選べば確定するOR局面と全手の確定を待つAND局面を区別する。未確定局面で無限継続を判定し、非負重みなら優先度付きキューで有限なminimax距離を確定する。

DAGのminimax再帰をそのまま循環グラフへ適用すると終了しない。終了へ強制できる集合を終端から拡大し、ORでは一つの確定手、ANDでは全手の確定を必要とする。未確定集合に残れる相手の選択を示して無限継続を証明する。

ABC261 Exの非負重みではminimax距離順の確定を使う。ABC413 Fでは妨害側が一方向を禁止する手と移動側の手をまとめると、二番目の有限な隣接値で確定する閾値規則になる。通常の最短路の一隣接確定とは区別する。

考え方

終了を目指すmin側と、妨害するmax側

状態には盤面だけでなく次の手番も含める。終端へ到達すると終了し、辺重みw≥0の累積費用をmin側が最小化、max側が最大化する。無限継続の値は、重みの総和が有限でも∞とする。終端の値は0で、終端は以降の手を持たない。非終端の手詰まりも終了扱いにするなら初めから終端へ含める。

有限に終了させられる状態の値は、min手番で d(v)=min_{v→u}(w(v,u)+d(u))、max手番で d(v)=max_{v→u}(w(v,u)+d(u)) となる。min側は一つの有限な後続を選べればよいOR、max側は全ての後続が有限でなければ∞を選べるANDである。これは交互に必勝・必敗を決めるnormal playの勝敗DPとは目的が異なる。

有限性の後退解析

まず距離を忘れて有限性だけを考える。終端を確定し、逆辺でその確定を前の状態へ伝える。OR状態は後続一つの確定で確定、AND状態は保持した未確定後続数remを一つ減らし、rem=0になって初めて確定する。各辺の伝播を一回にすればO(S+T)で有限集合を求められる。

最後の未確定集合では、ORの全後続が未確定、ANDには少なくとも一つ未確定の後続がある。max側がその手を選べばmin側が何を選んでも未確定集合へ残り続け、終端に入らない。したがって未確定の値は∞である。有限性を示す証拠なしに循環した方程式の解だけを採用してはいけない。例えば、max状態の重み0の自己loopと終端への辺は方程式上d=0を許しても、max側がloopを選び続けるため実際は∞となる。

距離順で候補を確定する更新

数値版は有限性の後退解析を優先度付きキューで行う。全状態に確定flag、ORには最良候補best=∞、ANDにはrem=出次数と最大候補mx=0を持つ。終端は距離候補0でmin-heapへ入れる。

  1. heapから最小候補(a,u)を取り出す。既に確定済み、またはORの古い候補なら捨て、そうでなければd(u)=aで確定する。
  2. 各逆辺v→uについて候補b=w(v,u)+d(u)を作る。vがORならbest[v]をmin(best[v],b)へ更新し、改善した候補をheapへ入れる。この時点ではまだvを確定しない。
  3. vがANDならrem[v]を減らし、mx[v]をmax(mx[v],b)へ更新する。rem[v]=0になった時だけ、候補(mx[v],v)をheapへ入れる。一つの小さい後続値だけでANDを登録しない。

ORも「最初に伝わった後続」で即座に確定しない。後続距離が小さくても辺が重ければ候補は大きく、後に伝わる別の候補が改善するからである。候補そのものをheapで比較し、取り出した時に確定する。ANDは全後続の確定後なので最大値を正確に取得できる。

非負重みより各候補は元の確定値以上で、ANDの最大候補も全ての後続値以上となる。よって確定値は非減少に並ぶ。ORにさらに小さい有限解があれば、その手の後続値も現在の候補以下で、その有限な終了戦略を終端まで辿ると小さい候補が先に伝わるはずである。ANDも全後続を待つためmax側の選択を過小評価しない。重み0で値が同じ場合も、ORの選ぶ後続やANDの全後続は先に確定した状態へ向かうので、確定順を逆に辿る有限な終了戦略が得られる。

heapが空になったら未確定は上記の∞。ORでbestを達成する辺を保存すればmin側の有限戦略を復元できる。ANDのremは後続頂点数ではなく合法遷移数を数え、多重辺はそれぞれ一回伝播する。ABC261 Ex公式解説では盤面頂点×手番の二状態を、この後退解析で評価する。

成立条件と計算量

S状態・T遷移に対し、数値版では各状態を一度確定、各逆辺を一度処理し、候補のheap操作はO(S+T)回。古い候補を残す二分heapならO((S+T) log(S+T))、記憶O(S+T)。状態の位置を管理してdecrease-keyするheapならO((S+T) log S)となる。有限性だけならheapは不要でO(S+T)。盤面を二手番へ展開する場合は、その後のS,Tを数える。

非負重みと「無限継続は∞、手詰まりは終端0」という目的が前提。負辺、途中の任意停止、無限継続を引き分けや累積和の極限で評価する規則には、この確定法をそのまま適用しない。∞を通常の整数として加算せず、有限距離にも累積費用を格納できる型を使う。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

前提・学習成果・出典

習得対象の目安: 黄色(2000–2399)。循環する局面でOR・ANDの確定条件を分け、引き分けと有限minimax距離を判定する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 動的計画法。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-cyclic-minimax-game

循環局面の後退解析とminimax距離

習得する技能

  • 終了局面から逆辺を辿り、終了側が一手選べば確定するOR局面と全手の確定を待つAND局面を区別する。未確定局面で無限継続を判定し、非負重みなら優先度付きキューで有限なminimax距離を確定する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: minimax・得点差・局面値を評価するゲームDP。

このUnitを直接前提とする単元: なし。

有限局面DAGのminimaxで得た考え方と実装を再利用し、循環局面の後退解析とminimax距離の発動条件・正当化・境界を重複なく学ぶ。

このUnitでは扱わないもの

  • 循環局面の後退解析とminimax距離の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠