設(shè)計(jì)目標(biāo)

要取得良好效果，首先要搞清楚一個(gè)問(wèn)題：我們想得到一個(gè)什么樣的斗地主AI？
我們的AI是用在手游產(chǎn)品當(dāng)中，在真實(shí)玩家不足時(shí)為用戶提供陪玩服務(wù)，這個(gè)目標(biāo)決定了這個(gè)AI要具備以下兩個(gè)核心特點(diǎn)：
1、執(zhí)行效率高，要為在線運(yùn)行為玩家提供服務(wù)，不能給服務(wù)器太大壓力；
2、模擬人的思維方式，讓AI看起來(lái)像一個(gè)中等水平的玩家，而不是追求很高的勝率。

斗地主的AI一般有三個(gè)核心部分：拆牌、出牌、接牌。要提高算法的執(zhí)行效率，在這三個(gè)環(huán)節(jié)就不能完全依賴深度搜索的策略，在本設(shè)計(jì)方案中，所有的策略基本都是“靜態(tài)規(guī)則+有限搜索”的套路。打個(gè)比方，在拆牌過(guò)程中，我拆出了三張、對(duì)子、單張之后，在給三張配帶牌的時(shí)候怎么選擇呢？我只會(huì)對(duì)單張、對(duì)子做一下簡(jiǎn)單的篩選，而不會(huì)去考慮是否把某個(gè)順子的尾部拆出來(lái)當(dāng)帶牌會(huì)更優(yōu)。

要讓AI看起來(lái)像人，其實(shí)就是把常見(jiàn)的一些出牌套路用算法表達(dá)出來(lái)。這里運(yùn)用策略模式來(lái)組織代碼，不同的策略有不同的優(yōu)先級(jí)，理論上，我們可以通過(guò)不斷地添加策略來(lái)完善這個(gè)AI。打個(gè)比方，對(duì)于出牌，假設(shè)我們有以下三條策略（實(shí)際算法當(dāng)然不止三條）：1)只剩一手牌策略，直接出完就贏了，2）只有一手小牌，其他全部大牌，小牌放到最后，其他從小往大出；3）小牌優(yōu)先策略，找出最小的牌來(lái)出。這幾個(gè)策略的優(yōu)先級(jí)就是1>2>3。

“搜索”在接牌過(guò)程中用得比較頻繁，比如別人出一個(gè)三帶一，我手上的牌拆出來(lái)是三帶一對(duì)，那么是把這個(gè)對(duì)子拆掉呢，還是另外找一個(gè)單張。打個(gè)比方如果手上是"QQQkk345678"，那么顯然是帶一張3比較好，如果手上是“QQQKK56789”,那么應(yīng)該拆對(duì)k。這里會(huì)對(duì)所有符合規(guī)則的帶牌做一個(gè)搜索，然后評(píng)判哪個(gè)方案是最優(yōu)的，于是關(guān)鍵點(diǎn)就是采用什么評(píng)判規(guī)則。

我采用一種基于分值的手牌評(píng)價(jià)規(guī)則，一手牌，無(wú)論多少?gòu)?，先進(jìn)行拆牌，然后每個(gè)牌組（牌組指單張、順子、對(duì)子等可以一次出掉的牌）都有一個(gè)分值，最后把所有牌組的分值加起來(lái)，形成一個(gè)手牌分值。上面所說(shuō)的接牌搜索過(guò)程，會(huì)進(jìn)行反復(fù)的拆牌和分值計(jì)算，因此拆牌的算法必須非常高效。

上面介紹了這個(gè)斗地主AI的核心設(shè)計(jì)思路，其中評(píng)分規(guī)則參考了這篇文章：https://blog.csdn.net/sm9sun/article/details/70787814；拆牌算法參考了這篇文章：http://www.360doc.com/content/11/0108/09/2617151_84917660.shtml，在此對(duì)兩位作者表示感謝。

網(wǎng)上介紹的所有斗地主AI設(shè)計(jì)，都過(guò)于簡(jiǎn)單，用來(lái)自?shī)首詷?lè)還行，直接用于線上產(chǎn)品則遠(yuǎn)遠(yuǎn)不夠。

拆牌算法

拆牌算法總體上是一個(gè)基于牌型優(yōu)先級(jí)的查找過(guò)程：

1. 如果有火箭，找出來(lái)；
2. 如果有炸彈，找出來(lái)（炸彈不拆）；
3. 如果有2，全部找出來(lái)（2不會(huì)參與順子）；
4. 如果有飛機(jī)，找出來(lái)（飛機(jī)也不拆）；
5. 找出所有的順子，每個(gè)順子盡量長(zhǎng)；
6. 處理順子
   1. 順子分裂，現(xiàn)有一個(gè)順子345678910，發(fā)現(xiàn)手上還剩下一張6和7，那么順子分裂成34567和678910；
   2. 順子拆出連對(duì)，現(xiàn)有一個(gè)順子345678910，發(fā)現(xiàn)手上還有345，變成334455和678910更好，就把順子里面的345放回去；
   3. 順子拆出三張，現(xiàn)有一個(gè)順子345678，發(fā)現(xiàn)手上還有88，那么變成34567和888更好，就把順子里面的8放回去；
   4. 順子如果蓋住對(duì)子、三張、連對(duì)，如果發(fā)現(xiàn)打散牌組數(shù)更少，則打散，比如7789910JJJQKK，拆散了更好；
   5. 順子拆出兩頭的對(duì)子，現(xiàn)有一個(gè)順子67890JQ，發(fā)現(xiàn)手上還有Q和6，那么把孫子里面的Q和6放回去；
   6. 反復(fù)進(jìn)行1）到5），直到?jīng)]有進(jìn)一步變化；
7. 剩余的牌里面找出所有的連對(duì)；
8. 查看所有的連對(duì)，如果長(zhǎng)度超過(guò)3，且一端有三條，把三條拆出來(lái)；
9. 剩余的牌里面找出所有的三張；
10. 延長(zhǎng)順子：如果一個(gè)順子的兩端外面有一個(gè)對(duì)子，如果這個(gè)對(duì)子小于10，則并入順子，比如34567+88,那么變成345678+8;
11. 合并順子：相同的順子變成連對(duì)，首尾相接的順子連成一個(gè)；
12. 剩余的牌里面找出所有對(duì)子和單張。

舉個(gè)例子，一手牌“333455678910JJK22小王”：

1. 先把炸彈、2、王拆出來(lái)，剩下“333455678910JJK”
2. 找順子，得到345678910J，剩下"335JK"
3. 由于順子的左側(cè)有3張，于是順子變成45678910J，剩下3335JK
4. 由于順子右側(cè)的J有一對(duì)，于是順子變成45678910,剩下3335JJK
5. 找三張，得到333；
6. 剩下的得到5、JJ、K。

至此，一手牌就拆好了，為了簡(jiǎn)化算法，我們不拆炸彈，不拆飛機(jī)。在主動(dòng)出牌時(shí)，會(huì)按著這個(gè)拆牌來(lái)出；在接牌時(shí)則不會(huì)，會(huì)依據(jù)對(duì)方的牌型來(lái)搜索一個(gè)更優(yōu)方案，此時(shí)順子、飛機(jī)、炸彈都可能被拆散，具體細(xì)節(jié)下文會(huì)講。

帶牌選擇

上面拆好的牌組，三張和飛機(jī)是沒(méi)有帶牌的，在此基礎(chǔ)上選擇帶牌是比較容易的，就是在對(duì)子和單張里面選擇最小的牌即可。

減少單張的拆牌

一個(gè)常見(jiàn)的場(chǎng)景是，當(dāng)我的敵人只剩下一張牌時(shí)，此時(shí)應(yīng)該采用一種“讓單張盡量少的策略”，這個(gè)策略和常規(guī)策略大體相同，有兩個(gè)不同點(diǎn)：

1. "延長(zhǎng)順子“這一步不執(zhí)行；
2. 帶牌選擇的時(shí)候，優(yōu)先選擇單張

評(píng)分規(guī)則

一手牌到底好不好，我們需要一個(gè)量化標(biāo)準(zhǔn)，也就是給手牌評(píng)一個(gè)分值。否則沒(méi)法決策是否叫地主，在接牌過(guò)程中也沒(méi)法決策A方案好，還是B方案好，抑或不要才是最好選擇。

評(píng)分的大體理念是，對(duì)一個(gè)牌組來(lái)說(shuō)，越能管牌，分值越大；越不容易被管，分值越大。而一手牌的分值，則不僅取決于拆出來(lái)的牌組的分?jǐn)?shù)，還取決于拆出來(lái)牌組的組數(shù)，和前者正相關(guān)和后者負(fù)相關(guān)。

為了平衡，牌組的分值可能是正的，也可能是負(fù)數(shù)，以10為參考點(diǎn)，單張10為0分，9為-1分，J為1分。每個(gè)牌組有一個(gè)maxCard屬性，單張和對(duì)子就是自身，順子和連對(duì)是最大那張牌，三帶是有三張的那個(gè)牌，這個(gè)很容易理解，相同的牌型比較大小，就是比較maxCard。我們?cè)u(píng)分也基于這個(gè)屬性。

這個(gè)設(shè)定規(guī)則，是在調(diào)試過(guò)程中依據(jù)經(jīng)驗(yàn)感覺(jué)不斷調(diào)節(jié)的出來(lái)的。比如對(duì)子和三張的額外加分問(wèn)題，是要體現(xiàn)出大對(duì)子比如(22)的價(jià)值。而順子分值公式，是基于“順子很難管牌，分?jǐn)?shù)不宜過(guò)高,但是本身也很難被管”這個(gè)事實(shí)。所以這組規(guī)則沒(méi)啥嚴(yán)密的邏輯，也不一定合理。

接下來(lái)就是手牌的評(píng)分規(guī)則，也就是若干個(gè)牌組在一起怎么評(píng)分，最初的公式是：sum(牌組分)-PxN，每個(gè)輪次設(shè)定一個(gè)固定的分值P，用牌組分值的和減去P乘以牌組數(shù)量N。這個(gè)機(jī)制有一個(gè)很難解決的問(wèn)題，就是P的取值，P過(guò)大，過(guò)于強(qiáng)調(diào)輪次的價(jià)值，在牌局初期接牌的時(shí)候過(guò)于激進(jìn)（無(wú)論出什么牌都導(dǎo)致總分值增加，因?yàn)檩喆螠p少了）；P過(guò)小，過(guò)于忽略輪次的價(jià)值，在牌局末期出牌過(guò)于保守（大牌攥著出不去，因?yàn)闇p少一個(gè)輪次加不了幾分）。

幾經(jīng)周折，最后定個(gè)兩個(gè)規(guī)則：
1、大牌的輪次忽略，因?yàn)榇笈瓶偸浅龅萌サ模ㄎ覀兪稚隙鄠€(gè)炸彈，不會(huì)有任何負(fù)面影響），包括王、2、炸彈；
2、P的取值是一個(gè)列表:{ 6, 6, 6, 5, 5, 5, 4, 4, 4, 3}，意思是索引1_{3->P=6，索引4}6->P=5，索引7~9->P=4；之后P=3，這樣在早期一手大牌出去減分會(huì)比較多(這時(shí)減少一組牌所得到的輪次分增益比較少)，到后期減分比較少。

總體來(lái)說(shuō)，牌的分值更多具有比較意義，而不具備絕對(duì)意義。我們?cè)谡麄€(gè)AI系統(tǒng)中，除了在叫地主時(shí)，盡量去比較兩個(gè)出牌方案的優(yōu)劣，而避免把一手牌的分值去和一個(gè)常數(shù)進(jìn)行比較。

出牌策略

出牌策略就是在一種特定模式下的出牌套路，所以我們識(shí)別一個(gè)特定模式，就可以編寫(xiě)一個(gè)策略。反過(guò)來(lái)，這個(gè)策略也會(huì)檢查一下，當(dāng)前的牌局是否符合對(duì)應(yīng)的模式，如果不符合它就不處理，交給下一個(gè)策略處理。

有些策略適用于農(nóng)民，有些適用于地主，這里我們羅列一下農(nóng)民的出牌策略，按優(yōu)先級(jí)從搞到低：

