麻雀AI開発その42・数学的なお話その２
2017-07-28(Fri)
前回（麻雀AI開発その32・数学的なお話（実データから押し引き基準を決める関数を策定））の数学的なお話の続き。
検討ソフトの外形を作っている裏で、押し引きに関する実データを取っていました。取れたのは5000試合分で、目標10000試合にはちょっと届かないけれど、ひとまずこれだけのデータで解析をやってみます。
まずは、実データをシャンテン数と他家最大攻撃ごとに別のデータテーブルに振り分けます。
とりあえず今回着目したのは0シャンテンで他家1軒リーチの場合です。
この場合、全部で45488行のデータになりました。
前回のおさらいから。
入力値（再帰局収支x(14),牌危険度指数y(14),実際に切られた牌番号i）に対して、打牌選好力f(x,y)という関数を定義して、以下で示す対数尤度を最大化するｆ（x,y）のパラメータを決定するのが目的です。
前回は打牌選好力の性質から2次関数の形にするのがいいだろうというところまで議論が進みましたが、
これだと、対数の真数条件（f(x,y)が常に正の値）を満たすために不等号制約条件が必要になるので問題が難しくなります。
・常に正の値を取る関数
・できれば極端な値になるほど急激に値が大きくなる関数
という条件でなんとかならないか、と考えていたら、指数関数を使えばうまいこといくんじゃない？と思いつきました。
つまりは、こういうことです。
expのべき乗なので、どのようなx,yに対してもf(x,y)は確実に正の値です。
expの中身は1次関数にしてもよかったのですが、「極端な値になるほど急激に値が大きくなる」というのを表現したい（1次関数だと低攻撃力低危険度・高攻撃力高危険度・中攻撃力中危険度が同じような打牌選好力になりやすい。）ので、2次関数は維持しました。
これだと中途半端戦略な中攻撃力中危険度の牌の打牌選好力を落とすことができるのではないかと考えました。
h(x,y)、g_j(x,y)、g(x,y)を次のように定義しておくと、
最初の最大化したい関数は次のように変形できます。
第1項（実際に切られた牌iに関する項）はlogとexpが相殺して簡単に書けます。
第2項についてはexpの中にΣがあるので、簡単にばらすことはできません。
↑の関数をパラメータa,b,c,d,e,fの6変数関数と見た時（逆にx,y,iについては実データそのものを代入して計算する）に、最も値が大きくなるような(a,b,c,d,e,f)の組を求めます。
このような問題は一般的には最適化問題とか最小値（最大値）問題と呼ばれます。
最適化問題を解く解法として、準ニュートン法（BFGS公式）というものを使います。（理解するのが大変だった…。）
準ニュートン法について詳しくは各自で調べてください、ということにしておきます。（ここからはかなり説明を端折ります）
準ニュートン法を使うためには対数尤度をそれぞれのパラメータで偏微分した関数が必要になります。
例えばaで偏微分したものがこんな感じです。
そこまで難しい関数ではないです。
特に定数項のfで微分した場合、第2項の分子分母にg(x,y)が出て、約分できて、第1項と第2項が全く同じになるので恒等的に0になります。
つまりfはどんな値でも対数尤度に影響しない（実際、定数項のexp(f)を掛け算で外に出せて第1項と打ち消しあってくれる。）ということです。以降はf=0として、変数が6つから5つに減ります。
なお、この計算式をそのまま使うとg_j(x,y)の計算で大きい数字の指数演算を先にするので、計算機上で数値がオーバーフローします。
そのため、次のような工夫を施します。
・入力値はx,yとも±1000前後の値を取るので、数値の入力前にあらかじめ1000で割ってある程度数値を標準化（±1前後の値を取る）する。
・式の形的に指数の内部で定数項を抜き出すと、expとlogが打ち消しあって、抜き出した定数項の引き算が出てくる。
この性質を使ってg_{1}～g_{14}までの中で最も大となるものを定数項として引いて（これによりΣg_jは高々14までで、大半のケースで、2を超えることはない。）指数計算と対数計算を行い、最後に抜き出した定数項を足し算する。
こうした工夫をしたのち、BFGS公式に当てはめます。その結果がこちら。大体、計算終了まで1分くらいです。
上5行が動かすパラメータで、初期値は全部0からスタートして、そこの偏微分とヘッセ行列の逆行列の近似H_mから次の最小パラメータ組候補（2列目以降）を帰納的に求めていきます。
真ん中行が最大化すべき対数尤度の-1倍（最小値問題として扱っているサイトが多かったので、最大値問題を最小値に置き換えるため-1倍する。）。回数が増えるごとにどんどん値が小さくなっていき、最終的にある点に収束することが分かります。
（何度か別の初期値でやってみたけど、同じところに収束したのでたぶんだいじょうぶそう。）
下5行がそれぞれのパラメータで偏微分した値。最初のうちは±の値が大きめになっていますが、回数が増えるごとにだんだん0に近づいていく（その近傍で曲面が平らになっている）のが分かります。
というわけで無事に尤度が最大となる、パラメータの組(a,b,c,d,e)を求めることができました。
では、実際にこのパラメータと打牌選好力関数f(x,y)を使ってどの程度まともに判断を下すことができるかを見てみます。
攻めるなら打1m、守るのも打1mが有利（6pはリーチの現物だが、他の二人に通ってなくて、1mが3巡以内捨て牌の外側＆2枚+1枚カベ効果でかなり危険度が低い）です。
これくらい明らかに打1mのケースで、打1mの（他の牌との相対的な）打牌選好力は他の打牌候補の打牌選択力と比べて桁違いになっています。1mが切られる確率（1mの打牌選好力÷全打牌候補の打牌選好力の和）は99.2％ということです。
シミュレーションパートでこれを入れる場合、再帰局収支（上がりや聴牌を考える打牌については再帰パートですでに求められている。手牌を崩す場合はてきとうにマイナスの大きい再帰局収支、例えば-3000点とかにする。）と危険度指数（シミュレーションパートで毎順求める）について全打牌候補に対して計算し、そこで乱数を1回振って打牌を決める（この場合は99.2%の高確率で1mが選択される）、という手順になるかと思います。
現行の手順（総放銃率を計算して定数％より高いかどうかだけを見る）よりは時間がかかりそうです。
次の例。次順に6mを引いたところ。
攻めるなら打6mだが、両無筋で危険度がかなり高い。現物は4m・6pだがどちらも切ればほぼ上がりはない。中途半端戦略の打3mもある。
この場合は打6mが40%、打4mが35%、打6pが10%、打3mが6%という切られる確率になっています。
2次関数にしている効果か、最大限攻めの打6mと最大限降りの打4mが選ばれる確率がやや高いです。
実際にシミュレーションで出会ったらどっちを選択するかは乱数の機嫌しだいというところでしょうか。
最後の例。
3pが現物…のはずが、なんか反映されてないくさくて、危険度指数がやけに高くなってます。
これはAI側のバグっぽいので修正しておきましょう。（やっぱりテストは大事ですなぁ。）
仮に3pが現物でないとしたら現物はないので（なお赤5切りで7sの危険度が下がるのはAIの思考としてまだ入ってないです。）、最大限に攻める打6pの打牌選好力・切られ率が高いということです。
今回は自手聴牌・対1軒リーチですけど、他にも一向聴・二向聴と他家1～4副露・ドラポン・2軒リーチがあるので、21パターンのうちまだ1パターンしかやっていません。
すでに準ニュートン法のマクロは組めていて、データテーブルを変えてからマクロを起動して1分待つの×20回なので、まぁほどなくパラメータは求まるでしょう。
検討ソフトの外形を作っている裏で、押し引きに関する実データを取っていました。取れたのは5000試合分で、目標10000試合にはちょっと届かないけれど、ひとまずこれだけのデータで解析をやってみます。
まずは、実データをシャンテン数と他家最大攻撃ごとに別のデータテーブルに振り分けます。
とりあえず今回着目したのは0シャンテンで他家1軒リーチの場合です。
この場合、全部で45488行のデータになりました。
前回のおさらいから。
入力値（再帰局収支x(14),牌危険度指数y(14),実際に切られた牌番号i）に対して、打牌選好力f(x,y)という関数を定義して、以下で示す対数尤度を最大化するｆ（x,y）のパラメータを決定するのが目的です。
前回は打牌選好力の性質から2次関数の形にするのがいいだろうというところまで議論が進みましたが、
これだと、対数の真数条件（f(x,y)が常に正の値）を満たすために不等号制約条件が必要になるので問題が難しくなります。
・常に正の値を取る関数
・できれば極端な値になるほど急激に値が大きくなる関数
という条件でなんとかならないか、と考えていたら、指数関数を使えばうまいこといくんじゃない？と思いつきました。
つまりは、こういうことです。
expのべき乗なので、どのようなx,yに対してもf(x,y)は確実に正の値です。
expの中身は1次関数にしてもよかったのですが、「極端な値になるほど急激に値が大きくなる」というのを表現したい（1次関数だと低攻撃力低危険度・高攻撃力高危険度・中攻撃力中危険度が同じような打牌選好力になりやすい。）ので、2次関数は維持しました。
これだと中途半端戦略な中攻撃力中危険度の牌の打牌選好力を落とすことができるのではないかと考えました。
h(x,y)、g_j(x,y)、g(x,y)を次のように定義しておくと、
最初の最大化したい関数は次のように変形できます。
第1項（実際に切られた牌iに関する項）はlogとexpが相殺して簡単に書けます。
第2項についてはexpの中にΣがあるので、簡単にばらすことはできません。
↑の関数をパラメータa,b,c,d,e,fの6変数関数と見た時（逆にx,y,iについては実データそのものを代入して計算する）に、最も値が大きくなるような(a,b,c,d,e,f)の組を求めます。
このような問題は一般的には最適化問題とか最小値（最大値）問題と呼ばれます。
最適化問題を解く解法として、準ニュートン法（BFGS公式）というものを使います。（理解するのが大変だった…。）
準ニュートン法について詳しくは各自で調べてください、ということにしておきます。（ここからはかなり説明を端折ります）
準ニュートン法を使うためには対数尤度をそれぞれのパラメータで偏微分した関数が必要になります。
例えばaで偏微分したものがこんな感じです。
そこまで難しい関数ではないです。
特に定数項のfで微分した場合、第2項の分子分母にg(x,y)が出て、約分できて、第1項と第2項が全く同じになるので恒等的に0になります。
つまりfはどんな値でも対数尤度に影響しない（実際、定数項のexp(f)を掛け算で外に出せて第1項と打ち消しあってくれる。）ということです。以降はf=0として、変数が6つから5つに減ります。
なお、この計算式をそのまま使うとg_j(x,y)の計算で大きい数字の指数演算を先にするので、計算機上で数値がオーバーフローします。
そのため、次のような工夫を施します。
・入力値はx,yとも±1000前後の値を取るので、数値の入力前にあらかじめ1000で割ってある程度数値を標準化（±1前後の値を取る）する。
・式の形的に指数の内部で定数項を抜き出すと、expとlogが打ち消しあって、抜き出した定数項の引き算が出てくる。
この性質を使ってg_{1}～g_{14}までの中で最も大となるものを定数項として引いて（これによりΣg_jは高々14までで、大半のケースで、2を超えることはない。）指数計算と対数計算を行い、最後に抜き出した定数項を足し算する。
こうした工夫をしたのち、BFGS公式に当てはめます。その結果がこちら。大体、計算終了まで1分くらいです。
上5行が動かすパラメータで、初期値は全部0からスタートして、そこの偏微分とヘッセ行列の逆行列の近似H_mから次の最小パラメータ組候補（2列目以降）を帰納的に求めていきます。
真ん中行が最大化すべき対数尤度の-1倍（最小値問題として扱っているサイトが多かったので、最大値問題を最小値に置き換えるため-1倍する。）。回数が増えるごとにどんどん値が小さくなっていき、最終的にある点に収束することが分かります。
（何度か別の初期値でやってみたけど、同じところに収束したのでたぶんだいじょうぶそう。）
下5行がそれぞれのパラメータで偏微分した値。最初のうちは±の値が大きめになっていますが、回数が増えるごとにだんだん0に近づいていく（その近傍で曲面が平らになっている）のが分かります。
というわけで無事に尤度が最大となる、パラメータの組(a,b,c,d,e)を求めることができました。
では、実際にこのパラメータと打牌選好力関数f(x,y)を使ってどの程度まともに判断を下すことができるかを見てみます。
攻めるなら打1m、守るのも打1mが有利（6pはリーチの現物だが、他の二人に通ってなくて、1mが3巡以内捨て牌の外側＆2枚+1枚カベ効果でかなり危険度が低い）です。
これくらい明らかに打1mのケースで、打1mの（他の牌との相対的な）打牌選好力は他の打牌候補の打牌選択力と比べて桁違いになっています。1mが切られる確率（1mの打牌選好力÷全打牌候補の打牌選好力の和）は99.2％ということです。
シミュレーションパートでこれを入れる場合、再帰局収支（上がりや聴牌を考える打牌については再帰パートですでに求められている。手牌を崩す場合はてきとうにマイナスの大きい再帰局収支、例えば-3000点とかにする。）と危険度指数（シミュレーションパートで毎順求める）について全打牌候補に対して計算し、そこで乱数を1回振って打牌を決める（この場合は99.2%の高確率で1mが選択される）、という手順になるかと思います。
現行の手順（総放銃率を計算して定数％より高いかどうかだけを見る）よりは時間がかかりそうです。
次の例。次順に6mを引いたところ。
攻めるなら打6mだが、両無筋で危険度がかなり高い。現物は4m・6pだがどちらも切ればほぼ上がりはない。中途半端戦略の打3mもある。
この場合は打6mが40%、打4mが35%、打6pが10%、打3mが6%という切られる確率になっています。
2次関数にしている効果か、最大限攻めの打6mと最大限降りの打4mが選ばれる確率がやや高いです。
実際にシミュレーションで出会ったらどっちを選択するかは乱数の機嫌しだいというところでしょうか。
最後の例。
3pが現物…のはずが、なんか反映されてないくさくて、危険度指数がやけに高くなってます。
これはAI側のバグっぽいので修正しておきましょう。（やっぱりテストは大事ですなぁ。）
仮に3pが現物でないとしたら現物はないので（なお赤5切りで7sの危険度が下がるのはAIの思考としてまだ入ってないです。）、最大限に攻める打6pの打牌選好力・切られ率が高いということです。
今回は自手聴牌・対1軒リーチですけど、他にも一向聴・二向聴と他家1～4副露・ドラポン・2軒リーチがあるので、21パターンのうちまだ1パターンしかやっていません。
すでに準ニュートン法のマクロは組めていて、データテーブルを変えてからマクロを起動して1分待つの×20回なので、まぁほどなくパラメータは求まるでしょう。
スポンサーサイト
