LoginSignup
1
1

More than 3 years have passed since last update.

@ikuo0

麻雀の和了判定アルゴリズム

Last updated at Posted at 2020-11-14

麻雀の和了判定アルゴリズム

１４枚の手牌の和了が完成しているかを検査します、向聴数を求めるアルゴリズムではありません。

データ形式

牌のデータにはONE-HOTを使用します、ONE-HOT配列を行方向に総和を取ると頭、刻子の判定が楽なのでONE-HOTを選択しました

# ONE-HOT表現の手牌
[
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
]

# 行方向に総和を取る
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 4, 1, 1, 1, 4, 1, 1, 0, 0, 0, 0, 0, 0, 0]
# 3以上の箇所は刻子の判断材料になる
# [1, 1, 1] で畳み込みを行い３以上の箇所は順子の判断材料になる
# 等の利点がある（ように思う）

検査方法

  1. 「頭」を全パターン検査する（一番外側のループ）
  2. 「頭」を取り除いた残りで「刻子」を全パターン検査する（内側のループ）
  3. 検査された「頭」、「刻子」を取り除いた残りで「順子」を検査し成立していれば取り除く
  4. １～３の手順で残された牌が０枚となったのなら和了とする

以上の手順で和了完成かどうかを検査します。

ソースコード


import itertools
import multiprocessing
import numpy as np
import os
import sys
import time

# m1-m9, p1-p9, s1-s9, dw, dg, dr, we, ww, ws, wn
# 三元牌＝Dragon
# 風牌＝Wind
tileKeyIndex = [
    "m1", "m2", "m3", "m4", "m5", "m6", "m7", "m8", "m9", 
    "p1", "p2", "p3", "p4", "p5", "p6", "p7", "p8", "p9", 
    "s1", "s2", "s3", "s4", "s5", "s6", "s7", "s8", "s9", 
    "dw", "dg", "dr",
    "we", "ww", "ws", "wn", 
]

MTileBits = [
    1, 1, 1, 1, 1, 1, 1, 1, 1, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0,
    0, 0, 0, 0
]

PTileBits = [
    0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0,
    0, 0, 0, 0
]

STileBits = [
    0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 
    0, 0, 0,
    0, 0, 0, 0
]

DTileBits = [
    0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 1, 1,
    0, 0, 0, 0
]

WTileBits = [
    0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0,
    1, 1, 1, 1
]

KokusiBits = [
    1, 0, 0, 0, 0, 0, 0, 0, 1, 
    1, 0, 0, 0, 0, 0, 0, 0, 1, 
    1, 0, 0, 0, 0, 0, 0, 0, 1, 
    1, 1, 1,
    1, 1, 1, 1
]

KokusiBits = np.array(KokusiBits)

# m1m2m3m4m5m6m7m8m9s1s2s3wnwn
def parseTehai(s):
    if len(s) != 28:
        print("error in {}, len(s)={}".format(sys._getframe().f_code.co_name, len(s)))
        sys.exit()
    tileMatrix = np.zeros((14, len(tileKeyIndex)))
    for i in range(14):
        pos = i * 2
        idx = tileKeyIndex.index(s[pos:pos + 2])
        tileMatrix[i][idx] = 1
    return tileMatrix

def isShuntsuCompleted(tileMatrix):
    indexes = []
    for tbits in [MTileBits, PTileBits, STileBits]:
        target = tileMatrix * tbits
        while True:
            b = list(map(lambda x: int(x != 0), target)) # 非0を1へ変換
            b = np.convolve(b, [1, 1, 1], mode="valid")
            if np.max(b) != 3:
                break
            idxs = np.where(b == 3)[0]
            idx = idxs[0]
            target[idx:idx + 3] -= 1
            indexes = indexes + list(np.arange(idx, idx + 3, 1))
    return indexes

def isCompleted(tileMatrix):
    rowSum = np.sum(tileMatrix, axis=0)
    headerIdxs = np.where(rowSum >= 2)[0]
    atama, kotsu, shuntsu = [], [], []

    # チートイツ
    if len(headerIdxs) == 7:
        return 1, list(headerIdxs) * 2, [], []

    # 国士
    kokusiCheck = (rowSum != 0).astype(int)
    if np.sum(kokusiCheck * KokusiBits) == 13 and np.sum(rowSum * KokusiBits) == 14:
        return 1, np.where(np.array(KokusiBits) == 1)[0], [], []

    # 頭を固定する
    # 刻子を全パターン予め出しておいて各パターン固定で順子を検査する
    for hidx in headerIdxs:
        # 元の配列を操作してしまわないようにコピーを作成
        calcBuffer = np.array(rowSum)

        # 頭を取り除く
        calcBuffer[hidx] -= 2

        # 刻子の可能性がある箇所を全て検出しておく
        kotsuPos = np.where(calcBuffer >= 3)[0]

        # 検出されたうちの刻子1個だけ有効、検出されたうちの刻子２個だけ有効……検出された刻子全て有効　の全パターンを作成する
        kotsuPatterns = []
        for i in range(len(kotsuPos)):
            comb = list(itertools.combinations(kotsuPos, i + 1))
            kotsuPatterns = kotsuPatterns + comb
        # 刻子が一つも有効ではないパターンを追加する
        kotsuPatterns.append(None)

        for kotsuIndexes in kotsuPatterns:
            # 元の配列を操作してしまわないようにコピーを作成
            calcBuffer2 = np.array(calcBuffer)
            if isinstance(kotsuIndexes, type(None)):
                pass
            else:
                # 刻子を取り除く
                for kidx in kotsuIndexes:
                    calcBuffer2[kidx] -= 3
            # 順子
            shuntsuIndexes = isShuntsuCompleted(calcBuffer2)
            for idx in shuntsuIndexes:
                # 順子を取り除く
                calcBuffer2[idx] -= 1

            # 頭、刻子、順子を取り除いた上で残った牌が無ければ完成している
            #print("np.sum(calcBuffer)", np.sum(calcBuffer2))
            if np.sum(calcBuffer2) == 0:
                atama.append(np.full(2, hidx))
                kotsu.append(kotsuIndexes)
                shuntsu.append(shuntsuIndexes)

    return len(atama), atama, kotsu, shuntsu

def Test1():
    #2333345677778
    #2333344567888
    #2345666777888
    #3344455566777
    #2223344455677
    #1112345556677
    #4556677888999

    #1425869待ち
    #14725869待ち
    #1245678待ち
    #36258待ち
    #6257待ち
    #672583待ち
    #789436待ち

    #tileMatrix = parseTehai("m1m2m3m4m5m6m7m8m9s1s2s3wnwn")
    #tileMatrix = parseTehai("wewewewwwwwwwswswsm9m9m9s1s1")
    #tileMatrix = parseTehai("s2s3s3s3s3s4s5s6s7s7s7s7s8s9") # s1, s2, s4, s5, s6, s8, s9
    #tileMatrix = parseTehai("m2m3m3m3m3m4m4m5m6m7m8m8m8m1") # 
    #tileMatrix = parseTehai("m2m3m4m5m6m6m6m7m7m7m8m8m8?")
    #tileMatrix = parseTehai("m3m3m4m4m4m5m5m5m6m6m7m7m7?")
    #tileMatrix = parseTehai("p2p2p2p3p3p4p4p4p5p5p6p7p7?")
    #tileMatrix = parseTehai("p1p1p1p2p3p4p5p5p5p6p6p7p7?")
    #tileMatrix = parseTehai("p4p5p5p6p6p7p7p8p8p8p9p9p9?")
    tileMatrix = parseTehai("m1m9p1p9s1s9wewswwwndwdgdrm1")
    completeCount, atama, kotsu, shuntsu = isCompleted(tileMatrix)
    if completeCount > 0:
        print("OK")
        print(atama)
        print(kotsu)
        print(shuntsu)
    else:
        print("NG")

def tileMatrixToTehaiString(tileMatrix):
    s = ""
    for r in tileMatrix:
        idx = np.where(r == 1)[0][0]
        s += tileKeyIndex[idx]
    return s

def appendFile(fileName, data):
    with open(fileName, mode="a") as f:
        f.write(data + "\n")

def TenhohTestSub(args):
    seed = time.time()
    seed = int((seed - int(seed)) * 10000000)
    np.random.seed(seed)
    instanceId, tryCount = args
    size = len(tileKeyIndex)
    allTile = []
    for i in range(size):
        tmp = [0] * size
        tmp[i] = 1
        for n in range(4):
            allTile.append(tmp)
    for i in range(tryCount):
        np.random.shuffle(allTile)
        tiles = np.array(allTile[:14])
        completeCount, atama, kotsu, shuntsu = isCompleted(tiles)
        if completeCount > 0:
            tehaiStr = tileMatrixToTehaiString(tiles)
            appendFile("tenhoh_{}.txt".format(instanceId), tehaiStr)

def TenhohTest():
    #TenhohTestSub(1, 400000)
    tryCount = 1000000

    args = []
    for i in range(4):
        args.append([i, tryCount])

    with multiprocessing.Pool(4) as p:
        p.map(TenhohTestSub, args)

def main():
    #Test1()
    TenhohTest()

if __name__ == "__main__":
    main()
# python main.py

ソースコードの使い方

def main():
    #Test1()
    TenhohTest()

