*All archives* |  *Admin*

<<07  2017/08  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31  09>>
麻雀AI開発その49・手牌情報と評価値関数作りその3
評価値パラメータに関するプログラミングをしながら、またネットの情報を漁って数式をいじってると、なんか思ってたより簡単にできそうなことが判明しました。

入力する手牌1個x(xはInteger型配列orベクトル)とパラメータの群p_1~p_M(M≒数百クラス)に対して、評価値を次のように定義(というかモデル化)します。
170809-01.png
g_j(x)はjとxには依存するけど、pには依存しない関数とします。(例えば、シャンテン数ならg_1(x)=(6-手牌シャンテン数)など、どのjについても割と簡単な式で書ける。→1件あたり計算時間はそこまで多くない。)
つまり、fはpの一次式で書けるということです。

それで、損失関数(学習データとの不一致の度合い)として、
max(0,f(x_1)-f(x_0)) (ただし、x_0は実際に選択された手牌、x_1は選択可能だったが実際には選択されなかった手牌)
を当初使うつもりでいましたが、(つまり、実際に選択されなかった手牌の評価値の方が実際に選択された手牌の評価値より高くなる逆転現象が起きているときのみ、正の値を取る関数)
これよりもロジスティック損失関数なるものを使うといいらしいです。(常に正の値、逆転現象が起きてる時ほど大きくなる、微分可能)
つまり、これです。
170809-02.png
これは手牌1組分の損失関数なので、
全パターン(今回は最初の100試合分。N組あるとする。Nは10万前後くらい)の損失関数の積が最小となるようなパラメータ群pを求めます。
170809-03.png
最急降下法を使うために1個のパラメータp_jで損失関数の積を微分します。
170809-04.png
fはpについて1次式になっているので、かなり簡単な形に書けました。
もともとは微分することを想定していなくて損失関数の偏差分を取る必要があると思ってましたが、かなり計算の負荷が小さい関数(分母と分子のfのexp項は、jに依存しないので使い回せる、g_j(x)の計算はかなり簡単。)で偏微分を直接計算できて、とてもラッキーです。

なお、指数関数の計算がからむ関係でオーバーフローさせないために評価値fの計算直後に、100000で割っててきとうに標準化しておきます。このへんは評価値のスケーリングの問題なので大した問題ではないでしょう。

それで今計算した各パラメータごとの偏微分の値を使って初期値で置いたパラメータ群を次の式で更新します。(最急降下法)
170809-05.png
αは学習率(jに依存しないスカラー倍。とりあえず今回はα=0.1にしておいた。)

それでは、実践。
↓の初期パラメータ群が最急降下法1回の試行で、
hyoukatipara_shoki.txt
↓こう変わる。(前半部分が偏微分の値、後半部分が変更後パラメータ群)
hyoukatipara_newpara.txt
(なお、当初考えていた一次有効牌の枚数の項は逆に大きなマイナスになってしまって都合が悪くなったので削除しました。おそらく、手牌を崩してシャンテン数が上がる打牌をすると一次有効牌の枚数が多くなるところに原因がありそう。)
(鳴き可能ボーナスについては実装がめんどうだったので、入れなかった。個々の手役力のところである程度反映されるだろうから、まぁいいか、と。)

かかる時間
・元CSVファイルのリストを読み込んで内部変数に保存する…2~30秒
・手牌1組に対して評価値fと偏微分(M個分)を計算…1秒当たり数千組くらい。N≒100000くらいで全部で1分弱程度。
・パラメータの更新とかファイル書き込み…ほぼ0

思ったよりもかなり早くできそうです。
リストの内部変数保存は最初に1回必要なだけ(ただしO(N)の時間がかかる。)なので、
実質はfと偏微分の計算にかかる時間(こちらもO(N))だけで、最急降下法をどの程度繰り返せば損失関数が最小値に収束するかにもよりますが、理論的に破たんをきたすほどの時間がかかるわけではなさそうなので、ほっとしました。
収束が遅くて無理そうなら前みたいにBFGS法を頑張って適用してみてもいいですし。
ある程度収束したら試合数(つまりNの数)を増やして正確さを増やしていく感じになるでしょうか。
スポンサーサイト
プロフィール

nisi5028

Author:nisi5028
FC2ブログへようこそ!

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
FC2カウンター
フリーエリア
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード