*All archives* |  *Admin*

<<04  2017/05  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  06>>
floodgate for mahjong へ参戦その15・シミュレーションパートの導入(自分他家とも鳴き無し)
前回に引き続き、麻雀AIの話です。

再帰計算(鳴き無し・他家和了考慮なし)で最適打を出すところまで前回できたので、今回からは他家和了や点棒状況を考慮するために、シミュレーションパートの作成に入ります。

今回できたのは、
・自分のツモ牌と打牌と和了・立直判定(再帰パートで計算した最適打に従って打牌する。)
・自分の打牌に対して他家聴牌者のロン和了(自分から見れば放銃)判定
・他家ツモ牌と打牌と和了・立直判定(乱数とパラメータ表から算出。)
・他家打牌に対して、自分のロン和了判定と他家聴牌者のロン和了(自分から見れば横移動)判定
です。

前の計算機だとグローバル変数で全部書いてたのを、機能ごとにパーツでばらすためにローカル変数に置き換える作業と、
配列操作メインで変数を扱っていたのをビット演算で高速計算するために、Long型(の組)の変数で全部書き換える作業がメインでした。


それで、バグを取りつつテストをしてみたところ、計算時間が遅いことこの上なかったです。
各打牌候補に対してシミュレーション回数は1万回でやったのですが、1打牌候補につき5秒くらいかかっていました。
実戦譜を読み込ませて、各プレイヤーのツモ番ごとにAIの評価値を出していく工程で、1局10~20分かかったのでこれはつらいです。
まだ、まともな動きをするかどうかの確認をしている段階で、現時点では高速化についてはあまり考えていないのですが、変数はほぼLong型の組に置き換え済みだからこれ以上短縮ってどうすればいいのか…と途方に暮れています。
今回は自分と相手4人分の情報を詰める必要があるので、どうしてもプレイヤーごとの情報は配列にせざるを得ません(Cloneメソッドで時間を食うと思われる)。

一番手っ取り早いのはシミュレーション回数を減らすことです。1万回を1000回に減らせば計算時間はほぼ10分の1なので、かなり待ち時間は少なく感じると思います。
ただ、こうするとばらつきが激しくなって正確性が減るので、これは最終手段として取っておきたいです。
(ただし、ばらつきが激しくなることはAIが同一局面で同じ打牌を返すとは限らない、という乱数の余地が入ることで人間側からすれば読みにくくなるということにもつながるので、完全なデメリットとは言い難い側面はあるかもしれない。実際にAIが打つ時は少ないシミュレーション回数、検討モードのときは多いシミュレーション回数と使い分けることも可能かも?)

次に考えるのは、全部の打牌候補に対して計算するのではなく、再帰パートで明らかに劣っている初手打牌は計算から除外する、というもの。他家無視の段階で一番いい打牌と二番目にいい打牌、もしくは他家攻撃に対してベタ降り(最も安全な牌を切る)との決選投票みたいに考えるとか。これはかなり有力です。

そういう小手先のテクニックに頼るのもまぁやむを得ないのですが、できれば基礎体力的な部分でより高速に計算できるに越したことはないです。
とりあえず他家の鳴きまで考慮したものを作った段階で考え得る限りの高速化のギミックを詰め込んで、
そのうえで、パーツごとに計算にかかった時間を測定しながらボトルネックになってるところを改善する、みたいな方針で頑張って作っていきたいと思います。
スポンサーサイト
floodgate for mahjong へ参戦その14・計算時間短縮その3
今日も引き続き処理速度向上の話です。

今回やったのは捨て牌と現物筋をLong型(のペア)で表すことを主にやりました。
だんだんビット演算も慣れてきました。
とにかく配列やListを嫌って、ビット演算で計算できるLong型(及びその派生構造体)に置き換えまくります。
どうしても配列で処理しないといけないところ(出る率・ツモ率・局収支や和了率等結果の仮置き変数)以外は全部置き換えが終わりました。

最終的に2233556678p5667sの手牌(1巡目)に対してかかった時間が6秒まで縮めることができました。
これでも今後のことを考えると不安ですけど、もう改善のネタが尽きました。
現状はこのあたりで許してもらうことにしましょう。
実際は巡目が深くなればループの段数が下がるし、今回みたいな複雑な牌姿(まず初手の候補手自体が多い)はそんなにないと思うので、これよりは計算時間が短いケースが多いでしょう。

もうそろそろ次の段階に移ろうかと思います。
次は鳴き考慮かシミュレーションパートの構築かどちらを先にやろうかと考えてましたが、
実戦投入(いつもツイッターの出題)をできるだけ早くやりたいので、シミュレーションパートの構築からやることにします。
鳴ける手牌は後回しになるけど、それよりかは他家の挙動とかを正確に反映したものとついでに点棒状況判断も考慮したものをしっかり土台を作っておいた方がいいかなーと。

