ホンモノのエンジニアになりたい

ITやビジネス、テクノロジーの話を中心とした雑記ブログです。

麻雀のアガリ判定アルゴリズムで苦戦したこと

ひょんな事から麻雀で使う清一色チンイツ)のツールを開発することになりました。

実際に手を動かしてアプリを作っていったら、これが結構大変だったので時間がかかったところの考え方だけでもインターネッツの世界に書き記しておこうと思います。

 

 

何が大変だったか

ガリ判定のアルゴリズムです。インターネッツで情報公開している先駆者の方の情報を参考にしましたが、なかなか判定し切れなかったです。

 

何を引いてきたかはとりあえず考えないで、以下の手牌のアガリ判定を考える。

f:id:kwnflog:20180612114946p:plain

麻雀経験者からすると清一色の手の割に簡単ですね。

f:id:kwnflog:20180612115610p:plain  f:id:kwnflog:20180612115620p:plain  f:id:kwnflog:20180612115631p:plain  f:id:kwnflog:20180612115631p:plain  f:id:kwnflog:20180612115640p:plain

頭の中でこう分解できれば和了

ただこの分解を実装しようとしたら意外に難しかった。

 

インターネッツで調べながらコードを書いてはチェケラしていったのですが、どうも全パターンは判定できない。ネッツで調べたところ大体以下の手順でした。

①頭候補を探し順に試行していく

刻子候補を探し面子確定させる

③残った手配を順子に分割できたらアガリ

 

①の頭の確定のところはたぶん正解だと思います。特殊形を除いて頭は必ず1つ必要なので先に確定させた方が試行回数が減少するはず。

で、次いで3枚以上ある牌で刻子を確定させ、残りの手牌は順子を構成するものとする。

 

順子だけの場合は端から判定して抜き出していけば、和了の時は問題なく全部抜き取れる。ただ刻子や頭と組み合わさった時が曲者なんですね。

 

上の例だと三萬と四萬が刻子候補ですが、何も考えずにこれらを面子確定させてしまうと、アガリ形とはならない。

f:id:kwnflog:20180612115620p:plain  f:id:kwnflog:20180612121356p:plain  f:id:kwnflog:20180612121550p:plain

 

じゃあ、とばかりに順子から面子確定させていくと、

f:id:kwnflog:20180612115610p:plain  f:id:kwnflog:20180612121814p:plain  f:id:kwnflog:20180612121814p:plain  f:id:kwnflog:20180612121848p:plain

 

やはりアガリ形をうまく判定できない。

 

大抵の清一色手牌だったり、清一色以外の手牌ではこういう事は発生しません。刻子と順子が同じ牌を使う場合のみに発生しうるレアケースですが、私が書いていたのは清一色で遊ぼう系アプリだったためこれは避けられない問題。

 

解決法ー刻子を組み合わせで考える

この手の場合どう考えればいいかというと、刻子候補のうち三萬のみを刻子として確定させ、残りを順子の組み合わせと考え面子確定させていくが正解です。アルゴリズム的な話にすると、

 

①牌種ごとに枚数をカウントする

②2枚以上ある牌種を頭候補として、各候補に対して以下を繰り返し

③頭を仮確定させ手牌から抜く

④3枚以上ある牌種を刻子候補として、その組み合わせを求める

刻子組み合わせ候補に対して以下を繰り返し

⑥対象の刻子を面子仮確定させ手牌から抜く

⑦残った手牌の端から順子を抜く

⑧全ての牌を抜き取れれば和了

 

もう少し具体的にみていきませう。

頭はアガリ形の中に必ず1組存在するため、順番に2枚以上ある牌を試せば問題はないかと思います。 ここでは上記手牌で八萬を頭候補とした場合を考えます。(もちろん3,4,5,6萬を頭候補としてアガリ判定を行い、全て失敗し八萬に到達した状況です)

この状況。

f:id:kwnflog:20180612131633p:plain  f:id:kwnflog:20180612115640p:plain

ここで上記④の刻子の組み合わせを求めます。

刻子自体は三萬と四萬がありますが、その組み合わせなので、

刻子無し)(三萬)(四萬)(三萬&四萬)の4パターンが存在することになります。

 

