用代码破解斗地主残局

相信大家都玩过斗地主，规则就不再介绍了。

直接上一张朋友圈看到的残局图：斗地主残局

这道题我刚看到时，曾尝试用手工来破解，每次都以为找到了农民的必胜策略时，最后都发现其实农民跑不掉。由于手工破解无法穷尽所有可能性，所以这道题究竟农民有没有妙手跑掉呢，只能通过代码来帮助我们运算了。

本文将简要讲述怎么通过代码来求解此类问题，在最后会公布残局的最后结果，并开源代码以供大家吐槽。

minimax

代码的核心思想是minimax。minimax可以拆解为两部分，mini和max，分别是最小和最大的意思。

直观的理解是什么呢？就有点像A、B两个人下棋。A现在可以在N个点走棋，假设A在某个点走棋了，使得A的这一步的盘面评估分数最高；但是轮到B下的时候，就一定会朝着让A最不利的方向走，使得A的下一步必然按照B设定的轨迹来，而没法达到A在第一步时估算到这一步的最高盘面评分。

在牌局中是一样的，如果农民的一手牌，让地主无论如何应对都不能赢的话，那么可以说农民有必胜策略；否则，农民必输。

核心逻辑

我们可以用一个函数hand_out来模拟一个人的出牌过程。在现实生活中，一个人想要出牌的话，必然需要知道自己手上的所有牌：me_pokers，也需要知道上一手的出的牌：last_hand。如果我们要用这个函数来模拟两个人的出牌，则还需要知道对手当前的所有牌：enemy_pokers。

这个函数的返回值，是轮到我me_pokers出牌时，是否能够必赢牌。如果能赢则返回真，否则返回假。

def hand_out(me_pokers, enemy_pokers, last_hand)

假设轮到我出牌时，如果我手上的牌都出完了，那么我将立刻知道我赢了；反之如果对手的牌都出完了，而我没有，则我失败了。

if not me_pokers:
    return True
if not enemy_pokers:
    return False

因为现在轮到我出牌，所以我首先需要知道我现在能出的所有手牌组合。注意：这个组合中，包括过牌（即不出牌）的策略。

all_hands = get_all_hands(me_pokers)

现在我们要对所有可能的手牌组合进行遍历。

首先我需要知道，上一手对方出的牌是什么。

如果对方上一手选择过牌，或者没有上一手牌，那么我这一轮必须不能过牌，但是我可以出任意的牌
如果对手上一手出了牌，则我必须要出一个比它更大的牌或者选择这一轮直接过牌（不出牌）

关键点来了，在出完我的牌或选择过牌后，我们需要用一个递归调用来模拟对手下一步的行为。如果对手的下一次出牌不能获胜的话，则我这一次的出牌必胜；否则，对于我的每一个出牌选择，对手都能获胜的话，则我必败。

全部代码如下：

def hand_out(me_pokers, enemy_pokers, last_hand, cache):
    if not me_pokers:
        # 我全部过牌，直接获胜
        return True
    if not enemy_pokers:
        # 对手全部过牌，我失败
        return False
    # 获取我当前可以出的所有手牌组合，包括过牌
    all_hands = get_all_hands(me_pokers)
    # 遍历我的所有出牌组合，进行模拟出牌
    for hand in all_hands:
        # 如果上一轮对手出了牌，则这一轮我必须要出比对手更大的牌 或者 对手上一轮选择过牌，那么我只需出任意牌，但是不能过牌
        if (last_hand and can_comb2_beat_comb1(last_hand, hand)) or (not last_hand and hand['type'] != COMB_TYPE.PASS):
            # 模拟对手出牌，如果对手不能取胜，则我必胜
            if not hand_out(enemy_pokers, make_hand(me_pokers, hand), hand, cache):
                return True
        # 如果上一轮对手出了牌，但我这一轮选择过牌
        elif last_hand and hand['type'] == COMB_TYPE.PASS:
            # 模拟对手出牌，如果对手不能取胜，则我必胜
            if not hand_out(enemy_pokers, me_pokers, None, cache):
                return True
    # 如果之前的所有出牌组合均不能必胜，则我必败
    return False

构建

以上核心逻辑理清楚后，构建破解器将变得十分简单。

首先，我们要用数字来表示牌的大小，这里我们用3表示3，11来表示J，12表示Q，依次类推……

其次，我们需要求出一个手牌的所有出牌组合，这里需要get_all_hands函数，具体实现比较繁琐但是很简单，就不在此赘述。

