3.3 重みの最適化

3.1節で、評価値をパラメータに重みつけたものの和であらわすことを説明しました。
今回はこの重みの計算方法について説明します。
これにはいくつか方法があると思いますが、ここでは過去の対局に基づいて計算する方法を紹介します。

まず棋譜を集めます。
必ずしも棋譜ではなく、いくつかの局面とその評価値を準備できれば良いのですが、棋譜から局面を生成するのが簡単です。
具体的にどの程多くの棋譜を集めればよいのかはよくわかりませんが、数千から数万といったところだと思います。
棋譜は、必ずしも強い対戦者同士のものが良いわけではありません。
悪手が含まれているものも必要です。

次に棋譜から各段階における局面を生成し、それに評価値をつけます。
終盤の局面ならAlpha-Beta法等で最善の評価を行うことができます。
しかし中盤では最善の評価を行うことができません。
そのため最善評価の近似値を求める事になります。
一つの方法として、まず終盤での評価関数の重みづけをした後に、それを用いて中盤の局面の評価値づけをするやり方があります。
またある程度強いプレイヤ又はプログラムによって最後まで打ち、その結果を利用することもできます。

次に重みの最適化を行います。
重みの最適化とは、上で生成した局面を評価したときに、評価関数による値の誤差が最小になるようにすることです。
局面を p 、パラメータを fi 、重みを wi とすると、評価関数 f (p) は

f (p) = wi fi (p) ......(1)

となります。
和は i についてとります。
局面に番号をつけ、 j 番目の局面を pj であらわし、その評価値を vj とすると、評価関数の誤差(2乗誤差) E は

E = ( 1/N ) { vj - f (pj ) } 2 ......(2)

となります。
N は局面の数で、和は j についてとります。

これを最小にするために、行列を用いる方法がありますが、パラメータの数が多い場合にはこの計算が大変になります。
そこで、ここでは「backpropagation(バックプロパゲーション)」として知られる方法を紹介します。
backpropagationは、日本語では「誤差逆伝播」と呼ばれ、現在の誤差から重みをどれだけ変化させればよいかを計算する方法です。
上式を最小にするために、その偏微分が0になるようにパラメータを調整します。

∂E/∂wi = -( 2/N ) { vj - f (pj ) } fi (pj ) ......(3)

和は j についてとります。
この値が大きければwiを小さくすればよく、逆に小さければwiを大きくすれば良いのです。
具体的な変化量は次式で表されます(和は j についてとる)。

i = ( 2β/N ) { vj - f (pj ) } fi (pj ) ......(4)

βは変化の大きさを決めるパラメータです。
βが小さいと収束が遅くなりますが、大きすぎてもよくありません。
注意してほしいのは、上式で最初の f に添え字がないのに対し、後の f に添え字があることです。
前者は評価関数をあらわし、後者は評価関数につかわれるパラメータの1つです。

この式によって何回か重みを変化させることによって、重みは(3)式が0になる解に近づきますが、必ずしも最適な(2乗誤差が最小になる)解に収束するとは限りません。
というのは、(3)式を満たす解は、最適解以外にも存在するからです。
最適に近い解を求める方法として、

  • 異なる初期値からパラメータ調整を行い、もっとも誤差の小さいものを採用する。

  • 重みを変化させるときにランダムな値を加える。加える値の絶対値は徐々に小さくしていく。
という方法等があります。

私はこの方法に関して詳しくないので、この程度の説明しかできません。
詳しく知りたいと言う方は「回帰分析」や「多変量解析」の専門書を参考にしてください。


トップに戻る
3.2 パターンによる評価