[Machine Learning] ミニマックス法 （min-max method）

二人零和有限確定完全情報ゲームにおけるミニマックス法（mini-max method）の基本は

• 自分にとって良い指手は相手にとって都合が悪い（自分の指手は評価が最大になるように選択する）
• 相手は自分にとって最悪の指手を選択する（相手の指手は評価値が最小になるように選択する）

という考え方を基本として，先読みした結果から次の自分の手を決めるのがミニマックス法（min-max method）です．

ミニマックス法（min-max method）を使う場合，局面の評価値が必要となります．その評価値は評価関数によって得ることになりますが，評価関数は

• 先手が有利（後手が不利）な局面ほど大きな値（例えば正の値）
• 後手が有利（先手が不利）な局面ほど小さな値（例えば負の値）
• 互角の場合は0

となるように作るのが一般的です．

二人零和有限確定完全情報ゲームでミニマックス法（min-max method）で指手を決める例

この例では指手は常に2通りの差し手があるとし，探索を行うのに，先手，後手，先手の三手先まで読むこととします．

評価値は最も深いレベル（この場合は，三手指した後手の局面で計算するレベル3まで探索すると8通りの評価値が計算されます．この評価値を使ってA，Bどちらかの手を指すべきかをミニマックス法（min-max method）で決定する手順を示します．

まずは上図のR - A - Cの局面に着目すると，この局面では先手はGとHの2通りの差し手があり，この評価値はそれぞれ1と3だとします．ここでは，先手の手番なので，評価値が最大になる差し手（H - 3）を選択します．従って，局面Cの評価値は3になります．

同様にR - A - Dの局面を計算すると，局面DではIとJの指手があり，それらの評価値はそれぞれ4と2だとします．なので，Dの局面の評価値は4になります．

局面Aは後手の手番なので，評価値が最小になるようにCとDの小さい法（C - 3）を選ぶので，局面Aの評価値は3になります．

3手レベルまでの，G - Nの全ての探索を行って，下図のように8通りの評価値が得られたとすると，Bの評価値は2隣，局面Rは先手の手番なので，評価値の大きい指手（A - 3）が有利であることになります．

このように先手番では評価値が最大（max）になる指手を選び，後手番では評価値が最小（min）となる指手を選んで，最終的に次の指手を決定する方法がミニマックス法（min-max method）です．

ただし，この例のように，三手先までしか読んでいない結果から得られた差し手が，最善手である保証はありません．上記の例ではゲーム木を3レベルまで探索してAを選びましたが，もう1レベル深く探索したら，Bの方が有利になる可能性があるからです．一方で，ゲーム木を最後まで探索できれば，常に最善手を指すことができます．

関連する投稿
ミニマックス法（min-max method），