理論上，如果我們找到新的模式，就可以創(chuàng)建新的策略添加到這個(gè)列表，我們的AI也就越完善。

牌的大小預(yù)測(cè)

在上面的策略中，提到一組牌是大還是小，實(shí)際是指，這手牌對(duì)方接住的可能性大還是小。比如我有一個(gè)34567，對(duì)方只有3張牌，而且王已經(jīng)出過(guò)了，那么我認(rèn)為這順子是大牌。

我們合理地利用“出過(guò)的牌“，“我手里的牌”，“別人手上牌的數(shù)量”這個(gè)幾個(gè)信息，做出上面的判斷。所謂“合理”，就是指正常的玩家，也知道這些信息，也能做出類(lèi)似的判斷；而不能去作弊開(kāi)“天眼”。

策略之間的呼應(yīng)

如果仔細(xì)琢磨一下，可以發(fā)現(xiàn)allBig，foreEnemySingle，enemyOnePoke這幾個(gè)策略之間是相互呼應(yīng)的。這一輪使用了這個(gè)策略，如果順利，下一輪就可能落入另外一個(gè)模式，這也有點(diǎn)像真人的布局謀劃。我在設(shè)計(jì)策略的時(shí)候，有兩個(gè)原則：1）策略上下文無(wú)關(guān)（以前的出牌過(guò)程不影響）；2）策略之間盡量互相呼應(yīng)。

接牌策略

接牌是被動(dòng)的，所以策略相對(duì)少一些。
以農(nóng)民接牌策略為例：

接牌策略里，這個(gè)兜底的策略是最難寫(xiě)的，因?yàn)檫@里要決策接還是不接，大體考慮以下幾個(gè)因素：

1. 是否隊(duì)友的牌；
2. 我的牌是否非常好；
3. 地主是我的上手還是下手；
4. 對(duì)方還剩多少牌；
5. 出牌大小；
6. 接牌的大小；

我設(shè)計(jì)的兜底策略大體是這樣的：

1. 首先通過(guò)搜索找到一個(gè)能接牌的最佳牌組，如果找不到，就結(jié)束了；
2. 如果是隊(duì)友的牌，相對(duì)還比較大，我不接
3. 如果是隊(duì)友的牌，我肯定不用大牌接；
4. 如果是地主的牌，我的牌絕對(duì)得好，肯定接；
5. 如果是地主的牌，接了之后我的牌不變差太多，接；
6. 如果是地主的牌，我的接牌比他大得不多（比如王對(duì)2），接；
7. 如果是地主的牌，接牌是順子、飛機(jī)、連對(duì)這類(lèi)，接；
8. 如果是地主的牌，我要?jiǎng)佑谜◤棧绻七€很多，出的又不是王和2之類(lèi)，不接；
9. 如果是地主的牌，他的牌很少，或者他出大牌了，接。

第一步搜索接牌，不會(huì)考慮拆牌的結(jié)果，而是去手牌里面強(qiáng)行搜索，比如要接一對(duì)QQ，我手里有KKK2235，那么KK和22會(huì)先后被搜索到，然后判斷剩下手牌的評(píng)分來(lái)比較方案的優(yōu)劣。

后面都是一些瑣碎的判斷，其中“多少分算絕對(duì)好牌”，“多少?gòu)埮扑愣唷?，都是比較主觀的設(shè)定。

贏牌路徑

在出牌策略和接牌策略里，有一個(gè)優(yōu)先級(jí)最高的策略，即“贏牌策略”，現(xiàn)在的牌面存在一個(gè)能贏的出牌方法。打個(gè)比方，我現(xiàn)在手里有3組牌，如果只有一組小牌，那么把它放的最后出就可以了。這個(gè)場(chǎng)景下，判斷一組牌的大小，是看對(duì)手有沒(méi)有可能接住它，而不是看它的絕對(duì)大小。先把如何“判斷大小”的細(xì)節(jié)放在一邊，先看看算法過(guò)程。

出牌贏牌路徑判定