Test1() ではソースコード内に手入力で準備した牌譜を検査します。
TenhohTest() では４コア使って１コアあたり１００万回ランダムに牌譜を作成し和了形だったら記録を取ります、記録は「tenhoh_0.txt」のようにコア毎の番号付きで記録されます。

下記に追記する画像変換プログラムを使う事で天和？した牌譜を画像化できます。

牌譜テキストの画像化プログラム

テキストを画像化するプログラムを公開します、使い方は後述。


import PIL.Image
import os
import sys

tileKeyIndex = [
    "m1", "m2", "m3", "m4", "m5", "m6", "m7", "m8", "m9", 
    "p1", "p2", "p3", "p4", "p5", "p6", "p7", "p8", "p9", 
    "s1", "s2", "s3", "s4", "s5", "s6", "s7", "s8", "s9", 
    "dw", "dg", "dr",
    "we", "ww", "ws", "wn", 
]

haiImageNames = [
    "p_ms1_1.gif", "p_ms2_1.gif", "p_ms3_1.gif", "p_ms4_1.gif", "p_ms5_1.gif", "p_ms6_1.gif", "p_ms7_1.gif", "p_ms8_1.gif", "p_ms9_1.gif", 
    "p_ps1_1.gif", "p_ps2_1.gif", "p_ps3_1.gif", "p_ps4_1.gif", "p_ps5_1.gif", "p_ps6_1.gif", "p_ps7_1.gif", "p_ps8_1.gif", "p_ps9_1.gif", 
    "p_ss1_1.gif", "p_ss2_1.gif", "p_ss3_1.gif", "p_ss4_1.gif", "p_ss5_1.gif", "p_ss6_1.gif", "p_ss7_1.gif", "p_ss8_1.gif", "p_ss9_1.gif", 
    "p_no_1.gif", "p_ji_h_1.gif", "p_ji_c_1.gif",
    "p_ji_e_1.gif", "p_ji_w_1.gif", "p_ji_s_1.gif", "p_ji_n_1.gif", 
]

def parseTehai(s):
    if len(s) != 28:
        print("error in {}, len(s)={}".format(sys._getframe().f_code.co_name, len(s)))
        sys.exit()
    indexes, tehai = [], []
    for i in range(14):
        pos = i * 2
        idx = tileKeyIndex.index(s[pos:pos + 2])
        indexes.append(idx)
        tehai.append(s[pos:pos + 2])
    return indexes, tehai

def enumFile():
    files = []
    for v in os.listdir("./"):
        if os.path.isfile(v) and v.startswith("tenhoh_"):
            files.append(v)
    return files

def readFile(fileName):
    with open(fileName, "r") as f:
        return f.read()

def tileIndexesToImage(indexes):
    images = []
    for idx in indexes:
        imageFile = os.path.join("./images", haiImageNames[idx])
        im = PIL.Image.open(imageFile)
        images.append(im)
    imageWidth = 0
    maxHeight = 0
    for im in images:
        imageWidth += im.width
        if im.height > maxHeight:
            maxHeight = im.height
    dst = PIL.Image.new('RGB', (imageWidth, maxHeight))
    for i, im in enumerate(images):
        dst.paste(im, (im.width * i, 0))
    return dst

def main():
    files = enumFile()
    for f in files:
        lines = readFile(f).split("\n")
        basename = os.path.basename(f)
        basename, _ = os.path.splitext(basename)
        for j, l in enumerate(lines):
            if len(l) < 28:
                continue
            indexes, tehai = parseTehai(l)
            indexes = sorted(indexes)
            image = tileIndexesToImage(indexes)
            destFile = "{}_{:03d}.png".format(basename, j)
            destFile = os.path.join("./dest", destFile)
            image.save(destFile)

if __name__ == "__main__":
    main()
# https://mj-king.net/sozai/
# python tehai_2_image.py

画像化プログラムの使い方

同フォルダの ”tenhoh_???.txt” ファイルを自動的に読み込んで ./images にある画像を元に ./dest へ画像を出力します

m7s5p2p6s7p4m6p7s6p5m5p2p5p6 を
↓
tenhoh_2_000.png
このようにソートして画像変換します。

麻雀王国の画像をダウンロードしてきて展開する

./images に「萬子２」「筒子２」「索子２」「字牌２」からダウンロードした画像データを解凍してください

画像フォルダ構成.PNG

フォルダ構成はこのようになります、 D:\tmp がプログラムフォルダだという体です。

dest フォルダを作成する

フォルダ構成.PNG

出力用のフォルダをあらかじめ作成します

実行する

python tehai_2_image.py

正常に実行されれば ./dest に画像化された牌譜が出力されます。

以上です。

1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1