ミニマックス法

テンプレート:読み仮名は最大の損失を最小にする行動案を選択することである。ミニマックス探索とも。この「最大の損失を最小にする行動案を第一順位とする」という決定基準をテンプレート:読み仮名、テンプレート:読み仮名という。

数学的に定義した場合、ミニマックス基準とは行動案の集合 $A$、状態の集合 $S$、損失関数 $g_a:S\to ℝ(a\in A)$ があるとき行動案 $a_{\text{minimax}}=\arg min\underset{a\in A}{}(\underset{s\in S}{max}{g}_a(s))$ を第一順位とする決定基準である。また、混合戦略におけるマクシミン基準とは混合戦略集合 $\mathrm{\Sigma }$、期待損失関数 $D_{\sigma }:S\to ℝ(\sigma \in \mathrm{\Sigma })$ があるとき混合戦略 ${\sigma }_{\text{minimax}}=\arg min\underset{\sigma \in \mathrm{\Sigma }}{}(\underset{s\in S}{max}{D}_{\sigma }(s))$ を第一順位とする決定基準である。

大雑把に言えば、ミニマックス法では最悪ケースが最もマシになるように決定をおこなう。将棋、チェス、リバーシなどといった二人零和有限確定完全情報ゲームをコンピュータに思考させるためのアルゴリズムとしても用いられるが、元々はフォン・ノイマンが中心となって数学的に理論化されたゲーム理論において、打ち手を決定する際に適用されるルールの一つ。ミニマックス基準の裏返しである「最小の利得を最大にする行動案を第一順位とする」という決定基準はマクシミン基準という。

ゲーム理論では、ミニマックス基準で第一順位となったプレイヤー $i$ の戦略（≒ 行動案）をプレイヤー $i$ のテンプレート:読み仮名という。ミニマックス戦略を選択した際に得られうる最大損失の最小値、すなわち純粋戦略における $v_{\text{minimax}}=\underset{a\in A}{min}(\underset{s\in S}{max}{g}_a(s))$、混合戦略における $w_{\text{minimax}}=\underset{\sigma \in \mathrm{\Sigma }}{min}(\underset{s\in S}{max}{D}_{\sigma }(s))$ はテンプレート:読み仮名という。ミニマックス戦略を選択した場合、プレイヤー $i$ の損失はミニマックス値以下になる（高々ミニマックス値になる）ことが保証される。

ゲーム木

テンプレート:出典の明記 テンプレート:Main 完全情報ゲームは、お互いがどの手を打ったかによってどのような局面が出現するかを場合分けしていくことでゲーム展開を樹形図にできる。このように現在の局面から出現するすべての局面の関係をゲーム木と呼ぶ。

ゲーム木は各段階で枝分かれてしていくが、枝分かれの数はプレーヤーの選択肢の数だけあり、ゲーム木を下にたどる（より先を読む）につれ局面(節点)の数は劇的に増加する。

思考プログラムの基本的な考え方

思考プログラムの基本は、局面がどの程度自分にとって有利か点数を付ける(評価する)ことである。局面の有利度を適切に評価することができれば、自分の打てる手のうち、最も評価の高い局面を出現させるような手を選択すればよいことになる。

局面に置かれている駒の位置・数などだけから算出した評価値を静的評価値、算出する関数を静的評価関数と呼ぶ。「静的」とはここでは先読みをしていないことを意味する。通常、静的評価関数だけで適切な局面評価を行うことは困難である。そのため、先読みを実現するのがこのミニマックス法である。

先読み

先を読んだ上で、ある局面がどの程度有利であるかを評価するには、以下の考え方を用いればよい。

1. 読みたい局面が相手の番であれば、その局面の次に出現するすべての局面のうち最も悪い（不利な）、つまり相手にとって最も有利な(評価値が最小)手を相手は打ってくるはずである。そこで、次に出現するすべての局面の評価値の最小値を局面の評価値にすればよい。
   
2. 読みたい局面が自分の番であれば、その局面の次に出現するすべての局面のうち最も良い評価(評価値が最大)の手を打つことができる。そこで、次に出現するすべての局面の評価値の最大値を局面の評価値にすればよい。
   

