利用Python破解斗地主残局详解

前言

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

直接上一张朋友圈看到的残局图:

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

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

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协议,随便玩。

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作能带来一定的帮助,如果有疑问大家可以留言交流,谢谢大家对我们的支持。

时间: 2017-06-27

利用Python破解验证码实例详解

一.前言 本实验将通过一个简单的例子来讲解破解验证码的原理,将学习和实践以下知识点: Python基本知识 PIL模块的使用 二.实例详解 安装 pillow(PIL)库: $ sudo apt-get update $ sudo apt-get install python-dev $ sudo apt-get install libtiff5-dev libjpeg8-dev zlib1g-dev \ libfreetype6-dev liblcms2-dev libwebp-dev tcl

MySQL数据库设计之利用Python操作Schema方法详解

弓在箭要射出之前,低声对箭说道,"你的自由是我的".Schema如箭,弓似Python,选择Python,是Schema最大的自由.而自由应是一个能使自己变得更好的机会. Schema是什么? 不管我们做什么应用,只要和用户输入打交道,就有一个原则--永远不要相信用户的输入数据.意味着我们要对用户输入进行严格的验证,web开发时一般输入数据都以JSON形式发送到后端API,API要对输入数据做验证.一般我都是加很多判断,各种if,导致代码很丑陋,能不能有一种方式比较优雅的验证用户数据呢

利用python如何处理nc数据详解

前言 这两天帮一个朋友处理了些 nc 数据,本以为很简单的事情,没想到里面涉及到了很多的细节和坑,无论是"知难行易"还是"知易行难"都不能充分的说明问题,还是"知行合一"来的更靠谱些,既要知道理论又要知道如何实现,于是经过不太充分的研究后总结成此文,以记录如何使用 python 处理 nc 数据. 一.nc 数据介绍 nc 全称 netCDF(The Network Common Data Form),可以用来存储一系列的数组,就是这么简单(参考

如何利用Python模拟GitHub登录详解

前言 最近学习了Fiddler抓包工具的简单使用,通过抓包,我们可以抓取到HTTP请求,并对其进行分析.现在我准备尝试着结合Python来模拟GitHub登录. Fiddler抓包分析 首先,我们想要模拟一个网站的登录,我们必须要简单了解其大致过程. 在这里,我通过Fiddler来抓取GitHub登录的请求,从网页上登录的URL为:https://github.com/login ,抓包结果如下: 左边的是会话列表,右边的是请求和响应的数据.一般情况下,登录都是用POST请求,因为我在左边的会话

python实现报表自动化详解

本篇文章将介绍: xlwt 常用功能 xlrd 常用功能 xlutils 常用功能 xlwt写Excel时公式的应用 xlwt写入特定目录(路径设置) xlwt Python语言中,写入Excel文件的扩展工具.可以实现指定表单.指定单元格的写入.支持excel03版到excel2013版.使用时请确保已经安装python环境 xlrd Python语言中,读取Excel的扩展工具.可以实现指定表单.指定单元格的读取.使用时请确保已经安装python环境. NOTICE: xlwt对Excel只

python时间日期函数与利用pandas进行时间序列处理详解

python标准库包含于日期(date)和时间(time)数据的数据类型,datetime.time以及calendar模块会被经常用到. datetime以毫秒形式存储日期和时间,datetime.timedelta表示两个datetime对象之间的时间差. 下面我们先简单的了解下python日期和时间数据类型及工具 给datetime对象加上或减去一个或多个timedelta,会产生一个新的对象 from datetime import datetime from datetime impo

Python字符串处理实例详解

Python字符串处理实例详解 一.拆分含有多种分隔符的字符串 1.如何拆分含有多种分隔符的字符串 问题: 我们要把某个字符串依据分隔符号拆分不同的字段,该字符串包含多种不同的分隔符,例如: s = "ab;cd|efg|hi,jkl|mn\topq;rst,uvw\txyz" 其中;,|,\t 都是分隔符号,如何处理? 方法一: 连续使用str.split()方法,每次处理一种分隔符号 s = "ab;cd|efg|hi,jkl|mn\topq;rst,uvw\txyz&q

Python模块WSGI使用详解

WSGI(Web Server Gateway Interface):Web服务网关接口,是Python中定义的服务器程序和应用程序之间的接口. Web程序开发中,一般分为服务器程序和应用程序.服务器程序负责对socket服务的数据进行封装和整理,而应用程序则负责对Web请求进行逻辑处理. Web应用本质上也是一个socket服务器,用户的浏览器就是一个socket客户端. 我们先用socket编程实现一个简单的Web服务器: import socket def handle_request(c

Python API 自动化实战详解(纯代码)

主要讲如何在公司利用Python 搞API自动化. 1.分层设计思路 dataPool :数据池层,里面有我们需要的各种数据,包括一些公共数据等 config :基础配置 tools : 工具层 common: 公共方法层 runCase :需要运行的测试用例 noRunCase :不需要运行的测试用例 testReport :这里存放生成的测试报告 2.编写common: 公共方法层 2.1 getTimestamp.py 我们在common文件夹下新建一个getTimestamp.py. 因