麻雀順位予想計算機のアルゴリズム

麻雀順位予想計算機のアルゴリズム
概要
この文書では、多クラスロジスティック回帰により、麻雀順位を予想する手法について解説
する。麻雀のルールについての説明は省略する。
1
アルゴリズム
以下ではプレーヤーを A,B,C,D としそれぞれ東１局の東家、南家、西家、北家とする。プレー
ヤーの点数はリーチ棒を除けば合計で 100000 点になるので、特徴ベクトル ϕ を


1.0


(A の点数 − B の点数)/10000

ϕ=
 (A の点数 − C の点数)/10000 


(A の点数 − D の点数)/10000
(1)
により定義する。また局については、各局ごとに独立に学習を行うのであって、特徴ベクトルには
含めない。したがって、以下では学習データ全てが特定の局（例えば南１局）のものと想定して議
論を進める。計算の目的は、与えられたベクトルから順位を予想することであり、その順位は上か
ら ABCD となるものから DCBA となるものまで 24 種類あるため、その種類ごとに 1 から 24 の
番号を割り振ることにする。n 番目の学習データの特徴ベクトルを ϕn とし、結果を表す 24 次元
ベクトル tn は
tnk

1 結果がk番目のクラスに属する場合。
=
0 それ以外
(2)
と定義し、学習データ全体を D = {tn , ϕn } と書くことにする。
確率推定モデルとしては wk を 4 次元ベクトルとし、96 次元ベクトル w = (w1 , · · · , w24 ) をパ
ラメータとする
f
∑k
j fj
pk
=
fk
= exp(wkT ϕ)
(3)
を用いる。
f
∑ nk
j fnj
pnk
=
fnk
= exp(wkT ϕn )
1
(4)
と書くことにすると、尤度関数 p と目的関数 E （負の対数尤度）は全データ数を N として
p(D) =
N ∏
K
∏
nk
ptnk
n=1 k=1
E
≡ − ln p(D) = −
N ∑
K
∑
tnk ln pnk
(5)
n=1 k=1
で与えられ、その微分（勾配ベクトル）と 2 階微分（ヘッセ行列）は
∂E
∂wl
=
∂E
∂wm ∂wl
=
N
∑
(pnl − tnl )ϕn
n=1
N
∑
(δml − pnm )pnl ϕn ϕTn
(6)
n=1
で与えられる。ここで δml は m = l のとき 1 でそれ以外で 0 と定義される。これにより、最急降
下法および、ニュートン法（この説明は省略する。）を用いることができる。
2
結果
実際の実装では、最急降下法は大域的に安定なアルゴリズムである一方収束が遅いこと、ニュー
トン法は収束が速い一方で不安定性があることから、最初の８ステップを最急降下法で行い、以降
をニュートン法で計算した。（実際最初からニュートン法だと安定しなかった。）最急降下法を用
いる場合、Ē ≡ E/N を用いた方が実用上やり易い。これは、データ数で割らない場合、勾配ベク
トルの大きさがデータ数に比例する形で大きくなり、最急降下法のステップパラメータをデータ数
に応じて変化させる必要が出てきてしまうためである。1 局あたりに用いたデータの数は 9000 で、
最急降下のステップパラメータは 1 とした（すなわち wnew = wold − ∇Eold ）。図１にあるように
おおよそ 16 ステップ程度で収束が得られた。図１は南１局のものであるが他の局も同様であった。
3
考察
おそらく、麻雀の順位予想を行うにあたりこの多クラスロジスティックモデルを用いるのは、最も
簡素でありながら最低限の特性を反映した方法であると考えられる。例えば、現状の順位が ABCD
であるならば、特徴ベクトルは 0 < ϕ2 < ϕ3 < ϕ4 となっているが、このとき、0 < wk=1,2 <
wk=1,3 < wk=1,4 とすれば、k = 1 クラス (着順 ABCD に対応）の確率を高くできるはずである。
実際にクラス k に関するパラメータの勾配ベクトルはおおよそ
N
∑
tnk ϕk
(7)
n=1
の方向を向いていることがわかる。計算のサイズとしても、個人のＰＣで最適化問題を解くのは１
００次元程度が無難と考えられる。
（ヘッセ行列を扱う数値計算は lapack を用いているが反復計算
をこれより大きいサイズで行うのは時間がかかってしまう。）
2
(a)
(b)
E 3.4
|▽E|0.6
3.2
0.5
-
-
0.4
3
0.3
2.8
0.2
2.6
2.4
0.1
0
2
4
6
8
10
12
14
0
0
16
step
2
4
6
8
10
12
14
16
step
図 1: 最適化プロセスの様子。(a) 対数尤度関数 (b) 勾配ベクトル。step = 8 でニュートン法へ切
り替えている。
また、データ数を変えたときの最終的な負の尤度の値 Ē(D) と、学習したパラメータを用いて計
算した他のデータでの負の尤度 Ē(D′ ) を図２に載せる。Ē(D′ ) の計算ではデータ数を 9000 に固定
してある。データを増やすことで過学習が抑制され (Ē(D) が増加する)、予想機としての精度が上
がっていることが確かめられる (Ē(D′ ) が減少する)。ここまでのデータは全て南１局のものである
が、このアルゴリズムは他の局にも適用可能で、その結果を図 2(b) に載せる。局が進むほど、確
率予想の精度があがるという妥当な結果が得られている。
3
(a)
(b)
-
E(D')
E 2.54
E(D')
2.5
2.46
3
E(D)
2
2.42
2.38
1000
3000
5000
7000
9000
2
N
3
4
5
6
7
8
局
図 2: (a) データ数を変えたときの最終的な負の尤度 Ē(D) および学習したパラメータを用いて計
算した他のデータでの負の尤度 Ē(D′ )。(b) 東２局から南４局までの得られた Ē(D′ ) の値。
4

Download Report