Help us understand the problem. What is going on with this article?

コンピュータ将棋の評価関数の仕組み

More than 3 years have passed since last update.

評価関数とは?

コンピュータ将棋で指し手を決定するときにこの指し手で進めた局面は何点、というように指し手選択の目安となる値を局面評価値といいます。
たとえば初手だと、76歩が200点、18香が-500点とか点数がついてるわけですね。
それが全合法手分あるので、一番高い点数の指し手を選びましょうというシンプルな考え方です。

評価関数をつくるには?

評価関数の作り方はいろいろあります。
人間の溢れる将棋の知識を利用して、将棋の局面の特徴(王手飛車とか割り打ちとか)に点数をつけていってそれを合算する方法とか、現在主流のKPPやKKPと呼ばれる3個の駒の位置関係に点数をつけていく方法とか、先進技術のDeepLearningを利用して現在の局面情報そのままのものに点数をつける方法とかがあります。
Bonanza登場以前はこの点数は開発者が考えて手作業で点数付けしていました。
しかしBonanzaが機械学習によってこの点数を自動的に調整する手法で大成功を収めました。
現在のベースはこの機械学習によって点数を調整する方法となっています。

機械学習とは?

ここで唐突に天気の話をします。
まずこれからお話する世界の天気は非常に単純で、3つの要素(前日の気温、前日の気圧、前日の湿度)で次の日の天気が決まるということにします。
私が明日の天気を知りたいとすると、3つの要素と天気との関係を蓄積されたデータから分析するわけですね。
たとえば前日の気温が30℃以上で湿度が60%以上のときは高確率で雨がふるとか、前日の気圧が950hPa以下の場合は暴風雨になる、とか。
で、そういうのを一般化して数式にするところから機械学習の考え方がはじまります。
たとえば、天気の種類が晴れ、雨、くもりの3種類しかないとします。
この場合に以下のような単純な数式で上記の関係を表すことを目指します。

天気 = 前日の気温 + 前日の気圧 + 前日の湿度

雨 = 0
曇り = 1
晴れ = 2

とします。
そうすると日本の気温がだいたい0~35℃くらい、気圧が950~1020hPaくらい、湿度が0~100%なので、このまま計算するとほとんどが晴れということになってしまいます。。
実際に値をいれてみると天気の予測なんて全くできてません。
ただ足しただけですから当然ですね。
そこで次はこうします。

天気 = A*前日の気温 + B*前日の気圧 + C*前日の湿度

AとBとCはなんらかの定数です。
そうすると、AとBとCをうまい具合に調整すれば上記の式が成り立つようになる気がしませんか?
この「うまい具合に調整」を自動で行うのが機械学習というわけです。

まずA、B、Cになんでもいいので初期値を設定します。
とりあえず全部初期値1にしときましょうか。
そして、データを代入していきます。
前日の気温が18℃、前日の気圧が1000hPa、前日の湿度が10%で、当日の天気が晴れというデータがあったとします。
そうすると上記式は

2 = 18A + 1000B + 10C

となります。
これを満たすABCを探せばいいわけですね。
で、式1個で変数3つなのでこの多元1次方程式は解けません。
式が3つ、つまりデータが3個あればこの方程式は解が出ます。

しかし、実際はデータはもっとやまほどあって、3個のデータに当てはまればおっけーみたいなことにはなってくれません。
そうするとどうするか?
全部のデータで「だいたい」当てはまるABCを見つけようという話になるわけです。
で、この「だいたい」当てはまる、ということはどういうことなのか?というのを数式で表すことを考えます。
そこで、まずどういうABCのときが全然当てはまってなくて、どういうABCのときがだいたい合ってるか考えてみましょう。

まず、A=B=C=1のとき

2=18+1000+10=1028

2と1028が一緒ですよ、となります。
全然当てはまってないですね。

次に
A=0.05 B=0.001 C=0.1のとき

2= 0.9 + 1 + 1 = 3

2と3が一緒ですよ!ってことになりましたので、
さっきよりはだいぶましです。
これを数学的に考えると、

Loss = 18A+1000B+10C - 2

このLossの値、ただ引き算しただけですが、が小さければだいたい当てはまってるといえそうです。
しかし、こういう場合に困った問題が起こります。

A=B=C=-1のとき

2=-18-1000-10=-1028

そうするとLossは-1030となり、0を振り切ってだいぶ小さくなります。
ただ小さいとおっけーとするとこういう問題が起こるので、

Loss = (-18-1000-10-2)^2

と、2乗することにします。
そうするとマイナス方向にどんどんずれてもLossはどんどん大きくなります。
この値でどれだけ当てはまっているかをみれば間違いなさそうですね。

このLoss = (f(x)-y)^2 のことを

平均2乗誤差

といいます。

f(x) = A*前日の気温 + B*前日の気圧 + C*前日の湿度
y = 天気

