About
RSS

Bit Focus


麻将听牌算法 [上篇]

Posted at 2014-07-02 10:13:02 | Updated at 2017-12-14 20:34:59

    作为一个人类经常在打清一色的时候望着手牌不知道听牌没不知道听了哪几张也不知道切哪一张会让听牌数量最大化是一件不愉快的事情, 除了九莲宝灯之类的定式役给背下来好像没别的有效方法. 或者, 写个程序来搞吧.
    首先是数据结构, 这里用如下类来描述
# tile.py

# 牌
class Tile(object):
    def __init__(self, suit, rank):
        self.suit = suit # 花色: 用 0, 1, 2, 3, 4 表示
                         # 其中 0-2 是数牌 3 是风牌 4 是三元牌
        self.rank = rank # 数值: 对于数牌范围是 0-8 风牌范围 0-3 三元牌范围 0-2

    def __eq__(self, rhs):
        return self.suit == rhs.suit and self.rank == rhs.rank

    # 为了能让这东西被放进 set
    def __hash__(self):
        return hash(self.suit) * hash(self.rank)

    # 直观显示
    def __repr__(self):
        return (self.suit, self.rank + 1).__repr__()

# 一个花色里的牌
class TilesSuite(object):
    def __init__(self, count, suit):
        # 这个数字表示个数
        # 比如手牌是 2 个二万 3 个三万, 那么这个数组会是 [0, 2, 3, 0, 0, 0, 0, 0, 0]
        self.rank_count = [0] * count
        self.suit = suit

    def count(self, rank):
        return self.rank_count[rank]

    # 摸上来一张牌
    def add_rank(self, rank):
        self.rank_count[rank] += 1

    # 打出一张牌
    def remove_rank(self, rank):
        self.rank_count[rank] -= 1

    def copy_rank(self):
        return self.rank_count[:]

    # 去掉所有为 0 的项目, 返回一个元素结构为
    #    (牌, 数量)
    # 元组的列表
    def list_tiles(self):
        return [(Tile(self.suit, i), e)
                for i, e in enumerate(self.rank_count) if e != 0]

    # 这个花色下总共有几张牌
    def total(self):
        return sum(self.rank_count)

WIND_SUIT = 3   # 如之前提到的, 风牌的花色值为 3
DRAGON_SUIT = 4 #             三元牌的花色值为 4

# 一副手牌
class HandTiles(object):
    def __init__(self):
        # 三种数牌个数量分布
        self.numerics = [TilesSuite(9, i) for i in xrange(3)]
        # 风牌的数量分布
        self.wind = TilesSuite(4, WIND_SUIT)
        # 三元牌的数量分布
        self.dragon = TilesSuite(3, DRAGON_SUIT)

    def total(self):
        return (sum([self.numerics[i].total() for i in xrange(3)]) +
                self.wind.total() + self.dragon.total())

    def list_tiles(self):
        return (sum([self.numerics[i].list_tiles() for i in xrange(3)], []) +
                self.wind.list_tiles() + self.dragon.list_tiles())
    (有关的翻译部分参考这里, 以及维基百科英文)
    在只处理听牌时, 以上结构中的风牌和三元牌其实可以合并到一起, 但若要处理和牌后的役还是暂且分开了.

    下面按日麻规则会处理三种截然不同的牌型听牌: 标准的 4 面子 1 对子; 七对子; 国士無双. 这三种情况应该分成三个对应的函数, 下面来起个头.
# waits.py

def waits(tiles):
    return set(_waits_13(tiles) + _waits_7pairs(tiles) + _waits_4groups(tiles))

# 国士 13 面听的全部牌, 容我写死在这里
_13_ORPHANS_WAITS = (
    [tile.Tile(0, 0), tile.Tile(0, 8), tile.Tile(1, 0), tile.Tile(1, 8),
     tile.Tile(2, 0), tile.Tile(2, 8)] +
    [tile.Tile(tile.WIND_SUIT, i) for i in xrange(4)] +
    [tile.Tile(tile.DRAGON_SUIT, i) for i in xrange(3)])

def _waits_13(tiles):
    if tiles.total() != 13:
        return []

    # 将手牌里的 13 种幺九字牌弄出来
    # 组成一个元素结构为
    #    (牌, 数量)
    # 元组的列表, 并对这个列表进行排序, 排序的键是上述元组中的 "数量"
    orphans = sorted(
        [(tile.Tile(s, 0), s.count(0)) for s in tiles.numerics] +
        [(tile.Tile(s, 8), s.count(8)) for s in tiles.numerics] +
        [(tile.Tile(tile.WIND_SUIT, i), tiles.wind.count(i))
         for i in xrange(4)] +
        [(tile.Tile(tile.DRAGON_SUIT, i), tiles.dragon.count(i))
         for i in xrange(3)], key=lambda k: k[1])
    # 如果这个列表开头两项的数量都为 0 (因为排序了所以只要看第二项是不是 0) 肯定不是国士听牌
    if orphans[1][1] == 0:
        return []
    # 而如果第一项的数量就是 1 那么一定就是 13 面听了
    if orphans[0][1] == 1:
        return _13_ORPHANS_WAITS
    # 否则听的牌就是缺的那个
    return [orphans[0][0]]

def _waits_7pairs(tiles):
    if tiles.total() != 13:
        return []
    # 列出当前所有牌以及该牌的数量
    tiles_list = tiles.list_tiles()

    # 如果牌的种类大于 7 肯定不是七对子听牌
    # 一般的日麻规则中不允许七对子出现两个相同的对子, 若按照这个规则此处判断应该是严格等于 7,
    if 7 < len(tiles_list):
        return []

    # 如果数量为奇数的牌恰好 1 个就是七对子听牌
    odds = [t[0] for t in tiles_list if t[1] % 2 == 1]
    return odds if len(odds) == 1 else []

def _waits_4groups(tiles):
    pass
    最后的 4 面子 1 对子听牌判定就稍复杂, 情况比较多. 从字牌的数量状况下手比较容易理清头绪. 考虑到听牌时, 如果字牌不是恰好全是刻子, 那么只有下面两种情况
从这个角度出发还有个好处, 在开局手牌比较乱的情况下, 先处理字牌有利于直接判定某个手牌形式根本没有听牌 (比如字牌中有两张单的, 或一个对子一张单的), 那样就不用去分解数牌了.
    废话不多说了, 实现如下
def _wind_dragon_groups(tiles):
    # 按照 (牌, 数量) 的方式列出全部字牌
    tiles_list = tiles.wind.list_tiles() + tiles.dragon.list_tiles()
    if len(tiles_list) == 0:
        return [], [], []
    singles = [t for t in tiles_list if t[1] == 1]
    pairs = [t for t in tiles_list if t[1] == 2]
    triplets = [t for t in tiles_list if t[1] == 3]
    quads = [t for t in tiles_list if t[1] == 4]
    # 如刚才所说 4 张牌被认为是 1 个刻子加上 1 个单张, 所以 quads 也会被加进 triplets 和 singles 中
    return triplets + quads, pairs, singles + quads

def _waits_4groups(tiles):
    triplets, pairs, singles = _wind_dragon_groups(tiles)
    if pairs and singles: # 同时有单张和对子, 没听牌
        return []
    if 1 == len(singles): # 字牌单骑, 如果剩下的数牌都能拆解成面子, 那么听牌就是被单骑的那个
        groups = _detect_completed_numeric_groups(tiles)
        return [] if groups is None else [singles[0][0]]
    if 2 == len(pairs): # 字牌里有两个对子, 如果剩下的数牌都能拆解成面子, 那么就是双碰听牌
        groups = _detect_completed_numeric_groups(tiles) # 见下方
        return [] if groups is None else [pairs[0][0], pairs[1][0]]
    if 1 == len(pairs): # 有一个对子, 如果剩下有某一个数牌能被拆解成面子 + 1 个搭子 / 1 个对子, 那么就能听牌
        waits, pair_wait = _detect_numeric_suit_with_two_more(tiles) # 见下方
        if len(waits) == 0:
            return []
        if pair_wait:
            waits.append(pairs[0][0])
        return waits
    # 字牌全是刻子或没有字牌的情况

# 这个函数用于检测是不是剩下的所有数牌都可以被分解成面子, 这是下一节的课题
# 如果可以, 那么这个函数会返回所有的面子列表; 否则会返回 None
def _detect_completed_numeric_groups(tiles):
    pass

