小白用Python | 用Python破解斗地主殘局

相信大家都玩過斗地主,規則就不再引見了。

直接上一張朋友圈看到的殘局圖:

小白用Python | 用Python破解斗地主殘局

這道題我剛看到時,曾嘗試用手工來破解,每次都以為找到了農民的必勝戰略時,最后都發現其實農民跑不掉。由于手工破解無法窮盡一切可能性,所以這道題終究農民有沒有妙手跑掉呢,只能經過代碼來協助我們運算了。

本文將簡要講述怎么通過代碼來求解此類問題,在最后會公布殘局的最后結果,并開源代碼以供大家吐槽。

minimax小白用Python | 用Python破解斗地主殘局

代碼的核心思想是minimax。minimax可以拆解為兩部分,mini和max,分別是最小和最大的意思。

直觀的理解是什么呢?就有點像A、B兩個人下棋。A現在可以在N個點走棋,假設A在某個點走棋了,使得A的這一步的盤面評估分數最高;但是輪到B下的時候,就一定會朝著讓A最不利的方向走,使得A的下一步必然按照B設定的軌跡來,而沒法達到A在第一步時估算到這一步的最高盤面評分。

在牌局中是一樣的,如果農民的一手牌,讓地主無論如何應對都不能贏的話,那么可以說農民有必勝策略;否則,農民必輸。

核心邏輯小白用Python | 用Python破解斗地主殘局

我們可以用一個函數hand_out來模擬一個人的出牌過程。在現實生活中,一個人想要出牌的話,必然需要知道自己手上的所有牌:me_pokers,也需要知道上一手的出的牌:last_hand。如果我們要用這個函數來模擬兩個人的出牌,則還需要知道對手當前的所有牌:enemy_pokers。

這個函數的返回值,是輪到我me_pokers出牌時,是否能夠必贏牌。如果能贏則返回真,否則返回假。

小白用Python | 用Python破解斗地主殘局

假設輪到我出牌時,如果我手上的牌都出完了,那么我將立刻知道我贏了;反之如果對手的牌都出完了,而我沒有,則我失敗了。

小白用Python | 用Python破解斗地主殘局

因為現在輪到我出牌,所以我首先需要知道我現在能出的所有手牌組合。注意:這個組合中,包括過牌(即不出牌)的策略。

小白用Python | 用Python破解斗地主殘局

現在我們要對所有可能的手牌組合進行遍歷。

首先我需要知道,上一手對方出的牌是什么。

  • 如果對方上一手選擇過牌,或者沒有上一手牌,那么我這一輪必須不能過牌,但是我可以出任意的牌
  • 如果對手上一手出了牌,則我必須要出一個比它更大的牌或者選擇這一輪直接過牌(不出牌)

關鍵點來了,在出完我的牌或選擇過牌后,我們需要用一個遞歸調用來模擬對手下一步的行為。如果對手的下一次出牌不能獲勝的話,則我這一次的出牌必勝;否則,對于我的每一個出牌選擇,對手都能獲勝的話,則我必敗。

全部代碼如下:

小白用Python | 用Python破解斗地主殘局

構建小白用Python | 用Python破解斗地主殘局

以上核心邏輯理清楚后,構建破解器將變得十分簡單。

首先,我們要用數字來表示牌的大小,這里我們用3表示3,11來表示J,12表示Q,依次類推……

其次,我們需要求出一個手牌的所有出牌組合,這里需要get_all_hands函數,具體實現比較繁瑣但是很簡單,就不在此贅述。

然后,我們還需要一個牌力判斷函數can_comb2_beat_comb1(comb1, comb2),這個函數用于比較兩組手牌的牌力,看是否comb2可以擊敗comb1。唯一需要注意的一點,在斗地主的規則中,除了炸彈外,其他所有牌力均等,只有牌型一樣時才能去比較。

最后,我們需要一個模擬出牌函數make_hand(pokers, hand),用于求出在手牌為pokers的情況下打出一手牌hand后,剩下的手牌,實現也非常簡單,只需簡單的移除掉那些打出的牌即可。

效率小白用Python | 用Python破解斗地主殘局

由于一副牌的可能手牌巨大,導致遞歸的分支數巨大。所以時間開銷非常大,為階乘級O(N!),根據斯特林公式,大約為O(N^N)。

由于可能會有很多重復的牌面出現,導致了很多重復的遞歸調用。所以加一個緩存能極大提升效率。

即對我方手牌和敵方手牌和上一輪手牌的描述(str(me_pokers)+str(enemy_pokers)+str(last_hand))為鍵,將求出的結果存進緩存字典中。下一次遇到相同的局面時,即可直接從緩存字典中取出,而無需再次重復計算。時間復雜度優化為指數級O(C^N)。

結果小白用Python | 用Python破解斗地主殘局

代碼運算出來的結果是,農民沒有必勝戰略。換言之,只需地主會玩,農民不可能贏。階級固化曾經如斯了么……

開源

代碼放于Github: doudizhu_solver,MIT協議,隨意玩。我曉得寫的很爛,歡送吐槽~

 

馬哥學習交流群

馬哥教育-Python開發-1群 335068227

馬哥教育-Python開發-2群 608459685

 

相關新聞

聯系我們

400-080-6560

在線咨詢:點擊這里給我發消息

郵件:[email protected]

工作時間:周一至周日,09:00-18:30

QR code
云南快乐10分开奖直播