機械学習エンジニアのための将棋AI開発入門その1

最近、機械学習を勉強している人が増えてきたので、簡単な機械学習ならわかるよといった人たち向けに将棋AIの開発、特に評価関数の設計について数学的な側面から書いていこうかと思います。線形代数と偏微分、連鎖律程度は知っているものとします。

3駒関係

3駒関係はBonanzaで初めて導入された、玉と任意の2駒との関係です。この線形和を評価関数の値として用います。評価関数とは、形勢を数値化して返す数学的な関数だと思ってください。

この3駒関係を俗にKPPと呼びます。King-Piece-Pieceの意味です。将棋の駒は40駒ありますので、{先手玉,後手玉}×残り39駒×残り38駒/2 通りの組み合わせがあります。この組み合わせは1482通りあります。Cをコンビネーション記号とすると、次のようになります。

$$ 2 \times {}_{39}C_{2}= 2 \times \frac{39 \times 38}{2 \times 1} = 39\times 38 = 1482 $$

つまり、88の升にある先手の玉 × 先手の78金 × 先手の77銀　のように任意の組み合わせに対して点数がつけてあります。上記の1482通りの組み合わせに対して、この点数を足し合わせます。

このとき、KPPのテーブル(3駒の組み合わせに対する点数が書かれている)を参照する回数(表引きの回数)が、1482回ということです。

Pieceのとりうる値は1500程度あります。(いま話を単純化するために、1500ちょうどとします。)

11の升にある先手の歩、12の升にある先手の歩、…、99の升にある先手の歩、11の升にある先手の香、…、99の升にある先手の香、…、桂、銀、金、角、飛車も同様。あと、成り駒、手駒、そして後手の駒も同様です。手駒は、「先手の1枚目の歩」「先手の2枚目の歩」みたいに、何枚目の駒であるかで異なる値を割り当てるものとします。

King-Piece-Pieceのすべての組み合わせは、先手玉81升×1500×1500 = 182,250,000となります。(約2億。以下、2億ぴったりであるとして話を進めます。)

後手玉の分も含めるとこの倍なのですが、すでにわりと大きいので、KPPのテーブルを先手用と後手用と別個に用意するのはもったいないため、後手用は用意せずに駒の位置を180度回転させた上で、先手用のテーブルを用います。なので後手のことは忘れてください。

2億次元もあるので、1つの要素を16bit符号付き整数で保持する場合、2億×2bytes = 400MB程度となります。

※　実際は、3駒関係の評価関数では、ここに手番(Turn)を含めた、KPPT型の評価関数を使うのが普通ですが、詳しい話は割愛します。詳しくは、NDFという将棋ソフトのWCSC24のPR文書にあります。

3駒関係のベクトルでの表現

数学のベクトルの表現を使うと、入力xを2億次元のベクトルとして表現できます。なお、ここに出てくるベクトルはすべて縦ベクトルとします。

$$\textbf{x} = \left(\begin{array}{}x_1\\
x_2\\
\space\vdots\\
x_n\\
\end{array}
\right)$$

点数(重み)も同じく2億次元のベクトルで表現しましょう。それをベクトル$\textbf{w}$とします。

$$\textbf{w} = \left(\begin{array}{}w_1\\
w_2\\
\space\vdots\\
w_n\\
\end{array}
\right)$$

そうすると、KPP型の評価関数は、$\textbf{w}$と$\textbf{x}$との内積で表現できます。

$$Eval(\textbf{x}) = \textbf{w}\cdot\textbf{x} = w_1 x_1 + w_2 x_2 + \cdots$$

ただ、xベクトルは上で書いたように1482箇所だけが1で他は0であるような疎(スパース)なベクトルです。実際の対局で、$Eval(\textbf{x})$の値を求めるときには各局面につき、1482箇所しか計算しません。(ついでに言うと、玉以外の駒が移動したときには簡単に差分計算ができるため、もっと小さな計算量で済みます。また、玉が移動したときにも巧妙に差分計算をする方法が存在します。)

あと、微分を考える上では、内積ではなく行列の掛け算として表記したほうがわかりやすいかも知れませんね。

$$Eval(\textbf{x}) = \textbf{w}^T\textbf{x}$$

ちなみに、ベクトル$\textbf{w}$をファイルに保存したものを評価関数ファイル(あるいは単に評価関数)と呼びます。将棋AIの開発者が「今年の評価関数は(棋力的に)強くなった」と言った場合、評価関数の関数形が変わったのではなく、評価関数パラメーターをうまく学習させて、いい具合に学習された評価関数ファイルができましたという意味です。

また、一般的な機械学習で、ここまで大きな次元のベクトルを扱うことは極稀でしょう。この手の機械学習では特徴量の10倍～100倍の教師が必要で、KPPT型の評価関数の学習においては、教師データも100億局面以上生成するのが普通です。そういう意味では、将棋AIの機械学習は、機械学習のなかでもかなり特異な部類であると言えます。

3駒関係の偏微分

