Bonanzaメソッドの解説 - TadaoYamaokaの開発日記

昨日、電王戦 Ponanza×佐藤天彦名人の第1局をニコニコ生放送で見ていました。

コンピュータ将棋には以前より興味があり、初めの頃から電王戦はウォッチしていました。

名人に勝ったPonanzaは、次はディープラーニングを使うということですが、昨日の対戦で使われたバージョンは、探索はミニマックス法の改良で、評価関数を機械学習で最適化するという方法で作られています。

ミニマックス法の並列化や高速化は、チェスのプログラムで昔から改良され続けてきました。
将棋プログラムでも基本は同じでありコンピュータ将棋での技術的な進歩はそれほどなかったと思います。

評価関数については、2006年のBonanzaの登場以前は、プログラマーがロジックを組んで調整していたものが、Bonanzaが3駒関係の特徴量の線形和をプロの棋譜から機械学習したことでブレイクスルーが起きました。

Bonanza登場以降は、ほぼすべての将棋プログラムがBonanzaの改良となっています。

Ponanzaは、他の将棋プログラムの一歩先を行っており、評価関数の学習に、プロの棋譜を使用しないで、自己対戦の結果を使って強化学習を行っているようです。

Bonanzaが取り入れた、評価関数の機械学習が今の将棋プログラムの重要な要素となっています。

ここでは、Bonanzaで行っている機械学習の方法(通称Bonanzaメソッド)について解説します。

Bonanzaメソッド

学習する局面の集合を ${\bf P}$ 、特徴ベクトルを ${\bf v}$ 、局面pの合法手数を $M_p$ 、棋譜で選択された子局面を $p_1$ 、m番目の合法手による子局面を $p_m$ とすると、

目的関数 $J({\bf P}, {\bf v})$ を、以下のように設計する。

$\displaystyle J({\bf P}, {\bf v}) = \sum_{p \in {\bf P}} \sum_{m=2}^{M_p} T_p[\xi(p_m, {\bf v}) - \xi(p_1, {\bf v})]$

ここで、 $\xi(p_m, {\bf v})$ は、Minimax探索の値である。
$T_p(x)$ は損失関数で、局面pの手番がMaxプレイヤーの場合、 $T_p(x)=T(+x)$ 、Minプレイヤーの場合、 $T_p(x)=T(-x)$ となる。
$T(x)$ は、一価の単調増加関数であればよく、Bonanzaではシグモイド関数

$\displaystyle 1/(1+e^{-0.0273x})$

が使われている。

勾配法を使用して、目的関数を最小化するように特徴ベクトル ${\bf v}$ を学習する。

解説

プロの棋譜で選ばれた手の正しい評価値が分かるわけではないので、直接評価関数を学習することができない。
そこで、現在の評価関数を使用して、プロの棋譜で選ばれた局面の評価値と、それ以外の局面の評価値の差の合計を損失関数 $T(x)$ としている。

プロの棋譜と違う手を選択した場合、その評価値を低く見積もった場合ほど、損失関数の値は大きくなる。

全局面分について損失関数を計算した合計が目的関数となっている。

損失関数を微分可能な関数にすることで、勾配法を用いて、特徴ベクトル ${\bf v}$ を最適化できる。

勾配法は、目的関数を $v_i$ について偏微分を行う。

$\displaystyle \frac{\partial J({\bf P}, {\bf v})}{\partial v_i} = \sum_{p \in {\bf P}} \sum_{m=2}^{M_p} \frac{d T_p(x)}{dx}[\frac{\partial \xi(p_m, {\bf v})}{\partial v_i} - \frac{\partial \xi(p_1, {\bf v})}{\partial v_i}]$

各パラメータ $v_i$ について、偏微分の値に、学習率を掛けてパラメータを更新する。

上記式で、 $T_p(x)$ の $v_i$ についての偏微分は、合成関数の微分の法則

$\displaystyle y=f(x), x=g({\bf v})$ のとき、 $\displaystyle \frac{\partial y}{\partial v_i}=\frac{d f}{d x} \frac{\partial g}{\partial v_i}$

を使用している。

$\xi(p_m, {\bf v})$ の微分は、探索結果の末端局面の評価関数の微分で代替する。
末端局面の評価関数は3駒関係の線形和であるため、微分可能である。

Bonanzaでは収束性をよくするために、束縛条件(持ち駒の評価値の合計を一定)と、L1正則化項を目的関数に加えている。

目的関数が全局面の損失関数の合計となっていることからわかるように、バッチ学習を行っている。

当時のコンピュータで、45833局の学習で、約1ヶ月かかっているようである。
2009-11-30

この部分は、ミニバッチにすることで、より収束が速くなると思われる。

おまけ

私は、以前にコンピュータ囲碁のAlphaGoのクローンを途中まで作成したことがある。
その際に、rollout policyをプロの棋譜から機械学習を行った。
rollout policyで学習するのはどの手を選択するかの方策であるため、出力をsoftmax関数とすることで、プロの棋譜で選択された手から直接学習を行うことができた。

また、AlphaGoのRL policy networkでも行われているように、強化学習の手法で方策を改善でき、Value Networkで方策から価値関数(評価関数)を学習できる。

学習した方策を枝刈りに使用し、学習した評価関数を探索の末端の評価関数に使用することで、もしかしたらAlphaGoの手法はコンピュータ将棋にも応用できるかもしれない。
その場合、方策で使用する関数が3駒関係でも有効なのかは試してないのでわからない。

参考文献

コンピュータ将棋の進歩 6 -プロ棋士に並ぶ-