1、先掃描一下所有的牌組，別人能接住的牌組數(shù)，記為s；
2、如果s=0或1，那么判定成功，只要把僅有的小牌放到后面即可；
3、如果s==2，假設(shè)這兩組牌為s1,s2；那么看剩下的牌里面是否有一組牌能接住s1，如果有，那么判定成功，此時(shí)出s1即可，s2也類(lèi)似；如果s1和s2都沒(méi)有牌能接住，判定失敗；
4、s>2，判定失敗。

接牌贏牌路徑判定

1、先找到一組能接住當(dāng)前牌的牌組，記為p，找不到則判定失??；
2、如果p是對(duì)手接不住的牌，那么看剩下的牌是否滿足“出牌贏牌路徑判定”；
3、如果p是對(duì)手能接住的牌，那么看剩下的牌組里面是否存在相同牌型的的當(dāng)前最大牌記為l（意思就是肯定能把牌再要回來(lái)，比如當(dāng)前出對(duì)子55，p是66，但是我手里還有22），再看剩下的牌（除了p和l）是否滿足“出牌贏牌路徑判定”；

判斷牌的大小

在贏牌路徑判定這個(gè)場(chǎng)景下，判斷一組牌的大小，是看對(duì)手有沒(méi)有可能接住它，而不是看它的絕對(duì)大小?？紤]三個(gè)因素：
桌面上還剩什么牌、我的手里有多少牌、對(duì)手還有幾張牌。依據(jù)這三個(gè)數(shù)據(jù)能計(jì)算出對(duì)手能接住某個(gè)牌組的概率。

算法大體是這樣的：
1、假設(shè)桌面上剩下牌的集合記作T，我手里的牌集合就做H，那么E=T-H是敵人手里牌的一個(gè)超集，敵人手里的牌張數(shù)是n，現(xiàn)在要牌組p能被敵人接住的概率；
2、如果敵人總的牌數(shù)n比p的張數(shù)還要少，那么p被接的概率等于敵人有火箭的概率；
3、看E里面能否找到能接住p的牌，如果找不到，那么p被接的概率等于敵人有火箭的概率；
4、如果找到一個(gè)牌組q能接住p，那么假設(shè)q包含的每張牌在敵人手里的概率是e/|E|,以二項(xiàng)分布的公式來(lái)計(jì)算敵人手里有q的概率；
5、如果能找到多組類(lèi)似的q，那么分別計(jì)算再以“或的關(guān)系”組合起來(lái)。

這個(gè)算法計(jì)算出的是一個(gè)大概的估計(jì)值，基本已經(jīng)夠用，而且我們并不考慮一般“炸彈”的存在，因?yàn)檎鎸?shí)的玩家也會(huì)傾向于忽略有普通炸彈的情況。

總結(jié)

從測(cè)試的情況來(lái)看，這個(gè)AI系統(tǒng)的效果還是可以的，看起來(lái)比較像人在出牌。這個(gè)實(shí)現(xiàn)方案有幾個(gè)顯著的缺點(diǎn)：
1、單純的對(duì)手牌評(píng)分局限很大，場(chǎng)上的局勢(shì)不僅包括我手里有什么牌，還包括主動(dòng)權(quán)的變化，桌面剩余牌的變化，沒(méi)有能找到一個(gè)合適的數(shù)據(jù)模型來(lái)統(tǒng)一這些因素；
2、由于前一個(gè)原因，導(dǎo)致算法不斷地針對(duì)特殊情況打補(bǔ)丁，上面的羅列的策略內(nèi)部，或多或少都有一些補(bǔ)丁，導(dǎo)致的后果就是算法的可維護(hù)性急劇下降，而且往往牽一發(fā)而動(dòng)全身；
3、不考慮上下文，比如不會(huì)針對(duì)某個(gè)人前面出過(guò)什么牌來(lái)猜測(cè)他手里有什么牌；
4、所謂按人的思維來(lái)建立策略，實(shí)際上就是按作者本人的打牌習(xí)慣，因此缺少一些變化，萬(wàn)一遇到?jīng)]考慮到的某種牌型，AI有可能犯傻；
5、沒(méi)有能設(shè)計(jì)出自動(dòng)化測(cè)試方案，我讓三個(gè)機(jī)器人來(lái)出牌，人工觀察是否有問(wèn)題，調(diào)試效率非常的低。