*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>>
一人麻雀計算機その5・聴牌かつ手替わりなしの計算
前回までで、有効牌の計算と和了時の得点計算という基礎的なところまでは終わったので、
いよいよ本題の一人麻雀の計算に入ります。

まずは一番簡単な聴牌かつ手替わりなしの場合。
上がり牌を引いたら和了して得点を計算、
上がり牌を引けなかったら次順に移る、
東家南家の18巡目と西家北家17巡目なら流局として得点を計算(今のところ他家聴牌者は一人と固定して計算する)、
という単純なプログラム、
…と言いたいところですが、かなり作るのに苦労しました。

「次順に移る」というところが曲者です。
例えば16巡目の期待値は
(17巡目に上がり牌を引く確率)*(上がった時の得点)+(17巡目に上がり牌を引けない確率)*(17巡目の期待値)

このままでは(17巡目の期待値)が分からないので、続いて
(17巡目の期待値)=(18巡目に上がり牌を引く確率)*(上がった時の得点)+(18巡目に上がり牌を引けない確率)*(18巡目の期待値)
(18巡目の期待値)=(流局時収入)

といった具合に再帰的に関数を呼び出す必要があります。
(実際は1mを引く確率、1m引いたときの期待値、みたいに毎順37個の足し算をします。)

もしくはいつもの局収支シミュレータみたいに、乱数を与えて最後の局結果を見る、という作業をn回繰り返して平均値を取る、モンテカルロシミュレーションにするかのどちらかです。

どちらにしても(上がり牌を引く確率)が必要になるので、前に取ったこちらのデータをパラメータとして採用します。
見えてる枚数別手持ち枚数別ツモ率
今は他家の挙動がないので、前半の手持ち枚数別ツモ率の数値です。
ドラ表示牌については自分の手にあるものと同等としてパラメータを参照します。(例えば、ドラ表示牌1mで自分1m対子持ちなら「3枚持ち」の数値を参照する。)
ただし、これをそのまま適用すると手牌にある牌次第ですべての牌のツモ率の合計がちょうど1にならないという問題が出てくるので、合計が1になるような調整(すべての牌のツモ率について、合計ツモ率で割る)を行います。

最初はモンテカルロシミュレーションで作ってみたのですが、毎順処理時間がかかるシャンテンチェックの関数を呼び出すためか
、1000局やるのに40秒という時間ばかりかかる残念なプログラムになってしまいました。
これだと10万局なら4000秒≒1時間もかかってしまいます。たった1局面を判別するだけでこれです。
とてもじゃないけどこのままではやってられないです。
できればモンテカルロ方式にして、4人麻雀への応用がしたかったけど、手替わりなし・聴牌でこの状態なのでしょうがないですね。

というわけで、再帰的に関数を呼び出す、従来の計算方式で作り直してみました。

手探りでいじっていったらやはりというかバグが出まくってものすごく苦労しました。

まず最初に作ってみたのがこちら。
161030-01.png
18巡目は流局時収入1500点そのままです。

17巡目は関数を再帰的に呼び出した回数が35回。
上がり牌以外の35種類の牌を引いたときに、18巡目の期待値を求めるために同じ関数を呼び出すので35回です。

16巡目は関数を再帰的に呼び出した回数が1260回。
17巡目に上がり牌を引けなかった35種類に対して、また17巡目の期待値を求めるために35回関数を呼び出すので1260回。
…なんか嫌な予感がしてきました。

15巡目。44135回。

14巡目。1544760回。
ここでギブアップ。14巡目を求めるのに3~4分も時間がかかったのでもう無理です。

今のままだと残り順目が多いと指数関数的に計算時間が増えてしまうようです。
これではモンテカルロ式以上に無理です。


というわけで、ない知恵絞って工夫してみました。

デバッグで中身の変数の推移を眺めていると、大半が同じような計算をやってることに気付きました。
同じ巡目、同じ手牌なら(乱数を使わない計算なので)同一の結果を返すので、
一度計算した巡目と手牌を記憶しておいて、同じ局面が再び現れた場合はそのとき計算済みの期待値を返す、
というような仕組みに変えました。
これなら関数を再帰的に呼び出す回数は少なくなりそうです。

これで作り直してみたところこんな感じになりました。
161030-02.png

今回は手替わりなしなので、記憶する情報のうち変わるのは現在巡目と(立直時)一発フラグだけです。
一番下の再帰回数を見ると差は歴然です。
6巡目でも385回です。1回計算したものは記憶しておけるので、ほぼ35×(18-6)回の呼び出し回数で済んでいます。

とはいえ、いいことばかりではありません。弊害もあります。
今のところ出ている問題は、
・自分がこの後捨てる牌については記憶することができない。
ということです。
記憶情報に捨て牌まで含んでしまうと、同一局面がこの先現れることはまずないため、処理時間の圧縮効果がなくなってしまうからです。
なので、一度捨てた牌の枚数が減ってツモ率が下がる(それにより他の牌のツモ率が上がる)効果が出なくなってしまいます。
極端なケースだと同じ牌を何回でもツモれる可能性があるので4枚目を引いた後、5枚目6枚目を引いてくる可能性もわずかにあるということです。

このへん、他の方はどうされてるんだろうか?

今後4人麻雀に拡張する場合でも、現在の順目以降の他家の挙動(捨て牌など)を記憶できないということが問題として出てきそうです。他家の挙動お構いなしに全ツッパする分にはそこまで影響は出なさそうですが、繊細な挙動をするAI作りとかの段階になったらかなり響いてきそうな気がします。


とはいえ、処理速度の軽減は重要なのでこの要素を取り下げることはできません。またなんかいいアイデアが浮かんだらいいですが。


こうして毎日ブログを更新しているのを見ると一人麻雀計算機なんか簡単に作れるんじゃないの?と誤解されるかもしれませんが、はっきり言っておきます。

作るの、超難しいです。

思いつきでいろいろいじってるのでバグが次から次に出ててんやわんやしてます。
やたらと時間かかるプログラムができるのも、知識・経験不足なんだろうなぁと思いつつ、ちょっとがっかり。
スポンサーサイト

コメントの投稿

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

コメント

プロフィール

nisi5028

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

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

この人とブロともになる

QRコード
QRコード