ミニマックス法

ミニマックス法(minimax)は、どの手が最善か算出するときに用いるアルゴリズムだそうだ。
自分は最も高い評価値を選び、敵は最も低い評価値を選ぶと仮定すると、次に選ぶべき手が一つに定まる。
まず、考えられる全ての手について探索し、ノードの末端(一定の深さ)の評価値を得て、
自分の手なら最大を、敵の手なら最小を選ぶようにすれば、次に取る手がわかるのだ。

プレイヤーA, Bがいると仮定し、ここでは、Aがミニマックス法で打つ手を探すものとする。
ルートの次(最初の分木)ではAの手であるから、片っ端から打てる場所に打つ。
そのノードについて、Bの手が何通りかあるので、これも片っ端から打っていく。
そのノードについてもAの手が何通りかあるので、以下省略。
一定の深さに達したら(ノードの末端)、その場面での評価値を計算する。
打てる手(同じ階層のノード)が3つあり、それぞれの評価値が8, -4, 6だったとする。
この末端ノードがAの手番だった場合、自分にとって有利となるように、必ず最大の評価値のノードである8を選ぶ(max)ので、1つ親のノードに8を返す。
※評価値が定まるとはどういうことだろう。ここでBの気持ちで考えてみよう。もしBがこの手を選ぶと、次のAの手番に8, -4, 6とあろうと、Aは必ず8を取ってくる筈だ。だからその手を選ぶとその時点では「Aが得る評価値は8に定まる」のだ。
この「1つ親のノード」は当然Bの手番であり、8を吸い上げる。同じ階層のノードの評価値にこの8と、他に9, 12があったとする。
※ 評価値が定まるとはどういうことだろう。今度はAの気持ちで考えてみる。もしAがこの手を選ぶと、次のBの手番に8, 9, 12があろうと、Bは必ず8を取ってくる筈だ。だからその手を選ぶとその時点では「Aが得る評価値は8に定まる」のだ(次の手まで考えると、Aには8, -4, 6とあり、Aは8を選ぶ)。
当然、BはAが有利になる手を選ぶはずがない。だからBは最も評価値の低い8の手を選び(min)、その親のノードに8を返す。
その親の手はAの手番である。同じ階層のノードに8, 2, 4があったとしたら、Aは8を選ぶ。
こうしていくことで次に取るべき手がわかる。
というよりは、実は始めから一つに定まっているものを選んでいるだけなのだが。