然后，我们还需要一个牌力判断函数can_comb2_beat_comb1(comb1, comb2)，这个函数用于比较两组手牌的牌力，看是否comb2可以击败comb1。唯一需要注意的一点，在斗地主的规则中，除了炸弹外，其他所有牌力均等，只有牌型一样时才能去比较。

最后，我们需要一个模拟出牌函数make_hand(pokers, hand)，用于求出在手牌为pokers的情况下打出一手牌hand后，剩下的手牌，实现也非常简单，只需简单的移除掉那些打出的牌即可。

效率

由于一副牌的可能手牌巨大，导致递归的分支数巨大。所以时间开销非常大，为阶乘级O(N!)，根据斯特林公式，大约为O(N^N)。

由于可能会有很多重复的牌面出现，导致了很多重复的递归调用。所以加一个缓存能极大提升效率。

即对我方手牌和敌方手牌和上一轮手牌的描述（str(me_pokers)+str(enemy_pokers)+str(last_hand)）为键，将求出的结果存进缓存字典中。下一次遇到相同的局面时，即可直接从缓存字典中取出，而无需再次重复计算。时间复杂度优化为指数级O(C^N)。

结果

代码运算出来的结果是，农民没有必胜策略。换言之，只要地主会玩，农民不可能赢。阶级固化已经如斯了么……

开源

代码放于Github: doudizhu_solver，MIT协议，随便玩。我知道写的很烂，欢迎吐槽~

26 responses

刚想了一下有必赢策略，不知道有没有遗漏。
先出一个A，如果地主炸上后面就输了，如果不管，再出34567，这里地主炸了后面不管怎么出都会输，不炸的话农民再出3个3带10，这里地主炸了或者三个9管上后面不管怎么出也会输，不管再出3个A带10，农民胜。如果一开始拆王炸管上A，出三个的，或出对都会输，出单个的话等出大王后农民4个3炸上然后4-6一个一个出就可以胜利

Tim说道：

2017/05/28 11:14

抱歉，你的第一个分支就出问题了，农民先出A，地主为什么要炸呢？单出一张小王不行吗？剩下的请自己再推敲一下。

回复
- basher说道：
  
  2017/06/05 11:52
  
  请仔细看完，后面有说这种情况。如果一开始拆王炸管上A，出三个的，或出对都会输，出单个的话等出大王后农民4个3炸上然后4-6一个一个出就可以胜利
  
  回复
  - Tim说道：
    
    2017/06/05 13:36
    
    农民四个三炸完后，地主剩三个9带一个J，农民还剩4,5,6,7，一对10和一对A，怎么赢呢？你是不是少算了张7呢？如果你是技术的话，要相信代码啊。。直接怼代码。。
    
    回复
    - basher说道：
      
      2017/06/06 12:12
      
      农民剩的是三个A,不是一对A，地主打单的时候农民没有用A管。相信代码没错，但前提是思路正确以及没有考虑不全的情况
      
      回复
      - Tim说道：
        
        2017/06/06 14:16
        
        思路不对或者考虑不全还是可以看代码解决，总比在这里推敲要好一点。。
        
        按照你的思路，农民剩三个A，那就是农民先出A，地主出小王，农民不炸，地主出J，农民还不出（因为农民只能出A或炸）对吗？（因为农民出A，已经讨论过了，所以你说农民不出A，还剩三个A）
        
        那么好，现在地主出牌，地主有一个大王，三个9带一个J；农民有四个3，4-7，一对10和三张A。
        
        好了，这时候地主出J，农民要是不应，直接三个9带一个大王走了，农民输
        
        农民要是应（出A或者炸），假设出A，地主出大王，农民只能炸，炸完后散牌肯定打不过剩下的三个九，农民输
        
        农民要是用四个三炸来应，好，轮到农民出牌，只要农民出任何一张单牌，地主都出大王，农民没法应，直接地主三个9走掉，还是农民输
        
        我觉得讨论这些很麻烦（费时间），所以写了代码，这就是为什么叫你看代码而不是推盘面的原因
        
        回复
游园密语说道：

2017/06/01 10:22

农民先出一个A，不炸的话农民再出3个3带10
地主三个9带J管上(剩下王炸和1张牌)
地主怎么会输?

回复
- sunny说道：
  
  2021/11/22 14:26
  
  因为他也没说同花顺算不算炸弹，也就是到底是三人斗地主还是四人斗地主，四人地主必输，双炸而且同花顺还比王炸大，三人才有几率互有输赢
  
  回复