10年ぶりのプログラム「引退したプログラマーがPythonでAIプログラミングに挑戦する」-18:AI_AlphaBeta
AlphaBeta法
AIの最後としてAlphaBeta法を説明します。
まずは下記の図をご覧ください。
これはMiniMaxで説明した図です。
注目して欲しいのは、Max(Min, Min, Min)となっている青い部分です。
この部分に注目して説明をします。
Max(Min, Min, Min)
それぞれの要素をA,B,CとするとMax(A,B,C)の計算をするということになります。このときABCがそれぞれ,5,2,3だとすると最初の5が選ばれます。これを「処理を実行しているプロセス中」の動きとして考えてみます。
処理を実行しているプロセス中の動き
まずは要素Aの値が5だとわかりました。
次の要素Bの計算に移ります。
要素Bの値を出すために、b1, b2, b3,,,,,,の値を計算しているとします。
このとき、b2が3だとわかったとします。
一旦何も考えずにこのまま計算を最後まで続けます。
その結果、最終的にはb12に2という値があったので、それがこの要素Bの結果になりました。
同じようにCも計算して3が選ばれました。
そしてMax(5,2,3)を計算し、5が選ばれたとします。
上限値
上記の要素Bの計算についてもう一度振り返ってみます。
b2の時点で3が求められた瞬間のことです。
b2＝3ということは、要素BはそもそもMin(b1, b2, b3,,,,,, b12,,,,, bn)ということですのでb3が終わった時点で、要素Bの値は
b2=3
br～bnの間にあるb2よりも小さい値
のどちらか一方ということになります。
つまり要素Minの上限値が判明するわけです。せいぜい「3」ということです。このb2=3よりも大きな値が選ばれることはありません。
Max(A,B,C)の計算
そして、この要素Bの結果は最終的にMax(A,B,C)という計算で使われるものです。今A=5はわかっています。
ということは、Bの値は「せいぜい3」ですので、Maxの計算においてAに勝つことはできません。Aの方が大きいわけです。
ですので仮に、要素Bの値が最終的に2に決まろうとも、暫定値としての3を使用しようとも、Aには勝てないということです。要するに、b4以降の計算は無駄ということです。
ならば、b3＝3とわかった時点で、b4以降の計算をやめにして、要素Cの計算に移動する方が効率的ということになります。
そして要素Cの計算のときにも、同様に、もしも上限値がAを超えないことが判明したら、そこで計算をストップします。
Min(Max,Max,Max)
Min(Max,Max,Max)についても同様です。
一応簡単に説明しますが、読み飛ばしていただいても問題ありません。
処理を実行しているプロセス中の動き
最終的にMin(7,9,11)になったとして、先と同様の説明をします。
まずは要素Aの値が7だとわかりました。
次の要素Bの計算に移ります。
要素Bの値を計算するときb1=6, b2=8,,,,b11=9,,,,b20=4だったとします。
このとき、ここではMaxを出すので、b11の9が要素Bとして選ばれます。
同じようにCも計算して11が選ばれました。
今回はMinですので、要素Aが最小値として選ばれます。
この7という数字は、要素Bを計算するときに事前に判明しているので、b2=8となった時点で、この要素Bの最大値は要素Aの値よりも大きくなってしまうことがわかります。つまり最終的には要素Bは選ばれないことがわかるので、b3以降の計算をカットします。
これがAlphaBetaの考え方です。考え方としては、特殊なものではないと思います。
アルファカット・ベータカット
前者( Max(min, min, min)) をアルファカット
後者( Min(max, max, max))をベータカット
と呼ぶようです。しかし名前は重要ではありません。少なくとも我々のような元プログラマーには不要でしょう。本質だけを理解すればいいと思います。
実装
上記をコーディングします。
このコーディングは、MiniMaxとNegaMaxの両方に適用できますが、MiniMaxでやると白番と黒番の二つのLoopの中身を修正することになるため、少し面倒です。
それゆえにNegaMaxだけで実装します。そういう意味でもNegaMax法は便利だと思います。
get_NegaMax_AlphaBeta_move
get_AI_move
下記の黄色い部分を追加してください。
chess_main.py
また、chess_mainのget_AI_moveを呼び出すパラメータを3に変更してください。
実行前に、get_NegaMax_AlphaBeta_moveのコードの説明をします。
アルファとベータの値の変化に注目してください。
Depth=2において、A,B,Cという3つの候補手がある場合について考えます。（このページの一番上の図と同様です。）
深読みを進める場合（下り）と、評価値を上に戻す（上り）とが混在するという点に注意してください。
DEPTH=2、白番の場合
まずはDepth=2のときが、白番の場合について考えてみます。
Depth=2のときのアルファ・ベータ（要素A）
このプログラムを呼び出すときには、
アルファ＝MIN_VALUE
ベータ＝MAX_VALUE
を渡します。
Depth=1のときのアルファ・ベータ（要素A）・・・下り
これまでと同様に、Depth＝2の候補手ABCがあったとして、Aについて深掘りをしていきます。つまり、Depth-1（Depth=1）として、自分自身を呼び出します。この呼び出すときのアルファ・ベータは、
アルファ：ベータ*(-1) → MAX_VALUE*(-1) → MIN_VALUE
ベータ：アルファ*(-1) → MIN_VALUE*(-1) → MAX_VALUE
となります。
Depth=1でもLoopの中で再帰的Depth＝0を呼び出しますが、引き渡すアルファやベータには意味がありません。
Depth=0のときのアルファ・ベータ（要素A）
Depth=0では、if depth==0 が実行されるので、Loopには入らずに、評価値だけをリターンします。このときには、turn_sign=+1なので、評価値そのものが戻ります。
Depth=1のときのアルファ・ベータ（要素A）・・・上り
Depth=1では、受け取った評価値をマイナスします。
ここでscoreとmax_scoreの比較をします。
max_scoreの初期値はMIN_VALUEなので、今受け取った値がmax_scoreになります。
さらにmax_scoreとアルファを比較します。アルファはMIN_VALUEですので、新しいアルファがこのmax_scoreとなります。
次に、アルファとベータを比較しますが、ベータはMAX_VALUEなので、ベータの方が大きいです。ゆえにベータは変化しません。
上記をDepth=1の中のLoopの End Loopまで行います。
気をつけるべきことは、scoreがマイナスになっているので、マイナスの評価値が大きいものつまり最小値が選ばれたということです。しかも値はマイナスのままです。
この結果、
アルファが決まります。
ベータはMAX_VALUEのままです。
Depth=2のときのアルファ・ベータ（要素B）
Depth=2に戻り、次の要素＝Bについて深掘りをしていきます。
このときのリターンにマイナスがついているので、評価値そのものがリターンされることになります。（評価値のマイナスのマイナス、ということです。）
ここで再帰的にDepth=1を呼びますが、パラメーターが要素Aとは異なります。
アルファ：マイナスベータ＝MIN_VALUE
ベータ：Aの評価値のマイナス
です。
Depth=１のときのアルファ・ベータ（要素B）・・・下り
このLoopの中でDepth=0を呼び出します。
Depth=0のときのアルファ・ベータ（要素B）
先ほどと同様に、評価値そのものがリターンされます。
Depth=１のときのアルファ・ベータ（要素B）・・・上り
ここからが、アルファやベータの値が意味を持ちます。
まず、ベータ＝要素Aの評価値のマイナスです。これは受け取った引数の値です。
そして今取得した値がmax_scoreになります。
この値とアルファを比較しますが、当然max_scoreの方が大きいので、先ほどと同様に
アルファ＝max_score
です。
問題は次です。
この値とベータを比較します。
アルファがベータよりも大きいかどうかを決めます。
このとき、お互いに「マイナスの値」になっていることに注目です。つまり本来のスコアが小さい方が勝つということです。
alpha > betaということは、アルファ（Bの評価値のマイナス）の方が、ベータ（Aの評価値のマイナス）よりも、絶対値は小さいということです。ということは、最終的にDepth=2でMax(A,B,C)をおこなうときに、Aには勝てませんよ、ということを意味します。なぜならば、Depth=2に上がるときには評価値のマイナスのマイナスつまり評価値そのものが戻るからです。
ゆえに、アルファがベータよりも大きい時点でそのDepth=1のLoopをbreakして、Depth2に戻ります。
Depth=2のときのアルファ・ベータ（要素C）
以下同様です。
DEPTH=2、黒番の場合
次に、Depth=2のときが黒番の場合についても考えてみたいと思います。白番と同様なので、ある程度省略した説明になります。
Depth=2のときのアルファ・ベータ（要素A）
プログラムを最初に呼び出すときアルファとベータは白番と同様です。
つまり、
アルファ＝MIN
ベータ＝MAX
です。
Depth=1のときのアルファ・ベータ（要素A）・・・下り
このときのLoopの中でdepth=0として再帰的に呼び出します。
Depth=0のときのアルファ・ベータ（要素A）
このときturn_sign=-1なので、マイナスの評価値をリターンします。
Depth=1のときのアルファ・ベータ（要素A）・・・上り
受け取った評価値をマイナスするので、プラスの評価値になります。
そしてこの値が、max_scoreおよびアルファになります。
上記を End Loopまで行います。
アルファが決まります。この値は評価値そのものです。
ベータはMAX_VALUEのままです。
Depth=2のときのアルファ・ベータ（要素B）
Depth=2に戻り、次の要素＝Bについて深掘りをしていきます。
リターンにマイナスがついているので、評価値のマイナスがリターンされます。
ここで再帰的にDepth=1を呼びますが、パラメーターが要素Aとは異なります。
アルファ：マイナスベータ＝MIN_VALUE
ベータ：Aの評価値（マイナスのマイナス）
です。
Depth=1のときのアルファ・ベータ（要素B）・・・下り
このときのLoopの中でdepth=0として再帰的に呼び出します。
Depth=0のときのアルファ・ベータ（要素B）
マイナスの評価値をリターンします。
Depth=1のときのアルファ・ベータ（要素B）・・・上り
プラスの評価値が戻ります。
そして最終的にアルファが決まります。アルファは評価値そのものです。
この値とベータを比較します。ベータは要素Aの評価値です。
alpha＞betaとは、このBの評価値のほうが大きいということですが、Depth=2では、Min(A,B,C)の計算をするので、BはAには勝てませんよということを意味します。
ゆえに、アルファがベータよりも大きい時点でそのDepth=1のLoopをbreakして、Depth2に戻ります。
以上がソースの説明になります。
どちらの場合についても、Max(Min,Min,,,,) or Min(Max,Max,,,)というMaxとMinの入れ子になっているということを考えれば、ご理解いただけると思います。
実行
それでは各自実行して確認してみてください。
カットされるデータ数
特に問題がなければ、どのくらいデータがカットされたかを確認しましょう。
私自身、実際の開発やプロジェクトに関わっていないので、実際にどのくらいカットされるのかについては予想がつきません。
確認方法としては、読み込むvalid_movesの件数と、breakしたときのイテレーターの値を比較することにします。
つまり、たとえば全部で26通りの候補手があったのに、3手目でLoopから抜けて次の親要素に移動したということであれば、23個がカットされたということを指します。
この検証だけをやってみます。
下記のようなprintを入れました。
結果は下記のようになりました。
count=2などでbreakしているものがあるので、効果はあるのだろうと思っています。しかし体感としては、そこまでの違いは感じませんでした。
むしろ、Depth=1のときに相手のvalid_movesの取得をスキップしましたが、そのときの効果の方が圧倒的に大きかったです。
ただし、スコアが最大or最小に近いと予想される候補手が、Loopの順番の前方に来るようにすれば、スキップできる計算が増えるので、処理速度が向上するはずです。そうなれば、わたしにも効果が体感できたのかもしれません。
実際に現場では、そのためのさまざまな工夫がされているだろうと思います。ここではそれについては触れません。
常に最大値が出せるのであれば、そもそもMinMaxなどを使う必要がないわけですので、これは「ある程度」までしかできないだろうと思っています。逆にいえばある程度はできるであろうと思っています。
以上でAlphaBetaの説明を終わります。
次回は最後のまとめです。
使用しているチェスのコマは、下記からダウンロードしました。
By jurgenwesterhof (adapted from work of Cburnett) - http://commons.wikimedia.org/wiki/Template:SVG_chess_pieces, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=35634436
この記事が気に入ったらサポートをしてみませんか？