相手番の局面の評価値を求めるには、次に出現するすべての局面(自分番)の評価値を求めればいいので、その自分番の評価値を求めるには・・・、と再帰的にゲーム木を展開していくことで求めることができる。

何手先まで読むかによって、その深さまで展開したところでは静的評価関数を用いることで探索を打ち切ることができる。前述したように、ゲーム木は深くなるにつれ局面数が爆発的に増える。そのため、ある程度以上の深さまで先読みをしようとすると、実用的な時間では難しくなってくる。

通常は有限の深さまで読むことで打ち切るが、ゲーム終了まで読めばゲームの勝敗を完全に読み切った上で、最善の手を打つことができる。終盤の読みや詰め将棋の解答などは完全読みが行われる（長手数の詰め将棋の解答では完全読みを行わないこともある）。リバーシのように勝敗だけでなく石差も問題となるゲームでは、勝敗のみを読み切ることを必勝読み、石差まで読み切ることを完全読みと区別する。

必勝読みでは、各局面の評価値は「勝ち」か「負け」の2通りに限定される。この場合、自分の手番の局面は、次の局面に「一つでも勝ち」があれば(自分はその局面を選択すればよいので)勝ちが決定し、相手の手番の局面は、次の局面が「すべて勝ち」なら(相手には負けを阻止する選択肢がないので)勝ちが決定する。これらは各局面の評価値の論理和（OR）、論理積（AND）とったものであることから、それぞれORノード、ANDノードと呼ばれる。このように評価値が勝敗のみで表されるゲーム木は、特にAND/OR木と呼ばれる。

擬似プログラム

以上のアルゴリズムを擬似コードで記述すると以下のようになる。

function MIN_MAX(position:局面, depth:integer): integer
begin
  if depth=0 then return STATIC_VALUE(position); {読み深さに達した}
  positionを展開→すべての子ノードをchildren[]に。子ノードの数をwに。
  if w=0 then return STATIC_VALUE(position); {終局}
  
  if positionは自分の局面 then begin
    max := -∞;
    for i:=1 to w do begin
      score = MIN_MAX( children[i], depth-1);
      if(score>max) max := score;
    end;
    return max;
  end else begin{positionは相手の局面}
    min := ∞;
    for i:=1 to w do begin
      score = MIN_MAX( children[i], depth-1);
      if(score<min) min := score;
    end;
    return min;
  end;
end;

マクシミン基準

テンプレート:読み仮名は「最小の利得を最大にする行動案を第一順位とする」という決定基準である。テンプレート:読み仮名、テンプレート:読み仮名とも。マクシミン基準を適用する手法はテンプレート:読み仮名と呼ばれる。

数学的に定義する場合、マクシミン基準とは、行動案の集合 $A$、状態の集合 $S$、利得関数 $f_a:S\to ℝ(a\in A)$ があるとき行動案 $a_{\text{maxmin}}=\arg max\underset{a\in A}{}(\underset{s\in S}{min}{f}_a(s))$ を第一順位とする決定基準である。

純粋戦略の場合、プレイヤー $i\in N$ のマクシミン基準とは、プレイヤー集合 $N$、プレイヤー $i$ の純粋戦略集合 $S_i(i\in N)$、$i$ 以外のプレイヤーの戦略の組み合わせの集合 $S_{-i}=\prod _{k\in N\setminus \{i\}}{S}_k(i\in N)$、プレイヤー $i$ の利得関数 $f_i:S_i\times S_{-i}\to ℝ(i\in N)$ があるとき純粋戦略 $s_{i,\text{maxmin}}=\arg max\underset{s_i\in S_i}{}(\underset{s_{-i}\in S_{-i}}{min}{f}_i(s_i,s_{-i}))$ を第一順位とする決定基準である。

