5分で覚えるAI Minimax（ミニマックス）法とalpha-beta法
2016.05.14
この記事は最終更新日から1年以上が経過しています。
どもです。
何かと盛り上がっているAIですが、今回はAIの初歩的なところでもある探索アルゴリズムである「Minimax（ミニマックス）」と「αβ（アルファベータ）法」について書いていきます。
完全情報零和ゲーム
勿論、探索アルゴリズムについては沢山ありますが、完全情報零和ゲームの探索アルゴリズムには「Minimax（ミニマックス）法」が最適だと言われております。
「完全情報零和ゲーム」と漢字ばかり並んでなにやら難しそうではありますが、「完全情報零和ゲーム」とは、自分にとって見えない情報が存在しない事で、後に続く「零和」とは、ゲームの勝負がそれ以降の勝負に何ら影響を与えない事を意味しています。
例としてあげると、「オセロ」であったり「将棋」「囲碁」などのゲームがそれに該当します。
これらの「完全情報零和ゲーム」の最善手を求める方法は、60年ほど前に数学学者であるアラン・チューリング（Alan Turing)などらによって提唱されています。
ゲーム木
アルゴリズムの説明に入る前にまずは、ゲーム木について軽くご説明を。
ゲーム木とは、「オセロ」であったり「将棋」「囲碁」などの最初の状態からの各局面を表現したものとなります。
まず、現在の局面で打てる手を列挙し、それらの手を一つ打つ事で次の局面ができます。
一旦、手を戻し、再度別の手を打つ事でまた別の局面ができます。
このように現在の局面から考えられる展開をリストアップする事ができます。
これらを図にすると、以下の様に表せます。（一部省略）
この様に、局面を起点として打てる手を列挙する事で、上記の図の様に局面を根とした木構造になっている事がわかります。
この木の事を「ゲーム木」と呼びます。
木の始点を「根（root）」と言い、ゲーム木においては現在の局面が根に該当します。
また、木の途中途中の分岐点を「接点」または「ノード（node）」と言います。
子ノードがないノード事を「葉（leaf）」と言います。
あるノード以下の分岐を「枝（branch）」と言います。
アルゴリズムによる木の探索を途中で打ち切る事を「枝刈り」と呼んだりもします。
「枝刈り」を行う事によって、いらない処理が省かれますので、処理の高速化を行うことができます。
ゲーム木においてよく見る図は以下の様な形かと思います。
上記の□で囲んで箇所が局面となります。
この箇所が「ノード（node）」に該当いたします。
また、この場合、「N0」が現在の局面となり、「根（root）」（ルートノード）に該当します。
各ノードとノードをつないでいる線が「枝（branch）」に該当し、着手（実際に石を打つこと）を表しております。
灰色に塗られているノードが黒の局面となり、太い枝は黒の着手を表しております。
参照しやすくするためノードの中には番号を振っております。
「N1」「N2」「N3」は、「N0」の下にあるので、この場合、「N0」の子ノードとなり、「N1」「N2」「N3」から参照した場合は「No」は親ノードとなります。
実際にオセロをするとき、ある手を打ったらどの様な局面になるかを予想しながら打っていくと思います。
「ここに打つと、相手はあそこを打てる様になる。」とか「ここは相手が不利になるからここに打ってくる」など
この様に何手か先を予想して着手を決めることを「先読み」と呼びます。
「Minimax（ミニマックス）」などにおける探索アルゴリズムは、この様に局面にて打てる手を列挙し実際に打っては戻して、また打っては戻して、と繰り返す事によって先読みの最適な手を導き出すアルゴリズムとなっております。
では、早速Minimaxアルゴリズムについて書いていきます。
Minimaxアルゴリズム
最善手を探し出すアルゴリズムが、「Minimax」（ミニマックス）アルゴリズムとなります。
また、完全情報零和ゲームの「Minimax」（ミニマックス）アルゴリズムで決めてしまっても良いかと思います。
「Minimax」（ミニマックス）アルゴリズムの思考としては「自分にとっての最善手は、相手にとっての最悪手」と言った考えに基づいております。
相手が常に相手にとっての最善手、つまり自分にとっての最悪手を打ってくると仮定して最善手を求めます。
それでは、2手先読みの例を見ていきましょう。
白の手番はコンピューター（AI）となりますので白をルートノードと致します。
それでは、図を見ていきましょう。
各局面の下に数値が記されているのが、「各局面における評価関数で求めた評価値」となります。
評価値とは、「ここを取ると有利」「ここを取ると不利」と言ったように、盤にそれぞれ点数付けしたものとなります。
オセロなどでは一般的に「四隅を取ると良い」などといった事が浸透しているかと思います。
また、逆に「四隅を取らせてしまう配置は良くない」と言ったように、「良い」箇所には点数が高く、「悪い」箇所には点数が低い評価値となります。
評価関数に関しては、また長くなりますので今回は割愛させて頂きます。
それでは、また図に戻りまして、まず最初にルートノードであるN0はコンピュターの手となります。
何箇所か打てる箇所が存在するとして、上記の図はその1手に着目しています。
まずは何も考えず、手を打ちます。
次は黒「相手」の手となります。
この時、黒の局面ではノード「N1-1」と「N1-2」の二つの手が存在するとします。
「N1-1」の局面における評価値が 7とし、「N1-2」の局面における評価値が12とします。
この時、黒「相手」は白「コンピューター」にとって良い手になる様には打たせたくない。と考えるものです。
つまり、黒「相手」は評価値が高い「N1-2」評価値12の局面を与えてくれず、相手にとって不利な局面を選択する仮定します。
よって、評価値の低いノード「N1-1」評価値7を選択。
つまり、ノード「N1」における評価値は7（MIN）となります。
これが、「Minimax」（ミニマックス）アルゴリズムの基本的な考え方となります。
それでは、ちょっと打てる手を増やして確認してみましょう。
N0の局面における打てる手が3つあったとします。
先ほど、ノード「N1」に関してみたので、次はノード「N2」の手を見ていきます。
何も考えず、手を打ち、「黒」（相手）の手番になります。
また、2つの手が打てる局面だとし、それぞれの局面をノード「N2-1」「N2-2」とします。
「N2-1」の評価値は-5、「N2-2」と-10とし、また「黒」（相手）は「N1」同様で白「コンピューター」にとって良い手になる様には打たせたくない。
つまり、悪い局面になる様に選択する。と仮定しますので、ここでは評価値の低い「N2-2」-10を選択。
よって、N2の評価値は-10。
N3も同様、評価値の最も高い「N3-1」評価値20が出現しますが、今まで同様に「黒」（相手）は、この局面にならない様に打ちますのでここでは「N3-2」評価値-3を選択。
よって、N3の評価値は-2。
これで、3つの手における評価が算出できました。
白「コンピューター」は評価値が高い（MAX）の手を選択しますので、この局面における打つ手は「N1」評価値7となります。
それでは、疑似コードの方を見ていきましょう。
Minimaxアルゴリズムの疑似コード
int maxlevel(int limit) {
if(深さ制限)
return 評価値;
可能な手を全て生成;
foreach（それぞれの手） {
int score, score_max;
手を打つ;
score = minlevel(limit - 1);次の相手の手
手を戻す;
if (score > score_max) {
より良い手が見つかった
score_max = score;
}
}
return score_max;
}
相手の手を調べる
int minlevel(int limit) {
if(深さ制限)
return 評価値;
可能な手を全て生成;
foreach（それぞれの手） {
int score, score_min;
手を打つ;
score = minlevel(limit - 1);次の自分の手
手を戻す;
if (score < score_min) {
より悪い手（相手にとって良い手）が見つかった
score_min = score;
}
}
return score_min;
}
関数maxlevel()では、自分（コンピュータ）が打つ手について調べていき、関数minlevel()では、相手の手について調べています。
「深さ制限」とは、何手先まで手を読むかといった制限となります。
この先読み手数の制限を1手増やす度に数倍となってしまうので、気をつける必要があります。
探索を始める前に「深さ制限」を決めておいて、その数を関数の方へと渡します。
再帰的に子ノードを調べる際に制限値を減らしていき、最終的に0になるまで探索を行います。
評価関数に関してはどちらも自分（コンピュータ）からみた評価値を返す様にしておきます。
実際に打つ手を決める際には、根（現在の局面）のノードの評価値を求めるのではなく、根の子ノードの評価値を全て求め、最も高い評価値を与える子ノードの手を打つことになります。
打つ手を決定するための疑似コード
void move() {
Point p;
int eval, eval_max = -INT_MAX;
foreach（それぞれの手） {
手を打つ;
eval = minlevel();
手を戻す;
if(eval > eval_max)
p = 今打った手;
}
手 pを打つ;
}
alpha-beta法
Mnimaxアルゴリズムが最善手を求めるアルゴリズムとされていますが、「時間がかかり過ぎてしまう」という欠点があります。
このMnimaxアルゴリズムの効率化されているアルゴリズムでよく知られている「alpha-beta法」というアルゴリズムがあります。
「alpha-beta法」では、絶対に採用されない手をそれ以上読み込まないことで枝刈りを行い、効率向上させることができます。
では、上記で使用した図を参考に見ていきましょう。
上記の図では最終的にN1のノード「評価値 7」が選択されました。
その後に探索を行ったN2、N3の探索が無駄になったのがわかります。このN2、N3の探索を効率よく探索を行いたいですよね。
N1に続く、N2、N3の探索では、N1のノード「評価値 7」より高い評価値が得られる手を探索していますので、N1のノード「評価値 7」より低い評価値となる場合は必要ないことになります。
つまり、「評価値 7」より低い評価値が返って来た際には、その時点で探索を打ち切って良いということが分かります。
それでは、N2を見ていきましょう。
上記のMinmax法では、ノード N2では評価値 -10 となりました。
N2-1では-5、N2-2では-10となっております。
しかし、N2-1の評価値 -5が返ってきた時点で、N1のノード「評価値 7」より低いのが明確となっておりますので、N2-2のノードの探索は必要ないことが分かります。
なので、N2-2の探索を行わず、N3の探索を行います。
N3の子ノードでは、N3-1では20、N3-2では-2となっております。
N3-1の時点では、N1のノード「評価値 7」より高いので、さらに探索を継続します。
しかし、N3-2で-2の評価値が返ってきますのでこの時点で探索を打ち切ります。
上記では、2つの手しかないのですが、もし、N3に3つや4つの手が存在した場合、N3-2の時点で探索は行いません。
「alpha-beta法」ではこう言った形で、「探索を打ち切る」事によって効率を向上する事ができます。
上記の例では、「評価値 7」より低い評価値が返って来た際には、枝刈りを行いました。
この「評価値 7」の下限値の事を「α値」と呼びます。
また、自分のノードを探索する際に、1つ上のノードの値で「高々この値」という上限値が存在します。
その上限値の事を「β値」と呼びます。
「α値」を用いて枝刈りを行う事を「α刈り」(alpha pruning)と言います。
また、「β値」を用いて枝刈りを行う事を「β刈り」(beta pruning)と言います。
「alpha-beta法」は、Minimaxアルゴリズムと同じ結果が返るうえ、枝刈りを行う事によって謝った手を選択する事も無くなるので、Minmax法を用いる場合は、「alpha-beta法」がほぼ使用されます。
それでは、疑似コードを見ていきましょう。
Minimaxアルゴリズムをベースに枝刈りの処理を追加した改良版という事がわかります。
int maxlevel(int alpha, int beta) {
if(深さ制限)
return 評価値;
可能な手を全て生成;
foreach（それぞれの手） {
int score, score_max;
手を打つ;
score = minlevel(alpha, beta);次の相手の手
手を戻す;
if (score => beta) {
beta値を上回ったら探索を中止
return score;
}
if (score > score_max) {
より良い手が見つかった
score_max = score;
alpha = max(alpha, score_max); α値を更新
}
}
return score_max;
}
相手の手を調べる
int minlevel(int alpha, int beta) {
if(深さ制限)
return 評価値;
可能な手を全て生成;
foreach（それぞれの手） {
int score, score_min;
手を打つ;
score = minlevel(limit - 1);次の自分の手
手を戻す;
if (score <= alpha) {
alpha値を上回ったら探索を中止
return score;
}
if (score < score_min) {
より悪い手（相手にとって良い手）が見つかった
score_min = score;
beta = min(beta,score_min); β値を更新
}
}
return score_min;
}
alphaとbetaを関数の引数として受け取り、α刈りとβ刈りを行っております。
というわけで探索アルゴリズム「Minimaxアルゴリズム」と「alpha-beta法」でした。
そのほかにも、negamax法や、NegaScout法などなどの探索アルゴリズムが存在します。
いつの日かの機会にと。
ではでは。
