続・ネット上の向聴数計算アルゴリズムの知見に勝手に補足する
概要
以下の記事でtomohxx氏の向聴数の計算のアルゴリズムを紹介した。
この記事の中で向聴数の事前計算に自分のPythonの環境では4時間半ほどかかったと述べたが、これを1分程度まで改善する方法を発見した。
上記の記事は既存のアイデアを解説するというものだったが、今回の記事は新規性があると思われる。多分。
既存の手法
既存の手法の詳しい内容は上記の記事を参照してほしいが、要約するとある手牌の距離を計算したいとき、全ての和了形を列挙して実際に必要な牌が何枚足りないかをカウントするというものだった。
たとえば12345mという手牌があるときに、11122mや456666777mや12344mのように、とにかく愚直に全て和了形を列挙し、
-
12345mを11122mにするためには1mが2枚と2mが1枚の計3枚必要 -
12345mを456666777mにするためには6mが4枚と7mが3枚の計7枚必要 -
12345mを12344mにするためには4mが1枚の計1枚必要
というように計算していき、その中で必要な牌が最小のものをその手牌の距離とした。
これを118,800通りある全て手牌に対して事前計算を行うので、和了形が実際には13,259通りあることを考えると、組み合わせは118800 * 13259 = 1,575,169,200通りとなり、結果的に4時間半もかかってしまっていた。
新しい手法
ダイクストラ法を使う。
ダイクストラ法の詳しい説明は以下の記事に譲る。
まず全ての手牌を列挙し、それぞれの手牌をグラフの頂点となんらかの方法で対応させたい。
たとえば11122mを頂点nに、11133mを頂点n+1に...といった具合である。
上記の対応のさせ方でも工夫すれば問題ないが、11122mは5枚和了形なら距離0、8枚和了形なら距離3であるということを考慮すると、見かけ上同じ手牌でも最終的な和了形を何枚にしたいかによって別物と扱ったほうが後々便利そうということが分かる。
そこで、この記事では
11122m|最終2枚を頂点nに、11122m|最終3枚を頂点n+1に...
11133m|最終2枚を頂点n+9に、11133m|最終3枚を頂点n+10に...
といった具合に、手牌と最終的な和了形の枚数の組み合わせをグラフの頂点と対応させることにする。
なお、最終◯枚の◯に入る数字は2, 3, 5, 6, 8, 9, 11, 12, 14の9通りである。
一般手の和了形に1種類の数牌が4枚ちょうどや7枚ちょうどだけ含まれることがありえないのは麻雀のルールから明らかである。
次にそれぞれの頂点にコストを割り当てる。このコストを更新していき、最終的には距離と一致させることを目標とする。
頂点の内、和了形に対応する頂点のコストを0に、それ以外の頂点のコストを無限大に設定する。
たとえば11122m|最終5枚のコストを0に設定する。
ここで11122m|最終8枚のような頂点のコストに0を設定してはいけないことには注意したい。
最終形を8枚で想定すると、11122mは和了形ではないからである。
次に頂点と頂点を結ぶ辺を貼る。
まず牌を捨てるような頂点間の移動にはコスト1の辺を貼る。
コスト1の辺を貼るということは、距離が1つ増える = 和了から遠ざかるということである。
たとえば、
-
11122m|最終5枚->1112m|最終5枚 -
11122m|最終5枚->1122m|最終5枚
のような向きの辺にはコスト1の辺を貼る。
ここで「牌を捨てても距離が増えないこともあるのでは？」と思う方もいるかも知れない。
たとえば1122339m|最終6枚 -> 112233m|最終6枚という辺にコスト1の辺を貼ったら矛盾が起きそうに感じる。9mは不要な牌なので捨てても距離が悪化するはずがないからである。
結論から言えば問題はない。
ダイクストラ法はコストが小さい頂点から探索していくアルゴリズムである。
つまり
- 距離0の頂点をすべて探索する
- 距離1の頂点をすべて探索する
- 距離2の頂点をすべて探索する
- ...
というように探索を進めていく。
つまり、距離nの頂点を探索しているときには距離0~n-1の頂点は全て探索済みで、そのコストが確定している。
たとえば、コスト1の頂点1122339m|最終6枚からコスト+1の辺を通って頂点112233m|最終6枚に到達しても、それより前の段階で既に頂点112233m|最終6枚は探索済みで、コスト2より小さいコストが代入されていることは保証されているので、常に最小コストで更新するようにさえすれば矛盾は発生しない。
同様に、牌を引くような頂点間の移動にはコスト0の辺を貼る。
たとえば、11122m|最終5枚 -> 111222m|最終5枚 のような向きの辺にはコスト0の辺を貼る。
これも、「牌を引いたら距離が1つ減る可能性があるのでは？」という疑問があるかも知れないが、先ほどと同様に矛盾は起きない。
そのような頂点は探索済みのはずだからである。
以上のアルゴリズムを実装すると、4時間半かかっていた処理が1分程度で終わるようになった。
まとめ
どうせ最初の一回しか計算しないなら、4時間半かかろうが1分かかろうがほぼ誤差のようなものかもしれない。
参考
実装
Discussion