基础知识

本文涉及的所有名词均在博文中有说明： http://blog.csdn.net/kunyus/article/details/78644517

测试结果

测试环境:

MEM: 4 GB
CPU: Intel(R) Xeon(R) CPU E3-1231 v3 @ 3.40GHz
虚拟机软件: Oracle VM VirtualBox
测试机操作系统: Microsoft Windows 7 旗舰版(SP1)

测试结果

• 带胡牌规则测试结果效率差本人猜测和 Golang 接口类型的实现方式有关.

• 因为胡牌规则回调无逻辑直接返回 nil 时测试结果也在 120w 数量级.(模拟数据)

  无中间表纯拆牌(单一数据): 1s >= 700w
  带中间表完整算法(单一数据): 1s >= 450w
  带基础胡牌规则回调(单一数据): 1s >= 150w

  无中间表纯拆牌(模拟数据): 1s >= 450w
  带中间表完整算法(模拟数据): 1s >= 340w
  带基础胡牌规则回调(模拟数据): 1s >= 120w

核心思想

本算法分为两部分, 第一部分通过算法负责拆牌, 第二部分负责解析胡牌规则

1. 去伪存真: 满足胡牌的部分, 要么是 {3*n}(不带将), 要么是 {3*n+2}(带将).

2. 端本正源: 麻将牌胡牌(除特殊规则)和牌面没有直接关系, 只和数量以及所处位置(顺子)相关.

3. 去粗取精: 麻将牌所有组合中, 只有顺子和其他牌有关联关系,且关系只存在于相连的两张牌中.

4. 各司其职: 实现中胡牌规则和基础算法分离已保证算法的精简.此处实现通过事件触发方式隔离.

通用拆牌算法

生成中间表

1. 将序数牌按花色以及牌个数进行归表并记录表中牌的总个数.

   此处用万举例, 其他花色结果一样:

   • 手牌 万: 1-9 各一张, 此时表内容应为: 111111111(9)
   • 手牌 万: 11 22 333 4 5 6 77 88, 此时表内容应为: 2231112200(14)

2. 将字牌按牌个数进行归表并记录表中牌的总个数, 相邻牌用 0 隔开.

   如: 东风 南风 西风 北风 红中 发财 白板, 表内容: 1010101010101(7)

3. 任意表中牌个数出现不满足 {3*n} 且不满足 {3*n+2} 的, 直接判定无法胡牌.

Golang 实现代码 :

// 0x01 - 0x09 - 筒
// 0x11 - 0x19 - 万
// 0x21 - 0x29 - 条
// 0x31 0x33 0x35 - 中发白
// 0x41 0x43 0x45 0x47 - 东南西北

func MarshalTiles(tiles []byte, filter MarshalFilter) (err error) {
    var mtables [5]struct {
        Count int
        Tiles [9]uint16
    }

    for _, tile := range tiles {
        group := uint16(tile) / 0x10

        if int(group+1) > len(mtables) {
            return errors.New("unrecognized type " + strconv.Itoa(int(group)) + " of tile")
        }

        index := uint16(tile) % 0x10 - 1

        if int(index) > (len(mtables[group].Tiles) - 1) {
            return errors.New("unrecognized tile " + strconv.Itoa(int(tile)))
        }

        mtables[group].Count++
        mtables[group].Tiles[index]++

        if mtables[group].Tiles[index] > 4 {
            return errors.New("abnormal number " + strconv.Itoa(int(mtables[group].Tiles[index])) + " of tile " + strconv.Itoa(int(tile)))
        }
    }

    for group, slice := range mtables {
        if 0 == slice.Count {
            continue
        }

        rest := slice.Count % 3 

        if 0 != rest && 2 != rest {
            return errors.New("slice length " + strconv.Itoa(int(slice.Count)) + " check does not pass")
        }


        if err := marshalSlice(group, slice.Tiles[:], filter); nil != err {
            return err
        }
    }

    if err := filter.OnComplete(); nil != err {
        return err
    }

    return nil
}

处理中间表

1. 分别对生成的中间表进行正向遍历, 并分别进行 2 - 6 步处理.

2. 当前位是否为 0, 为 0 直接跳到下一个继续处理.

3. 当前值是否为 1 且表长度大于 3, 满足分别对当前值和后两个值减 1 , 出现负数无法胡牌.

4. 当前位是否为 2, 满足将其视为刻子, 值改 0, 跳到下一个继续处理