仮に刻子候補が3つあればそれぞれを刻子とするか否かの二択が3つなので、2の3乗の8パターン、刻子が4つであれば2の4乗の16パターンを考えることになります。刻子が4つであれば四暗刻なので別に四暗刻判定を入れてもいいかもしれません。

 

ではまず八萬を頭、刻子無しと考えて残りを順子分解してみましょう。

 f:id:kwnflog:20180612115610p:plain  f:id:kwnflog:20180612121814p:plain  f:id:kwnflog:20180612121814p:plain  f:id:kwnflog:20180612132420p:plain  f:id:kwnflog:20180612115640p:plain

ノー和了

 

次は三萬のみ刻子として考えた場合、こうなって、

f:id:kwnflog:20180612132758p:plain  f:id:kwnflog:20180612115620p:plain   f:id:kwnflog:20180612115640p:plain

こう。

f:id:kwnflog:20180612115610p:plain  f:id:kwnflog:20180612115631p:plain  f:id:kwnflog:20180612115631p:plain  f:id:kwnflog:20180612115620p:plain  f:id:kwnflog:20180612115640p:plain

和了

 

最後まで見てみましょう。次は四萬のみ刻子とする場合。

f:id:kwnflog:20180612133103p:plain  f:id:kwnflog:20180612121356p:plain  f:id:kwnflog:20180612115640p:plain

ノー和了

 

三萬と四萬を刻子とする場合、

f:id:kwnflog:20180612133226p:plain  f:id:kwnflog:20180612115620p:plain  f:id:kwnflog:20180612121356p:plain  f:id:kwnflog:20180612115640p:plain

これもノー和了

 

結局のところアガリと判定することができたのは、三萬のみを刻子と考えて残りを順子と見做した1パターンだけでした。

一盃口に頭がくっついた11223344であったり、それを含んだ更に複雑な形だと複数のアガリ形が存在し、アガリ役や点数に影響が出るため途中でアガリ形が求められても最後まで処理を継続する必要があると思います。

例えば、11223344456789 という形であれば頭を一萬とするか、四萬とするかで一気通貫がつくかが変わってしまうためです。

 

 

他の先駆者の方が公開している内容を見ると、頭を最初に抜き出すのは殆どの方が一致しています。

その後のアプローチに結構やり方の違いがあって、頭→刻子→順子と抜き出す人だったり頭→順子→刻子で抜き出す人がいます。

 

私がたどり着いた結論は以下。

抜き出す順番ではなく、抜き出す刻子の組み合わせが重要

刻子として抜き出せるけど、抜き出さないケースを考慮する

 

ここでは刻子の組み合わせに注目していますが、反対に順子の抜き出しの組み合わせを考えても同じようにアガリ判定ができるはずです。

ただ、

  • 刻子のほうができにくいので、数が少なく組み合わせを考えるのに適している
  • 順子は抜き出した面子によって、その後抜き出せなくなるケースが存在する

という理由で刻子の組み合わせを考える方が効率が良いと考えています。

 

例えば手牌中に以下のような形があったとして、

f:id:kwnflog:20180612140217p:plain

ここから取り出し得る順子は以下の4パターンがあります。

f:id:kwnflog:20180612140337p:plain f:id:kwnflog:20180612115610p:plain f:id:kwnflog:20180612121814p:plain f:id:kwnflog:20180612115631p:plain

ただし123を抜き出した場合は、234と345は取れなくなります。234か345で面子を作ると他の面子を作ることはできないです。

このように抜き出した面子によって、その後抜き出せる面子が変わってしまうため、事前チェックが必要となりコードとして冗長になってしまいます。

刻子であればどのように刻子面子を確定させようと、他の刻子面子には影響が出ません。

 

 

おまけ.組み合わせを考えないと判定できない牌姿一覧

清一色のアガリ形から「抜き出せるけど抜き出さない」をしないとアガリ判定ができない手牌を並べます。

この手牌は単純に刻子を全部抜き出すとか順子を全部抜き出すといった方法ではアガリ判定ができないのでテストに使えると思います。というか複雑な形が多いのでこの手牌を頭の中で瞬時に分解できれば清一色上級者と言えるかもしれません。

 

