将棋ＡＩも採用、ミニ・マックス法の無駄を省いた α β（アルファ・ベータ）法と α 値、β 値の具体例の解説

将棋界では、１９歳の天才・藤井聡太四冠の勢いが止まらない。彼の強さを説明する時、よく持ち出されるのが、ＡＩとか、ディープ・ラーニングという話だが、普通のメディア情報だと、そうした言葉だけ使って、中身を説明してないものがほとんどになってる。

まだＡＩも、全ての変化は読み切れないので、途中で読みを打ち切って、一方がどれだけ有利・不利なのか、形勢判断することになる。途中でどのように形勢判断するのか？　どのように評価値を計算するのか？

ある１つの局面だけを取り出して、先は読まずに、その時点だけでどう評価するのかについては、特殊なソフト（評価関数）が色々あるようで、そこはとりあえずスルーしとこう。

今回は、先を少し読んだ上で、今現在の評価値を出す方法、コンピューター手続き（アルゴリズム）について解説してみる。あちこちに説明があるが、導く途中のプロセスが書かれてないものや、言葉の意味（ミニ、マックス、α値、β値）を具体的にハッキリ示してないものがほとんどだった。

そんな中で、最も役に立ったのはいつものように、英語版ウィキペディアの説明（minimax、αβ pruning）。特に、図やアニメは明らかに優れてる。他に、補助的に役立ったのは、近大の石水隆氏のｐｄｆファイルだった。

   　　　　　☆　　　　　☆　　　　　☆

下は英語版ウィキのαβ簡略化法の図だが、これを用いて、元になってるミニマックス戦略から説明する。

将棋、碁、チェス、オセロなど、１対１のボードゲームだと、一方がどれか１手を選んで指して、それに対して、相手がいくつかの選択肢から選んで応じる形になる。その変化を樹形図（ツリー）として示したのが下図。グレー（灰色）の意味は、しばらく後で説明。

一番上の自分の手番では、３つの選択肢（丸印）があって、これから自分が最善の手を選ぶ。そのそれぞれに対して、相手には２つの選択肢（四角印）がある。一番下に並んでるのはすべて、自分の側に対する評価値。相手は当然、この値から出来る限り低いものを選ぼうとするはず。

ちなみに将棋の最初の局面なら、下のような変化をまとめてることになる。自分には、７六歩、２六歩、５六歩という３つの選択肢がある。そのそれぞれに対して、相手には、８四歩、３四歩という選択肢がある。

　　　　　☆　　　　　☆　　　　　☆

さて、相手としては、自分（私）の評価値を下げたいから、最も低い値（ミニマム）になる選択肢を選ぶと考える。例えば上図の左端だと、評価値５と６の変化があるから、相手は５の選択肢を選ぶ。以下、同様で、それぞれの相手の手番における自分の評価値がまず決まる。

上図で、下から２段目の薄い黄色のエリアには、左から、５、４、３、６、６、７、５、８、６という値が並んでる。これは、私がその直前に選んだそれぞれの選択肢（丸印）に対する評価値ということになる。自分（私）は当然、それらの中から、なるべく大きい値（マックス）を選ぶ。

だから、上図のように、下から３段目の私の手番では、私が大きい値の選択肢を選んだと考えてる。左端の分岐点なら、５と４の内、５になる選択肢を選んだということ。右端なら、８と６だから、８になる選択肢を選んだ。

この時点で、下から２段目の薄い青緑のエリアには、左から、５、３、６、７、５、８という値が並んでる。これは、相手のそれぞれの選択肢に対応する、自分（私）の評価値ということ。

ちなみに、それぞれの点（局面）は、英語でカタカナ英語でノード（node）と呼ばれてる。普通は分岐点のことだが、決着がついた最後の局面は分岐点ではないし、指し手が１つしかない時も分岐点にはならない。

　　　　　☆　　　　　☆　　　　　☆

相手はまた、自分（私）の値を低くする選択肢を採用すると考えると、下図のようになる。中央の変化だと、６と７だから、小さい６になる選択肢を取る。

