電王戦で一躍有名になったものの一つに「評価値」というものがあります。これはコンピュータが考える局面の形勢を数値化したものであり、歩一枚が100点程度になるように規格化されています。ちなみに、歩が100点というのは、コンピュータチェスのセンチポーン(1点=歩兵の100分の1)に由来しています。
機械が計算する値なら、電卓のように、局面を入れればポンと決まった値が出てきそうな気がしますが、実際の評価値は時間が経つと共に数値が更新されていきます。これはコンピュータが“考えている”からなのですが、一体、何をどうやって“考えている”のでしょうか?
実は、局面を入れればポンと出てくる値というのはちゃんと存在していて、「静的評価値」と言います。機械学習等で作るのは、この値を計算する関数(静的評価関数)です。コンピュータは、この静的評価値に基づいて、先の手を読んで(探索と言う)、評価値を更新していきます。いわゆる「評価値」というのは、読んだ先の局面の静的評価値のことであり、それ故に、探索が進むにつれて値が変わってくるわけです。
この辺の手法というのは、意外と人間に近い感じがします。「静的評価値」が“一目の判断”に対応していると考えると、それに基づいて先の展開を読んで、形勢を判断したり、指し手を決めたりするということ自体は人間のやり方と同じです。
それでは、実際にコンピュータはどのように探索を行っているのでしょうか?
もちろん、技術の詳細は複雑であり、また、ソフトによっても違うわけですが、今回は最も基本となる仕組みである「ミニマックス法」について解説します。
まず、先の展開を読むためには、自分の指し手の方針を決め、また、相手の指し手を予測しなければなりません。いわゆる戦略が必要になります。
自分の指し手については、最も評価値の高い局面(“最善手”と言う、本当に最善であるかは神のみぞ知る)を選択することにします。序盤では定跡ファイルの登録手を用いたり、対人ゲームでは擬似乱数によって手をばらけさせたりというようなこともありますが、ここでは最善手のみを考えます。
相手の指し手については、相手が自分であると想定して、相手にとっての最善手(こちらの評価値を最も下げる手)を指し手として予測します。「なぜベストを尽くさないのか」というわけです。
このように両者が最善手で応じると考えると、先の展開を読むことが可能になります。この戦略を「ミニマックス法」と言います。「ミニマックス」とは「最小(min)となる最大損害(max)」という意味であり、将棋は2人で指すものですから、こちらのミスをなくしてひたすら耐えていれば、その内に相手がミスをして有利を築けるだろうと考えていることになります(※ここでの「耐える」というのは将棋の攻め/受けとは別の概念であり、攻めでも受けでも、得をするためにやるのではなく、損をしないためにやっているということです)。
ちなみに、将棋の場合には「自分の損害」=「相手の利益」ですので(零和と言う)、「最小となる相手の最大利益」と言い換えることもできます。ただの言い換えですが、受ける印象は変わります。また、「損害」と「利益」というのは、原点と符号だけの違いですので、「最大(max)となる最小利益(min)」と言い換えることもでき、この場合は「マクシミン」戦略と呼ばれます。この辺は様々な書き方ができるので混乱の元になるのですが、本質は同じことです。
それでは、具体的にやってみましょう。
簡単のために深さを3に固定して、以下の図のゲーム展開(ゲーム木と言う)における3手の読みを考えてみます。
一番左が出発局面(根ノード)で自分の手番(青色)とします。そこから、指し手の候補が2つに分かれて、右側の相手の手番(赤色)の局面となり、さらに分岐して右へ右へと展開していきます。右端の末端局面(葉ノード)にある数字が、その局面の静的評価値です。静的評価値の数値は、こちらが優勢となる正の値が多いですが、中には負の値となってしまう変化も含まれています。
両者最善の変化を探すには、以下の図のように、右端の末端局面から順番に遡っていきます。こちらの手番では最大値を選び、相手の手番では最小値を選びます。
結果的に、一番上の変化が両者最善であったということが分かり(※後の説明のために、意図的にそういう順序にしています)、出発局面の評価値が+500点であるということも分かりました。
ここで、「何で探索なんて行っているんだろう?」「探索なんてせずに静的評価値をそのまま使えばいいじゃないか」という疑問をもたれる方もいるかもしれません。確かに、探索を行っても最終的に使うのは末端局面の静的評価値なわけですから、静的評価値の確からしさが現局面においても末端局面においてもそんなに変わらないとすると、無駄に仮定をおいて現局面から離れていく分だけ、探索は評価値の精度を落としているだけという可能性もあるわけです。もしそうなら、読み切りができる最終盤を除けば、探索をしない方がよいということも考えられます。
実は、ここのところがミニマックス法が「戦略」である所以であり、仮に評価値の精度が向上していないとしても、少なくとも探索の範囲内においてミスをしないことが勝率に結び付くだろうという考え方なのです(※評価値の精度自体は変わらなくても、探索を行えば、探索範囲分の下限保証が付いた値になります)。
ミニマックス法がどういう状況ならば「戦略」として正しいのかというのは非常に難しい問題なのですが、理論の話はさておき、現実のコンピュータ将棋においては探索の深さと勝率には強い正の相関があります。コンピュータ将棋におけるミニマックス法の有効性は実証的に示されていると言えます。
また、ミニマックス法に基づくと、静的評価関数の良し悪しについても一つの指針が立てられます。それは「両者最善で指し手が進んだ時に静的評価値の変動が少ないものが良い」ということです。もし静的評価値の変動が少なければ、末端局面からさらに探索を進めたのと同様の結果をその分の探索をせずに得られることになりますし、また、次回に説明するように、探索自体もより効率的に行えるようになります。
Bonanza式の機械学習においては、教師となる棋譜に基づいて、指し手がなるべく一致するように(かつ過剰に一致しすぎないように)静的評価関数を作成するわけですが、このやり方では、手に入る良質な教師棋譜の数に制限があるために、どうしても限界が出てきてしまいます。そこで、上記の方針を採用すれば、自らの探索結果を教師とすることで、Bonanza式の静的評価関数をさらに強化していく学習が可能になるわけです。この手法を確立したのは、筆者の理解では、NineDayFever(NDF)だと思います。
さて、上の例では深さを固定しているわけですが、これでは持ち時間のある対局には対応できません。ですので、最初は浅い深さで読んで、そこから徐々に深く読んでいくという反復深化の手法が採られます。また、末端局面で王手や駒取り等に手を絞った少量の探索(静止探索と言う)を行ったり、有望そうな局面について探索を延長したりというようなことも行われます。これらの技術についての説明は、ここでは省略します。
また、上の例では、全ての局面を全幅的に探索して答えを出しているのですが、これは明らかに非効率的であり、平均分岐数が約80と言われる将棋においては、このやり方では深く読むことはできません。読む必要のない変化を切り捨てる「枝刈り」と呼ばれる手法が必須になってきます。
次回は、この「枝刈り」について解説します。
- 次の記事:「ミニマックス法とは何か? 2:アルファベータ枝刈り」
コメント