'23333444556688', '22333456667788', '22344445556677', '11123334445577', '22223333444556', '11222345556677', '22333344555667', '11333445566678', '11122223334455', '22555566677788', '23333444555566', '22566667778899', '22444567778899', '22444455666778', '12222333445599', '22223344455688', '11123334445555', '33344555566678', '44455667778999', '11112233344566', '11444556667778', '11225566778899', '44445555666778', '12222333445588', '22234555667777', '33345666778888', '11122334445666', '22223334445588', '33345666777788', '11122334445677', '22233345556677', '11223344667799', '11123444555566', '44455567778899', '33444455666778', '22234445556666', '11222334455567', '44456667778888', '11123344455688', '11222334445556', '11444566777889', '11123334445588', '11333344555667', '22234555666677', '11122333444566', '44566667778899', '55666677788899', '33334455566799', '11555667778889', '11333455566677', '22223344455699', '33344445556677', '33555566777889', '22233445556799', '11122333444588', '11122223344456', '22223334445599', '34444555666677', '44445566677899', '55556666777889', '22444556677789', '11122333444599', '11112223334499', '11334455667799', '33345566677899', '11123344455666', '33334445556699', '33444566777889', '11122233444556', '11666677788899', '33344555666788', '22233334445556', '11123334445566', '11566667778899', '11224466778899', '11224455667799', '22444556667778', '12222333444455', '22234445556677', '33444455566677', '22333344455566', '11123334445599', '33444556677789', '11122333444577', '11112223334466', '11122223334445', '22234455566667', '22223334445577', '11223355668899', '11444455666778', '11123444556688', '44555667778889', '11122334445699', '11333456667788', '11112223334488', '55566667778889', '11233334445566', '11334455668899', '33345556667799', '22233344555667', '34444555667799', '11223344557799', '11224455667788', '22333445556667', '22234445556688', '22234444555667', '11224455668899', '22234555667799', '11112233344599', '33344445556667', '44445566677888', '11112223334477', '55556677788999', '11112233344588', '11112222333445', '22234455566799', '11123444556699', '33555667778889', '22333445566678', '33566667778899', '12222333445577', '22444566777889', '22233444455567', '44455666677789', '22555677788899', '44455556677789', '44555566777889', '22233445556788', '11224455778899', '44455566777889', '33444567778899', '11444566677788', '44456667778899', '22335566778899', '33334444555667', '11223344668899', '22234455566777', '44456777888899', '33344556667899', '44455556667778', '11223344557788', '33666677788899', '11112233344555', '55567778889999', '11444455566677', '11455556667788', '33345556667788', '33344456667788', '22233444555699', '44555566677788', '11222233444556', '11122333344456', '11344445556677', '11222344555667', '44445556667799', '33555677788899', '22233444555677', '11123344455699', '11333445556667', '44456677788889', '22333455666778', '33455556667788', '11123344455556', '11334466778899', '33555566677788', '11444556677789', '44456677788999', '11122234445566', '22555667778889', '22455556667788', '33444556667778', '22233445556777', '33344445566678', '11555566677788', '33344555666799', '22555566777889', '33345566677778', '33345556667777', '33334455566788', '22233334455567', '22234445556699', '33334445556688', '11333344455566', '44455556667788', '33345566677888', '11123333444556', '33344556667888', '11222344455566', '33345555666778', '22234455566788', '22333455566677', '44455666777899', '23333444556699', '11333455666778', '11223344558899', '11444567778899', '11335566778899', '33334455566777', '45555666777788', '44456666777889', '11123344455677', '33444566677788', '11123444556666', '22444455566677', '22223344455666', '22233444555688', '11222233344455', '44456777889999', '44555677788899', '22444566677788', '22666677788899', '22233334445566', '44666677788899', '11122334445688', '22334455668899', '33344455666778', '56666777888899', '11555566777889', '55566667778899', '11112233344577', '22223344455677', '11555677788899'

 

おわりに

この問題は考えていて結構おもしろい問題でした。どう分解するアルゴリズムなら漏れなくアガリ形を捉えられるか、いい感じの難易度とコーディングの自由さがあって楽しめました。

 

色々やっているうちに結局のところアガリ判定はインデックス法(全アガリパターンの配列とマッチングする方法)を使うことにしましたが、その他の機能で部分的に生きてくるモジュールになるので書ききりました。たぶんシャンテン数を計算する機能で使うはず。

 

おわり