ミニマックス法

ミニマックス法とは

ミニマックス法（Minimax）は、意思決定理論、特にゲーム理論において重要な役割を果たす戦略の一つです。この戦略の核心は、「相手が取りうる最悪のシナリオを想定し、その上で自分にとって最も有利な（すなわち、想定される最大の損害が最も小さくなる）選択肢を選ぶ」という点にあります。これは、不確実な状況下でリスクを最小限に抑えたい場合に有効なアプローチと言えます。

フォン・ノイマンらが数学的に体系化したゲーム理論に由来するミニマックス法は、将棋やチェス、リバーシといった、二人で対戦し、一方が得をすれば他方が損をする（零和）、手数が限られており、全ての情報がお互いに開示されている（完全情報）ゲームにおいて、コンピュータが最善手を探索するための主要なアルゴリズムとして広く応用されています。

対照的に、想定される最小の利益が最大になるように決定を下す戦略は「マクシミン戦略」と呼ばれ、ミニマックス法とはリスクへの捉え方が異なります。

ゲーム木を用いた思考プロセス

完全情報ゲームでは、現在の局面から可能な全ての手を順に追っていくことで、ゲームの展開を樹状の構造として表現できます。これを「ゲーム木」と呼びます。ゲーム木は、ある局面（節点）から次の局面へと、プレイヤーの可能な手の数だけ枝分かれして伸びていきます。

コンピュータがゲームを思考する基本的な考え方は、まず現在の局面や、これから出現しうる局面が、自分にとってどれだけ有利かを数値化して評価することです。この評価値を「静的評価値」と呼び、現在の駒の配置など、その局面の情報のみに基づいて算出する関数を「静的評価関数」と言います。「静的」とは、将来の展開を考慮していないことを意味します。

しかし、実際のゲームでは、目の前の状況だけでなく、数手先の展開を読み切ることが勝敗に直結します。静的評価関数だけで局面の優劣を正確に判断することは困難であるため、ミニマックス法のような先読みアルゴリズムが必要となります。

ミニマックス法による先読みの仕組み

ミニマックス法では、将来の局面を評価するために、以下の再帰的な考え方を利用します。

1. 相手の番の局面を評価する場合: 相手は自分にとって最も不利になる手（つまり、相手にとって最も有利になる手、評価値が最小になる手）を選んでくると仮定します。したがって、その局面の次に現れる可能性のある全ての局面（自分の番）の評価値を計算し、その中で最も低い評価値をその相手番の局面の評価値とします。
2. 自分の番の局面を評価する場合: 自分は自分にとって最も有利になる手（評価値が最大になる手）を選べると仮定します。したがって、その局面の次に現れる可能性のある全ての局面（相手の番）の評価値を計算し、その中で最も高い評価値をその自分の番の局面の評価値とします。

このように、局面の評価値を求めるために、その次の局面の評価値を求め、さらにその次の…と、ゲーム木を深く探索しながら再帰的に計算を進めていきます。

探索の深さと効率

ゲーム木は、深くなるにつれて考慮すべき局面数が爆発的に増加します。そのため、現実的な時間内に計算を終えるために、あらかじめ定めた一定の深さまで探索したら計算を打ち切り、その時点の局面を静的評価関数で評価して探索の終点とすることが一般的です。

ゲーム終了まで完全に読み切る「完全読み」は、特に終盤や詰みの局面で行われることがありますが、非常に長い手数の場合は困難です。リバーシのように、勝敗だけでなく点差も重要なゲームでは、勝敗のみを読み切ることを「必勝読み」、点差まで読み切ることを「完全読み」と区別することもあります。

勝敗のみを評価値とする場合、ゲーム木は特に「AND/OR木」と呼ばれます。自分の手番の局面（ORノード）は、次局面に一つでも勝ちがあれば勝ちとみなされ、相手の手番の局面（ANDノード）は、次局面が全て勝ちであれば勝ちとみなされます。

応用アルゴリズム

基本的なミニマックス法は、将来の全ての可能性を網羅的に探索するため、実際には考慮する必要のない（相手が選ばないような）手まで評価してしまい、効率が悪いという欠点があります。この効率を改善するために、「α-β法」という枝刈りアルゴリズムが開発されました。α-β法は、明らかに最善手ではないと判断できる局面の探索を打ち切ることで、計算量を大幅に削減します。

また、ミニマックス法を改良した「ネガマックス法」も存在します。これは、パスのないゲームなど特定の条件下で、ミニマックス法の自分の番と相手の番で異なる処理を、符号を反転させることで一つの関数に統一する手法です。実際のゲームAIでは、α-β法やネガマックス法を基にした、さらに洗練された探索アルゴリズムが用いられています。

もう一度検索