ミニマックス法

ミニマックス法 †

このページは競技プログラミングに興味のある方向けにミニマックス法を簡単に説明するページです

ミニマックス法って何？ †

最悪の場合に得られる利益が最大になるようにする手法です

具体的に †

例えば以下のようなゲームを考えましょう

・プレイヤー二人は同時にAまたはBを決定する
・プレイヤー1の利益は以下の行列であらわされる
・プレイヤー2の利益はプレイヤーAの利益に-1を乗じたものとする

この時、プレイヤー1は以下の思考をしたとします
・自分がAを選んで、相手がAを選んだ場合、「"少なくとも"1点はもらうことが出来る」
・自分がBを選んで、相手がBを選んだ場合、「"少なくとも"2点はもらうことが出来る」
・だったら、Bを選んだ方がマシかな

という考え方でプレイヤー1はBを選びます
このような「考え方」をミニマックス法と言います

（プレイヤー1(自分)の思考時に、「プレイヤー2(相手)は、プレイヤー1(自分)の利益を最小化するように必ず選ぶ」と決めつけていることに注意。それがミニマックス法です。）

ミニマックス法って万能じゃん †

いいえ、ミニマックス法はあくまでも「戦略」の一種で「解答(最適解)」ではありません
例えば上記のような場合でもプレイヤー1が「プレイヤー2は俺のこの思考を読んでBを選ぶから裏をかいてAを選ぶぜ」
と考えた場合、プレイヤー1が選択肢Aを選んで3点を得ることが出来るかもしれません

だったら使い道ないじゃん †

そんなことはありません。ある特定の条件の時にですがミニマックス法が最適解になることがあります

条件って？ †

プレイヤー1と2の各々の視点でミニマックス法を用いたときの結果が同じ場合、その選択肢の組みがゲームの解になります。
具体的には以下のような行列であらわされるゲームです(ルールは前述のゲームと同じ)

プレイヤー1はAを選べば「少なくとも選択肢の組(プレイヤー1,プレイヤー2)=(A, A)で1点を得ることが出来る」
プレイヤー1はBを選べば「少なくとも選択肢の組(B, A)で3点を得ることが出来る」
なので、プレイヤー1がミニマックス法によって選択肢を選ぶなら選択肢Bを選ぶ

プレイヤー2はAを選べば「最悪のパターンだと選択肢の組(B, A)の時-3点の失点になる」
プレイヤー2はBを選べば「最悪のパターンだと選択肢の組(B, B)の時-4点の失点になる」
なので、プレイヤー2がミニマックス法によって選択肢を選ぶなら選択肢Aを選ぶ

結果、プレイヤー1は3点を得てプレイヤー2は3点を失います
このように両者のミニマックス(あるいは一方の逆をとってマクシミン)が一致するとき、ミニマックス法に基づく選択肢の組はそのゲームの最適解となります

具体的にどういう風に使うの †

例えばオセロなどでは「中盤までは自分の色のコマが少ない方が良い」と言うセオリーがあります
そこで、「15手先の自分の色のコマについて「最悪の場合に保証されているコマの数が最も少なくなる」ような手を打つ」などと言った手法を取るときなどに使われます

オセロの思考プログラムを作ったら計算に時間かかりまくってるんだけど †

当たり前です。1回の手の候補が5か所あったとしたら15手先を計算すると300億通りのパターンを調べないといけないんですよ

じゃぁどうすればいいですか †

ミニマックス法の改良版として「α-β法」などがあります。ご自身で調べてみてください