前言

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

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

這道題我剛看到時(shí)，曾嘗試用手工來(lái)破解，每次都以為找到了農(nóng)民的必勝策略時(shí)，最后都發(fā)現(xiàn)其實(shí)農(nóng)民跑不掉。由于手工破解無(wú)法窮盡所有可能性，所以這道題究竟農(nóng)民有沒(méi)有妙手跑掉呢，只能通過(guò)代碼來(lái)幫助我們運(yùn)算了。

本文將簡(jiǎn)要講述怎么通過(guò)代碼來(lái)求解此類(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ì)都不能贏的話(huà)，那么可以說(shuō)農(nóng)民有必勝策略；否則，農(nóng)民必輸。

核心邏輯

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

這個(gè)函數(shù)的返回值，是輪到我me_pokers出牌時(shí)，是否能夠必贏牌。如果能贏則返回真，否則返回假。

def hand_out(me_pokers, enemy_pokers, last_hand)

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

if not me_pokers: return Trueif not enemy_pokers: return False

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

all_hands = get_all_hands(me_pokers)

現(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ì)手的下一次出牌不能獲勝的話(huà)，則我這一次的出牌必勝；否則，對(duì)于我的每一個(gè)出牌選擇，對(duì)手都能獲勝的話(huà)，則我必?cái)　?/p>

全部代碼如下：

def hand_out(me_pokers, enemy_pokers, last_hand, cache): if not me_pokers:  # 我全部過(guò)牌，直接獲勝  return True if not enemy_pokers:  # 對(duì)手全部過(guò)牌，我失敗  return False # 獲取我當(dāng)前可以出的所有手牌組合，包括過(guò)牌 all_hands = get_all_hands(me_pokers) # 遍歷我的所有出牌組合，進(jìn)行模擬出牌 for hand in all_hands:  # 如果上一輪對(duì)手出了牌，則這一輪我必須要出比對(duì)手更大的牌 或者 對(duì)手上一輪選擇過(guò)牌，那么我只需出任意牌，但是不能過(guò)牌  if (last_hand and can_comb2_beat_comb1(last_hand, hand)) or (not last_hand and hand['type'] != COMB_TYPE.PASS):   # 模擬對(duì)手出牌，如果對(duì)手不能取勝，則我必勝   if not hand_out(enemy_pokers, make_hand(me_pokers, hand), hand, cache):    return True  # 如果上一輪對(duì)手出了牌，但我這一輪選擇過(guò)牌  elif last_hand and hand['type'] == COMB_TYPE.PASS:   # 模擬對(duì)手出牌，如果對(duì)手不能取勝，則我必勝   if not hand_out(enemy_pokers, me_pokers, None, cache):    return True # 如果之前的所有出牌組合均不能必勝，則我必?cái)?return False

構(gòu)建

以上核心邏輯理清楚后，構(gòu)建破解器將變得十分簡(jiǎn)單。

首先，我們要用數(shù)字來(lái)表示牌的大小，這里我們用3表示3，11來(lái)表示J，12表示Q，依次類(lèi)推……

其次，我們需要求出一個(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)銷(xiāo)非常大，為階乘級(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)有必勝策略。換言之，只要地主會(huì)玩，農(nóng)民不可能贏。階級(jí)固化已經(jīng)如斯了么……

開(kāi)源

代碼放于Github: doudizhu_solver，或者大家可以本地下載，MIT協(xié)議，隨便玩。

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來(lái)一定的幫助，如果有疑問(wèn)大家可以留言交流，謝謝大家對(duì)VEVB武林網(wǎng)的支持。