麻雀の待ち形の判別

# 麻雀の待ち形の判別

http://qiita.com/arc279/items/7894d582a882906b94c7
これの続き。

なんというか思ったより相当めんどくさかった。

一部試行錯誤してるうちに悲惨な事になってしまった。
それはそれで面白いので試行の過程残したまま載せてみる。

かなり雑に書いてるんでおかしかったら教えてくれると嬉しいです。

参考にしたのはここ。
清一色判定のみなので、ここからスタートしてオレオレ超解釈でけっこう書き換えた。
http://d.hatena.ne.jp/staebchen/20100403/1270256158

クロージャとジェネレータ使いまくってしまったので
_python_ 以外で書き直そうとすると手こずるかもしれないけど、その辺はまぁアレ。

## 基本になるとこ

基本前のやつと同じだけど、それなりに手直し入れたのでまた全部貼る。

＃ _gist_とか外部にコード置くのは個人的にあんま好きじゃないので。
＃＃ 1カ所で完結してると嬉しい。

```py:mj2.py
#!/usr/bin/env python
# -*- coding: utf8 -*-

import itertools
import random

class Yama(list):
    u'''牌山'''
    WANPAI_NUM = 14

    class TsumoDoesNotRemain(Exception):
        u'''王牌しか残ってない'''
        pass

    def __init__(self):
        pais = [ Pai.from_index(i) 
                for i in range(Pai.TOTAL_KIND_NUM * Pai.NUM_OF_EACH_KIND) ]
        # 洗牌
        random.shuffle(pais)
        super(Yama, self).__init__(pais)

    def tsumo(self):
        u'''自摸'''
        if len(self) <= self.WANPAI_NUM:
            raise self.TsumoDoesNotRemain

        return self.pop(0)

    def wanpai(self):
        u'''王牌'''
        return self[-self.WANPAI_NUM:]

    def haipai(self):
        u'''配牌'''
        tehais = [ Tehai(), Tehai(), Tehai(), Tehai() ] # 東(親) 南 西 北

        # 4*3巡
        for j in range(0, 3):
            for tehai in tehais:
                for i in range(0, 4):
                    pai = self.tsumo()
                    tehai.append(pai)

        # ちょんちょん
        for tehai in tehais:
            pai = self.tsumo()
            tehai.append(pai)

        pai = self.tsumo()
        tehais[0].append(pai)

        return tehais

class Pai(object):
    u'''牌'''

    TOTAL_KIND_NUM = 34          # M/P/S + 字牌合わせた全ての種類
    NUM_OF_EACH_KIND = 4         # 1種類につき4枚
    NUM_OF_EACH_NUMBER_PAIS = 9  # M/P/S の数字牌は1..9まで

    class Suit:
        M = 0   # 萬
        P = 1   # 筒
        S = 2   # 策
        J = 3   # 字

        NAMES = {
            M: u"萬",
            P: u"筒",
            S: u"策",
            J: u"　",
        }

    class Num:
        NAMES = {
            1: u"一",
            2: u"二",
            3: u"三",
            4: u"四",
            5: u"五",
            6: u"六",
            7: u"七",
            8: u"八",
            9: u"九",
        }

    class Tsuhai:
        E   = 1
        S   = 2
        W   = 3
        N   = 4
        HAK = 5
        HAT = 6
        CHU = 7

        NAMES = {
            E:   u"東",
            S:   u"南",
            W:   u"西",
            N:   u"北",
            HAK: u"白",
            HAT: u"撥",
            CHU: u"中",
        }

    @classmethod
    def all(cls):
        u'''全ての牌'''
        return [cls(suit, num)
                for suit in cls.Suit.NAMES
                for num in range(1, cls.NUM_OF_EACH_NUMBER_PAIS+1)
                if suit != cls.Suit.J
            ] + [ cls(cls.Suit.J, num) for num in cls.Tsuhai.NAMES.keys() ]

    @classmethod
    def yaochupai(cls):
        u'''么九牌'''
        return [
            cls(cls.Suit.M, 1),
            cls(cls.Suit.M, 9),
            cls(cls.Suit.P, 1),
            cls(cls.Suit.P, 9),
            cls(cls.Suit.S, 1),
            cls(cls.Suit.S, 9),
            cls(cls.Suit.J, cls.Tsuhai.E),
            cls(cls.Suit.J, cls.Tsuhai.S),
            cls(cls.Suit.J, cls.Tsuhai.W),
            cls(cls.Suit.J, cls.Tsuhai.N),
            cls(cls.Suit.J, cls.Tsuhai.HAK),
            cls(cls.Suit.J, cls.Tsuhai.HAT),
            cls(cls.Suit.J, cls.Tsuhai.CHU),
        ]

    @classmethod
    def chuchanpai(cls):
        u'''中張牌'''
        yaochupai = cls.yaochupai()
        return [ x for x in cls.all() if x not in yaochupai ]

    def __init__(self, suit, num):
        self.suit = suit
        self.num  = num

    @property
    def index(self):
        return self.suit * self.NUM_OF_EACH_NUMBER_PAIS + self.num - 1

    def is_next(self, other, index=1):
        u'''次の数字牌かどうか'''
        if self.suit != self.Suit.J: # 字牌でなくて
            if self.suit == other.suit: # 牌種が同じで
                if other.num == (self.num + index): # 連番
                    return True
        return False
        
    def is_prev(self, other, index=1):
        u'''前の数字牌かどうか'''
        return self.is_next(other, -index)

    @classmethod
    def is_syuntsu(cls, first, second, third):
        u'''順子かどうか'''
        #return second.is_prev(first) and second.is_next(third)
        return first.is_next(second) and first.is_next(third, 2)

    def __repr__(self):
        #return str((self.suit, self.num))    # タプル表示
        if self.suit == self.Suit.J:
            return self.Tsuhai.NAMES[self.num].encode('utf-8')
        else:
            return (self.Num.NAMES[self.num] + self.Suit.NAMES[self.suit]).encode('utf-8')

    def __eq__(self, other):
        return self.suit == other.suit and self.num == other.num

    @classmethod
    def from_index(cls, index):
        u'''indexから取得'''
        kind = index % cls.TOTAL_KIND_NUM

        if True:
            suit = kind / cls.NUM_OF_EACH_NUMBER_PAIS
            num  = kind % cls.NUM_OF_EACH_NUMBER_PAIS + 1
        else:
            if 0 <= kind < 9:
                suit = cls.Suit.M
                num  = kind - 0 + 1
            elif 9 <= kind < 18:
                suit = cls.Suit.P
                num  = kind - 9 + 1
            elif 18 <= kind < 27:
                suit = cls.Suit.S
                num  = kind - 18 + 1
            elif 27 <= kind < 34:
                suit = cls.Suit.J
                num  = kind - 27 + 1

        assert(cls.Suit.M <= suit <= cls.Suit.J)
        assert(1 <= num <= cls.NUM_OF_EACH_NUMBER_PAIS)

        return cls(suit, num)

    @classmethod
    def from_name(cls, name):
        u'''名前から取得'''
        for x in cls.all():
            if name == repr(x):
                return x
        return None

class Tehai(list):
    u'''手牌'''

    @staticmethod
    def sorter(a, b):
        u'''理牌の方法'''
        return a.suit - b.suit if a.suit != b.suit else a.num - b.num

    def rihai(self):
        u'''理牌'''
        self.sort(cmp=self.sorter)
        return self

    @classmethod
    def aggregate(cls, tehai):
        u'''{牌種 : 枚数} の形に集計'''
        hash = { x[0]: len(list(x[1])) for x in itertools.groupby(tehai.rihai()) }
        # キー（ソート済みの牌）も一緒に返す
        return hash, sorted(hash.keys(), cmp=cls.sorter)

    def show(self):
        u'''見やすい形に表示'''
        line1 = u"|"
        line2 = u"|"
        for pai in self.rihai():
            if pai.suit != Pai.Suit.J:
                line1 += Pai.Num.NAMES[pai.num] + u"|"
                line2 += Pai.Suit.NAMES[pai.suit] + u"|"
            else:
                line1 += Pai.Tsuhai.NAMES[pai.num] + u"|"
                line2 += u"　|"

        print line1.encode("utf-8")
        print line2.encode("utf-8")

    @classmethod
    def search_syuntsu(cls, pais, keys):
        u'''順子を探す
        引数は aggregate() の戻り値と同じ形で渡す。'''
        for i in range( len(keys)-2 ):   # ラスト2枚はチェック不要
            tmp = pais.copy()
            first = keys[i]
            if tmp[first] >= 1:
                try:
                    second = keys[i+1]
                    third  = keys[i+2]
                except IndexError as e:
                    # 残り2種無い
                    continue

                if not Pai.is_syuntsu(first, second, third):
                    continue

                if tmp[second] >= 1 and tmp[third] >= 1:
                    tmp[first]  -= 1
                    tmp[second] -= 1
                    tmp[third]  -= 1
                    # 見付かった順子, 残りの牌
                    yield (first, second, third), tmp

    @classmethod
    def search_kohtu(cls, pais, keys):
        u'''刻子を探す
        引数は aggregate() の戻り値と同じ形で渡す。'''
        for i, p in enumerate(keys):
            tmp = pais.copy()
            if tmp[p] >= 3:
                tmp[p] -= 3
                # 見付かった刻子, 残りの牌
                yield (p, p, p), tmp
```

