アルファベータ探索（alpha-beta pruning）やろうぜ（＾～＾）？

「　アルファベータ探索　やろうぜ？」

「　カツ丼に影響されて……」

【将棋AI】電竜戦TSEC2 + 講演「将棋AI超入門」

「　👆　この動画の　最初の３０分が　アルファベータ探索の説明になってるわよ」

「　マンガでなければ　わたしには分からないんで」

「　👆　アルファベータ探索は、よく　こんな絵で　説明されるな」

「　何だぜ　それ？」

「　説明すると　お父んが寝てしまうので　手順を進めながら　やってみよう」

ミニマックス法（Minimax）

　　

「　👆　まず　こっちの枝で　一番大きな数は　１５　なんで、　わたしは　１５　を選ぶぜ」

「　👆　別のところにも枝があるな」

「　👆　そっちの枝で　一番大きな数は　４０　なんで、　わたしは　４０　を選ぶぜ」

「　👆　すると　次は　相手プレイヤーの番だぜ」

「　👆　相手プレイヤーは　いじわる　をして、　一番小さな数　１５　を選ぶぜ」

「　嫌なやつよね」

「　👆　こうして　わたしの枝の１つは　１５点　だと分かったわけだぜ」

「　どこが　アルファ　で、　どこが　ベータ　なんだぜ？」

「　これは　ミニマックス法　の説明なんで。
アルファとか　ベータとか　まだなんで」

「　👆　一番　小さな数　を、できるかぎり　大きくしよう、　というのが　ミニマックス　だぜ」

「　まわりくど」

ベーターカット（beta cutoff）

「　👆　ベーターカットは、よく　こんな絵で　説明されるな」

「　赤いハテナの箱は何だぜ？」

「　知る必要はないぜ」

「　なぜだぜ？」

「　👆　ここに　５　があるだろ」

「　👆　そして　ここに　6　があるな」

「　👆　赤い箱の中身を確認しなくても、　６以上　は確定しているぜ」

「　やったぜ！」

「　👆　じゃあ　相手プレイヤーは　赤い箱の中身が何であろうと　５　を選ぶぜ」

「　なんてこった！」

アルファーカット（alpha cutoff）

「　👆　アルファーカットは、よく　こんな絵で　説明されるな」

「　赤いハテナの箱は何だぜ？」

「　知る必要はないぜ」

「　なぜだぜ？」

「　👆　ここに　6　があるだろ」

「　👆　そして　ここに　5　があるな」

「　👆　赤い箱の中身を確認しなくても、　５以下　は確定しているぜ」

「　なんてやつだぜ！」

「　👆　じゃあ　わたしは　赤い箱の中身が何であろうと　6　を選ぶぜ」

「　しょんぼり」

アルファーカットと、ベーターカットって何が違うんだぜ？

「　あれっ？」

「　👆　これが　ベーターカットが起こるとき」

「　そうだぜ」

「　👆　これが　アルファーカットが起こるとき」

「　そうだぜ」

「　何が違うんだぜ？」

「　違うだろ」

「　手番と　大小関係が　ひっくり返っているだけで　同じことでは？」

「　ひっくり返ってるのが違うだろ」

「　こんな　細々したやつを　プログラムで組めんの？」

どっちが　アルファーカットで、どっちがベーターカット？

「　👆　あれっ？
えっ？？
どっちが　アルファーカットで　どっちが　ベーターカット？？？」

「　お父んは　契約書とか　読んだことあるだろ」

「　えっ、契約書？？」

「　お父ん（以下　甲とする）、きふわらべ（以下　乙とする）　みたいなやつだぜ」

「　見たくもないぜ」

「　利益を増やそうとしている　わたしは　アルファー さん、
アルファーさんになるべく利益が出ないようにしている相手が　ベーター さんだぜ」

「　日本語では　甲乙（こうおつ）、　英語では　AB（エービー）、　数式ではギリシャ文字を使うので　αβ（アルファー、ベーター）よね」

「　で、どっちが　アルファー？」

「　わたしが　アルファー、　相手がベーター」

「　👆　ベーターさんにとって要らないものをカットするから　ベーターカット、　アルファーさんにとって要らないものをカットするから　アルファーカットよ」

「　ただの　カット　なのでは？」

「　お父んには　カット　が　１つに見えるんだろ」

「　見える」

「　カットは　２つある。
ベーターカットと　アルファーカットは　違う所をカットしている」