混合戦略の場合、プレイヤー $i$ のマクシミン基準とは、$S_i$ に対応する $i$ の混合戦略集合 ${\mathrm{\Sigma }}_i(i\in N)$、$i$ 以外のプレイヤーの混合戦略の組み合わせの集合 ${\mathrm{\Sigma }}_{-i}=\prod _{k\in N\setminus \{i\}}{\mathrm{\Sigma }}_k(i\in N)$、 $i$ の期待利得関数 $E_i:{\mathrm{\Sigma }}_i\times {\mathrm{\Sigma }}_{-i}\to ℝ(i\in N)$ があるとき混合戦略${\sigma }_{i,\text{maxmin}}=\arg max\underset{{\sigma }_i\in {\mathrm{\Sigma }}_i}{}(\underset{{\sigma }_{-i}\in {\mathrm{\Sigma }}_{-i}}{min}f({\sigma }_i,{\sigma }_{-i}))$ を第一順位とする決定基準である。

マクシミン基準では、ある行動案に対して起こり得る全ての状態での利得を計算する。これら利得を比較することである行動案で得うる最小の利得（= 最悪ケースでの利得、保証水準（テンプレート:Lang-en-short））がわかる。これを全ての行動案に対しておこなうと各行動案での最小利得がわかる。それらを比較し、最小の利得が最大となる行動案を第一順位とする。大雑把に言えば、マクシミン基準では最悪ケースが最もマシになるように決定をおこなう。常に最悪の状況を想定する悲観主義者がその中で合理的に利得を最大化しようとする方法とも捉えられるため、悲観的決定基準とも呼ばれる。

マクシミン基準はミニマックス基準の裏返しである。損失が利得の逆すなわち損失関数 $g_a=-f_a$ である場合、負符号と min/max 反転に気をつけると、純粋戦略において次が常に成立する：

$\begin{array}{cc}{a}_{\text{maxmin}}& =\arg max\underset{a\in A}{}(\underset{s\in S}{min}{f}_a(s))\\ & =\arg max\underset{a\in A}{}(-\underset{s\in S}{max}{g}_a(s))\\ & =\arg min\underset{a\in A}{}(\underset{s\in S}{max}{g}_a(s))=a_{\text{minimax}}\end{array}$

すなわち、損失が利得の逆ならマクシミン基準とミニマックス基準は同義である。

ゲーム理論では、マクシミン基準で第一順位となったプレイヤー $i$ の戦略（≒ 行動案）をプレイヤー $i$ のテンプレート:読み仮名という。マクシミン戦略を選択した際に得られうる最小利得の最大値、すなわち純粋戦略における $v_{\text{maxmin}}=\underset{a\in A}{max}(\underset{s\in S}{min}{f}_a(s))$、混合戦略における $w_{\text{maxmin}}=\underset{\sigma \in \mathrm{\Sigma }}{max}(\underset{s\in S}{min}{E}_{\sigma }(s))$ はテンプレート:読み仮名という。マクシミン戦略を選択した場合、プレイヤー $i$ の利得はマクシミン値以上になることが保証される。

マクシミン基準は確率分布を要さない決定基準であり、不確実性がある状況での決定に用いることができる。

ネガマックス法

チェスなどパスのないゲームでは、ノードごとに評価値の正負を逆転させることで「相手は自分にとって損な手を探索する」のではなく「相手は相手にとって得な手を探索する」ように書き換えることができる。これをネガマックス(Negamax)法と呼ぶ。

function NEGA_MAX(position:局面, depth:integer): integer
begin
  if depth=0 then return STATIC_VALUE(position); {読み深さに達した}
  positionを展開→すべての子ノードをchildren[]に。子ノードの数をwに。
  if w=0 then return STATIC_VALUE(position); {終局}
  
  max := -∞;
  for i:=1 to w do begin
    score = -NEGA_MAX( children[i], depth-1);
    if(score>max) max := score;
  end;
  return max;
end;

応用アルゴリズム

ミニマックス法はすべての局面に対してしらみつぶしに探索を行うため、実際には読む必要のない（評価しなくても支障がない）手も読むことになり探索効率が悪い。これを改善したアルゴリズムとしてα-β法がある。α-β法は、読む必要のない手を打ち切ることで高速化を図っている。

実際のゲームプログラムではα-β法をさらに応用したアルゴリズムが用いられることが多い。

参考文献

• テンプレート:Cite book

関連項目

• 決定基準
• 決定理論
  • ゲーム理論