次に、機械学習で使うために、wベクトルのi番目の要素で評価関数を微分してみましょう。これは偏微分となりますが、wのi番目の要素にはxのi番目の要素しか掛け算されていないので偏微分は次のようになります。

$$\frac{\partial}{\partial w_i}Eval(\textbf{x}) =x_i$$

これは、wのi番目の要素が評価関数の出力値にどれだけ寄与しているかを示していて、Eval(x)は理想的にはこうなって欲しいという値があったときに、この寄与した分だけwを調整すれば良いことを示しています。

繰り返しになりますが、その局面に出現していなかった3駒関係に関しては$x_i$は、0になりますから、出現していなかった3駒関係の$w_i$での偏微分は0になります。つまりは、出現していなかった3駒関係に関しては考えなくて良いということです。当然ですね。

その昔、Bonanzaが導入した機械学習の論文を見ても実装の仕方がわからない人に対して、GPS将棋の金子知適先生は「桂馬で微分するんだよ」みたいなことをおっしゃっていた記憶があります。上式は、出現した駒(に掛かっている係数)で偏微分してありますので、「桂馬で微分」は正しい説明だとは思います。(ただ、「桂馬で微分」というのは、パワーワードなので、初めて聞く人は耳を疑うかも..)　※　コメント欄に補足あり

さて、評価関数Eval(x)はスカラー値をとります。スカラー値をベクトルで微分する場合の記法と公式を用いれば、次のように書き表せます。

$$\frac{\partial}{\partial \textbf{w}}Eval(\textbf{x}) = \frac{\partial}{\partial \textbf{w}}\textbf{w}^T\textbf{x} = \textbf{x}$$

評価関数から勝率への関数への変換

いま、この評価関数Eval(x)は歩を100点とするように正規化してあるものとします。この評価関数は、3駒関係のそれぞれの点数の線形和なので、実際の期待勝率とは異なります。

例えば、Eval(x) = 1000の場合を考えてみましょう。1000は、歩の1枚の価値の10倍の得をしている局面ですが、将棋では相手の駒が自分の駒になるので、駒得は、相手から歩が1枚減り(先手から見て+100)、自分の手駒に歩が加わる(先手から見て+100)で合計200点のプラスとなります。つまりEval(x)=1000は、歩を5枚、駒得していることに相当すると言えるでしょう。

Eval(x) = 2000　の局面は、Eval(x) = 1000 の局面より2倍勝ちやすいかというとそんなわけもないでしょう。つまり、勝ちやすさ(期待勝率)を表現する関数 $\varphi$があるとして、$\varphi(x)$は、Eval(x)=0のとき0.5(期待勝率50%)、Eval(x)=∞のとき1.0(期待勝率100%)、Eval(x)= -∞のとき0.0(期待勝率0%)となるような関数であって欲しいわけです。

このように関数に見覚えはないですか？そうです。シグモイド関数です。

$$\varsigma(x)=\frac{1}{1+exp(-ax))}$$

ある評価値をとった局面から、同じ程度の棋力のAIプレイヤー同士で終局まで対局させて統計的に調べると、評価値evalと期待勝率$\varphi$とは次のような式で近似できることがわかりました。

$$\varphi(eval) = \frac{1}{1+exp(-1/600 \times eval)}$$

これは定数a が 1/600 であるシグモイド関数です。この1/600は、Ponanzaで最初に使われたので将棋AI界隈ではPonanza定数と呼ばれています。(実際はもう少し小さい値とも言われています。)

シグモイド関数を使うメリットとして、上で書いたように、$\varsigma(\infty) = 1, \varsigma(0) = 0.5 , \varsigma(- \infty) = 0$ というような性質があることの他に、微分したものが、次のように自分自身の関数を用いて簡単に表せるということが挙げられます。(この式はあとで使います)

$$\frac{d\varsigma(x)}{dx} = a\space\varsigma(x)(1-\varsigma(x))$$

※　高校レベルの微分の計算なので証明はここでは省略しますが、気になる方は、シグモイド関数の微分(Qiita)をご覧ください。

強化学習のための損失関数の設計

長い時間思考させたときの評価値を教師として、評価関数の出力が、その教師の評価値に近づくように重みパラメーターであるwベクトルを調整することを考えます。教師自体は自己対局させていけば自然と色々な局面が出現するので都合良いでしょう。よくある強化学習ですね。

この強化学習のために、損失関数(目的関数)を設計します。いま教師局面の評価値をa,その局面での評価関数の出力bをとします。

終盤に近づくと評価関数の出力は発散していきますが、評価値が10000と20000とでさほど期待勝率に差があるわけではないので、先手必勝の局面で、評価関数が10000を出力しようが20000を出力しようがあまり大差はないわけです。逆に-200と200とは期待勝率は大差です。つまり、評価値が0付近のところほど敏感に反応するような評価関数であって欲しいので、損失関数を単純に(a – b) の足し合わせとして、それを最小化するような考えかたでは少しまずいのです。