「　えっ！」

アルファ値とベータ値

「　👆　こういう　２人が　ゲームしてるわけだぜ」

「　仲悪いの　わらう」

「　👆　アルファーカットしているのは　負の無限大に近い方、
ベーターカットしているのは　正の無限大に近い方だぜ」

「　全部一気に　アルファーカットと　ベーターカットして　０　にしたったらどうだぜ？」

「　全部カットしたら　投了しちゃうんじゃない？」

「　👆　アルファー値とか、ベーター値とか、いろんなとこに　いっぱいあるんじゃないのかだぜ？」

「　カットオフしようとしている　わたしは、兄　だけ見ろだぜ。それが　ベーター値だし、
カットオフしようとしている相手は　兄　だけ見ろだぜ。それが　アルファ―値　だぜ」

シミュレーション

「　じゃあ　ちょっと、シミュレーションしようぜ？」

「　👆　平手初期局面って　こんなんだろ」

「　１三きりん」

「　👆　こうかな」

「　３二らいおん」

「　👆　こうかな」

「　１四らいおん」

「　👆　こうかな」

「　👆　じゃあ　仮に　葉局面の盤面評価値（Value）が 10 だったとしようぜ。
きふわらべ、他の手も選んでくれだぜ」

「　👆　おっと　その前に　アルファー値　も右にずらして　10　だな」

「　１二きりん」

「　👆　こうかな」

「　👆　じゃあ仮に　好手　だったとしようぜ。　評価値（Value）に　５０点付けよう」

「　やったぜ！」

「　きふわらべ、他の手も選んでくれだぜ」

「　👆　おっと　その前に　アルファー値も　50　になるぜ」

「　アルファー・アップデートね」

「　１一きりん」

「　👆　こうかな」

「　👆　じゃあ仮に　これが　あんまり良くない手で　３点　だったとしようぜ？」

「　なんてこった」

「　アルファー値が　５０点　なのに、　評価値（Value）が　３点　なんで、
アルファー値を　評価値が下回ったから、この指し手は不採用だぜ。
アルファー・アップデートなし　だぜ」

「　アルファー・アップデートなし　なことに　何か名前はないの？　何とかカットとか」

「　もう指しちゃった　からな。　指したあとに　この手は　低い点だな、と　不採用　を決めただろ。
そんなの　ただの　選別　だぜ。　これは　カット　とは違う。
アルファー・カットや、ベーター・カットは　指す前　にやらないと、そう言わない。
こういうの　前向き枝刈り探索 。
根っこから　葉っぱに向かってるときにやるから　前向き　という。
アルファー・アップデートなし　は、葉っぱから根っこに向かってるときにやるから、 後ろ向き という」

「　名前　無いのか」

「　👆　きふわらべは　１番大きな点数の　１二きりん　を選ぶぜ」

「　👆　すると　アルファー値は　戻って……。
相手は　この指し手が　きふわらべから見て　５０　点だと分かったんで、
５０点より低い　評価値になる指し手を探したいな」

「　嫌なやつだぜ」

「　ベーター値を　５０点　にセットするぜ」

「　ベーター・アップデートね」

「　👆　相手は　別の手も指してみるが、まだ評価値は分かんないぜ。
他の枝と同じ深さまで指そうぜ。
きふわらべ、次の手を選んでくれだぜ」

「　２二ひよこ」

「　👆　じゃあ　仮に　絶妙な手で　７０点　だったとしようぜ？」

「　やったぜ！」

「　👆　でも　ここに　５０点　がいるぜ？」

（（（（ワナワナワナワナ））））

「　相手は　５０点以下の手を探しているので、それ以上の　良い点　を見つけても　採用されないぜ。
ベーター値によってカットされるから、 これ、 ベーターカット」

（（（（プンスカ　ドォォォォン））））

「　👆　じゃあ　こんな手　考えるの　止め止め！　探索を打ち切りだぜ！」

「　それでも　相手さんは　もっと　ベーター値を下げれないかな、と別の手を探すぜ。
きふわらべ、次の手を選んでくれだぜ」

「　👆　40　点の手があったが、これは　すでに見つけてある　５０点の手より点数が低いんで　採用したくないんだが……」

「　じゃあもっと　高い点数の手を探せだぜ」

「　👆　その前に　アルファー・アップデート　だぜ」

「　👆　-20　点のダメな手があったぜ」

「　アルファーアップデートしない　ぜ」