です。
この誤差が全てのデータを代入したときに一番小さくなるABCが、おそらくこの数式が一番だいたい当てはまってるということになります。
そういうABCが見つけられたら明日の天気が予測できるわけですね。

で、次に問題になるのはどれだけあてはまってないかがわかったところで、どうやってABCを調整していくんだ?ということになります。

ここで、Loss関数(平均2乗誤差)がいったいどういうグラフになるか考えてみます。
単純な2次関数なので、0を最小値とした放物線になりますね。
で、この関数が最小値となるようにAやBやCを調整するわけです。

ここで話をもっと単純化するために、天気を前日の気温だけで予測できる世界の話をします。
そうした場合、天気を予測するための数式は

天気 = A*気温

となり、Lossは

Loss = (A*気温-天気)^2

となります。
次は関数のお話です。
この2次関数(A*気温-天気)^2を普通の関数っぽく
Loss=y
気温=a
天気=b
A=x
と書き換えることにします。ただ文字をアルファベットにしただけです。
そうすると

y=(ax-b)^2

という式になります。
で、この関数が最小となるようなxを求めるためにはどうするか?
2次関数ですので、変曲点、つまりこの関数の増減が0の点でのxが求めるものだということがわかります。
というわけでこの関数の増減を知りたいので、微分することにします。
そうすると

y'=2(ax-b)*a

となり、x=b/aのときに最小値となることがわかります。
しかし、aもbもたくさんあるのでこんなにかっちり答えが出る事はまずありません。
そうした場合にどうしたらいいか?

そういうときには勾配法というものを使います。
ざっくりいうと、xに値を当てはめていってそのたびにLossを計算して、
Lossが小さくなる方向にxをだんだん動かしていく方法です。

Loss = (A*気温-天気)^2にいろいろ値を当てはめていきましょう。

天気=晴れ=2
気温=25℃
のデータがあったとします。
このときにA=1をとりあえず当てはめてみましょう。

Loss = (1*25-2)^2 = 529

すっごいでかいので、とりあえずマイナスにしてみましょう。
A=-1

Loss = (-1*25 -2)^2 = 729

あらま、でかくなってしまいました。
では、次は。。。
とやっていくといつ終わるかわからないので、どのくらい動かせばいいかの目安がほしいところです。

ここでLossの関数が2次関数であることに注目します。
この関数は2次関数なので放物線になるわけです。
で、放物線なので最小値のときのAの値から離れれば離れるほど増加の勢いが増えます。
このことを利用します。

今やりたいことは、

1、Lossを最小値に近づけるためにAを動かすべき方向を知りたい
2、Lossを最小値に近づけるためにAを動かすべき量を知りたい

ということなので、まず方向から。
Lossのグラフの接線の傾きに注目します。

最小値からプラス方向にAがずれてる場合は、接線の傾きは正になります。放物線なので。
最小値からマイナス方向にAがずれてる場合は、接線の傾きは負になります。放物線なので。

というわけで、接線の傾きの符号を逆転したものがAを動かすべき方向だということがわかります。

次に量です。
この場合も接線の傾きに注目します。

最小値から大きくAが離れてる場合には、接線の傾きは大きくなります。放物線なので。
最小値にAが近い場合には、接線の傾きは0に近づきます。放物線なので。

というわけで、量は接線の傾きそのままを動かしてやればよさそうです。

そうすると結果的には「接線の傾きの符号を逆転したもの」というのが
私の今知りたい「Lossを最小値に近づけるためにAを動かすべき量と方向」ということになります。

まぁ、簡単にいうと微分した値を符号逆転すればいいわけですね。

というわけでLossを微分した式をもう一度ひっぱってきます。

Loss' = 2*(A*気温-天気)*気温

となるので、

天気=晴れ=2
気温=25℃
A=1

を代入してみましょう。

Loss' = 2(1*25-2)*25 = 1150

というわけで符号を逆転して-1150だけAを動かしてみます。

天気=晴れ=2
気温=25℃
A=-1149

Loss' = 2(-1149*25-2)*(-1149)= 66019242

う~む、こんなはずでは。。。
こういう現象を発散といいます。
接線の傾きのスケールがでかすぎて最小値からどんどん離れていってしまうという現象です。
スケールがおかしいだけなので、スケールを縮めてやればいいわけです。
そのスケールを学習率といいます。通常αで表します。

Loss' = α2(A*気温-天気)*気温

と修正します。
ここで、α=0.0001に設定します。ここはいろいろ試して発散しないくらいの値を設定します。
そうすると

天気=晴れ=2
気温=25℃
A=1

のとき

Loss' = 0.0001*2(1*25-2)*25 = 0.115

ではAを-0.115だけ動かすことにします。

天気=晴れ=2
気温=25℃
A=0.885

