いぬおさんのおもしろ数学実験室

おいしい紅茶でも飲みながら数学、物理、工学、プログラミング、そして読書を楽しみましょう

将棋ソフトのミニマックス法、αβ法

 将棋を指すソフトなどが手を考えるときに使うミニマックス法、αβ法について簡単に説明しましょう。ことによるとディープラーニング全盛の今、違う部分もあるかも知れませんが、大事さは変わらないと思います。

 まず基礎知識として将棋ソフトの大体の仕組み。将棋ソフトは探索ルーチンと評価関数を持ち、人間の思考をシミュレーション(真似、まね)します。探索ルーチンは、この局面からはこういう手がある、別のああいう手もある、……、そしてそれぞれの手に対して相手はこういう手を指すかも、いや、こんな手を指してくるかも、……、そしてそれらの手に対してこちらはどんな手があり、……というようにゲームの進行を追跡します。次に評価関数です。評価関数は、盤面を見て「これなら先手がかなり有利だ」とか、「後手が少しだけ有利だ」とか判定(評価)します。局面の評価は大変難しいです。雑でいいなら、将棋ならどちらが駒をたくさん持っているか、とかで評価できますが。
 ソフトは基本的にはミニマックス法に基づいて着手を決定します。図を見て下さい。

f:id:Inuosann:20210122192109p:plain

考え方の説明なので、ソフトは2手先までしか読まないとしましょう。Aは現在の局面、自分の手番(これから自分が手を指す)だとします。可能な手は3通りあるとしましょう。それぞれの手に対し、局面はB,C,Dと変わります。Bからは相手の着手は3通り、Cからは3通り、Dからは2通りです。2手先の局面はE~Lです。これらE~Lの局面は、評価値は自分から見てそれぞれ3,7,8,2,6,5,14,5点だとしましょう。これは評価関数で計算するのです。Bは相手の手番ですから、そこでは手xを指すはずです。相手にしてみれば評価値を下げたいわけだから。同じ理由でC,Dではそれぞれ手y、zを選ぶはずです。これで局面B、C、Dの評価値が3,2,5点と決まりました。Aでは自分が手を決めます。もちろん手wを指します。B、C、Dの評価値のうち、最大のものを選ぶからです。Aでは手wを指すのが最善だということです。図は木(をひっくり返したもの)に見えますから、ゲーム木と呼ばれます。こうして、ゲーム木で交互に最小値、最大値、最小値、最大値、……と選んで自分の着手を決定する方法をミニマックス法と言います。よい方法です。
 ……実はしかしホントはあまりうまくありません。プロ棋士羽生善治氏は「ひとつの局面で、可能な手は平均80手ある」と言っています。例えば7手先まで読めればソフトは相当強くなるはずです。7手先には何通りの局面があるでしょうか。羽生の言っていることが確かだとすると(80の6乗)≒262144000000、なんと2600億通り以上です!! さっき書いたように正しい評価値の計算は実際には非常に難しいため、7手先、2600億通りの局面の評価値を全て計算していたら時間がかかりすぎてどうにもなりません。そこでミニマックス法を改良したαβ法の出番です。
 αβ法は、計算しても意味のない評価値を計算しないようにする工夫です。図では、3段目の3,7,8から最小値が上に上がります。これでBは3点と分かるのでした。次にCの点数を考えましょう。Cからは着手は3通り。Hは2点です。このとき、実は局面IJの評価値は計算する必要はありません。Hは2点なので、もうCは2点以下です。HIJからは最小値が上に上がるからです。Bは3点、そしてBCDからはAに最大値が上がるので、もはやCのちゃんとした点は考える必要がありません。そこで、IJの評価値を計算する必要がなくなるのです。こうして、C-I、C-Jの枝をゲーム木から刈り取ることができました。これをαカットと言います。ゲーム木の無駄な枝を刈るので、枝刈りと言います。同様のβカットというのもあり、ミニマックス法にこの枝刈りを組み合わせた方法がαβ法です。
 こうした方法で(他にもたくさん工夫はありますが)将棋ソフトは限られた時間でなるべくよい手を探します。さっきも少し書きましたが、今のプログラムはいわゆるAIを導入しているみたいですよね。どうやってディープラーニングを将棋を指すのに使うのか知りませんが、多分今回書いたことは相変わらずやっているはず、と想像しています。

 「こういう場面ではこう指す、ああいう場面ではああ指す、……」という事実をたくさん憶えていて将棋を指すんだ、なんて思ってませんでしたか!? ソフトはきちんと「考えて」いるのです。