正在加载验证码......
请先拖动验证码到相应位置利用Python破解斗地主残局详解
转载 & & 作者：Tim
斗地主应该对大家来说都不陌生，下面这篇文章主要跟大家分享了关于利用Python破解斗地主残局的相关资料，文中介绍的非常详细，对大家具有一定的参考学习价值，需要的朋友们下面来一起看看吧。
相信大家都玩过斗地主，规则就不再介绍了。
直接上一张朋友圈看到的残局图：
这道题我刚看到时，曾尝试用手工来破解，每次都以为找到了农民的必胜策略时，最后都发现其实农民跑不掉。由于手工破解无法穷尽所有可能性，所以这道题究竟农民有没有妙手跑掉呢，只能通过代码来帮助我们运算了。
本文将简要讲述怎么通过代码来求解此类问题，在最后会公布残局的最后结果，并开源代码以供大家吐槽。
代码的核心思想是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: ，或者大家可以，MIT协议，随便玩。
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作能带来一定的帮助，如果有疑问大家可以留言交流，谢谢大家对脚本之家的支持。
大家感兴趣的内容
12345678910
最近更新的内容
常用在线小工具微信欢乐斗地主残局怎么通关 1-50关通关攻略大全
微信欢乐斗地主残局怎么通关 1-50关通关攻略大全&欢乐斗地主残局是微信上一款不错的小游戏了，想要通关1-50关还是有一定难度的。不少玩家还不清楚一些关卡的通关攻略了，下面就来一起看下微信欢乐斗地主残局攻略大全吧。
微信欢乐斗地主残局1-50关攻略
顺子，再出9。
先出顺子3，A，9，10&【具体详解】你先出顺子，对方不要你再出3，对方出5你出9，对方出10你出A，对方出2你不要，对方再出对Q，对2你都不要，对方这时出张3你出张9，等着出张10就赢了。
对3,对J,10,2,5,Q,Q就赢了
对7，对9，对K，4jQ
先出对4，对8，9，A，小王，3，J赢了。
按照下面这个出牌顺序就赢了：
对六，对十，对K，一张四，一张八，一张A
对5，顺子6-J，对J，K，8赢了。
你先出对3，对方出对9你不出，他再出4，你出9，他出Q，你出K,他出A，你出2，他出王，你不出，他出5，你出10，他出J，你出A，最后再出对8，第八关就过了。
对方不要，你就继续出10，他如果还不出，你就出对8，如果出，你就等他出了王用A大住他出对8
对5，6，9，10，J，K，2，3
对5，对K，8，2，8，大王，3。
第十一关：
你先出3，对方出J
你出Q，对方小王，你不要
对方出顺子（3，4，5，6，7）
你也出顺子（6，7，8，9，10）
你再出对J，对方出对2，你不要
对方出对10，你出对A，赢了
第十二关：
你先出顺子9到K，对方王炸。
你不要，对方三带一。
你不要，对方出4。
你出A，对方出2。
你不要，对方对6。
你不要，对方出个7。
你出个A，赢了。
第十三关：
先出Q，对方出大王。你不要，对方顺子4-J。你不要，对方出对7。你出对2，对方不要。然后再出对8，对10，对3，赢了。
第十四关：
你先出对6，对方对10你对J，对方对Q你不要，对方出对3你不要，对方出个4你出8，对方出K你出A，对方出2你不要，对方出个5你出9，对方不要你再出个4，对方出7你出K，然后再出5，赢了
第十五关：
你先出4，对方出Q。
你出K，对方出个A。
你不要，对方出对6，对J 。
你都不要，对方出3。
你出8，对方出个2。
你出小王，对方不要。
你再出对6，对5，Q，赢了。
第十六关：
你先出对6，对方对7。
你出对J，对方出对A。
你不要，对方再出三带一。
你不要，对方出对5。
你不要，对方出个6。
你出K，对方不要。
你出三带一(9993)，对方不要。
你出个4，对方出8。
你出个2，对方不要。
你再出10，赢了。
第十七关：
你先出三带一对，对方也出三代一对
你不要，对方再出对K
你不要，对方出3
你出7，对方出9
你出J，对方出A
你不要，对方6
你出K，对方不要
你再出A，对方还是不要
最后再出个5，赢了
第十八关：
先打7，小王，三带一(3个Q带个4)，再对5，三带一，赢了具体详解你先打7，对方A你再打小王，你对大王，你不要对方对7，对J，对K，你都不要对方这时候在三带一，你也三带一(3个Q)压他，对方不要对方只剩下6了，你在对5，三带一，赢了
第十九关：
先出4，8，2，顺子(7 8 9 10 J)，3，J具体详解:你先出4，对方出5你出8，对方出Q你出2，对方不要你出顺子7 8 9 10 J，对方不要你出3，对方出K，连对，2，你都不要最后他只剩下4和3了，他不管出什么你都赢了
第二十关：
你先出Q，对方出A。
你不要，对方出顺子。
你不要，对方三带一。
你也三带一(5557)，对方不要
你出对K，对方不要。
你出个10，对方小王。
你不要，等着过张A就赢了。
第二十一关：
你先出对6，对7，对3，J，Q，A，7具体详解:你先出对6，对方对K你不要，对方对5你对7，对方不要你再对3，对方不要你出张J，对方出2你不要，对方出3你出Q，对方出大王你不要，对方出8你出A，对方不要你出7，赢了
第二十二关：
你先出顺子9 10 J Q K，4，7，7，10
先出顺子(9 10 J Q K)，对方不要
你再出4，对方出5
你出7(把对7拆掉)，对方J
你不要，接着对方再出对8，对K，对A
你都不要，这时候对方出3了
你再出7，对方出Q
你不要，对方出2
你不要，对方出6
你出10，赢了
第二十三关：
你先出J，对方出A。
你不要，对方再出顺子。
你不要，对方出5。
你出Q，对方不要。
你再出顺子，对方不要。
你出个Q，赢了。
第二十四关：
你先出Q，对方出2。你不要，对方三带一对。你不要，对方出4。你出K，对方出2。你不要，对方出7。你出2，对方不要。然后你再出对3，对9，三带一，2，6 就赢了。
第二十五关：
你先出顺子(45678)，对方不要。
你再出对9，对方出对A。
你不要，对方出个3。
你出5，对方出6。
你出J，对方出Q。
你出K，对方出A。
你不要，等着过张Q就赢了。
第二十六关：
你先出张9，对方出10你出K，对方出大王你不要，对方出对J你不要，对方出对Q你还是不要，这时候对方出张3你出8，对方出9你再压个A，对方不要这个时候你再出小王，2，9，对5对方它都不会了最后再出个3，赢了
第二十七关：
你先出连对(10 10 JJ QQ)，对方不要
你再出3，对方出5
你出6，对方出10
你出K，对方出2
你不要，对方再出对7，对A
你都不要，对方这时候出张3
你出张8，然后等着过张2就赢了
第二十八关：
你先出对Q，对方对2。你不要，对方三带一对。你不要，对方出个3。你出个4，对方出7。你出10，对方出K。你出大王，对方不要。你再出三带一，赢了
第二十九关：
你先出三带一(JJJ3)，对方不要。
你出顺子6 7 8 9 10，对方也出顺子。
你不要，对方出个3。
你出个7，对方出个Q。
你出A，对方出2。
你不要，然后等着过张8 就赢了。
第三十关：
你先出张8，对方出A。
你不要，对方对7，对方对8，对10，对K。
你都不要，对方出个3。
你出个10，对方出2。
你不要，对方出个5。
你出K，对方不要。
然后你出对4，三带一，就赢了。
第三十一关：
你先出J，对方不要。你再出K，对方出个2。你不要，对方出顺子。你不要，对方再出8。你出大王，对方不要。然后你再出对A，顺子，K，赢了。
第三十二关：
你先出张6，对方出9。你出10，对方出Q。你出K，对方出个2。你不要，对方再出连对。你不要，对方出对10。你出对Q，对方不要。你再出个7，对方出2。你出小王，对方不要。然后你再出对3，对4，A 就赢了。
第三十三关：
先出三带一，对3，对J，6，8，10 赢了
【具体详解】
你先出三带一(三个K带张5)，对方不要
你出对3，对方对9
你出对J，对方对A
你不要，对方出3
你出6，对方出7
你出8，对方出A，2
你都不要，对方再出个5
你出个10，赢了
第三十四关：
你先出四带二，对方不要
你再出对J，对方对K
你不要，对方再出对4，对9
你都不要，这时候对方出6
你出10，对方出J
你出K，然后等着过张A就赢了
第三十五关：
先出8，2，对7，对J，8，10，J，K，3，A，5
【具体详解】
你先出张8(把对8先拆掉)，对方出A
你再出2，对方出大王
你不要，对方出对4
你出对7，对方对10
你对J，对方再出对K
你不要，对方出个3
你出8，对方出2
你不要，对方出5
你压个10，对方不要
你再出J，K，对方都不要
这时候你出个3，对方出个6
你再压个A，对方不要
最后出个5，赢了
第三十六关：
先出对9，A，2，J，2，5，2，3，6【具体详解】你先出对9，对方出对K你不要，对方出6你出A，对方出小王你不要，对方出7你出2，对方压大王你不要，对方出9你出个J，对方出个Q你压个2，对方不要你再出个5，对方出10你出2，对方不要这个时候你出个3，然后等着过张6就赢了
第三十七关：
你先出对J，对方出对A。
你不要，对方再出对10。
你出对K，对方不要。
你出张3，对方出4。
你出5，对方出7。
你出8，对方出9。
你出10，对方出Q。
你不要，然后等着过个7 就赢了。
第三十八关：
先出10，对A，对6，对8，J，大王，Q，K，7 赢了
【具体详解】
你先出10，对方出A，你不要
对方四带二，你不要
对方出对9，你不要
对方出对J，你再出对A，对方不要
你再出对6，对8，对方不要
你再出J，对方出2
你出大王，对方不要
你再出Q，K，7。赢了
第三十九关：
你先出三带二(55544)，对方王炸。
你不要，对方三带一。
你不要，对方出个4。
你出个9，对方出10。
你出J，对方出Q。
你出K，对方不要。
你出个3，对方出个K。
你等着过个Q就赢了。
第四十关：
先出对10，K，A，J，对Q，J，Q，3具体详解你先出对10，对方出对A你不要，对方出4你出K，对方出2你不要，对方出6你出A，对方出2你不要，你对再9你出J，对方出小王你不要，对方再出对8你对Q，对方不要你再出J，对方出大王你不要，对方出10你出Q，对方不要你再出个3，赢了
第四十一关：
你先出个7，对方出个J。
你不要，对方出对5。
你出对Q，对方出对2。
你不要，对方出对9。
你不要，对方出个6。
你出个大王，对方不要。
你再出顺子，对方不要。
你出个8，赢了。
第四十二关：
先出8，2，对7，对J，8，10，J，K，3，A，5【具体详解】你先出张8(把对8先拆掉)，对方出A你再出2，对方出大王你不要，对方出对4你出对7，对方对10你对J，对方再出对K你不要，对方出个3你出8，对方出2你不要，对方出5你压个10，对方不要你再出J，K，对方都不要这时候你出个3，对方出个6你再压个A，对方不要最后出个5，赢了
第四十三关：
你先出对9，对方不要。你再出对K，对方不要。你出顺子34567，对方也出顺子。你不要，对方再出个4。你出个7，然后等着过张2 就赢了。
第四十四关：
你先出对K，对方对A
你不要，对方出对5
你出对J，对方不要
你出张3，对方出4
你出7，对方出8
你再出J，对方出2
你不要，对方出3
你出4，对方再出7
你出8，对方出9
你这时候出张Q，对方不要
你再张10，赢了
第四十五关：
先出9，2，7，Q，3，K，对6，2，对8【具体详解】你先出9，对方出K你出2，对方不要你再出7，对方出9你出Q，对方不要你再出3，对方出10你出K，对方不要你出对6，对方出对J你不要，对方出对Q你不要，对方这时候出个5你出个2，对方不要然后再出对8，赢了
第四十六关：
你先出7，对方出9
你出A，对方出2
你不要，对方出对6
你不要，对方出7
你出J，对方出2
你不要，对方出对3
你出对5，对方不要
你出10，对方出J
你出Q，对方出2
你不要，对方出对4
你出对6，对方不要
你再出对K，对方还不要
你再出个9，赢了
第四十七关：
你先出10，对方 出K你不要，对方出三带一你不要，对方出 对4你还是不要，对方出 对Q这时你出 对2，对方不要你再出个6，对方出8你出9，对方出10你出2，对方不要你出个5，对方出A你出2，对方不要你再出 对J，对方不要最后你再出8，赢了
第四十八关：
你先出8，对方出10你出A，对方出小王你出大王，对方不要你出个10，对方出A你不要，对方再出对3你出对J，对方出对2你不要，对方出个6你出个9，对方出A你不要，对方出对8你出对Q，对9，对4 然后就赢了
第四十九关：
你先出4，对方出8
你出10，对方出J
你出Q，对方出K
你出2，对方不要
你再出3，对方出10
你出K，对方出A
你出2，对方不要
你再出8，对方不要
你出9，对方出Q
你出2，对方不要
你再出对5，对方出对7
你不要，对方出Q
你等着过张9 就赢了
第五十关：
你先出K，对方出2。你不要，对方出10。你不要，对方出K。你不要，对方出8。你还是不要，对方再出8。你出9，对方出J。你出Q，对方出2。你不要，对方对5。你对9，对方不要。你出个Q，对方出2。你不要，对方出对7。你对A，对方不要。你再对4，对方还不要。你出个7，赢了。
上面就是微信欢乐斗地主残局攻略大全了，更多手游资讯攻略敬请关注！
责任编辑：向思《好看》依托百度技术，精准推荐优质短视频内容，懂你所好，量身打造最适合你的短视频客户端！