前言

相信大家都玩過斗地主，規則就不再介紹了。

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

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

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

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)

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

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

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