minimax・得点差・局面値を評価するゲームDP
概要
有限局面DAGのminimax
相手も最善を尽くすとき、自分の一手で最終結果をどこまで良くできるかを求める。扱うのは、互いに局面をすべて把握でき、偶然による分岐がなく、一方が大きくしたい評価を他方が小さくしたい二人零和ゲームである。得点差なら「自分の得点−相手の得点」を評価にすれば、両者の目的が逆向きになる。
局面を頂点、合法な一手を有向辺とするグラフを考える。この単元では局面数が有限で、同じ局面へ戻る循環がない場合を扱う。この有向非巡回グラフをDAGと呼ぶ。終端の評価から始め、手番に応じて後続の値の最大・最小を選ぶ方法がminimaxである。
考え方
手番側の得点差なら、次の局面の値を引く
まず、袋が一列に並び、交互に左端か右端の袋を一つ取り、その中の点数を得るゲームを考える。袋がなくなったら終了し、双方が自分と相手の得点差を最大にする。これはこの単元用の独自の小例であり、ABC349 Eの盤面やABC303 Gの有料の操作を表すものではない。
残り列を とし、 を「ここから先に、今の手番の人が得る点数−相手が得る点数」の最適値とする。すでに取った点数は含めない。空の列を と書くと、追加の点数はないので 。一袋だけならそれを取るしかなく、、 となる。
残り列が のときは、最初の一手を二通りとも調べる。
- 2を取ると、相手は残る7を取る。次の局面の は相手から見た得点差なので、今の手番側から見た値は 。
- 7を取ると、相手は残る2を取る。同様に 。
したがって で、7を取るのが最適である。相手の値を引くのは、相手も得点差を最大にしようとするからであり、次の手番でも最大を取ってよい。局面 から一手で進む局面を 、その一手で得る点数を とすれば、非終端の式は
となる。手番が毎回交代することと、 の評価基準が相手へ変わることを一組で覚える。同じ人が続けて動く規則なら、その遷移で機械的に符号を反転してはいけない。
固定したLeft側の利得なら、手番ごとに最大・最小を切り替える
同じ小例で、二人をLeftとRightと呼び、評価を常に「Leftの点数−Rightの点数」に固定する。残り列 と手番 に対する、ここから先の得点差の最適値を とする。手番の記号はLeftなら 、Rightなら と書く。空の列の値はどちらの手番でも0である。
Leftが点数 を取る一手は 、Rightが取る一手は を加える。Leftはこの値を最大に、Rightは最小にしたい。先ほどの二通りを、Leftの手番から固定基準で追う。
- Leftが2を取ると、Rightは残る7を取る。空列の値は0なので、残り一袋の局面値は 。最初の手も含めた値は となる。
- Leftが7を取ると、Rightは残る2を取る。残り一袋の局面値は 。最初の手も含めた値は となる。
Leftは最大の5を選ぶ。一方、同じ残り列 でRightの手番なら、Rightが2を取る枝は 、7を取る枝は なので、 を選ぶ。ここでもRight自身から見た得点差は5である。
この得点ゲームでは、 を手番側の取得点数とすると、Leftの手番の式は
となる。一方、Rightの手番の式は
となる。ここでは に手番も含めた。Rightの取得点数はLeftの得点差を減らすので、最大・最小を替えるだけでなく一手の加点の符号も替える。二つの表現の関係は、Left手番なら 、Right手番なら 。同じ最適行動を違う基準で記録している。
終端の規則を決めてから、後続の値を戻す
小例の空列を0にできたのは、取得点数を一手ごとに加算済みで、終端に追加の利得がないからである。勝敗や終局時の評価を返す問題では、その規則を基底にする。
ABC349 Eでは、まず同色の三目が成立していればその色の勝ちとして終了する。三目がなく盤面が満杯のときだけ得点を比較する。Leftを高橋君とし、高橋君の勝ちを 、青木君の勝ちを と置けば、途中の一手には点数を加えず、終端の勝敗を最大・最小で戻せる。盤面の得点差をそのまま勝敗の値にしたり、満杯なら一律0にしたりすると、三目の優先順位を失う。
ABC303 Gでは、一手で袋から得た金額から、その手で支払う金額を引いた純利得を とする。手番側基準ではその純利得から次の局面の を引く。空区間は追加の利得がないので0だが、最後の一手での取得額・支払額はその遷移に含める。
計算は終端から始める。小例では袋数が毎回一つ減るので、空列、一袋、二袋の順に評価できる。一般の区間でも残り長が小さい順に進めればよい。盤面なら空きマス数など、一手で必ず減る量を探す。メモ化再帰なら、まず終端を判定し、未計算の後続を求めてから現在の値を保存する。
各後続の値が正しければ、一手を固定した後の最適な結果も正しく分かる。その全候補から手番の目的に沿う最大・最小を選ぶので、現在の局面値も正しい。これをDAGの終端から繰り返せば、初期局面の値が得られる。最良値を達成する手も保存すれば、相手の手への応答を含む戦略を復元できる。
成立条件と計算量
状態には、合法手と将来の評価を決める情報をすべて含める。同じ盤面でも手番が違えば選べる手や評価の向きが変わるため、通常は手番も持つ。ABC349 Eでは塗られたマス数の偶奇から手番を復元でき、別の添字は不要である。小例やABC303 Gでは双方の操作規則が同じなので、手番側基準の得点差にすれば個人名を状態から省ける。特にABC303 Gでは一手で複数袋を取れるため、残り袋数の偶奇から個人の手番を決めてはいけない。
評価する異なる局面の数を 、それらから調べる合法手の総数を とする。各局面を一度だけ評価し、一手の値の合成・比較と終端判定が定数時間なら、時間計算量は 。局面表現の構築、合法手の生成、終端の評価にそれ以上の費用がかかるなら、その総費用も加える。メモ化せず同じ局面を何度も訪ねる探索の費用を、この局面数だけで評価してはいけない。小例を長さ の列へ広げた場合、残り区間は 個、各区間の手は高々二つなので、時間・空間ともに である。ABC303 Gの複数袋を取る遷移では候補が増えるため、さらに集約の工夫が要る。
局面の表現と値を一つあたり定数領域で持ち、後続をその場で生成するなら、値・最適手の保存と再帰スタックに必要な空間は 。全合法手を辺として保存するなら となり、入力や盤面操作の作業領域は別に加える。
引き分けが終端規則として決まるなら、その値を与えて同じDAG上で評価できる。循環による無限継続と の扱いは循環局面の後退解析とminimax距離、独立ゲームのGrundy数のXORはゲーム状態の勝敗とGrundy数、Conwayの数の加算は独立な数ゲームの和で扱う。ここでの得点差を、独立ゲームの勝敗を合成する数へそのまま流用しない。
問題一覧
- ABC349 E「Weighted Tic-Tac-Toe」 公式問題
技能・出典
主題: minimax・得点差・局面値を評価するゲームDP(有限DAGの局面で手番ごとの最大化・最小化と終端値を定義し、得点差や利得を後続状態から評価できる。循環時の無限継続と独立な数ゲームの加算は別の技能として扱う。)。主タグ: 有限局面DAGのminimax
- ABC303 G「Bags Game」 公式問題
技能・出典
主題: minimax・得点差・局面値を評価するゲームDP(有限DAGの局面で手番ごとの最大化・最小化と終端値を定義し、得点差や利得を後続状態から評価できる。循環時の無限継続と独立な数ゲームの加算は別の技能として扱う。)。既習技能: 支配関係から不要な候補を単調stack・queueで削る(候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。)。主タグ: 有限局面DAGのminimax / 補助タグ: 単調stack・queueによる支配候補の削除
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC218 G「Game on Tree 2」 公式問題
技能・出典
主題: rollback・DFS入退場の状態復元(更新前の差分をstackへ記録し、分割統治・時間Segment Tree・DFSの退場時に状態を正確に巻き戻す。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: minimax・得点差・局面値を評価するゲームDP(有限DAGの局面で手番ごとの最大化・最小化と終端値を定義し、得点差や利得を後続状態から評価できる。循環時の無限継続と独立な数ゲームの加算は別の技能として扱う。) / ordered set・multisetの動的順序管理(比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: rollback・DFS入退場の状態復元 / 補助タグ: 有限局面DAGのminimax、ordered set・multisetの動的順序管理
前提・学習成果・出典
習得対象の目安: 水色(1200–1599)。手番と終端利得を明示し、minimaxや得点差の再帰を実装する。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 動的計画法。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-dp-game-value
習得する技能
- 有限DAGの局面で手番ごとの最大化・最小化と終端値を定義し、得点差や利得を後続状態から評価できる。循環時の無限継続と独立な数ゲームの加算は別の技能として扱う。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: 最小十分状態からDPを設計する。
このUnitを直接前提とする単元: 独立な数ゲームの和、循環局面の後退解析とminimax距離。
状態遷移を設計できることを前提に、双方の最適行動を最大化・最小化として評価する。
このUnitでは扱わないもの
- 勝敗だけを分類する通常の後退解析・Grundy数。