最後に、自分は、３、６、５と並ぶ数字から、一番大きい６になる中央の選択肢を選べばよい。したがって、最初（一番上）の時点での評価値は、６ということになる。自分の指し手を青い線、相手の指し手を黄色の線で示した。自分の２回目の指し手は２通りあって、どちらでも同じ評価になってる。

なお、相手だけが間違えた場合は、評価値は９まで上がる可能性がある（６から一番下の段まで下りた時の、最大の値）。一方、上図の場合は、自分が間違えたとしても、最悪の評価値は６（上側の６から一番下の段まで下りた時の、最小の値）。

　　　　　　☆　　　　　☆　　　　　☆

上のような方法が、ミニマックス戦略。相手は、自分（私）の評価を最小（ミニ）にすると考えて、自分は評価を最大（マックス）にすると考える方法。ちょっと難しい言い方だと、自分の最悪の損害を、最小化する戦略。歴史的には、一般的なゲーム理論やナッシュ均衡まで遡るらしい。

もちろん、実際の人間がそのような最善の判断をするかどうかは分からないし、そもそも一番下の段の評価値が正しいとも限らない。ＡＩも最後の終局・投了まで読み切ってるわけではないし、人間との形勢判断の違いも大きい。

とにかく、そうしたミニマックス法から、無駄な読みを取り除く（prune：プルーン）方法が現在、使われてるらしい。α値、β値というものを使うから、英語だと αβ pruning。日本語だと αβ 法が普通の言い方だけど、意味的には αβ簡略化法ということだ。

　　　　　　☆　　　　　☆　　　　　☆

ＡＩは左から右へと計算していくと仮定。まず、左下の枝分かれを見てみよう。

相手の手番である下から二段目で、左端に、自分の評価値としてまず５が出てる（赤丸）。この時点では、これがα値。その上の段階で、自分は、この５より小さい値は選ばないはず。

ところが、右へと計算していくと、一番下の段が４となった時点で、その上側の評価値も４になる。この後、上のグレー（灰色）の値が何であっても、すぐ上の値は４以下になる。相手はなるべく小さい値を選ぶから。

α値と同じ段の右側に、α未満の値が出た瞬間、その後の下側の計算はもう不要になる。自分（私）はその直前の段階で、α値の選択肢を選ぶ方が得だから。したがって、上の枝分かれだと、自分は下から二段目の左側の５の選択肢を選ぶことが決定する。赤い斜線の右下は計算不要でカット。

同様に、中央の枝分かれでも、赤線の右下は計算不要で省略される。下図を参照。ここでのα値は、とりあえず６（下から二段目の左側）。右下の灰色のマス目の値が何であっても、すぐ上の値は６以下だから、自分の選択肢の値は６と決定。

ただし、この場合は２通りの変化が同点になってる。これは将棋ＡＩでも見られる現象。

　　　　　　☆　　　　　☆　　　　　☆

最後に、β値については、この樹形図だとたまたま役に立ってない。

上図で、下から二段目の自分の手番において、左端にまず５と出てる。これが最初の時点でのβ値で、これより大きい値が同じ段の右側に出たら、その後の下側はカットされるが、β値より小さい３が出たので、何もカットされてない。

中央の枝分かれは、そこでのβ値６より大きな値が出てるが、その後にカットされるべき選択肢がないので、たまたま役に立たない。右端の枝分かれは、β値５によるカットを使う前に、上から二段目のα値（ここでは６）が働いて、下側の３段が丸ごとカットされてしまう。

　　　　　☆　　　　　☆　　　　　☆

仮に、右側の枝分かれの５の代わりに７とすれば、下図のように、β値を上回る値が出た後の下側のカット（省略）が生じる。

それにしても、もともと一番下の段の評価値が間違っていたら、ミニマックス法もαβ法も意味が無くなってしまうはず。今後、その辺りも調べてみたいが、将棋だけでも１通りではないから大変かも。

ともあれ、今日のところはこの辺で。。☆彡

　　　　　　　（計　３１３４字）