利用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,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,依次类推…… 其次,我们需要求出一个手牌的所有出牌组合,这里需要 然后,我们还需要一个牌力判断函数 最后,我们需要一个模拟出牌函数 效率 由于一副牌的可能手牌巨大,导致递归的分支数巨大。所以时间开销非常大,为阶乘级O(N!),根据斯特林公式,大约为O(N^N)。 由于可能会有很多重复的牌面出现,导致了很多重复的递归调用。所以加一个缓存能极大提升效率。 即对我方手牌和敌方手牌和上一轮手牌的描述 结果 代码运算出来的结果是,农民没有必胜策略。换言之,只要地主会玩,农民不可能赢。阶级固化已经如斯了么…… 开源 代码放于Github: doudizhu_solver,或者大家可以本地下载,MIT协议,随便玩。 总结 以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作能带来一定的帮助,如果有疑问大家可以留言交流,谢谢大家对编程小技巧的支持。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |