minimax・得点差・局面値を評価するゲームDP

概要

有限局面DAGのminimax

相手も最善を尽くすとき、自分の一手で最終結果をどこまで良くできるかを求める。扱うのは、互いに局面をすべて把握でき、偶然による分岐がなく、一方が大きくしたい評価を他方が小さくしたい二人零和ゲームである。得点差なら「自分の得点−相手の得点」を評価にすれば、両者の目的が逆向きになる。

局面を頂点、合法な一手を有向辺とするグラフを考える。この単元では局面数が有限で、同じ局面へ戻る循環がない場合を扱う。この有向非巡回グラフをDAGと呼ぶ。終端の評価から始め、手番に応じて後続の値の最大・最小を選ぶ方法がminimaxである。

考え方

手番側の得点差なら、次の局面の値を引く

まず、袋が一列に並び、交互に左端か右端の袋を一つ取り、その中の点数を得るゲームを考える。袋がなくなったら終了し、双方が自分と相手の得点差を最大にする。これはこの単元用の独自の小例であり、ABC349 Eの盤面やABC303 Gの有料の操作を表すものではない。

残り列を ss とし、D(s)D(s) を「ここから先に、今の手番の人が得る点数−相手が得る点数」の最適値とする。すでに取った点数は含めない。空の列を ∅\varnothing と書くと、追加の点数はないので D(∅)=0D(\varnothing)=0。一袋だけならそれを取るしかなく、D((2))=2D((2))=2、D((7))=7D((7))=7 となる。

残り列が (2,7)(2,7) のときは、最初の一手を二通りとも調べる。

  • 2を取ると、相手は残る7を取る。次の局面の D((7))=7D((7))=7 は相手から見た得点差なので、今の手番側から見た値は 2−D((7))=2−7=−52-D((7))=2-7=-5。
  • 7を取ると、相手は残る2を取る。同様に 7−D((2))=7−2=57-D((2))=7-2=5。

したがって D((2,7))=max⁡(2−7,7−2)=5D((2,7))=\max(2-7,7-2)=5 で、7を取るのが最適である。相手の値を引くのは、相手も得点差を最大にしようとするからであり、次の手番でも最大を取ってよい。局面 vv から一手で進む局面を uu、その一手で得る点数を r(v,u)r(v,u) とすれば、非終端の式は

D(v)=max⁡v→u(r(v,u)−D(u))D(v)=\max_{v\to u}\bigl(r(v,u)-D(u)\bigr)

となる。手番が毎回交代することと、D(u)D(u) の評価基準が相手へ変わることを一組で覚える。同じ人が続けて動く規則なら、その遷移で機械的に符号を反転してはいけない。

固定したLeft側の利得なら、手番ごとに最大・最小を切り替える

同じ小例で、二人をLeftとRightと呼び、評価を常に「Leftの点数−Rightの点数」に固定する。残り列 ss と手番 pp に対する、ここから先の得点差の最適値を V(s,p)V(s,p) とする。手番の記号はLeftなら LL、Rightなら RR と書く。空の列の値はどちらの手番でも0である。

Leftが点数 aa を取る一手は +a+a、Rightが取る一手は −a-a を加える。Leftはこの値を最大に、Rightは最小にしたい。先ほどの二通りを、Leftの手番から固定基準で追う。

  • Leftが2を取ると、Rightは残る7を取る。空列の値は0なので、残り一袋の局面値は V((7),R)=−7+0=−7V((7),R)=-7+0=-7。最初の手も含めた値は 2+(−7)=−52+(-7)=-5 となる。
  • Leftが7を取ると、Rightは残る2を取る。残り一袋の局面値は V((2),R)=−2+0=−2V((2),R)=-2+0=-2。最初の手も含めた値は 7+(−2)=57+(-2)=5 となる。

Leftは最大の5を選ぶ。一方、同じ残り列 (2,7)(2,7) でRightの手番なら、Rightが2を取る枝は −2+7=5-2+7=5、7を取る枝は −7+2=−5-7+2=-5 なので、V((2,7),R)=min⁡(5,−5)=−5V((2,7),R)=\min(5,-5)=-5 を選ぶ。ここでもRight自身から見た得点差は5である。

この得点ゲームでは、r(v,u)r(v,u) を手番側の取得点数とすると、Leftの手番の式は

