About
RSS

Bit Focus


麻将听牌算法 [下篇]

Posted at 2014-07-16 05:43:49 | Updated at 2017-12-14 20:32:50

上篇中分析了听牌可能有关字牌的情形, 具体包括字牌中有一个单张, 而剩下的数牌全能构成面子的单骑醒, 或者字牌中有个对子, 而剩下某数牌含有一个对子的双碰型或一个搭子的边/嵌张听牌. 这篇要讨论字牌全是刻子时的类似情况. 之所以说类似是由于此时数牌只可能有以下两种情况
体现成代码就是, 需要解决以下两个函数
def _waits_4groups(tiles):
    # 前略
    # 在前面情况不满足时, 调用如下实现
    return (_detect_numeric_suit_with_one_more(tiles) +
            _detect_2_numeric_suits_with_2_more(tiles))

# 找一个花色, 它的数量模 3 余 1
def _detect_numeric_suit_with_one_more(tiles):
    pass

# 找两个花色, 它们各自的牌的数量模 3 都余 2
def _detect_2_numeric_suits_with_2_more(tiles):
    pass
在上一篇代码的支援下, 后一个函数的实现相对容易一些, 如下
def _detect_2_numeric_suits_with_2_more(tiles):
    # 首先, 跟上节中实现的 _detect_numeric_suit_with_two_more 函数
    # 使用类似的方法, 找出是哪些花色多出两张牌
    mod_numerics = sorted([(i, tiles.numerics[i].total() % 3)
                           for i in xrange(3)], key=lambda k: -k[1])
    if mod_numerics[0][1] != 2 or mod_numerics[1][1] != 2:
        return []

    # 先看看剩下的那个花色是否能恰好完全构成面子, 如果不行, 那么后面也就不用继续了
    group_suit = mod_numerics[2][0]
    completed_groups = _completed_numeric_groups(
        group_suit, tiles.numerics[group_suit].copy_rank()).value()

    if completed_groups is None:
        return []

    # 调用上节实现的 _numeric_suit_with_two_more
    # 分别分析这两个花色的牌
    suit_2more_a, suit_2more_b = mod_numerics[0][0], mod_numerics[1][0]
    waits_a, flag_pair_a = _numeric_suit_with_two_more(
        suit_2more_a, tiles.numerics[suit_2more_a].copy_rank())
    waits_b, flag_pair_b = _numeric_suit_with_two_more(
        suit_2more_b, tiles.numerics[suit_2more_b].copy_rank())

    # 那么, 当其中一个花色有对子时, 另一个花色所缺的牌都是听牌
    # 特别地, 如果两个花色都没有对子, 即 flag_pair_a, flag_pair_b 都是 False 时
    # result 会是空集, 此时没有听牌
    result = []
    if flag_pair_a:
        result.extend(waits_b)
    if flag_pair_b:
        result.extend(waits_a)
    return result
    而 _detect_numeric_suit_with_one_more 会相对麻烦一点, 因为它内部也有单骑 (除了面子多出 1 张) 和一个对子加上一个搭子或对子 (多出 4 张) 两种情况.
    不过为了省代码, 就把这两个情况放一个循环里写了. 下面是实现.
def _detect_numeric_suit_with_one_more(tiles):
    # 先找出数量模 3 余 1 的那个花色, 以及, 看看剩下的两个花色能否都构成面子
    mod_numerics = sorted([(i, tiles.numerics[i].total() % 3)
                           for i in xrange(3)], key=lambda k: -k[1])
    if mod_numerics[0][1] != 1 or mod_numerics[1][1] != 0:
        return []
    suit_one_more = mod_numerics[0][0]
    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 []

    tiles = tiles.numerics[suit_one_more].copy_rank()
    result = []
    for i, c in enumerate(tiles):
        # 如果某个牌至少有一张, 那么假定单骑这张牌; 去掉这一张, 试试剩下的能否全部构成面子
        if c != 0:
            copy_tiles = tiles[:]
            copy_tiles[i] -= 1
            groups = _completed_numeric_groups(suit_one_more, copy_tiles)
            if groups.value() is not None:
                result.append(tile.Tile(suit_one_more, i))

        # 如果某个牌至少有两张, 那么假定该牌是对子
        # 去掉这个对子, 试试剩下的是不是一个搭子或对子加上面子
        if c >= 2:
            copy_tiles = tiles[:]
            copy_tiles[i] -= 2
            result.extend(_numeric_suit_with_two_more(
                suit_one_more, copy_tiles)[0])

    return result
    如此便实现完毕了. 完整的源代码可以在这里看到.

    最后再放上测试代码, 保存为 test.py, 然后使用 python -m unittest test 来执行这些测试.
