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

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


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

``` python
# 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. １～３の手順で残された牌が０枚となったのなら和了とする 

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

## ソースコード

``` python

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

```

## ソースコードの使い方

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

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

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

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

``` python

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](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/104691/1d8eea67-7653-046f-9455-aa8e0c81f8c5.png)
このようにソートして画像変換します。

### 麻雀王国の画像をダウンロードしてきて展開する
./images に「萬子２」「筒子２」「索子２」「字牌２」からダウンロードした画像データを解凍してください

![画像フォルダ構成.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/104691/22f12799-0ae6-b3ef-02e7-507f15997263.png)

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

### dest フォルダを作成する

![フォルダ構成.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/104691/fe117e73-2bcf-58a2-a0e9-eb426896842b.png)

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

## 実行する

```
python tehai_2_image.py
```

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


以上です。