Loss' = 0.0001*2(0.885*25-2)*25 = 0.110625

接線の傾きが上のときより0に近くなりました。
このときのLossの値は

Loss = (0.885*25-2)^2 = 405.015625

A=1のときの729より減っていますね。
なので、Aを動かす方向、量ともに間違っていなそうです。

これを何十回、何百回と繰り返せばいつかは全てのデータでのLossの最小値、つまり

天気 = A*気温

が全てのデータでもっとも当てはまりのいいAを見つけられることになります。

次に世界を天気が気温、気圧、湿度の3つで予測できる世界に戻りましょう。
この世界での数式は

天気 = A*前日の気温 + B*前日の気圧 + C*前日の湿度

でした。
そうするとLossは

Loss = (A*前日の気温 + B*前日の気圧 + C*前日の湿度 - 天気)^2

となるわけです。
で、これを微分したいわけですが、ABC3つも変数があるものの微分ってどうやんの?ということになるわけです。
ここで偏微分というものをやるわけです。大学で習いますね。

LossをAで偏微分してやると

Loss'A = 2*(A*前日の気温 + B*前日の気圧 + C*前日の湿度 - 天気)*前日の気温

となります。偏微分について詳しくはぐぐってください。

そうするとAを動かすべき量と方向は、

A ← A - α2(A*前日の気温 + B*前日の気圧 + C*前日の湿度 - 天気)*前日の気温

となります。
これを全部のデータで何回も繰り返せば、もっとも当てはまりのいいAがみつかります。
B,Cに関しても偏微分してやって動かすべき方向と量を求めればいいことになります。

つまり、

「たくさんのデータ」と

「予測したいもの = わかってるデータの特徴の和」という式ができて、

「勾配法」を適用してやれば

どんなものでも機械学習ができますよ、ということですね。

機械学習をコンピュータ将棋に適用するには?

機械学習を適用するには「たくさんのデータ」と「予測したいもの = わかってるデータの特徴の和」と「勾配法」があればできることはわかりました。
では、将棋において「たくさんのデータ」というのは何になるでしょうか?
普通に考えれば棋譜になりますね。
では、将棋の評価関数で「予測したいもの」っていったいなんでしょうか?
当然局面の評価値になります。
しかし、これが機械学習を適用するにあたって大きな問題になります。
どうして問題かというと、天気を予測したい場合には予測したいものはデータの中に含まれていました。
しかし、将棋の棋譜には評価値は含まれているでしょうか?
Floodgate等のコンピュータ将棋の棋譜にはあるかもしれませんが、少なくともプロ棋士の棋譜に評価値がのってるというのは聞いたことがありません。
これは困りました。
予測したいものの値のデータがない限り機械学習は適用できません。

そこでどうするか?
機械学習は本当に予測したいものの値のデータがない限り適用できないのか?
実はそうではありません。
予測したいものの値のデータがなくても、いくつかの条件を満たせば機械学習を適用することが可能なアルゴリズムが存在します。

その中のひとつに「ランキング学習」というものがあります。
ランキング学習というのは予測したい値そのもののデータがなくても、データサンプル同士の優劣や順序がわかっている場合に、その優劣や順序に従うように学習させるアルゴリズムです。

ランキング学習とは?

ランキング学習というのは、データの評価値そのものずばりはわからないけどデータサンプル同士の優劣ならわかる、というときに使える学習方法です。
将棋の場合だと棋譜にはその局面の評価値、というものはありません。しかし、たくさんある合法手の中から棋譜にある指し手を選んだ、というデータがあります。
これは、指した棋士が

「選んだ指し手の価値」 > 「選ばなかった他の合法手の価値」

と判断したことに他なりません。
このデータを機械学習に使おうとするとどうすればいいか?
天気の話だと、予測したいもの = 特徴要素に係数をかけたもの、となりましたが
上記の不等式を無理やり天気の話のような形にしようとすると、

予測したいもの1 > 予測したいもの2

という形になります。
「選んだ指し手で進めた局面の価値」は当然予測したいものなのですが、「選ばなかった他の合法手で進めた局面の価値」というものも予測したいものであることがわかってもらえるでしょうか?
わかってもらえているとして、この式をもう少し変形させます。

移項して

予測したいもの1 - 予測したいもの2 > 0

両辺-1を掛けて

予測したいもの2 - 予測したいもの1 < 0

となります。
つまり、

「選ばなかった他の合法手で進めた局面の価値」から「選んだ指し手で進めた局面の価値」を引いたものが0よりも小さくなるように学習すればいい、ということになります。
さらに、この式が最も都合のいい状態を考えます。
「選ばなかった他の合法手で進めた局面の価値」と「選んだ指し手で進めた局面の価値」の差が0よりも小さくなればまぁいいわけですが、どのくらい小さくなれば最も都合がいいでしょうか?
差が大きければ大きいほど「選ばなかった他の合法手で進めた局面の価値」と「選んだ指し手で進めた局面の価値」、つまり「プロ棋士が指さなかった手」と「プロ棋士が指した手」の価値を正確に識別できているような気がしませんか?