import unittest

import tile
import waits

# 为了简化手牌信息输入, 这里使用函数将字符串转换为手牌
# 如 123 234 555 11 22
#    前三个是数牌花色, 分别是 123 各一张, 555 各一张, 3 三张
#    第四个是风牌, 11 表示两个东 (2/3/4 则分别表示南/西/北)
#    最后一个是三元牌, 1/2/3 分别表示中/白/发 (其实对于三元牌来说哪个是哪个无所谓了)
#    如果某个位置是一个横线, 则表示该花色没牌
def str2hand_tiles(s):
    suits = s.split(' ')

    tiles = tile.HandTiles()
    for i in xrange(3):
        if suits[i] != '-':
            for s in suits[i]:
                tiles.numerics[i].add_rank(int(s) - 1)

    if suits[3] != '-':
        for s in suits[3]:
            tiles.wind.add_rank(int(s) - 1)

    if suits[4] != '-':
        for s in suits[4]:
            tiles.dragon.add_rank(int(s) - 1)
    return tiles

# 同样为了简化代码, 将字符串变成牌的集合, 各部分与上面的函数意义一致
def str2tile_set(s):
    suits = s.split(' ')
    tiles = set()

    for i in xrange(3):
        if suits[i] != '-':
            for s in suits[i]:
                tiles.add(tile.Tile(i, int(s) - 1))

    if suits[3] != '-':
        for s in suits[3]:
            tiles.add(tile.Tile(tile.WIND_SUIT, int(s) - 1))

    if suits[4] != '-':
        for s in suits[4]:
            tiles.add(tile.Tile(tile.DRAGON_SUIT, int(s) - 1))
    return tiles

NO_TILE = '- - - - -'


class Waits(unittest.TestCase):
    def assertWait(self, hand, waits_):
        self.assertSetEqual(str2tile_set(waits_),
                            waits.waits(str2hand_tiles(hand)))

    def test_13_orphans(self):
        self.assertWait('19 19 1999 123 12', NO_TILE)
        self.assertWait('19 19 199 124 123', '- - - 3 -')
        self.assertWait('19 19 19 1234 123', '19 19 19 1234 123')

    def test_7_pairs(self):
        self.assertWait('11 22 3 1122 1122', '- - 3 - -')
        self.assertWait('112233 111 - 1122 -', '- 1 - 12 -')

    def test_in_one_num_suit(self):
        self.assertWait('1 - - - -', '1 - - - -')
        self.assertWait('1223 - - - -', '2 - - - -')
        self.assertWait('1123 - - - -', '14 - - - -')
        self.assertWait('1233 - - - -', '3 - - - -')
        self.assertWait('2355 - - - -', '14 - - - -')
        self.assertWait('1234 - - - -', '14 - - - -')
        self.assertWait('2345699 - - - -', '147 - - - -')
        self.assertWait('2345678 - - - -', '258 - - - -')
        self.assertWait('2233 - - - -', '23 - - - -')
        self.assertWait('2333 - - - -', '124 - - - -')
        self.assertWait('2233445566 - - - -', '2356 - - - -')
        self.assertWait('2233445566678 - - - -', '23569 - - - -')
        self.assertWait('1112345677889 - - - -', '235689 - - - -')
        self.assertWait('2223333444456 - - - -', '1234567 - - - -')
        self.assertWait('2223456777999 - - - -', '12345678 - - - -')
        self.assertWait('1112345678999 - - - -', '123456789 - - - -')

    def test_in_two_num_suits(self):
        self.assertWait('11 11 - - -', '1 1 - - -')
        self.assertWait('12233 11 - - -', '14 - - - -')
        self.assertWait('11 23 - - -', '- 14 - - -')
        self.assertWait('11 13 - - -', '- 2 - - -')
        self.assertWait('23456 11 - - -', '147 - - - -')
        self.assertWait('11123 11123 - - -', '14 14 - - -')
        self.assertWait('23 13 - - -', NO_TILE)
        self.assertWait('11 11234567 - 111 -', '1 1 - - -')
        self.assertWait('11 11123456 - 111 -', '1 147 - - -')
        self.assertWait('11 11123 - 111222 -', '1 14 - - -')

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