ゲームの思考ルーチンに興味があって将棋プログラムを作ってみたはいいけど、外側のインターフェイス部分で断念して結局手動の２人対戦になってしまった俺が来ましたよ。
って、エロと風俗情報満載 どう抜く？の話なんですけど。ミニマックス書いてみたいなーと思いつつ、そういえばあまりよく知らないなーと思ったので、勉強しつつまとめてみます。
そもそも何が「最小最大」なのか、というと・・・。例えば自分の次の手が５通りあったとすると、その５通りに対して相手は最善の手を打ってくるはず。つまり、自分にとっては最悪の手になる。なので、５通りの手に対してそれぞれ最悪のケースを考え、その中でも最善の手を次の手にするというのが基本的な考え方のようです。
多分これって日常的にみんなやってるよね。次の行動を決めるときに、それぞれ最悪のケースを考えて最もリスクの少ない物を選ぶという。
具体的な局面を考えてみる。例えばこういう局面があったとして・・・
相手 = 6 自分1 自分2 自分3 2 4 6
相手の手に対して、自分の取りうる次の手が3通りあったとき。当然自分は最もスコアの高い"6"の手を打つだろうから、相手のこの手の評価値は"6"になる。
では逆に、自分の手に対して、相手の取りうる次の手が3通りあったときはどうか。評価値は、あくまでも自分基準*1なので、相手としては自分にとって最も不利になる手＝最も評価値の低い手を選択するはず。ということは、自分のこの手の評価値は"2"になる。
自分 = 2
相手1 相手2 相手3
2 4 6
と、こんな風にして、ツリーの下から最小値と最大値を交互に求めていく。最終的に、自分の次の手の１つを頂点としたツリーが手の数だけ作られるので、その中で評価値が最大の手を次の手にすればよいということになります。
最小値と最大値を交互に求めてツリーを上がるのはいいけど、じゃあ元々の（最初の）評価値はどうやって求めるのかといえば、局面から評価値が静的に決まるところまでやるのでしょう。静的に決まればその値を、決まらなければ子のツリーまでさかのぼってみると。というのは、ある程度手が進んでからでないと有利不利というのはなかなか決まらないものなので、優劣がはっきりと分かるところまでは再帰的にツリーをたどっていく必要があるのでしょう。
いまのところ、こういう感じの理解。実際に作ってみますかねー。
続いてネガマックス法
さっきの話で言えば、この例は「自分は自分にとって最善の手を選択するはず」ということになる。
相手 = 6 <= 自分視点 自分1 自分2 自分3 2 4 6 <= 自分視点
で、こっちは「相手は自分にとって最悪の手を選択するはず」となる。
自分 = 2 <= 自分視点
相手1 相手2 相手3
2 4 6 <= 自分視点
視点が常に自分にあるので、最大値を求める作業と最小値を求める作業を交互に行う必要があって、めんどくさい。ここで、2番目の例において、評価値のプラスマイナスを反転してみたらどうなるか。ゼロ和ゲームでは「相手の損＝自分の得」なので、「自分にとって最悪の手」＝「相手にとって最善の手」になる。つまり
自分 = -2 <= 相手視点
相手1 相手2 相手3
-2 -4 -6 <= 相手視点
こうなる。そうすると、最小値と最大値を交互に求める必要はなく、常に最大値を求めればいいので楽ちん。この例では、さらに自分の-2という値を反転して2にすれば、自分の手の中で最善のものを求めればよいことになる。
結局のところ、「反転して最大値を求める」という処理を繰り返せばいい。アルゴリズムが簡単になる。毎回反転とか頭が混乱してくるので、「ノードが自分の手番視点の評価値を持っているようにする」と覚えておけばいいかな。
*1:例えばオセロだと、自分の色の石が何個あるか・・・みたいな
