*All archives* |  *Admin*

<<09  2017/10  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  11>>
一人麻雀計算機その9・テストと改善その2
今日の成果はこちら。

更新履歴
2016年11月4日 ver1.03
計算時間をさらに圧縮。(記憶探索を同一巡目のもののみを探索するように変更。)
天鳳方式の牌の入力方式に対応
和了時一発割合の出力値を追加
高速シャンテンチェック関数について、1面子2塔子と0面子4塔子の両方が取れるとき(13578899mなど)に誤って後者を優先させていたバグを修正。
シャンテンチェック関数をハッシュテーブルから検索する方式を追加。

2016年11月3日 ver1.02
計算時間をさらに圧縮。(シャンテンチェックでパーツごとに切り分けてからメンツ数・メンツ候補数を数える方式に変更。)
シャンテンチェックの関数を従前のものと今回のパーツ切り分けバージョンの2つから選択可能に。

2016年11月3日 ver1.01
計算をバックグラウンドで行うように変更
手牌情報の出力について1m,2m,…,8m,9m,5M,1p,…の順から1m,2m,3m,4m,5m,5M,6m,7m,…の順に変更
一向聴以上の手替わり時、一発が消えていたバグを修正
計算が正常に終了した時に自動でテキスト出力する機能を追加
計算時間を大幅に圧縮。(一度計算した手牌の有効牌を記憶して呼び出す方式に変更。)

2016年11月2日 ver1.00
一人麻雀計算を実装

2016年10月29日 ver0.5
初回公開
シャンテンチェック、有効牌の計算、和了時のメンツ切り分け、役判定、得点計算を実装


割と地味ですが、確かな品質向上です。
主な修正は3つ。

1個目は一向聴で手替わり1回のとき10秒くらい時間を取っていた記憶検索について。
今までは巡目&手牌情報&一発フラグ&残り手替わり回数の文字列を結合したやつを単純にかたっぱしから記憶していって、先頭から順に検索するのではなく、
巡目でラベル付けして、1~18個の文字列リストの配列を新たに作り、
巡目でグループ分けして、手牌情報&一発フラグ&残り手替わり回数だけをリストたちに次々放り込む手法を取ってみました。
これなら関係ない巡目の情報は検索しないで済むので、処理時間が短くなると思われます。
後でいろいろ調べていて気づいたのですが、これってハッシュ法の思想そのままでしたね。昨日は「自分では絶対思いつかない」と言っておきながら、あっさり前言が覆されるという。
これによって記憶検索が1秒ちょっとと、計算時間が10分の1に近い短縮率になりました。とてもいい結果です。

2個目が天鳳方式の牌の入力方式に対応したという点。
今までは数牌なら2文字、字牌なら漢字1文字をそれぞれ対応させて、入力した手牌情報の文字列を先頭から順に読んでいく独自の文法(基本的には東風荘のmjscore形式)を使っていましたが、天鳳の牌理ツールの表現方法との対応があった方がいいのでは?的なツイートが流れてきたので、そちらもできるようにしました。
天鳳の牌理ツールの文法が独自方式と異なる点は
・赤5に対応する数字が「0」
・字牌は「z」の文字を使う。
・同色の牌が並んでいるときは先に出てきている牌の色情報を省略できる。(1m2m3m→123m)
このへんはDo文と文字列操作の組み合わせで何とかなりました。
副露手の記述方法は従前と同様(チーポン明槓が「;」、暗槓が「;;」)としています。
担当しているチェックボックスのチェックのオンオフが切り替わった時にすでに入力済み情報を両方式に相互に変換して表示する機能もついでにつけています。
ちょっと動かしてみましたが特に天鳳方式と従前方式では計算速度はそんなに変わらないっぽい(もちろん計算結果は同一。)ので、それなら天鳳方式の方が色情報が省略できるとか、いちいち日本語入力に切り替えずに入力できるという点で優れているような気がします。

3つ目が昨日出てきてた、シャンテン数を計算する関数にハッシュテーブルを取り入れて検索することです。
これはいろいろなパターンのパーツ構成に対してあらかじめメンツ数とメンツ候補数を計算しておき、テーブルに仕込んでおくことで、シャンテン数を計算する再帰式を呼び出すのを極力回避するのが骨子の1点目。
2点目は単純に全パターンをリストにすると量が膨大で検索する時間がかかってしまうので、ハッシュ値というパーツ構成情報の一部みたいなものごとにグループ分けして、そのグループごとにリストを管理して検索時間を減らそう、という思想です。
さっきやった記憶検索のときと似ていますね。

シャンテン数を計算する関数の前半はパーツごとに区切る作業からやります。
パーツとは同色の牌のうち、±2以内の距離にある牌の塊のことです。例えば135899mなら135mが1個の塊で、5と8は3だけ距離が離れていて、シャンテン数を計算する上では相互に関係することがないので、別の塊扱いで899mが塊2つ目です。
次に135mと357mでは数字は違いますが、シャンテン数を計算する上では同等です。(0面子1塔子。)
なので、数字については区別をせず、塊の先頭の牌から手持ちの枚数をサイズ9の配列に順に放り込んでいきます。
各塊ごとにサイズ9配列を計算していって、次のメンツ切り分け関数へこの配列を引数として渡すわけです。

メンツ切り分け関数はサイズ9配列を引数として、メンツ数とメンツ候補数の組を返す関数です。
なので、サイズ9配列に対応する2変数の組をあらかじめ計算しておいて、ハッシュテーブルとして保存しておけば、
引数として渡されたサイズ9配列の内容を検索して、ヒットしたら即座にメンツ数とメンツ候補数の組がわかるというわけです。再帰式は使わないのでスピードが増すであろうと。