「　ああ、名前のないやつね」

「　２三きりん」

「　43　点。
50点を下回っているから　ベータカット　されないし、
40点を上回ったから　アルファー・アップデート　だぜ」

「　結局　わたしが選べる枝になるときには　５０点を下回る点になってるということだろ。
ベータカット　されないと　嬉しくないな。
アルファー値で　底を上げてはいるけど。
これが　ミニマックス　なんだろうけど」

「　👆　アルファー値以上の手にしたいし、ベータ値を超えると　採用されないし、
アルファー値と　ベーター値の間で　手を探すことになるのねえ」

「　分かったぜ！
これが　コンピューター将棋プログラミングのお題の鉄板、　アルファーベーター探索　かだぜ！」

「　鉄板って何だぜ？」

ネガマックス(Negamax)

「　コンピューター将棋では、強いソフトが　アルファーベーター探索を　そのまま使うことは　ほぼ無く、
もう一工夫している」

「　フーン」

「　説明すると　お父んが寝てしまうので　手順を進めながら　やってみよう」

「　👆　ネガマックスは、絵で説明しにくいが、相手番も　自分の手番として考えようということだぜ」

「　なんで　そんなことをするんだぜ？」

「　コーディングが簡単になるから だぜ。
自分の番と　相手の番の２つを　コーディングしなくてはいけないところを、
ネガマックス　にすることで　自分の番　だけコーディングすれば　よくなるんだぜ」

「　２つやらなくちゃいけないことが　１つになったら　楽よねえ」

「　なんで　そんなことができるんだぜ？」

「　ネガマックスじゃなかったときは、　評価値は、わたしから見たものだぜ」

「　将棋は　二人零和ゲームなので、自分が良ければ相手が悪く、自分が悪ければ相手が良いぜ。
だから　手番が変わるときに　評価値の正負を入れ替えれば　どちらの手番でも
自分から見た評価値（Value）になるぜ」

「　フーン」

「　プラス、マイナスを　ひっくり返せばいいのは　評価値だけじゃないわよね。
あと　２つある」

「　何があったっけ？」

「　👆　アルファー値と、ベーター値よ」

「　ありゃあ！」

「　👆　わたしのとき　ベーターさんに　ベーター値より大きな値は　ベーターカットされるが、
相手のとき　わたしに　アルファー値より小さな値は　アルファーカットされるから、
うーん、
アルファー値と　ベーター値は　交互になる……？？」

「　お父ん、　アルファー値とベーター値が交互になる　んだったら、ちゃんとそのような図を描けだぜ。
その図は　言葉通りに描けてないぜ」

「　えっ！？」

「　👆　交互に入れ替わるって、こうよね」

「　フーム」

「　それ以外のものも　ひっくり返ってない？」

「　どこがだぜ？」

「　👆　この人が」

「　その人は　誰と入れ替わるんだぜ？？」

「　わたしじゃないのか？」

「　👆　こんなとこ入れ替わって　どうすんだぜ？
アルファー値と　ベーター値を入れ替えたいのに、１段上の緑色のおっさんと入れ替わっていいのかだぜ？」

「　👆　下にも　おんなじ人が居んじゃないの？」

「　そんな　無関係な人と　入れ替えていいのかだぜ？」

「　おんなじ　なんだから　いいんじゃないの？」

「　お父んが苦手な、　シコーリョク　というやつだな。
お父んは　頭の中で　あれと　これは　別の物だから　同じようにしてはいけないと考えるから　シコー　が停まるんだぜ。
別の物でも　同じように使えるなら　同じように使おうというのが　シコー　だぜ」

「　合理性を受け入れられないのよね」

「　👆　やったら！
あれっ、何も　入れ替わらね？」

「　何も入れ替わらないのなら、何もしなくていいのでは？」

「　じゃあ　評価値（Value）のプラス・マイナスをひっくり返して、
アルファー値と　ベーター値を　入れ替えたらいいのかだぜ？」

「　シミュレーションしてみましょう！」

Negamaxのシミュレーション

「　👆　初期配置は　変わんないだろ。
先手は最初から　１０点　有利としようぜ。
あと　評価値バーのデザインを　一新したぜ」

「　１三きりん」

「　👆　こうかだぜ？」

「　👆　ここで知識だぜ。丸いとこを　ノード（節；Node）、　線を　エッジ（辺；Edge）　と呼ぶぜ。
別の呼び方もあるが、この記事では　これで行くぜ」

「　👆　そして　ネガマックス（Negamax）を理解するための　知識のパズルピースとして、
エッジに　箱を作ろう。　これが工夫」

「　お父んしか　使わないけどな」

「　👆　そして　手番変更。
評価値バーの青いところを見てくれだぜ。
イラストを描き直すのが　めんどくさいので　バー自体を　１８０°回転するぜ」

「　そんなこと　企んでいたのね」

「　検証しようぜ。　先手が　＋１０点　なら、後手から見れば　ー１０点　だな。合ってるな」

「　アルファー値と　ベーター値の入れ替わりも確認したいのよ。これじゃ分かんないわよ」

「　端っこの葉っぱまで、シミュレーションを続けようぜ？」

「　３二ライオン」

「　👆　はい、手番変更。
評価値バーの青いところを見てくれだぜ」

「　先手から見た評価値（Value）に戻ってるな」

「　１四ライオン」

「　👆　はい、手番変更。
局面評価値（Value）は 先手の得も込みで　20点　だったとしようぜ。
そして　後手から見た評価値だから、
評価値バーの青いところを見てくれだぜ。ひっくり返ってるな」

「　－20点ね」

「　ところで　説明のためにウソをついていたんだが」

「　ウソをつくなだぜ。やり直せ」

「　👆　評価値（Value）というのは　先手番が有利だから最初から　10点　付いているというものではなく、
端っこの　葉の局面で計算されて　枝を戻っていく帰り道に付くものだぜ」

「　プラス・マイナスをひっくり返して　箱に　20　を入れたのね」

「　アルファー・アップデート は、エッジの箱の中の方の評価値を使うぜ」

「　１二きりん」

「　👆　バー回転」

「　ベータ値が　-20　になってるけど、いいのかなあ？」

「　👆　評価値（Value）は　-60　点。
アルファー値　-∞　以上、　ベーター値　-20　以下だから、いけるな」

「　それだと　悪い手、もっと悪い手　を探していかないかだぜ？
ネガマックスは　自分がいいと思っている手を探すんだろ」

「　自分の手番のときは　自分にとって　良い手、良い手　を　探している　し、
相手番のときは　自分にとって　悪い手、悪い手を　探している　し、
物は言いようだな、
相手番のときは　あとでプラス・マイナスがひっくり返るから　いつでも自分にとって　良い手、良い手　を　探しているように説明できる　んだぜ」

「　ややこし！」

「　もう少し　シミュレーションを続けてみようぜ？」

「　👆　１手　戻したら　評価値が　+60　点に反転したぜ」

「　プラス・マイナスが反転するのね。ややこし！」

「　相手番のとき　自分のアルファーが　相手のベーターになっていて、
自分のベーターが　相手のアルファーになってるな。
ベーターを右に動かすことがなくなって、アルファ―を左に動かしているだけ。
評価値（Value）が　アルファーを下回るのは　ただの　アルファー・アップデートしない なので、
アルファーカットは無くなったな。
じゃあ、アルファーカットは無くなって、ベータカットだけが有るようになるのかだぜ？」

「　そうなんじゃないか？」

「　👆　アルファー・アップデート　するぜ」

「　ノード（丸いところ）の評価値ではなく、エッジ（線のところ）の評価値を見て　比較するのか。
ややこし！」

「　バーを１８０°回転させてるとこ、うまく　コーディングできんの？」

雑なNegamaxのコーディングの説明

search(alpha, beta, depth):
    if depth == 0:
        # 葉ノード
        node_value = 局面評価値計算( )
        return  (node_value, _)

    bestmove = 投了
    move_list = 合法手生成( )

    for m in move_list:
        # バーが180°回転していることを実感しなさい（＾～＾）
        (node_value, _) = search(-beta, -alpha, depth-1)
        # エッジの箱を思い出しなさい（＾～＾）
        edge_value = -node_value

        if alpha <= edge_value:
            # アルファーアップデート
            bestmove = m
            alpha = edge_value

        if beta < alpha:
            # ベータカット
            break

    return (alpha, bestmove)

main( ):
    # 無限大とか使わず、十分大きな値で十分
    search(-30000, 30000, 4)

「　👆　これが　ネガマックスのアルファー・ベーター探索部　の雰囲気だぜ。
そのままコピー貼り付けしても動かないから、感じろ」

「　じゃあ　お父ん、わたしに実装してくれだぜ」

＜おわり＞