シミュレーションパートのロジックはだいたい前に作った四麻計算機(バグが残ってるままお蔵入りになってるやつ)を参考にしながら頑張って作っていきます。
ひとつ問題があるのが、他家の攻撃に対してどの程度押すか、というパラメータは事前に何らかの形で決定しておく必要があるということです。
とりあえず勝手がいまいちわからんので、最初はてきとうにしておくか。(例えば他家無視局収支と瞬間の危険度だけを見るmanue
方式局収支が一定以上なら押すとか。)
できてからfloodgate for mahjongに流してみて押し引きの一定値をどこに置いたらよさげかを測ってみる、みたいなのが必要になるでしょうか。
ただ、明らかな差がつくような多数試合ができるようなプログラムと時間ができるのかどうかはけっこうあやしいですが。
それか鳳凰卓の実戦譜をAIに計算させて、実際のプレイヤーが押し引きのラインをどこに置いてるのかを見て学習する、みたいなプチディープラーニング的なことをやった方が可能性はあるかもしれない。

まぁ、御託を述べる前にそれっぽいシミュレーションパートを作る(もう最悪全ツでもいい)ことから始めましょう。
floodgate for mahjong へ参戦その13・計算時間短縮その2
前回に引き続き、AIの処理速度改善の話です。

やったこと
・内部変数のうち副露以外手牌、副露手牌、見えてる枚数、有効牌について、Integer型配列で扱っていたのをLong型(もしくはビット数の都合で、Long型2個組の構造体)に変更
・引数の型が変わったので、それに合わせて関数の中身も変更
・関数のうち、シャンテン計算関数と和了処理関数のアルゴリズムを速度改善の方向に抜本的に見直し
・変えた部分のテストとバグ潰し

設計思想として、
・なるべく加算減算とビット演算のみで処理を行う。
・乗算はなるべく使わない。(Modでの剰余計算なんてもってのほか。)
・配列をなるべく使わない。(初期化とか参照に時間がかかると思ったので。後は参照型配列のクローン作製の処理にも時間がかかるので、構造体の値型で、数値コピーにかかる手間を省く。)
・コードの長さは長くなってもいいけど、ループとか分岐で判定する回数をなるべく減らす。(分岐判定や乗算剰余の使用の回避を優先する。)
・可読性や保守はしにくい(Long型変数から手牌とか枚数の形が瞬時に判断しにくい)けど、速度優先。
という考え方でやっています。

かなり全面的な改訂になったので疲れました。
けれど、それに見合った成果はでました。

前回と同じ手牌をAIにかけてみると、
170521-01.png

パーツごとの途中経過時間も測定するタイプで、全部で16秒。
さらに、途中経過時間を呼び出す関数(Timegettime関数)でけっこう時間を食ってることが判明したので、
その部分をカットしたタイプだと、9秒まで時間を減らすことができました。
これくらいだとまぁなんとか実戦には耐えることができそうな感じです。
ここから鳴き判断とか他家和了考慮のシミュレーションパートとかも入れたらまた増えるんでしょうけど。

パーツごとの時間を見る限りは明らかにボトルネック的になってる箇所はなくて、ある程度分散しているのが分かります。
まだ改善できてないところ(捨て牌とか現物・筋の変数とかがまだListや配列のまま)も残っているので、それを見直したらまた早くなるかもしれませんが、今のところはそれ以外でここを良くしたら劇的に速度改善する、というところはないですね。
とりあえず改善のネタが尽きてからまた考えることにしましょう。
floodgate for mahjong へ参戦その12・計算時間短縮その1
floodgate for mahjong へ参戦その11・スタックオーバーフロー撃退
前回の続き。

今回は計算時間的にネックになってる部分のうち和了処理(5番)の計算時間を短縮させました。
170516-01.png

なんとか5秒くらい縮めるのに成功しました。

まず最初は和了ハン数符数の記憶検索のキーをString型からもっと短時間で計算できる型にしてみました。
昨日調べてると、BigInteger型なる、扱える数字の上限がないという夢のような整数型を見つけて、これすごくいいんじゃない?
と思ったけど、実際使ってみるとビットシフト演算するにしても検索のキーにするにしてもちょっと遅かったです。String型と五十歩百歩的な。

次の案で、副露以外手牌は51ビットでLong型で扱える、
晒し部分は鳴いた牌が37種類(7ビット)、鳴きの種類(チーが下2枚・カンチャン・上2枚と赤含みかどうかで6種、ポンが赤含みかどうかで2種、カンが暗槓と明槓で2種の計10種、4ビット)の副露数最大4で11×4=44ビット
と上がり牌37種類が7ビットと偶発役で5ビットなので、44+7+5=56ビットでこっちもぎりぎりLong型で扱える、
この2情報を構造体にまとめてビットシフトと検索のキーとして使います。
最初はこれも遅かったのですが、GetHashcodeなるものを使うと検索が効率的になるらしく、なんかスピードアップしました。