ただし、http://ara.moo.jp/mjhmr/shanten.htmにあるように、全パターンを登録するとリストの要素数が多すぎて、検索時間がかかってかえって効率が悪くなる可能性があります。
なので、あらさんの教えに従い、合計枚数が8枚以下のパーツのみを計算してテーブル化しておきました。

実際に作った(計算したのは全部プログラムがですが。)のがこんな感じの表です。

1
00 0000000
01 1000000
01 1010000
02 1010100
02 1010101
03 1010102

21 1041100
12 1042000
01 1100000
02 1101000

12 4200000
12 4201000
20 4210000
21 4300000

2
01 0000000
01 1000000
02 1010000
02 1010100
03 1010101

18
11 0000000
12 0100000
12 0101000
12 0110000
12 0200000
20 1000000
20 1010000
21 1100000
21 2000000

19
20 0000000
21 0100000
21 1000000

20
21 0000000

各区分ごとの冒頭にある1~20の数値はハッシュキーで、(塊の先頭の数字の手持ち枚数)+4×(2番目の数字の手持ち枚数)です。サイズ9配列のうち先頭の2つをとってきたものです。この計算式ならば1種類の最大枚数が4枚なので、1,2枚目の枚数が違うならば異なるハッシュ値を返してくれます。(もちろん同じ枚数なら同じハッシュ値。)
各行は「xy zzzzzzz」という形式になっていますが、xがメンツ数、yがメンツ候補数、zが配列の後半7つの手持ち枚数です。
例えば、ハッシュキーが1の「21 1041100」なら先頭が1枚で2番目が0枚(1+4×0=1)なので、1010411の並び、つまり13555567mみたいな形です。この形は13mが1メンツ候補、555mが1メンツ、567mが2メンツの計2面子1メンツ候補ですが、行の先頭を見てみると確かに「21」となっているのがわかります。

ハッシュテーブルの作成のコードはこんな感じ。
table_sakusei.txt
テーブルの総行数は2587行とそこそこです。
これをハッシュキーで20個に振り分けていくので、単純計算だと平均で2587÷20で130個の要素数があるリストを検索することになります。
なお、塊の総枚数が9枚以上のパーツはハッシュテーブルに載っていないので、従来通り再帰式で計算をしています。

それで今日いろいろ作って計算時間を出したのがこちら。
161104-01.png
一番左がハッシュテーブルなしで手替わり0、中央がハッシュテーブルなしで手替わり1、一番右はハッシュテーブルを用いた手替わり1回です。

いろいろ妙手順を尽くして合計6秒まで短縮することができました。最初は集計に5分かかってたものがここまで短くなったのですから感動ものですね。経過時間の中身は大半が記憶情報の検索時間で、ハッシュ値も用いて高速化しているので、さすがにこれ以上は厳しいですかね…。

後、思いつくのはこれくらいです。
テーブルを見ると出現頻度が低いと思われる、4枚使いのパターンも入っていて、こういうのを後ろに回す一方、
一度計算して出現頻度が高そうなパターンを前方に持ってくることでハッシュテーブル検索を効率的に行うみたいな。(あらさんのサイトに同様の記述があります。)
また、リストに載ってない9枚以上パターンについても一回計算したものはテーブルに載せておくみたいな。
さらにリストが多くなってきて効率が悪くなって来たら、ある程度から後ろはテーブルからばっさりカットしちゃうとか。

プログラムが自分で学習してテーブルを再生成するようなイメージですね。

もしくはハッシュ関数の取り方をもうちょっと工夫してみるとか。(再ハッシュも視野に入れる。)

とまぁ、専門的な話でハッスルするのはこのあたりにしておきましょうか。


また別の話ですが、ソフトの公開方法をどうしようか悩み中です。

ソフトをばんばん公開して、みなさんに使っていただいて世に広める、というのもまぁそれはそれでいいのですが、
これを作るのに相当苦労してるので、その苦労の成果をタダで大盤振る舞いして、研究の中身が安く見られるのはちょっと気分的に嫌だなーいうのもあります。
前に公開した得点計算と有効牌だけ計算するツール(ver0.5)はまぁ成果としては大したことないのでいいのですが。

そのへんのさじ加減を考え中です。
一つ考えているのは
・親交のある方には無償でフルバージョンを配る。
・一般の方には機能を制限した体験版みたいなのを公開する。
・体験版じゃなくてフルバージョンが欲しいみたいな人にはシェアウェア的ななにかか、フリーソフト(寄付歓迎)とかでそのへんは適度に。
くらいの案。

すでに作ってある局収支シミュレータの最新版を一般公開せずに出し惜しみしてるのもまぁ、そういう気持ち面が要因のひとつです。
今レベルだとお金取れるレベルではないような気はしますが(あらさんのものと同程度かそれより下の部類なので。)、
これが4人麻雀への拡張までフリーソフトでやってしまうとさすがにフリーでは研究を大安売りしすぎじゃない?みたいな気はします。
そのへんの感覚とか相場観みたいなのはよくわからないですが、どんなもんなんでしょうね。
スポンサーサイト

コメントの投稿

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

コメント

No title
ハッシュを探索する時間に悩まれているようですが、
1-9の数牌が0枚から4枚の組み合わせの全パターン(=5^9=1953125パターン)を9桁の5進数と考えて面子、ターツ数を順番に配列に入れておけば、
新たに面子、ターツ数を求めたいパターンから5進数に変換する計算コストだけで答えが得られるようになります。
プロフィール

nisi5028

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

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

この人とブロともになる

QRコード
QRコード