## 待ちのチェック

調子乗って書いてたら酷い事になった。けどまぁいいや。
もう直すのもめんどくさい。

9面待ち九蓮宝燈とかちょっと怪しいかも。
待ちとか種類多すぎてちゃんとチェックできてないので…

あくまで待ちの形だけで役の判定は入ってない。

あと、力尽きたので七対子と国士無双の待ちは入れてない。
まぁアガリ型の判別にちょっと手入れればできるんじゃないかな。

```py:mj2.py
def check_tenpai(tehai):
    u'''聴牌の形をチェック'''
    # TODO: 七対子と国士無双の待ちチェック入れてない
    assert(len(tehai) == 13)

    # (アタマ, 面子, 待ち) の形
    candidate = set()

    def check_machi(mentsu, tartsu):
        u'''待ちの形を調べる'''
        assert(len(mentsu) == 3)

        keys = sorted(tartsu.keys(), cmp=Tehai.sorter)
        #print mentsu, tartsu, keys

        def check_tanki():
            u'''単騎待ちチェック'''
            for i, p in enumerate(keys):
                tmp = tartsu.copy()
                if tmp[p] == 3:
                    # 残った面子が刻子
                    assert(len(tmp) == 2)
                    tmp[p] -= 3
                    tanki = { pai: num for pai, num in tmp.items() if num > 0 }.keys()
                    # 面子に突っ込む
                    ins = tuple( sorted(mentsu + [(p, p, p)]) )
                    candidate.add( ((), ins, tuple(tanki)) )
                else:
                    # 残った面子が順子
                    first  = p
                    try:
                        second = keys[i+1]
                        third  = keys[i+2]
                    except IndexError as e:
                        continue

                    if not Pai.is_syuntsu(first, second, third):
                        continue

                    tmp[first]  -= 1
                    tmp[second] -= 1
                    tmp[third]  -= 1
                    tanki = { pai: num for pai, num in tmp.items() if num > 0 }.keys()
                    # 面子に突っ込む
                    ins = tuple( sorted(mentsu + [(first, second, third)]) )
                    candidate.add( ((), ins, tuple(tanki)) )

        def check_non_tanki():
            u'''単騎以外の待ちチェック'''
            for i, p in enumerate(keys):
                tmp = tartsu.copy()

                # 雀頭チェック
                if not tmp[p] >= 2:
                    continue
                tmp[p] -= 2
                atama = (p, p)

                for j, q in enumerate(keys):
                    # 両面、辺張
                    try:
                        next = keys[j+1]
                        if q.is_next(next):
                            ins = tuple( sorted(mentsu) )
                            candidate.add( (atama, ins, (q, next) ) )
                            break
                    except IndexError as e:
                        pass

                    # 嵌張
                    try:
                        next = keys[j+1]
                        if q.is_next(next, 2):
                            ins = tuple( sorted(mentsu) )
                            candidate.add( (atama, ins, (q, next) ) )
                            break
                    except IndexError as e:
                        pass

                    # 双碰
                    if tmp[q] >= 2:
                        ins = tuple( sorted(mentsu) )
                        candidate.add( (atama, ins, (q, q) ) )
                        break

        check_tanki()
        check_non_tanki()

    # 3面子探す
    pais, keys = Tehai.aggregate(tehai)
    #print pais, keys

    if True:
        # 再帰でやるとこうかな
        def search_mentsu(depth, proc):
            searchers = [Tehai.search_syuntsu, Tehai.search_kohtu]
            # 順子 / 刻子 の探索
            def inner(pais, mentsu = [], nest = 0):
                if nest < depth:
                    for search in searchers:
                        for m, a in search(pais, keys):
                            inner(a, mentsu + [m], nest+1)
                else:
                    proc(mentsu, pais)
            inner(pais)

        search_mentsu(3, lambda mentsu, pais:
                check_machi(mentsu, { x[0]:x[1] for x in pais.items() if x[1] > 0 })
            )
    else:
        # ベタ書きするとこう
        searchers = [Tehai.search_syuntsu, Tehai.search_kohtu]
        for p1 in searchers:
            for p2 in searchers:
                for p3 in searchers:
                    # 適用
                    for m1, a1 in p1(pais, keys):
                        for m2, a2 in p2(a1, keys):
                            for m3, a3 in p3(a2, keys):
                                mentsu = [m1, m2, m3]
                                # 残りの牌
                                tartsu = { x[0]:x[1] for x in a3.items() if x[1] > 0 }
                                check_machi(mentsu, tartsu)

    return candidate
```

