教你一招用Python破解斗地主殘局

斗地主應該對大家來說都不陌生，以下這篇文章主要跟大家分享了關於利用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協議，隨便玩。

以上是教你一招用Python破解斗地主殘局的詳細內容。更多資訊請關注PHP中文網其他相關文章！