小白用Python | 用Python破解斗地主殘局
相信大家都玩過(guò)斗地主,規(guī)則就不再引見(jiàn)了。
直接上一張朋友圈看到的殘局圖:

這道題我剛看到時(shí),曾嘗試用手工來(lái)破解,每次都以為找到了農(nóng)民的必勝戰(zhàn)略時(shí),最后都發(fā)現(xiàn)其實(shí)農(nóng)民跑不掉。由于手工破解無(wú)法窮盡一切可能性,所以這道題終究農(nóng)民有沒(méi)有妙手跑掉呢,只能經(jīng)過(guò)代碼來(lái)協(xié)助我們運(yùn)算了。
本文將簡(jiǎn)要講述怎么通過(guò)代碼來(lái)求解此類問(wèn)題,在最后會(huì)公布?xì)埦值淖詈蠼Y(jié)果,并開(kāi)源代碼以供大家吐槽。
minimax

代碼的核心思想是minimax。minimax可以拆解為兩部分,mini和max,分別是最小和最大的意思。
直觀的理解是什么呢?就有點(diǎn)像A、B兩個(gè)人下棋。A現(xiàn)在可以在N個(gè)點(diǎn)走棋,假設(shè)A在某個(gè)點(diǎn)走棋了,使得A的這一步的盤(pán)面評(píng)估分?jǐn)?shù)最高;但是輪到B下的時(shí)候,就一定會(huì)朝著讓A最不利的方向走,使得A的下一步必然按照B設(shè)定的軌跡來(lái),而沒(méi)法達(dá)到A在第一步時(shí)估算到這一步的最高盤(pán)面評(píng)分。
在牌局中是一樣的,如果農(nóng)民的一手牌,讓地主無(wú)論如何應(yīng)對(duì)都不能贏的話,那么可以說(shuō)農(nóng)民有必勝策略;否則,農(nóng)民必輸。
核心邏輯

我們可以用一個(gè)函數(shù)hand_out來(lái)模擬一個(gè)人的出牌過(guò)程。在現(xiàn)實(shí)生活中,一個(gè)人想要出牌的話,必然需要知道自己手上的所有牌:me_pokers,也需要知道上一手的出的牌:last_hand。如果我們要用這個(gè)函數(shù)來(lái)模擬兩個(gè)人的出牌,則還需要知道對(duì)手當(dāng)前的所有牌:enemy_pokers。
這個(gè)函數(shù)的返回值,是輪到我me_pokers出牌時(shí),是否能夠必贏牌。如果能贏則返回真,否則返回假。

假設(shè)輪到我出牌時(shí),如果我手上的牌都出完了,那么我將立刻知道我贏了;反之如果對(duì)手的牌都出完了,而我沒(méi)有,則我失敗了。

因?yàn)楝F(xiàn)在輪到我出牌,所以我首先需要知道我現(xiàn)在能出的所有手牌組合。注意:這個(gè)組合中,包括過(guò)牌(即不出牌)的策略。

現(xiàn)在我們要對(duì)所有可能的手牌組合進(jìn)行遍歷。
首先我需要知道,上一手對(duì)方出的牌是什么。
- 如果對(duì)方上一手選擇過(guò)牌,或者沒(méi)有上一手牌,那么我這一輪必須不能過(guò)牌,但是我可以出任意的牌
- 如果對(duì)手上一手出了牌,則我必須要出一個(gè)比它更大的牌或者選擇這一輪直接過(guò)牌(不出牌)
關(guān)鍵點(diǎn)來(lái)了,在出完我的牌或選擇過(guò)牌后,我們需要用一個(gè)遞歸調(diào)用來(lái)模擬對(duì)手下一步的行為。如果對(duì)手的下一次出牌不能獲勝的話,則我這一次的出牌必勝;否則,對(duì)于我的每一個(gè)出牌選擇,對(duì)手都能獲勝的話,則我必?cái) ?/p>
全部代碼如下:

構(gòu)建

以上核心邏輯理清楚后,構(gòu)建破解器將變得十分簡(jiǎn)單。
首先,我們要用數(shù)字來(lái)表示牌的大小,這里我們用3表示3,11來(lái)表示J,12表示Q,依次類推……
其次,我們需要求出一個(gè)手牌的所有出牌組合,這里需要get_all_hands函數(shù),具體實(shí)現(xiàn)比較繁瑣但是很簡(jiǎn)單,就不在此贅述。
然后,我們還需要一個(gè)牌力判斷函數(shù)can_comb2_beat_comb1(comb1, comb2),這個(gè)函數(shù)用于比較兩組手牌的牌力,看是否comb2可以擊敗comb1。唯一需要注意的一點(diǎn),在斗地主的規(guī)則中,除了炸彈外,其他所有牌力均等,只有牌型一樣時(shí)才能去比較。
最后,我們需要一個(gè)模擬出牌函數(shù)make_hand(pokers, hand),用于求出在手牌為pokers的情況下打出一手牌hand后,剩下的手牌,實(shí)現(xiàn)也非常簡(jiǎn)單,只需簡(jiǎn)單的移除掉那些打出的牌即可。
效率

由于一副牌的可能手牌巨大,導(dǎo)致遞歸的分支數(shù)巨大。所以時(shí)間開(kāi)銷非常大,為階乘級(jí)O(N!),根據(jù)斯特林公式,大約為O(N^N)。
由于可能會(huì)有很多重復(fù)的牌面出現(xiàn),導(dǎo)致了很多重復(fù)的遞歸調(diào)用。所以加一個(gè)緩存能極大提升效率。
即對(duì)我方手牌和敵方手牌和上一輪手牌的描述(str(me_pokers)+str(enemy_pokers)+str(last_hand))為鍵,將求出的結(jié)果存進(jìn)緩存字典中。下一次遇到相同的局面時(shí),即可直接從緩存字典中取出,而無(wú)需再次重復(fù)計(jì)算。時(shí)間復(fù)雜度優(yōu)化為指數(shù)級(jí)O(C^N)。
結(jié)果

代碼運(yùn)算出來(lái)的結(jié)果是,農(nóng)民沒(méi)有必勝戰(zhàn)略。換言之,只需地主會(huì)玩,農(nóng)民不可能贏。階級(jí)固化曾經(jīng)如斯了么……
開(kāi)源
代碼放于Github: doudizhu_solver,MIT協(xié)議,隨意玩。我曉得寫(xiě)的很爛,歡送吐槽~
馬哥學(xué)習(xí)交流群
馬哥教育-Python開(kāi)發(fā)-1群 335068227
馬哥教育-Python開(kāi)發(fā)-2群 608459685