検索キーの問題はこれで済んだのですが、まだ和了処理全体があまり早くなりませんでした。
そこで、さらに小分けにしてネックになってるところを調べていると、
前回に出てきた牌姿についても、見えてる枚数とか巡目とかを参照して毎回裏ドラ計算してるところが遅かったみたいでした。
和了のたびに前の使いまわしができずにツモ率計算とかdouble型の乗算とかやってたので、そりゃぁ遅いわけです。

さすがにこのままだとやってられないので、裏ドラ計算のところを手抜き(単純に(4-手牌枚数)÷122をツモ率にした)して、記憶情報の中に上がり打点も盛り込みました。

すると、5番でかかった時間が1秒ちょっとに減りました。
これでもまだ長いのですが、なんとか最大のネックは解消できました。

さて、次に手を付けるのは12番の他家切られ率と16番その他のInteger型配列軍団の整理ですなぁ。
こっちはさらに影響範囲が全範囲に及ぶのでたいへんです。
floodgate for mahjong へ参戦その11・スタックオーバーフロー撃退
ここのところ集中してAI製作の作業をやってました。
頑張った結果ちょっと前進しました。

やったこと
・スタックオーバーフロー対策で、再帰関数を使わず自前のスタック管理をするためにコード全体を大幅改変。
・他家からのロン和了を考慮するコードをそれに合わせて書く。
・それに対するバグ大量発生のお祭りを収束させる。なんとかそれっぽい数値は出てきた。

テストの風景はこんな感じ。
入力手牌は"2p2p3p3p5p5p6p6p7p8p5s6s6s7s"で(ウザク本Q18より)、
(捨て牌を適当に設定するのがめんどうだったので)親の1巡目。
170515-05.png
他家からのロンを込みでの一人麻雀の再帰計算だと本の解答通り打8pが最も局収支がいいとAIは返してきました。

途中でエラーで途中終了することも和了率800%局収支8万とかいう意味不明な結果を返すこともなく、順当な結果になってくれました。
毎度のことながらバグ取り大変だった…。参照型の配列に対して値を代入することで他のところの数値も変わっちゃうみたいなバグとか。

ただですねぇ、結果が出るまですげー時間がかかるのです。
170515-04.png
最初は45秒とかかかってたのですが、ちょこちょこと涙ぐましい節約の努力をして(ほとんど時間の短縮にならなかった改良も多かったですが、)34秒まで短縮しました。
30秒とか40秒って…。打牌候補が多くて複雑な牌姿とはいえ、一打で何十秒も食ってたら試合にならんですぞ。

パーツごとにばらして計算時間を測定すると、ボトルネックになってるところが複数個所にばらけてるので、一筋縄ではいかなさそうです。

処理時間が長いところから順番に、

・5…和了処理
この部分だけstring型を使用しているので一番遅くなっています。
手牌のうち副露部分と和了牌の情報を加えた文字列で、和了点数の記憶情報にアクセスしてる分です。
和了牌はともかく、副露部分についてもうまいこと(できればビット演算で)長整数型とかに変換して、
副露以外手牌のLong型と副露部分のLong型の組を構造体(orクラス)で宣言して…とか。
うまい変換関数を作る必要があります。

・12…他家から出る率計算
立直者情報とか見えてる切れてる枚数とかカベ効果等などが複数の関数を組み込んでいるので、ここが時間を食ってしまうのはしょうがない…、と諦めてしまっては他のところでいくら節約しようとどうしようもないので頑張らないといけないです。
ここに限らず、Integer型配列でごまかしてるところが多いので、これもうまいことビット演算で長整数型にして、関数を一から作り直しにするとか。
とりあえず広範囲の見直しでしんどいことだけはわかった。

・16…分岐後諸計算
各打牌候補について手牌を1枚減らして、捨て牌に1枚加えて、みたいな変数(だいたいInteger型配列)への代入とか複製とかでなんかよくわからんけどつもりつもって4秒とか食っていやがる。
おそらく、再帰を使わない→参照型のInteger型配列を直接操作する→連動することがないように複製(clone)を逐一用意する、のところで時間を食ってると思われる。
cloneにしたせいで時間がかかるっぽいし、かといって同じ処理をループで回すのももっと時間がかかって論外だし、直代入だと連動バグが発生するし。
この件もあるからあらゆるInteger型配列をLong型変換しないといけないとか。
参照型、嫌い。もはやトラウマです。
7と11も同じく。

・10…先頭ハッシュ関数計算
巡目とリーチ等状態と残り手替わり回数から加算乗算でハッシュ値を計算しているパート。
整数型の乗算ならいけるだろうとたかをくくっていたら、呼び出される回数が多いせいか、けっこう時間を食ってる。
これもビット演算に置き換えるか…。

一難去ってまた一難ですなぁ。
プロフィール

nisi5028

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

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

この人とブロともになる

QRコード
QRコード