## テストとか

デバッグ用のアレ。

```py:mj2.py
    class Debug:
        u'''for debug'''

        TEST_HOHRA = [
            [2, 3, 3, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7],
            [0, 0, 8, 8, 13, 13, 20, 20, 25, 25, 29, 29, 31, 31],      # ちーといつ
            [0, 8, 9, 17, 18, 26, 27, 28, 29, 30, 31, 32, 33, 9],      # こくしむそう
            [33, 33, 33, 32, 32, 32, 31, 31, 31, 0, 0, 0, 2, 2],    # だいさんげん
            [0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 8, 1],      # ちゅうれんぽうとう
            [19, 19, 20, 20, 21, 21, 23, 23, 23, 25, 25, 32, 32, 32],      # りゅういーそう
            [0, 1, 2, 3, 4, 5, 6, 7, 8, 5, 5, 0, 1, 2],      # ちんいつ いっつー いーぺーこう
        ]

        TEST_TENPAI = [
            [0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 8],      # 純正ちゅうれんぽうとう
            [1, 2, 3, 4, 5, 5, 5, 6, 20, 20, 21, 22, 23],  # かんちゃん しゃぼ(順子がからむやつ)
            [13, 14, 15, 18, 19, 19, 20, 21, 24, 24, 24, 31, 31],   # りゃんめん かんちゃん
            [25, 25, 25, 1, 2, 3, 11, 12, 13, 11, 23, 23, 23],  # りゃんめん たんき
            [25, 25, 25, 1, 2, 3, 11, 12, 13, 11, 12, 23, 24],   # りゃんめん
            [1, 2, 3, 4, 4, 6, 7, 8, 9, 10, 11, 29, 29],    # しゃぼ
        ]

        @classmethod
        def tehai_from_indexes(cls, indexes):
            assert(len(indexes) == 13 or len(indexes) == 14)
            return Tehai([ Pai.from_index(x) for x in indexes ])

        @classmethod
        def test_hohra(cls, idx = None):
            u'''和了形のテスト'''
            return cls.tehai_from_indexes(cls.TEST_HOHRA[idx])

        @classmethod
        def test_tenpai(cls, idx = 0):
            u'''聴牌形のテスト'''
            return cls.tehai_from_indexes(cls.TEST_TENPAI[idx])

        @classmethod
        def gen_tehai(cls, num = 14):
            u'''適当に配牌形を作る'''
            assert(num == 13 or num == 14)
            yama = Yama()
            return Tehai([ yama.tsumo() for x in range(num) ])

        @classmethod
        def gen_hohra(cls):
            u'''適当にアガリ形を作る'''
            tehai = Tehai()

            def gen_syuntsu():
                u'''順子作る'''
                first = Pai.from_index(random.choice(range(Pai.TOTAL_KIND_NUM)))
                if first.suit == Pai.Suit.J:
                    # 字牌は順子できない
                    return None

                if first.num > 7:
                    # (7 8 9) 以上は順子できない
                    return None

                second = Pai(first.suit, first.num+1)
                third  = Pai(first.suit, first.num+2)

                if tehai.count(first) == 4 or tehai.count(second) == 4 or tehai.count(third) == 4:
                    # 残枚数不足
                    return None

                return [first, second, third]

            def gen_kohtu():
                u'''刻子作る'''
                pai = Pai.from_index(random.choice(range(Pai.TOTAL_KIND_NUM)))
                if tehai.count(pai) >= 2:
                    # 残枚数不足
                    return None
                return [pai, pai, pai]

            def gen_atama():
                u'''雀頭作る'''
                pai = Pai.from_index(random.choice(range(Pai.TOTAL_KIND_NUM)))
                if tehai.count(pai) >= 3:
                    # 残枚数不足
                    return None
                return [pai, pai]

            tehai.extend(gen_atama())   # 雀頭

            # 順子と刻子が同じ出現確率だとアレなので重み付けしておく
            weighted_choices = [(gen_syuntsu, 3), (gen_kohtu, 1)]
            population = [val for val, cnt in weighted_choices for i in range(cnt)]
            while len(tehai) < 14:
                ret = random.choice(population)()
                if ret is not None:
                    tehai.extend(ret)
            return tehai

        @classmethod
        def gen_tenpai(cls):
            u'''適当に聴牌形を作る'''
            tehai = cls.gen_hohra()
            assert(len(tehai) == 14)
            # アガリ形から適当に1個ぶっコ抜く
            tehai.pop(random.randrange(len(tehai)))
            return tehai


    class Test:
        u'''for test'''

        @classmethod
        def check_tenho(cls):
            u'''天和チェック'''
            import sys
            for cnt in (x for x in itertools.count()):
                print >>sys.stderr, cnt
                yama = Yama()
                oya, _, _, _ = yama.haipai()
                ret = check_hohra(oya)
                if ret:
                    print "---------------------------------------------"
                    print cnt
                    oya.show()
                    for atama, mentsu in ret:
                        print atama, mentsu
                    break

        @classmethod
        def check_machi(cls, times = 100):
            u'''待ちを大量にチェック'''
            for x in range(times):
                tehai = Debug.gen_tenpai()
                ret = check_tenpai(tehai.rihai())
                if not ret:
                    # ここに来たらテンパってない。要は不具合。修正対象の手牌。
                    print oya
                    print [ Pai.from_name(repr(x)).index for x in oya ]
            print "complete."


if __name__ == '__main__':
    Test.check_machi()

```

## で、結果は

一応、聴牌形をたくさんチェックかけても取りこぼしはたぶんない…はず。
問題はちゃんと待ちを全部列挙できてるかどうかなんだけど…

けっこう無駄な事やってるので改良の余地はありまくると思う。

なんかバグってたら教えてください。

### 参考までに

純正九蓮宝燈の待ちをチェックかけたらこんな感じ。

1行目が手牌。

2行目以降
`雀頭 面子 待ち`
の形で。

```
[一萬, 一萬, 一萬, 二萬, 三萬, 四萬, 五萬, 六萬, 七萬, 八萬, 九萬, 九萬, 九萬]
() ((一萬, 一萬, 一萬), (三萬, 四萬, 五萬), (六萬, 七萬, 八萬), (九萬, 九萬, 九萬)) (二萬,)
() ((一萬, 一萬, 一萬), (二萬, 三萬, 四萬), (五萬, 六萬, 七萬), (九萬, 九萬, 九萬)) (八萬,)
(九萬, 九萬) ((一萬, 二萬, 三萬), (四萬, 五萬, 六萬), (七萬, 八萬, 九萬)) (一萬, 一萬)
(一萬, 一萬) ((一萬, 二萬, 三萬), (六萬, 七萬, 八萬), (九萬, 九萬, 九萬)) (四萬, 五萬)
(九萬, 九萬) ((一萬, 一萬, 一萬), (二萬, 三萬, 四萬), (五萬, 六萬, 七萬)) (八萬, 九萬)
(九萬, 九萬) ((一萬, 一萬, 一萬), (四萬, 五萬, 六萬), (七萬, 八萬, 九萬)) (二萬, 三萬)
(九萬, 九萬) ((一萬, 一萬, 一萬), (二萬, 三萬, 四萬), (七萬, 八萬, 九萬)) (五萬, 六萬)
(一萬, 一萬) ((三萬, 四萬, 五萬), (六萬, 七萬, 八萬), (九萬, 九萬, 九萬)) (一萬, 二萬)
(一萬, 一萬) ((一萬, 二萬, 三萬), (四萬, 五萬, 六萬), (七萬, 八萬, 九萬)) (九萬, 九萬)
() ((一萬, 一萬, 一萬), (二萬, 三萬, 四萬), (六萬, 七萬, 八萬), (九萬, 九萬, 九萬)) (五萬,)
(一萬, 一萬) ((一萬, 二萬, 三萬), (四萬, 五萬, 六萬), (九萬, 九萬, 九萬)) (七萬, 八萬)
```

これホントに合ってんの？