# 这个函数用于检测手牌中是否两个花色都能被拆解成面子
# 而另一个花色的牌去掉一个搭子或去掉一个对子之后也能全部拆解成面子
# 这个函数返回 2 个值, 分别是
#    若拆解成功, 返回搭子所缺的牌的列表 (空列表表示拆解失败)
#    若拆解成功, 返回去掉一个对子后是否能完全拆解为面子
def _detect_numeric_suit_with_two_more(tiles):
    pass
    具体说一下 if 1 == len(pairs) 这个分支要做的事情. 分支第一句话会得到一个二元组 waits, pair_wait, 根据下面计划会实现的函数的描述, waits 表示这个花色中除了面子剩下的搭子缺什么, 那么缺什么就会听什么; 还有一种情况, 就是 pair_wait 是真, 也就是说可能这是个双碰听牌, 这样的话该字牌对子本身也是所听的牌之一. 具体的例子如
这个分支也就是在以上情况中选择是否将字牌加入所听的牌的列表中.

    而无论是实现 _detect_completed_numeric_groups 还是 _detect_numeric_suit_with_two_more 都依赖于一个算法: 将数牌拆解成面子. 实现这个函数之前先弄几个类似 list 的数据结构, 用于混合正常返回和错误返回. (虽然这并不是最好的设计)
# group.py

class Group(object):
    pass

# 顺子
class Sequence(Group):
    def __init__(self, suit, starting_rank):
        self.suit = suit
        self.starting_rank = starting_rank

# 刻子
class Triplet(Group):
    def __init__(self, suit, rank):
        self.suit = suit
        self.rank = rank

# 没有分组, 此类的实例表示错误的返回值
class NoGroup(object):
    def value(self):
        return None # 这个特殊的返回值将会作为标记使用

    def __add__(self, rhs):
        return self

    def append_group(self, group):
        return self

# 分组, 此类的实例就是面子分组列表
class Groups(list, NoGroup):
    def __init__(self, value=None):
        list.__init__(self, value or [])

    def value(self):
        return self

    def __add__(self, rhs):
        if type(rhs) is NoGroup: # 如果加上错误值则为错误值
            return NoGroup()
        return Groups(list.__add__(self, rhs))

    def append_group(self, group):
        self.append(group)
        return self
    那么接下来就是分组函数了. 返回值是上面的 NoGroup 实例, 或它子类 Groups 的实例.
def _completed_numeric_groups(suit, suit_tiles):
    for i, c in enumerate(suit_tiles):
        if c != 0:
            first_rank = i # 找到该花色下序数最小的一张牌, 记下它的序数
            break
    else:
        return group.Groups() # 如果该花色下已经没牌了, 那么分组有效, 只不过是空的

    # 因为此时该牌序数最小, 如果此牌数量不小于 3, 那么肯定最终会被分解成刻子
    # 或者是三个相同的顺子, 但这种情况被分解成三连刻也没有问题
    if suit_tiles[first_rank] >= 3:
        tri = group.Triplet(suit, first_rank)
        suit_tiles[first_rank] -= 3 # 将这个刻子独立出来, 剩下地牌递归处理
        return _completed_numeric_groups(suit, suit_tiles).append_group(tri)

    # 如果序数最小的牌不形成刻子, 那么以下情况不可能组成合理的顺子
    #    这个牌序数太靠后 (>6)
    #    序数比此牌大 1 或大 2 的牌的数量少于此牌
    if (first_rank > 6 or suit_tiles[first_rank] > suit_tiles[first_rank + 1]
            or suit_tiles[first_rank] > suit_tiles[first_rank + 2]):
        return group.NoGroup()

    # 如果满足组成顺子的条件, 那么将构成这些顺子的牌给扣除, 剩下的牌再递归处理
    seqs = [group.Sequence(suit, first_rank)
            for _ in xrange(suit_tiles[first_rank])]
    suit_tiles[first_rank + 1] -= suit_tiles[first_rank]
    suit_tiles[first_rank + 2] -= suit_tiles[first_rank]
    suit_tiles[first_rank] = 0
    return _completed_numeric_groups(suit, suit_tiles) + seqs
    有了以上实现, 那么检测 3 种花色是否都各自形成面子就很容易了
def _detect_completed_numeric_groups(tiles):
    for i in xrange(3):
        if tiles.numerics[i].total() % 3 != 0:
            return None
    return sum([_completed_numeric_groups(i, tiles.numerics[i].copy_rank())
                for i in xrange(3)], group.Groups()).value()
    而检测某个花色多出来两个, 剩余两个花色全是面子则会繁琐许多