5. 当前位是否为 3 , 满足将值改为 1 跳到步骤 2 处理, 处理失败无法胡牌.

6. 当前位是否为 4, 满足将值改为 1 跳到步骤 2 处理, 处理失败将值改为 1 跳到步骤 2 处理, 处理失败无法胡牌.

Golang 实现代码 :

type MeldType int

const (
    MeldPair MeldType = 1
    MeldTriplet MeldType = 2
    MeldSequence MeldType = 3
)

type MarshalFilter interface {
    OnComplete() (error)

    OnMeld(group int, index int, mtype MeldType) (error)
}

func marshalSlice(group int, slice []uint16, filter MarshalFilter) (error){
    sliceSize := len(slice)

    if nil == filter {
        tmp := make([]uint16, sliceSize)
        copy(tmp, slice)
        slice = tmp
    }

    for index, tile := range slice {
        for {
            if 0 == tile {
                break
            }

            var meldType MeldType

            switch(tile){
            case 0:
                break
            case 1:
                if (sliceSize - index) < 3 {
                    return errors.New("failed to remove sequence, slice length is not enough")
                } else if slice[index + 1] < 1 || slice[index + 2] < 1 {
                    return errors.New("failed to remove sequence, continuous tile does not exist")
                }

                tile = 0
                slice[index + 1]--
                slice[index + 2]--

                meldType = MeldSequence
            case 2:
                tile = 0
                meldType = MeldPair
            case 3:
                if ((sliceSize - index) > 3 && 4 == slice[index + 3]) { // 拆 3 拆 4 皆可时, 优先拆 4
                    tile = 0
                    meldType = MeldTriplet
                    break
                } 

                slice[index] = 1
                if err := marshalSlice(group, slice[index:], nil); nil == err { // 尝试拆 顺子
                    tile = 1
                    meldType = MeldPair
                } else {
                    tile = 0
                    meldType = MeldTriplet
                }

            case 4:
                slice[index] = 1
                if err := marshalSlice(group, slice[index:], nil); nil == err { // 尝试拆 顺子
                    tile = 1
                    meldType = MeldTriplet
                } else { // 拆成两个对子
                    tile = 2
                    meldType = MeldPair
                }
            }

            if nil == filter {
                continue
            }

            if err := filter.OnMeld(group, index, meldType); nil != err {
                return err
            }
        }

    }

    return nil
}

胡牌规则处理

拆牌算法在进行拆牌时会将所有数量为 2 的牌视为 对子, 这种情况在出现连续的 3 个 对子 时不满足基础胡法. 所以在基础胡法回调中会对 对子 进行特殊处理, 将连续的 3 个 对子 更新为顺子.

• 此代码仅做 demo 使用, 里面有无用代码, 使用时请酌量删除.

Golang 实现代码 :

type BaseMarshalFilter struct {
    MeldCount [4]int
    Melds [4][5][9]int
}

func NewBaseMarshalFilter() (MarshalFilter){
    return &BaseMarshalFilter{
    }
}

func (b *BaseMarshalFilter) OnComplete() (error) {
    if b.MeldCount[MeldPair] != 1 {
        return errors.New("the number of eyes " + strconv.Itoa(b.MeldCount[MeldPair]) + " too much")
    }

    return nil
}

func (b *BaseMarshalFilter) OnMeld(group int, index int, mtype MeldType) (error) {
    if MeldPair == mtype && index >= 2 && b.MeldCount[MeldPair] >= 2 {
        if b.Melds[MeldPair][group][index - 1] >= 1 && b.Melds[MeldPair][group][index - 2] >= 1 {
            b.MeldCount[MeldPair] -= 2

            b.Melds[MeldPair][group][index-1]--
            b.Melds[MeldPair][group][index-2]--

            mtype = MeldSequence

            b.MeldCount[mtype]++
            b.Melds[mtype][group][index]++
        }
    }

    b.MeldCount[mtype]++
    b.Melds[mtype][group][index]++

    return nil
}

调用方式

        tiles := []byte{0x03, 0x03, 0x03, 0x03, 0x04, 0x05, 0x13, 0x13,  0x14,  0x15,  0x16, 0x27, 0x27, 0x27}
        if err := MarshalTiles(tiles, NewBaseMarshalFilter()); nil != err {
            print_tiles(tiles, 0, 0, err)
        }