前言
相信大家都玩過斗地主，規則就不再介紹了。
直接上一張朋友圈看到的殘局圖：
這道題我剛看到時，曾嘗試用手工來破解，每次都以為找到了農民的必勝策略時，最后都發現其實農民跑不掉。由于手工破解無法窮盡所有可能性，所以這道題究竟農民有沒有妙手跑掉呢，只能通過代碼來幫助我們運算了。
本文將簡要講述怎么通過代碼來求解此類問題，在最后會公布殘局的最后結果，并開源代碼以供大家吐槽。
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 Trueif 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!)，根據
感谢您访问我们的网站，您可能还对以下资源感兴趣：