def _detect_numeric_suit_with_two_more(tiles):
    # 首先得判断到底是哪个花色多出两个
    mod_numerics = sorted([(i, tiles.numerics[i].total() % 3)
                           for i in xrange(3)], key=lambda k: -k[1])
    # 将 (花色 ID, 该花色牌的数量对 3 取模) 这个元组序列按 "模 3 的余数" 进行排序
    # 如果满足前提, 那么当然第一个值的余数是 2, 而后两个都是 0
    if mod_numerics[0][1] != 2 or mod_numerics[1][1] != 0:
        return [], False

    # 然后先检测这两个花色是不是恰好都能分解成面子, 如果不是, 那么也就没有继续下去的必要了
    group_suit_a, group_suit_b = mod_numerics[1][0], mod_numerics[2][0]
    completed_groups = (
        _completed_numeric_groups(
            group_suit_a, tiles.numerics[group_suit_a].copy_rank()) +
        _completed_numeric_groups(
            group_suit_b, tiles.numerics[group_suit_b].copy_rank())
    ).value()

    if completed_groups is None:
        return [], False

    # 下面会有一堆函数涵盖在一个花色多出 2 张牌时的各种情况
    suit_two_more = mod_numerics[0][0]
    return _numeric_suit_with_two_more(
        suit_two_more, tiles.numerics[suit_two_more].copy_rank())

def _numeric_suit_with_two_more(suit, tiles):
    # 如果多出来的是对子
    result = [tile.Tile(suit, pair_rank) for pair_rank, groups in
              _numeric_groups_with_pair(suit, tiles[:])]
    flag_pair = len(result) != 0 # 记得设置对子 flag

    # 如果多出来的是两面搭子
    for starting_rank, groups in _numeric_groups_with_side_waits(
            suit, tiles[:]):
        if starting_rank != 0:
            result.append(tile.Tile(suit, starting_rank - 1))
        if starting_rank != 7:
            result.append(tile.Tile(suit, starting_rank + 2))

    # 如果多出来的是嵌张
    result.extend([
        tile.Tile(suit, staring_rank + 1)
        for staring_rank, groups in _numeric_groups_with_middle_waits(
            suit, tiles[:])])

    return result, flag_pair

def _numeric_groups_with_pair(suit, suit_tiles):
    result = []
    for i, c in enumerate(suit_tiles):
        # 找到一个对子, 去掉它, 试试剩下的能不能全凑成面子
        if c >= 2:
            copy_tiles = suit_tiles[:]
            copy_tiles[i] -= 2
            groups = _completed_numeric_groups(suit, copy_tiles)
            if groups.value() is not None:
                result.append((i, groups))
    return result

def _numeric_groups_with_side_waits(suit, suit_tiles):
    result = []
    for i in xrange(8):
        # 找出一个搭子, 去掉之后试试剩下的能不能全凑成面子
        if suit_tiles[i] and suit_tiles[i + 1]:
            copy_tiles = suit_tiles[:]
            copy_tiles[i] -= 1
            copy_tiles[i + 1] -= 1
            groups = _completed_numeric_groups(suit, copy_tiles)
            if groups.value() is not None:
                result.append((i, groups))
    return result

def _numeric_groups_with_middle_waits(suit, suit_tiles):
    result = []
    for i in xrange(7):
        # 找出一个两坎, 去掉之后试试剩下的能不能全凑成面子
        if suit_tiles[i] and suit_tiles[i + 2]:
            copy_tiles = suit_tiles[:]
            copy_tiles[i] -= 1
            copy_tiles[i + 2] -= 1
            groups = _completed_numeric_groups(suit, copy_tiles)
            if groups.value() is not None:
                result.append((i, groups))
    return result
    最后的各个函数返回值类型均为元素结构为 (对子或搭子首张序数, 面子分组) 的列表.

    这样所有听牌与字牌可能相关的情况讨论完毕. 而无字牌或字牌全为刻子的情况则会在下篇中讨论.

Post tags:   麻将  Algorithm  Python

Leave a comment:




Creative Commons License Your comment will be licensed under
CC-NC-ND 3.0


. Back to Bit Focus
NijiPress - Copyright (C) Neuron Teckid @ Bit Focus
About this site