![企業-master.com [05/27update]](http://kigyo-m.com/image/kigyo-m.com.jpg)
ミニマックス法 wikipedia|無料辞書
前のページ 1/1 次のページ
ミニマックス法(minimax)は、想定される最大の損害が最小になるように決断を行う戦略のこと。
将棋、
チェスなどといった
完全情報ゲームをコンピュータに思考させるための
アルゴリズムの一つであり、それらの中で最も基礎となるものである。
これに対し、想定される最小の利益が最大になるように決断を行う戦略は
マクシミン戦略という。
◆ゲーム木
完全情報ゲームは、お互いがどの手を打ったかによってどのような局面が出現するかを場合分けしていくことでゲーム展開を樹形図にできる。このように現在の局面から出現するすべての局面の関係を
ゲーム木と呼ぶ。
ゲーム木は各段階で枝分かれてしていくが、枝分かれの数はプレーヤーの選択肢の数だけあり、ゲーム木を下にたどる(より先を読む)につれ局面(節点)の数は爆発的に増加する。
ゲームの思考をすることは、ゲーム木を読み解くことに他ならない。
◆思考プログラムの基本的な考え方
思考プログラムの基本は、局面がどの程度自分にとって有利か点数を付ける(評価する)ことである。局面の有利度を適切に評価することができれば、自分の打てる手のうち、最も評価の高い局面を出現させるような手を選択すればよいことになる。
局面に置かれている駒の位置・数などだけから算出した評価値を静的評価値、算出する関数を静的評価関数と呼ぶ。「静的」とはここでは先読みをしていないことを意味する。通常、静的評価関数だけで適切な局面評価を行うことは困難である。そのため、先読みを実現するのがこのミニマックス法である。
◆先読み
先を読んだ上で、ある局面がどの程度有利であるかを評価するには、以下の考え方を用いればよい。
#読みたい局面が相手の番であれば、その局面の次に出現するすべての局面のうち最も悪い(不利な)、つまり相手にとって最も有利な(評価値が最小)手を相手は打ってくるはずである。そこで、
次に出現するすべての局面の評価値の最小値を局面の評価値にすればよい。
#読みたい局面が自分の番であれば、その局面の次に出現するすべての局面のうち最も良い評価(評価値が最大)の手を打つことができる。そこで、
次に出現するすべての局面の評価値の最大値を局面の評価値にすればよい。
相手番の局面の評価値を求めるには、次に出現するすべての局面(自分番)の評価値を求めればいいので、その自分番の評価値を求めるには・・・、と再帰的にゲーム木を展開していくことで求めることができる。
何手先まで読むかによって、その深さまで展開したところでは静的評価関数を用いることで探索を打ち切ることができる。前述したように、ゲーム木は深くなるにつれ局面数が爆発的に増える。そのため、ある程度以上の深さまで先読みをしようとすると、実用的な時間では難しくなってくる。
通常は有限の深さまで読むことで打ち切るが、ゲーム終了まで読めばゲームの勝敗を完全に読み切った上で、最善の手を打つことができる。終盤の読みや
詰め将棋の解答などは完全読みが行われる(長手数の詰め将棋の解答では完全読みを行わないこともある)。
オセロのように勝敗だけでなく石差も問題となるゲームでは、勝敗のみを読み切ることを
必勝読み、石差まで読み切ることを
完全読みと区別する。
必勝読みでは、各局面の評価値は「勝ち」か「負け」の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
min := ∞;
for i:=1 to w do begin
score = MIN_MAX( children
[外部リンク]i, depth-1);