V(v)=max⁡v→u(r(v,u)+V(u))V(v)=\max_{v\to u}\bigl(r(v,u)+V(u)\bigr)

となる。一方、Rightの手番の式は

V(v)=min⁡v→u(−r(v,u)+V(u))V(v)=\min_{v\to u}\bigl(-r(v,u)+V(u)\bigr)

となる。ここでは vv に手番も含めた。Rightの取得点数はLeftの得点差を減らすので、最大・最小を替えるだけでなく一手の加点の符号も替える。二つの表現の関係は、Left手番なら V=DV=D、Right手番なら V=−DV=-D。同じ最適行動を違う基準で記録している。

終端の規則を決めてから、後続の値を戻す

小例の空列を0にできたのは、取得点数を一手ごとに加算済みで、終端に追加の利得がないからである。勝敗や終局時の評価を返す問題では、その規則を基底にする。

ABC349 Eでは、まず同色の三目が成立していればその色の勝ちとして終了する。三目がなく盤面が満杯のときだけ得点を比較する。Leftを高橋君とし、高橋君の勝ちを +1+1、青木君の勝ちを −1-1 と置けば、途中の一手には点数を加えず、終端の勝敗を最大・最小で戻せる。盤面の得点差をそのまま勝敗の値にしたり、満杯なら一律0にしたりすると、三目の優先順位を失う。

ABC303 Gでは、一手で袋から得た金額から、その手で支払う金額を引いた純利得を r(v,u)r(v,u) とする。手番側基準ではその純利得から次の局面の D(u)D(u) を引く。空区間は追加の利得がないので0だが、最後の一手での取得額・支払額はその遷移に含める。

計算は終端から始める。小例では袋数が毎回一つ減るので、空列、一袋、二袋の順に評価できる。一般の区間でも残り長が小さい順に進めればよい。盤面なら空きマス数など、一手で必ず減る量を探す。メモ化再帰なら、まず終端を判定し、未計算の後続を求めてから現在の値を保存する。

各後続の値が正しければ、一手を固定した後の最適な結果も正しく分かる。その全候補から手番の目的に沿う最大・最小を選ぶので、現在の局面値も正しい。これをDAGの終端から繰り返せば、初期局面の値が得られる。最良値を達成する手も保存すれば、相手の手への応答を含む戦略を復元できる。

成立条件と計算量

状態には、合法手と将来の評価を決める情報をすべて含める。同じ盤面でも手番が違えば選べる手や評価の向きが変わるため、通常は手番も持つ。ABC349 Eでは塗られたマス数の偶奇から手番を復元でき、別の添字は不要である。小例やABC303 Gでは双方の操作規則が同じなので、手番側基準の得点差にすれば個人名を状態から省ける。特にABC303 Gでは一手で複数袋を取れるため、残り袋数の偶奇から個人の手番を決めてはいけない。

評価する異なる局面の数を SS、それらから調べる合法手の総数を TT とする。各局面を一度だけ評価し、一手の値の合成・比較と終端判定が定数時間なら、時間計算量は O(S+T)O(S+T)。局面表現の構築、合法手の生成、終端の評価にそれ以上の費用がかかるなら、その総費用も加える。メモ化せず同じ局面を何度も訪ねる探索の費用を、この局面数だけで評価してはいけない。小例を長さ NN の列へ広げた場合、残り区間は O(N2)O(N^2) 個、各区間の手は高々二つなので、時間・空間ともに O(N2)O(N^2) である。ABC303 Gの複数袋を取る遷移では候補が増えるため、さらに集約の工夫が要る。

局面の表現と値を一つあたり定数領域で持ち、後続をその場で生成するなら、値・最適手の保存と再帰スタックに必要な空間は O(S)O(S)。全合法手を辺として保存するなら O(S+T)O(S+T) となり、入力や盤面操作の作業領域は別に加える。

引き分けが終端規則として決まるなら、その値を与えて同じDAG上で評価できる。循環による無限継続と ∞\infty の扱いは循環局面の後退解析とminimax距離、独立ゲームのGrundy数のXORはゲーム状態の勝敗とGrundy数、Conwayの数の加算は独立な数ゲームの和で扱う。ここでの得点差を、独立ゲームの勝敗を合成する数へそのまま流用しない。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 水色(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数。

根拠