そこで上記式を下記のように書き換えます

-∞ ← 予測したいもの2 - 予測したいもの1

つまり、「選ばなかった他の合法手で進めた局面の価値」から「選んだ指し手で進めた局面の価値」を引いたものの差を-∞に近づけたい、というわけです。

さらに上記式を勾配法に都合のいいように、以下のように書き換えます。

sigmoid(-∞) ← sigmoid(予測したいもの2 - 予測したいもの1)

ここでsigmoid関数というものを使います。
この関数は中身は他のところで調べてもらって、性質だけをここでは説明します。
sigmoid関数というものは、-∞~∞の範囲のものを0~1までに変換してくれる便利な関数です。
さらに、微分が可能であるという勾配法に非常に都合がいい関数でもあります。
そうすると、sigmoid(-∞)というのは0になります。なので上記式は

0 ← sigmoid(予測したいもの2 - 予測したいもの1)

と書き換えられます。
さらに、sigmoid(予測したいもの2 - 予測したいもの1)の値が大きければ大きいほど評価値が間違っている、小さければ小さいほど評価値が正しい、といえます。
ということは、

Loss = sigmoid(予測したいもの2 - 予測したいもの1)
としたら学習できそうな気がしてきませんか?
これが今回の損失関数となります。

sigmoid関数をぐぐって調べてもらえばわかるのですが、sigmoid関数も微分した値の符号を逆転したものを加算していけば、どんどん最小値(0)に近づく関数になっています。
ですので、微分したものに学習率を掛けた値をどんどんパラメータに加算していけば、いつかはもっとも当てはまりのいいパラメータが求められるということになります。

上記は「選ばなかった他の合法手で進めた局面の価値」と「選んだ指し手で進めた局面の価値」を1組にして学習するので、ランキング学習の中でも

Pair Wise

と呼ばれる手法になります。
1組ごとに学習して賢くなっていく、という意味ですね。
ランキング学習には上記のPair Wise以外にPoint Wise、List Wiseと大きくわけて3種類あります。
これ以上ここでは詳しくは説明しませんが、ボナンザメソッドはPair WiseではなくList Wiseに近い方法をとっていると考えられます。

機械学習をコンピュータ将棋に適用するには?2

コンピュータ将棋に機械学習を適用する方法は上記ランキング学習の他にもうひとつの手法が考えられます。強化学習というものです。
強化学習というのは、普通の機械学習のように予測したいものがわかっているわけでもなく、予測したいものの優劣がわかってるわけでもないが、

「実際に数多くの試行をすることができる」

場合に適用できる手法です。

たとえば天気の予測であれば、1日ごとの天気予測を数万回、数億回やるのにいったい何年かかるんだろう?となってしまうので数多くの試行は実質的に不可能ですが、
コンピュータ将棋の場合、コンピュータ同士の対局は思考時間を短く設定すれば数万回、数億回の試行が可能です。

では具体的にどうやって学習するのか?
詳しい説明はGA将やひまわりのページに譲りますが、
ざっくり説明すると、対局した経験によってだんだん賢くなっていく学習方法です。
人間でも将棋をはじめたばかりのときに、まずルールだけ覚えてあとは何回か対局すればそれなりに将棋の勝ち方というものがわかってくると思います。
ただ、人間の場合は数億局もの対局が実質的に不可能だったりするので、実際の対局の経験だけではなく、本を読んだり、他人の研究結果を学んだりして強くなります。
しかし、コンピュータは数億局の対局が可能です。
ですので、コンピュータ自身がいろいろな指し手を試して、どの手が勝ちやすいかを蓄積していくということができます。
強化学習は理屈自体は非常に簡単な学習方法です。
コンピュータ同士で対局して、勝ったほうの指した手が優れている手、負けたほうの指した手が劣っている手として点数を累積していけば、極限的には最善手がもっとも高い点数になるじゃないか、という考え方です。
実装もそれほど難しくありませんが(詳しい実装はGA将やひまわりのページへ)教師あり学習に対して非常に時間がかかるという欠点があります。
しかし、強化学習手法のいくつかは極限的にはグローバルな最善手に収束することが数学的に証明されています。
つまり、数学的に神の1手が指せるようになることが保証されている手法です。
どうですか?夢があると思いませんか?

ちなみに〇×ゲーム程度であれば10分くらいの学習で神の1手が指せるようになります。
そんな手法が強化学習というものです。

sakuramaru7777
コンピュータ将棋ソフト「mEssiah」をつくってます。第29回世界コンピュータ選手権ではうさぴょん外伝の評価関数部を担当し、1次予選15位でした。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした