| 2012/05/10 | 麻雀得点計算アルゴリズム編−２(役の判定)[★★★◎◎] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
前回、麻雀の面子列挙アルゴリズムを紹介しました。 今回は、列挙した面子の個々の得点を求めていきます。 実際のコードはVC#講座のページにあるサンプルを参照ください。 1. はじめに 2. 全体の方針 3. 面子の分解 4. 鳴き牌・上がり牌の処理 5. 麻雀の得点決定要素一覧 6. まとめ 1. はじめに 説明のための前提事項を書いておきます。 前回同様、以下では牌に以下の表記を用います。
役の判定で便利なので、サンプル中でも「14牌が指定した牌のみで構成されているかどうか」を判定する関数を準備しています。 この「指定した牌」を判定するのに以下の書式を利用しています。 Inc("111111111 111111111 111111111 1111 111") この関数Incの引数は、萬子９個・索子９個・筒子９個・字牌７個に対応していて、1になっている牌だけを含むならTrue、それ以外の牌を含むならFalseを返します。 多くの役は、「〜〜の牌を含む」や「〜〜の牌を含まない」と言う形をとるので、このような判定が容易になります。 2. 得点計算の方針 前回書いた通り、方針は以下の通りです。
2番の役判定では、以下の手順を踏みます。 役満の判定→役満が１個でもあれば、得点を出して終了→役満が無ければ、役満以外の役を判定して計算 なので、まずは役満を判定していくことにします。 なお、前提として、前回の面子列挙を通過した段階で、面子はちゃんとそろっていることとします。 3. 役満の判定 役満では、同時に複数の役満を満たす場合があるので、常に全役満パターンを検索します。 では順に見ていくことにします。 基本的には、麻雀のルールに則り判定していくだけです。 天和・地和はわざわざ判定するまでもないのでここでは省略。 ○○の牌だけで構成される系の役満 このパターンは先のInc関数を用いて判定できます。
特定の構成を含む系の役満 このパターンは、各牌の数をカウントして判定できます。 九蓮宝燈のダブル役満判定がちょっと面倒ですね。
その他の役満
4. 役満以外の役の判定 役満の役が出た場合、役満以外の判定は行いません。 役満の役がない場合、各役の判定を行っていきます。 と言っても、麻雀の役のルールをそのままプログラムで判定するだけですね。 最初の４面子１雀頭を作る処理に比べると容易です。役の種類が多い分面倒ですが。 牌取得時の状態で決まる役 以下の役は、手元の牌ではなく、牌を取得した状態で決まる役です。
○○の牌で構成される系の役 先ほどのInc関数だけで判定できるものは意外と少ないです。
特定牌だけで構成される役で、Inc関数だけでは判定できないのは下記の通り。 チャンタの説明でなぜ「７」が出るか不思議かもしれないですが、今回は順子のデータ構造として先頭の牌の数値で管理していることに注意。 例えば、７で始まる順子は、７８９の並びを意味しているので問題ない。
順子系の役 あとは役固有の並びをしているか判定するので、個別にみていくしかないですね。
刻子系の役
その他の役 これまでのパターンには含まれないような役です。 七対子だけは４面子１雀頭じゃないので、ちょっと特殊ですね。
以上の役を順々に処理していくと、合計の飜数が決まります。 6. 符の計算 さて、役が終わったら符の計算ですね。 とはいえ符の計算は麻雀の点数計算のルールに則って粛々とやるだけですね。 一応説明していきます。 得られる符は、下記項目を足し合わせ、最後に10の位で切り上げる。
刻子・槓子は上がり牌に複数含まれる可能性があるので少し面倒だけど、それ以外は１つ１つ確認すればよいね。 7. 翻と符からの得点計算 さて、翻と符が決まるとようやく最終的な得点が決まります。 まずは役満の得点だけ先に終えてしまいます。 N重役満の時の得点は以下の通りです。
さて、役満以外の得点です。 一般的には満貫未満のスコアは得点表を用いることが多いですが、実はすべて計算で算出可能です。 まず、F符H翻の時の基本得点Sは以下のように算出されます。 S = F×(2^(2+F)) 例えば30符3翻ならS=30×(2^5)=960ですね。 これを踏まえて、得点は以下のようになります。 [数式]は100単位の繰り上げになります。 また、Sが2000を超える場合は満貫になります。
上の数式を符と翻で表にしてみます。満貫とかありえないマスも、ひとまず上記に従って計算してみます。 これは子の場合。
これで見慣れた点数表が出てくることがわかります。 最後に、リーチ棒やツミ棒に関する得点を合わせて終了です。 複数の上がり方がある場合は、もっとも高い上がりを取ればよいでしょう。 8. まとめ 以上で得点計算を終わります。 前回の面子の列挙の方がアルゴリズム的には面白かったかな。 今回の内容は麻雀の役や点数計算を単純にプログラムで辿るだけなので。 麻雀の役判定はかなりややこしいので、これができればポーカーとかは楽にできそうですね。 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 2010/12/30 | 麻雀得点計算アルゴリズム編−１(面子の列挙)[★★★◎◎] | |||||||||||||||||||||||||||||||||||||
|
先日、VC#講座のページに麻雀の得点計算のサンプルを掲載しました。 ここでは、実装を解説していきたいと思います。 1. はじめに 2. 全体の方針 3. 面子の分解 4. 鳴き牌・上がり牌の処理 5. 麻雀の得点決定要素一覧 6. まとめ 1. はじめに 元々麻雀の得点計算をしようと思ったのは、あなたのスキルで飯は食えるか？ 史上最大のコーディングスキル判定(ITmedia)の記事がきっかけです。 ここに出てくる問題(清一色の上がり牌探索)に挑戦してみたら意外とすんなり解けたので、ついでに得点計算までやってみようと思い立ちました。 さて、麻雀の得点計算のアルゴリズムですが、ネットで調べても意外と出てきません。 少し調べて見つかったのは以下の２つ。 前者は会員登録しないと詳細が読めず、後者はアルゴリズムの高速化がメインです。 どちらも１からアルゴリズムを理解するには不便ですね。 ここでは、自分で作ってみた計算アルゴリズムの概要を説明していきます。 細かい実装や、実動作は上記サンプルを見てもらえばよいかと。 なお、以下では牌に以下の表記を用います。
今回はC++風の疑似コードを用いてアルゴリズム表記をしますが、その際以下の表記を用います。
2. 全体の方針 得点計算は以下の手順で行っていきます。
まず、14牌からあり得る全パターンの面子の組み合わせを考えます。 そしてそれぞれについて役を判定し、得点を計算します。 各面子の得点の中から、最も得点が高い組み合わせが得点となります。 以下、少しずつ説明していきます。 ここで次に行く前に少し補足。 上記サンプルでは、上がり牌を指定しない場合に、あり得る上がり牌と得点の一覧を出すようにしています。 この実装は単純で、13牌に対し34種の牌をそれぞれ上がり牌として加えて得点計算を繰り返す、というだけです。これはテンパイ判定にも使えますね。 当然34回得点計算をするので処理としては若干重たいですが、現在のPCなら問題ないです。携帯機ではわかりませんが…。 3. 面子の分解 麻雀では、基本的に４面子＋１雀頭を構成することになります。 14牌が与えられたとき、そこから構築可能な４面子＋１雀頭のパターンを列挙することを考えます。 この構成から外れる役としては七対子と国士無双がありますが、これは別途記載します。 まずは一番シンプルに、鳴きがない状態を考えます。 上がり牌とそうでない牌の区別もしません。 まず、雀頭を確定させてみます。 手牌の中で、２つ以上ある牌を探し、それを雀頭として抜き出した時、残り12牌から４面子を構成できるかチェックします。
List<M> G // 上がり形の一覧、グローバル変数
function 上がり形列挙(S) {
G.clear();
foreach(s, S) {
if (S.count(s) >= 2) {
// sが２つ以上あるなら、面子の集合を作り、雀頭を加える
M = new 面子集合
M.add(new 面子(sが2つの雀頭));
// s 2つを取り除いて、残りから面子を列挙
S.remove(s)
S.remove(s)
面子列挙(S,M)
// s 2つをもとに戻す
S.add(s)
S.add(s)
}
}
}
さて、これで後は残り12牌から4面子を抜き出せばよいです。ここでは、深さ優先探索で検索します。残った牌集合の一番小さな牌が、順子または刻子を構成できるか調べていきます。 残り牌が0にできたら4面子が構築できたので、その面子一覧を上がり形一覧に加えていきます。
function 面子列挙(S,M) {
if (S.size == 0) {
// 4面子列挙したので、上がり形一覧に追加
G.add(M)
return
}
s = S.min
if (count(s,S) >= 3) {
// sが3つ以上あるなら、刻子と判断する。
m = new 面子(sの刻子))
M.add(m)
// s 3つを取り除いて、残りから面子を列挙
S.remove(s)
S.remove(s)
S.remove(s)
面子列挙(S,M)
// s 3つをもとに戻す
S.add(s)
S.add(s)
S.add(s)
// 加えた面子をもとに戻す
M.remove(m)
}
if (s < 30 && S.exists(s) && S.exists(s+1) && S.exists(s+2)) {
// 数牌において、最小の牌が次の牌と次の次の牌を持つなら
// 順子と判断する
m = new 面子(sの順子))
M.add(m)
// 順子の牌を取り除いて、残りから面子を列挙
S.remove(s)
S.remove(s+1)
S.remove(s+2)
面子列挙(S,M)
// 順子の牌をもとに戻す
S.add(s)
S.add(s+1)
S.add(s+2)
// 加えた面子をもとに戻す
M.remove(m)
}
}
再帰関数を用いていますが、考え方は割と簡単ですね。最初に書いたITmediaの問題も、これと同等の考えで答えが出せます。 念のため、なぜ最小の牌でのみ面子構成をチェックするか書いておきます。 確かに、最小の牌でなくてもSの全牌に対し刻子・順子をチェックしてもよいです。 ただ、この場合同一内容で並びが異なるだけのMが出てしまいます。 麻雀においては(上がり牌を除けば)面子構成の順番は考える必要がないので、これが無駄になります。 また、麻雀は手牌すべてを用いて面子を作るゲームなので、最小の牌を選んだ場合、その牌はいずれかの面子に含まれなければなりません。 よって、最小の牌を順子・刻子をチェックすれば十分だと言えます。 4. 鳴き牌・上がり牌の処理 上記のコードは鳴き牌・上がり牌を考慮していませんでした。 ここではこれらの要素を考慮した上がり形列挙を考えます。 鳴き牌の場合、最初に面子Mのうち鳴き牌分が確定した状態で、残りの牌に対し上記「上がり形列挙」を実行すればよいです。 上記では「上がり形列挙」の中で面子集合Mを初期化してますが、代わりにこの関数を呼ぶ側で鳴き牌の面子を加えたMを与えればよいです。 コードとして書くと下記のように表せます。
function 上がり形列挙(S,M) {
foreach(s, S) {
if (S.count(s) >= 2) {
// sが２つ以上あるなら、面子の集合を作り、雀頭を加える
m = new 面子(sが2つの雀頭)
M.add(m)
// s 2つを取り除いて、残りから面子を列挙
S.remove(s)
S.remove(s)
面子列挙(S,M)
// s 2つをもとに戻す
S.add(s)
S.add(s)
// 雀頭を削除
M.remove(m)
}
}
}
麻雀は14牌のうちどれが上がり牌かにより得点が変わるので、上がり牌の処理も重要です。 上がり牌の処理は以下の方式が考えられます。どちらでもうまく行くでしょう。
まず前者は、既に上がり形列挙・面子列挙で対子・順子・刻子をチェックするコードを書いているのに、上がり牌チェック用にまた似たような処理のチェック用関数を作らないといけません。 後者は、上がり牌が複数使われている場合、得点が変わる可能性があるので、上がり形をコピーして別々に覚えておく必要があります。 例えば、５が上がり牌で手牌が４５５６６７の場合、５が４５６と５６７どちらの一部かによって得点が変わります。 本サンプルでは前者で実装しました。 5. 麻雀の得点決定要素一覧 役の判定は次回に行うとして、ここでは参考までに麻雀の上がり時の得点計算に必要な情報を記述しておきます。 これらを以下にプログラムで表現するかは、プログラマのデータ構造の作り方次第ですね。
参考までに、サンプルでのデータ構造を記載しておきます。 あまり綺麗ではないですが…。 なお、１巡目上がりは無条件役満でわざわざ得点計算をする必要がないので、ここには含んでいません。
//状態
public class MJState {
public bool TsumoAgari = false; //ツモかどうか
public int Richi = 0; //リーチ・ダブルリーチかどうか
// 一発・海底・嶺上・槍槓の有無
public bool Ippatsu = false, Haitei = false, Rinshan = false, Chankan = false;
public Kaze Jikaze = Kaze.TON; //自風
public Kaze Bakaze = Kaze.TON; //場風
public List
6. まとめ 今回は、麻雀の面子列挙を行ってみました。 再帰関数による深さ優先探索は、いかにもコンピュータのアルゴリズムっぽいですね。 次回は、各種役の判定を行っていきます。ただ、こちらは麻雀の役ルールに則り延々チェックしていくだけなのであまり面白味はないかもしれませんね。 | ||||||||||||||||||||||||||||||||||||||