そこで、この手の機械学習でよく用いられる交差エントロピーを使って損失関数を定義します。つまり、教師とEvalの評価値a,bから推定した勝率の確率分布が一致して欲しいので、その交差エントロピーを損失関数として定め、これを最小化するという考えかたです。これは、SDT4(第4回将棋電王トーナメント)の†白美神†のPR文書に簡単な説明があります。

https://denou.jp/tournament2016/img/PR/Hakubishin.pdf

上記のPR文書の数式、少し間違っているところがあるので、以下に書き直しておきます。

p: 深い探索の評価値から推定した勝率
q: 浅い探索の評価値から推定した勝率
とします。

q は、 Eval(x)をシグモイド関数に通したやつです。
$q=\varphi (Eval(\textbf{x})) = \varphi (\textbf{w}^T\textbf{x}) $
※　実際は、浅い探索の評価値としては、$Eval(\textbf{x})$の値ではなく、qsearch(静止探索)の値を使うことのほうが多いですが、細かいことはいま気にしません。

pは実際に長い時間をかけて思考させたときに得られた評価値(探索の評価値)をシグモイド関数に通したやつです。
$p = \varphi( search\_eval )$

損失関数$l$ = 交差エントロピー$H(p,q)
= – \displaystyle\sum_x {P(x) log \space Q(x)}
$
ここではxは勝ちか負けの2値をとるので
$
= -p \space log \space q \space – \space (1 – p) log(1 – q)
$

※　上式は2値分類問題の交差エントロピーとして機械学習の教科書などに書かれています。$P(勝ち)=p,P(負け)=1-p,Q(勝ち)=q,Q(負け)=1-q$のときの交差エントロピーを求めています。

このように損失関数$l$を設定して、これを最小化するベクトル$\textbf{w}$を求めます。

損失関数の勾配

$l$の$w_i$での偏微分を考えます。この時、$p$は定数とみなせます。

$
l’ = \displaystyle{\frac{\partial l}{\partial w_i} = – \frac{pq’}{q} – \frac{(1 – p)(1 – q)’}{1 – q}\\
= – \frac{pq’}{q} + \frac{(1 – p) q’}{1 – q}\\
= \frac{-pq'(1 – q)+(1 – p)qq’}{q(1 – q)}}\\
$

$q$はシグモイド関数$\varphi$であり、上式の分母の$q(1 – q)$は、さきほど出てきたシグモイド関数の微分した形(いま定数aは無視する)なので分母を$q’$に置き換えると

$
= -p(1-q) + (1-p)q\\
= q~-~p
$

※　実際はシグモイド関数の定数aが上式に出てくるが、SGDなどで学習させるときには学習率$\eta$を調整するので、勾配が定数倍されている分には問題とならない。

めでたく、$q~-~p$となりました。つまり、教師の評価値と評価関数のEvalから算出される期待勝率の差の分だけ、ベクトル$\textbf{w}$を調整すれば良いということですね。

※　その局面で出現していた特徴量$x_i$のみが1で、出現していなかったものは0になるので、出現していた特徴量に付随する$w_i$だけを動かせばよろしいです。

評価関数と損失関数の関係

評価関数は、歩の価値を100とするように設計されているので、その値を期待勝率に変換するときはシグモイド関数を通す必要がありました。また、損失関数に交差エントロピーを用いる場合、その勾配のところに$q(1 – q)$の形が出てきて、これがシグモイド関数の場合に$q’$ になることから式が簡単化できました。

ここでは評価関数については、歩の価値を100とする以上の仮定はしていないので、KPP型の評価関数以外でもこの性質は成り立ちます。具体的には、tanuki-チームが開発したNNUE評価関数という、全結合のシンプルな3層程度のニューラルネットワークでも、同様の議論ができます。(NNUE評価関数もKPP同様に歩の価値を基準とした評価値を出力します。)

評価関数にニューラルネットワークを用いる場合、出力を期待勝率にするのが普通ですが、ニューラルネットワークの層が浅い場合、線型性が強い(非線形な変換が得意ではない)ので、NNUEぐらいの層の浅いニューラルネットワークの場合、どちらにするほうが優れているのかは一概には言えません。

まとめ

将棋AIの評価関数を開発してみたい機械学習系のエンジニアのために、駆け足でKPP型評価関数の損失関数の設計まで見てきました。ここまでくれば、SGDやAdaGradなどでwベクトルを調整すれば良いだけですね。

機械学習系のエンジニアの人たちはこれで自分なりの評価関数を作っていけるはずです。

次回は、NNUEのような簡単なニューラルネットワークが何故、将棋AIの評価関数としてうまく機能するのかだとか、CNNやResNetが何故うまく局面を評価できるのかについて数学的な観点から書いていきたいと思います。(次を書くかどうかはわからん)

本記事で将棋AIの評価関数に興味を持っていただけたなら幸いです。

追記

次記事
機械学習エンジニアのための将棋AI開発入門その2