高性能麻将AI算法

想要一个高性能的麻将AI算法，这个问题我们拆解成2个子集来思考，“高性能”，“麻将AI算法”，我们先针对麻将AI算法来讨论。

• 麻将AI
  “麻将AI”，什么样的才叫AI，在很多项目中，并不严格要求可以与人类顶尖高手pk能力的AI，而是麻将选手陪玩机器人，基本做到一般人类选手的水平。那么这个问题我们可以继续修改“一般能力麻将AI”。
  现在我们来继续分解这个“一般能力麻将AI”，我们可以把这个AI变成”一个不懂得算桌子上牌，只会盯着自己牌的选手，然后可以得出我打出哪张牌后，我胡牌几率最大的人”。
  根据上篇的，麻将胡牌算法我们可以得出，如果想得出“胡牌”的概念可以用得到3N的牌面以及3N+2的说法替代。所以这个时候问题变成“只会盯着自己牌的选手，针对同一种花色，计算出这个花色的牌打出一张后，变成3N或者3N+2的几率多大”。
  此时就有一个问题了，针对一种花色在很多牌面中，我打出一张牌的张数并不是3N或者3N+2，这个时候怎么办？这里可以用到一个近似解，“在某个特定的array中，我需要补多少张，才可以得到3N或者3N+2的组合”，为了简单说明起见，后续只说明如何构造3N的牌型。
  这个时候还剩下最后一个问题了，概率问题如何结算，这个可以通过回溯来求去最大解，来了牌值大小为1到9的一个集合，每次抽取1张，然后可以构成3N，需要抽取多轮。这个就是个9叉树，然后通过一定的剪枝手段来控制树的总大小。伪代码如下

// array 表示手牌，level代表补的张数 
// 1/chance表示概率,所以chance表示为概率的倒数
// chance = chance * 136 / 4。表示136张牌中来这张牌概率，这里可以优化下改成当前
// 牌里剩下的张数在出于牌堆总数，这里为了表达方便，直接用 136 / 4，可以优化这个常量，
// 比如，136按照扣除自己手牌数136-13*4计算，
//4可以用 4-自己手牌的张数这个数来替代，这样AI就是个会算自己手牌
// 的机器人了，不会导致说自己手牌中有4个一万，还是来一万胡牌概率高的情况
//发生了，如果优化136 / 4 这个常量，会针对不可能不到的情况，会剪枝了，也减少会一定的运算。

//计算牌的概率
getchance(array,level,chance)
//大于等于6一定要剪枝，不可能需要大于6的情况存在，补的最多的6张，要只有 1 3 7 这种情况
    if(level >= 6) return MAX 
   if check3N(array) return chance
    for i =1 to 9
        array[i] = array[i]+1
        //这里check3N直接用上篇用工具生成的3N的hash表来查询，所以本质是个O(1)的操作
        if array[i] <= 4
            if check3N(array)
                chance = chance * 4/136
                //如果优化修改4/136 这个常量，需要求去1到9中值的最大概率
                return chance
            else
                chance = dfs(array,level+1,chance)
        array[i] = array[i]-1
        return chance

//生成概率data
gen_chance()
    //定义array
    for j=1 to 4
        for i=1 to 9
            array[i] = array[i] + 1
            chance = getchance(array)
            print chance // 这里可以把array的key以及概率写入data文件

计算3N2的概率，只需要把上述代码中check3N改成check3N2即可。

下面给出会计算getchance的优化版本，可以算自己手牌了。

//计算牌的概率
getchance(array,level,chance)
    //大于等于6一定要剪枝，不可能需要大于6的情况存在，补的最多的6张，要只有 1 3 7 这种情况
    if(level >= 6) return MAX 
   if check3N(array) return 1,0 //表示该组合已经是3N了，不需要打出牌
    //定义
    maxchance = 0 
    for i =1 to 9
        left = 4 - array[i] 
        array[i] = array[i]+1
        //这里check3N直接用上篇用工具生成的3N的hash表来查询，所以本质是个O(1)的操作
        //上述算法中的136 这个稍微准确点改成83稍微更准确点，136-13*3-14 = 83，这个值只会小于83的，但是不论136
        //还是83都不影响本质
        if array[i] <= 4
            if check3N(array) AND left > 0
                chance = chance * left/83
                if chance > maxchance
                    maxchance = chance
            else
                chance = dfs(array,level+1,chance* left/83)
                if chance > maxchance
                    maxchance = chance
        array[i] = array[i]+1

    return maxchance

left还剩几张可以提供给我，这里没计算别人打出去的牌
这个也是此算法不够智能的地方，因为别人打出去的牌是动态的，事先生成data只能看静态数据，这样可以选取一张打出去某张牌，获取胡牌概率可以做到O(1)。
如果想智能高一点，可以服务器运行过程中跑这个算法，动态的计算出left以及83这个常量，就更能准确的提高AI智能了，但是换来了，服务器计算资源的牺牲，确实没有两全起美的办法。

• 高性能
  上述的代码中已经给我们生成好了组成当前牌组成3N以及3N2的概率的data，当服务器启动时，就可以把data读入内存，构建hash表。
  服务器判定到底出那张的伪代码如下

//针对同一种花色的数组中，计算出打出某一张牌可以得到3n 以及3n2的最大概率
outcard(array)
    //定义最大3n概率以及最大概率下应出的牌 max3nchance  max3n_i
    //定义最大3n2概率以及最大概率下应出的牌 max3n2chance max3n2_i
    for i=1 to 9
        if array[i] > 0
            array[i] = array[i]  - 1 //先扣掉出的牌
            //获取当前花色的牌构建出3n的概率 直接从上述代码data文件中的哈希表查询
            chance3n = get3nchace(array)    
            if chance3n > max3nchance
                max3nchance = chance3n
                max3n_i = i
            //获取当前花色的牌构建出3n2的概率 直接从上述代码data文件中的哈希表查询
            chance3n2 = get3n2chace(array)  
            if chance3n2 > max3n2chance
                max3n2chance = chance3n2
                max3n_i = i
            array[i] = array[i]  + 1 //恢复

        return max3nchance,max3n_i,max3n2chance,max3n2_i

最终计算胡牌，计算出选取一个3n2以及剩下花色3n的总体概率最大值即可，此时就找到了应该打出哪一张牌，其实针对碰杠吃的做法也一样
碰了后能不能让我赢面最大，只是这里扣除一张牌，改成扣除碰的牌来判断而已。
此时麻将AI已经有了非常高的性能以及智能，几乎模拟了“一个会算自己手牌，但是不会看桌子上牌的”人类玩家。
因为很多项目中，对性能要求很高，并不是1V1的AI，可能需要几万个AI陪玩机器人来陪玩，所以高性能是必须的。