*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>>
一人麻雀計算機その8・テストと改善その1
とりあえず(見た目だけは)完成した一人麻雀計算機をいろいろ走らせてテストとバグ取りをします。

まず使用した牌姿は
東1局西家7巡目
6p7p7p8p1s1s2s2s3s4s5s中中 ツモ7p ドラ西

傑作「何切る」300選のQ003です。
(ウザクさん、牌姿の利用を許可していただきありがとうございました。)

一向聴の手牌です。
打7pを選択したものとして、計算してみたところこんな感じの出力結果になりました。
(テンパイしたら常に立直するものとする。)
161103-02.png
内容はひとまず置いといて、計算結果が非常に時間がかかってしまいました。

左が手替わり0ですが、昨日やったのより早い巡目(7巡目)であるためか、昨日よりもっと遅くなりました。22秒です。これは辛すぎる…。

右の手替わり1に至っては322秒。さすがに5分はかかりすぎです。

というわけでなんとかして計算スピードを上げたいと思ったので、まずはどの部分で時間を食っているのかを分析しました。
それが上の画像の下の方の「処理時間(秒)」、以下の項目です。
時間のうちかなりの部分を「4:有効牌セット」の項目で使っていることが判明しました。
ここをさらに詳細に分けて調べてみると、どうやらシャンテンチェックにかかる時間が大半を占めることが分かりました。

というわけでシャンテンチェック関数のスピードアップ、もしくは呼び出す回数を減らすことを考えてみます。
書いたコードをぼーっと眺めてたり、デバッグで動かしたりしてると、毎回すべてのツモと(手替わりありの場合)切ることができる牌すべてに対して、毎回シャンテンチェックの呼び出しをしているように思いました。その中には前と全く同じ手牌が出てきたときにも同じ関数を呼び出しているケースもありました。

本体の再帰計算については、省力化のため、巡目&(13枚)手牌&一発フラグ&残り手替わり回数がすべて一致した場合は前回の計算結果をそのまま引っ張ってくる仕組みを取り入れていたのですが、それと同様の仕組みを有効牌の計算(大半はシャンテンチェック)にも取り入れようかと思いました。

本体の再帰計算では巡目&(13枚)手牌&一発フラグ&残り手替わり回数のすべてが一致したときに計算結果を記憶していましたが、シャンテン数と一次有効牌(シャンテンの進むツモ)については手牌以外の情報は関係ないので、一致させる条件は「現在の手牌が前回にも出現した」かどうかだけで済みます。
従前だと巡目が違っていればまた計算し直していた分が1回の計算で済むので、7巡目で残り10巡だからこの部分で計算時間が10分の1にカットされる計算になります。これはすばらしい。ただし、前回に記憶した手牌情報を検索する時間が別途かかるようになるので、簡単に10分の1になるわけではないですが。

これでやり直したところこんな感じに。(手替わり1回の出力値が変わってるのは他にバグ修正とかこまごまとした微修正が入ったためだと思います。)
161103-03.png
手替わり0回で0.387秒、手替わり1回で33.9秒と大幅にスピードアップしました。
これくらいなら実際に使用できるレベルまで来ましたね。すばらしいです。

詳細にかかった時間を分析してみると、シャンテンチェックにかかる時間(10番)が大幅に減っていますが、手替わり1回については3番の「記憶検索」の項目が14秒とそこそこの時間になっています。バグ修正により、再帰回数(本体の計算関数を呼び出した回数)が2倍に膨れたことが影響してるのだと思います。記憶してる配列変数の量が増えると計算の回数に加え、1回の検索にかかる時間も長くなるので、単純計算で2倍の2乗で4倍になってしまいます。まぁ本体を呼び出して再帰の段数が増えるよりはよっぽどこちらの方がましなので、この部分はしょうがないでしょう。

それで出来上がりにほくそ笑んでいていろんな牌姿を入力値にして遊んでいたのですが、
(例えば先ほどのQ003の例なら↓のような表をたくさん作って遊んでいました。本の通り、打8pが有利。)
161103-01.png
ここで耳より情報が飛び込んできました。
こちらのコメントです。


あらさんのサイトでシャンテン数計算の高速化方法が公開されていますがこちらは実装されておりますでしょうか。
http://mahjong.ara.black/etc/shanten/shanten8.htm


この情報は初耳でした。頭が悪くて、内容を理解するのにしばらくかかりましたが、骨子はこういうことだろうと思います。
1・手牌をパーツごとに区切ってパーツごとにメンツ数・メンツ候補数をカウントする。
2・区切ったパーツに対して、あらかじめメンツ数とメンツ候補数の情報を載せた計算用テーブルを用意し、関数呼び出し時にその情報を検索してメンツ数等の情報をゲットする。

1については頭の片隅にはちょっとだけあったのですが、直すのが面倒だと思ったので後回しにしていました。でも、確かに言われてみればスピードアップはできそうな感じはありますね。
従前だと14枚(or13枚)手牌からメンツを一個抜き出して、また再帰を呼び出して…、全パターン抜き終わったら今度は塔子・対子も全部抜いて…みたいなのだったので、再帰の段数が下がれば楽になりそう。いろいろ新しく変数を設定したり関数の戻り値とかをいじったりと大変そうだが。


2についてはすごいこと考え付くなーと非常に感心しました。私なら絶対思いつきません。これもやってみる価値はあるでしょう。

今日やったのは1についてです。
計算時間は減りそうだけど、コードの行数が非常に長くなった。
そして予定調和のごとく、バグが大量発生して大変だったなー。
出力値が「-4シャンテン」だったときには思わず苦笑が漏れる。

それでなんとか出来上がったのがこちらです。(エラーで途中終了もなく、出力値も従前の方法と全く同じ値になったので、おそらく同一のシャンテン数を返していると思われます。)
161103-04.png
大体、さっきより計算時間半減になってますねー。効果は大きいです。
なぜかあんまり関係ないはずの記憶検索の部分も減ってますが、まぁその辺は動かした時のPCの機嫌とかそんなところの違いでしょうか。

今度はむしろ記憶検索の方が時間を取っているようですね。2のハッシュテーブルも一応やってみますが、これ以上シャンテンチェックの時間が減るよりは記憶検索の方を次は計算時間を減らしたいところです。ただ、記憶検索についてはただ分量が多いだけで、中身はfor文1回をごり押ししてるだけなのでこれ以上どうしようもないような気はしますが。

どちらにしてもコメントをくださった方、ありがとうございました。非常に助かりました。
スポンサーサイト

コメントの投稿

Secret
(非公開コメント受付中)

コメント

プロフィール

nisi5028

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

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

この人とブロともになる

QRコード
QRコード