ひょんな事から麻雀で使う清一色（チンイツ）のツールを開発することになりました。
実際に手を動かしてアプリを作っていったら、これが結構大変だったので時間がかかったところの考え方だけでもインターネッツの世界に書き記しておこうと思います。
何が大変だったか
アガリ判定のアルゴリズムです。インターネッツで情報公開している先駆者の方の情報を参考にしましたが、なかなか判定し切れなかったです。
何を引いてきたかはとりあえず考えないで、以下の手牌のアガリ判定を考えてみましょう。
麻雀経験者からすると清一色の手の割に簡単ですね。
頭の中でこう分解できれば和了。
ただこの分解を実装しようとしたら意外に難しかったです。
インターネッツで調べながらコードを書いてはチェケラしていったのですが、どうも全パターンを判定できない。ネッツで調べたところ大体以下の手順でした。
①頭候補を探し順に試行していく
②刻子候補を探し面子確定させる
③残った手配を順子に分割できたらアガリ
①の頭の確定のところはたぶん正解だと思います。特殊形を除いて頭は必ず１つ必要なので先に確定させた方が試行回数が減少するはず。
で、次いで3枚以上ある牌で刻子を確定させ、残りの手牌は順子を構成するものとする。
順子だけの場合は端から判定して抜き出していけば、和了の時は問題なく全部抜き取れます。ただ刻子や頭と組み合わさった時が曲者なんですね。
上の例だと三萬と四萬が刻子候補ですが、何も考えずにこれらを面子確定させてしまうとアガリ形とはなりません。
じゃあ、とばかりに順子から面子確定させていくと、
やはりアガリ形をうまく判定できません。
清一色以外の手牌ではこういう事はあまり発生しません。刻子と順子が同じ牌を使える場合のみに発生するレアケースですが、私が書いていたのは清一色で遊ぼう系アプリだったためこれは避けられない問題。
解決法ー刻子を組み合わせで考える
この手の場合どう考えればいいかというと、刻子候補のうち三萬のみを刻子として確定させ、残りを順子の組み合わせと考え、面子確定させていくが正解です。アルゴリズム的な話にすると、
①牌種ごとに枚数をカウントする
②2枚以上ある牌種を頭候補として、各候補に対して以下を繰り返し
③頭を仮確定させ手牌から抜く
④3枚以上ある牌種を刻子候補として、その組み合わせを求める
⑤刻子組み合わせ候補に対して以下を繰り返し
⑥対象の刻子を面子仮確定させ手牌から抜く
⑦残った手牌の端から順子を抜く
⑧全ての牌を抜き取れれば和了
もう少し具体的にみていきませう。
頭はアガリ形の中に必ず１組存在するため、順番に2枚以上ある牌を試せば問題はないかと思います。 ここでは上記手牌で八萬を頭候補とした場合を考えます。（もちろん3,4,5,6萬を頭候補としてアガリ判定を行い、全て失敗し八萬に到達した状況です）
この状況。
ここで上記④の刻子の組み合わせを求めます。
刻子自体は三萬と四萬で取れますが、その組み合わせなので、
（刻子無し）（三萬）（四萬）（三萬＆四萬）の４パターンが存在することになります。
仮に刻子候補が３つあればそれぞれを刻子とするか否かの二択が３つなので、2の３乗の８パターン、刻子が４つであれば2の4乗の16パターンを考えることになります。刻子が４つであれば四暗刻なので別に四暗刻判定を入れてもいいかもしれません。
ではまず八萬を頭、刻子無しと考えて残りを順子分解してみましょう。
ノー和了です。
次は三萬のみ刻子として考えた場合、こうなって、
こう。
で和了！
最後まで見てみましょう。次は四萬のみ刻子とする場合。
ノー和了。
三萬と四萬を刻子とする場合、
これもノー和了
結局のところアガリと判定することができたのは、三萬のみを刻子と考えて残りを順子と見なした１パターンだけでした。
一盃口に頭がくっついた11223344であったり、それを含んだ更に複雑な形だと複数のアガリ形が存在します。これらはアガリ役や点数に影響が出るため途中でアガリ形が求められても最後まで処理を継続する必要があると思います。
例えば、11223344456789 という形であれば頭を一萬とするか、四萬とするかで一気通貫がつくかが変わってしまうためです。
他の先駆者の方が公開している内容を見ると、頭を最初に抜き出すのは殆どの方が一致しています。
その後のアプローチに結構やり方の違いがあって、頭→刻子→順子と抜き出す人だったり頭→順子→刻子で抜き出す人がいます。
私がたどり着いた結論は以下。
抜き出す順番ではなく、抜き出す刻子の組み合わせが重要
刻子として抜き出せるけど、抜き出さないケースを考慮する
ここでは刻子の組み合わせに注目していますが、反対に順子の抜き出しの組み合わせを考えても同じようにアガリ判定ができるはずです。
ただ、
- 刻子のほうができにくいので、数が少なく組み合わせを考えるのに適している
- 順子は抜き出した面子によって、その後抜き出せなくなるケースが存在する
という理由で刻子の組み合わせを考える方が効率的と考えています。
例えば手牌中に以下のような形があったとして、
ここから取り出し得る順子は以下の４パターンがあります。
ただし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'
おわりに
この問題は考えていて結構おもしろい問題でした。どう分解するアルゴリズムなら漏れなくアガリ形を捉えられるか、いい感じの難易度とコーディングの自由さがあって楽しめました。
色々やっているうちに結局のところアガリ判定はインデックス法（全アガリパターンの配列とマッチングする方法）を使うことにしましたが、その他の機能で部分的に生きてくるモジュールになるので書ききりました。たぶんシャンテン数を計算する機能で使うはず。
おわり
