利用Python破解斗地主残局详解
作者:Tim 发布时间:2021-06-04 06:16:49
前言
相信大家都玩过斗地主,规则就不再介绍了。
直接上一张朋友圈看到的残局图:
这道题我刚看到时,曾尝试用手工来破解,每次都以为找到了农民的必胜策略时,最后都发现其实农民跑不掉。由于手工破解无法穷尽所有可能性,所以这道题究竟农民有没有妙手跑掉呢,只能通过代码来帮助我们运算了。
本文将简要讲述怎么通过代码来求解此类问题,在最后会公布残局的最后结果,并开源代码以供大家吐槽。
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协议,随便玩。
来源:http://wuzhiwei.net/doudizhu_solver/
猜你喜欢
- 1.网页背景色的设置 犯错机率:很大普遍性:较广犯错可能性:懒/不知道约2年前我曾发现21cn上出现过一次没有设置背景色的情况,当时我用Em
- 如何显示数据库的结构?<html><head><meta http-equiv="Cont
- 本文给大家介绍PHP中Http协议post请求参数,具体内容如下所示:WEB开发中信息基本全是在POST与GET请求与响应中进行,GET因其
- 1.Python代码import cx_Oracletns=cx_Oracle.makedsn('127.0.0.1',
- 在实际处理数据时,因系统内存有限,我们不可能一次把所有数据都导出进行操作,所以需要批量导出依次操作。为了加快运行,我们会采用多线程的方法进行
- Logo是品牌图形区别的点睛之处,我们每天都要接触很多logo - 在高速公路上,在购买商品时,以及浏览各种网站。我们查看很多logo设计,
- 一、创建虚拟环境(1)打开cmd命令窗口(2)创建虚拟环境 conda create -n mydjango_env(3)查看虚拟环境 co
- 如何让图片自动缩放以适合界面大小,拿出你的Editplus,打开c_function.asp文件,找到UBBCode函数,在第417行有如下
- 许多人在编写程序的时候因为贪图方便或不小心使用到程式的保留字,有时明明程序没有错,就是无法正确执行。您知道有哪些常见的保留字吗? 下面的都是
- 这篇论坛文章(赛迪网技术社区)主要介绍了配置一个高可用性的MySQL服务器负载均衡群集的具体过程,详细内容请参考下文:本文将告诉你如何配置一
- 1.用一个栈【python中可以用List】就可以解决,时间和空间复杂度都是O(n)# -*- coding: utf8 -*-# 符号表S
- 本文实例为大家分享了python绘制直方图的具体代码,供大家参考,具体内容如下运行结果如下代码如下from matplotlib impor
- 需求:对一个配置文件进行处理,拿出可用的字符来拼接,下面是原始文本,我们要得到这样的结果,redis -h 127.0.0.1 -p 637
- 代码如下: 代码如下:///<summary> /// 将两个列不同的DataTable合并成一个新的DataTab
- 在应用SA-FileUp时,必须确认用户已对目的路径有读、写、删除的权力。在多文件上传中,由于浏览器不支持SIZE= 属性,所以对多文件的情
- 原文: gradio.app/interface-s…1.全局状态例子来解释import gradio as grsc
- px比em更加容易使用,em指字体高,任意浏览器的默认字体高都是16px。所以未经调整的浏览器都符合: 1em=16px,所以10px=0.
- 我们的规范到底做到哪一步算是发挥良好的价值?其实一件事物我们理解错根本目的会导致出大不一样的结果,直接反应在设计师到底要体现什么的价值。想想
- 我们有时候希望回车键敲在文本框(input element)里来提交表单(form),但有时候又不希望如此。比如搜索行为,希望输入完关键词之
- 概述可以获取的数据包括:video-视频模块user-用户模块dynamic-动态模块这次用“Running Man”十周年特辑的视频,来做