Mini-Max法とは

Mini-Max法は、チェスや将棋、オセロのように、2人が交互に手を選び、サイコロのような偶然の要素がなく、盤面の情報がすべて見えているゲーム（二人零和確定完全情報ゲーム）で、次の一手を決める方法です。考え方の土台は、数学者フォン・ノイマンが1928年に示したゲーム理論の定理にあります。1950年には、クロード・シャノンがコンピュータにチェスを指させる方法として論じました。

仕組み

まず、今の局面から先の手順を探索木に広げます。末端の局面には、自分にとっての有利さを表す評価値をつけます。終局まで読み切れるなら勝ち・負け・引き分けを使い、読み切れないなら評価関数で見積もった値を使います。

次に、末端から上へ向かって評価値を決めていきます。相手の手番のノードには、その下にある値の中で最も小さい値を入れます。相手は自分にとって最も不利な手を選ぶと仮定するからです。自分の手番のノードには、最も大きい値を入れます。最後に、最上段で最大の値につながる手を選びます。最小（Min）と最大（Max）を交互に取るので、Mini-Max法と呼びます。

意味と限界

この方法は、相手がどれだけうまく指しても確保できる値が最も大きい手を選ぶ、慎重な戦略です。ただし、先読みの手数が増えると、調べる局面の数が爆発的に増えます。そこで、結果を変えずに無駄な枝を省くαβ法が使われます。囲碁のように局面の数が非常に多く、評価関数を作りにくいゲームでは、モンテカルロ法を使った探索が発展しました。

覚え方

「相手の番はMin、自分の番はMax。最悪の場合の中で最善を選ぶ」と覚えます。