設計目標

要取得良好效果窿冯，首先要搞清楚一個問題：我們想得到一個什么樣的斗地主AI伦籍？
我們的AI是用在手游產品當中善延，在真實玩家不足時為用戶提供陪玩服務悄晃，這個目標決定了這個AI要具備以下兩個核心特點：
1玫霎、執(zhí)行效率高，要為在線運行為玩家提供服務妈橄，不能給服務器太大壓力；
2翁脆、模擬人的思維方式眷蚓，讓AI看起來像一個中等水平的玩家，而不是追求很高的勝率反番。

斗地主的AI一般有三個核心部分：拆牌沙热、出牌叉钥、接牌。要提高算法的執(zhí)行效率篙贸，在這三個環(huán)節(jié)就不能完全依賴深度搜索的策略投队，在本設計方案中，所有的策略基本都是“靜態(tài)規(guī)則+有限搜索”的套路爵川。打個比方敷鸦，在拆牌過程中，我拆出了三張寝贡、對子扒披、單張之后，在給三張配帶牌的時候怎么選擇呢圃泡？我只會對單張碟案、對子做一下簡單的篩選，而不會去考慮是否把某個順子的尾部拆出來當帶牌會更優(yōu)颇蜡。

要讓AI看起來像人价说，其實就是把常見的一些出牌套路用算法表達出來。這里運用策略模式來組織代碼风秤，不同的策略有不同的優(yōu)先級鳖目，理論上，我們可以通過不斷地添加策略來完善這個AI唁情。打個比方疑苔，對于出牌，假設我們有以下三條策略（實際算法當然不止三條）：1)只剩一手牌策略甸鸟，直接出完就贏了惦费，2）只有一手小牌，其他全部大牌抢韭，小牌放到最后薪贫，其他從小往大出；3）小牌優(yōu)先策略刻恭，找出最小的牌來出瞧省。這幾個策略的優(yōu)先級就是1>2>3。

“搜索”在接牌過程中用得比較頻繁鳍贾，比如別人出一個三帶一鞍匾，我手上的牌拆出來是三帶一對，那么是把這個對子拆掉呢骑科，還是另外找一個單張橡淑。打個比方如果手上是"QQQkk345678"，那么顯然是帶一張3比較好咆爽，如果手上是“QQQKK56789”,那么應該拆對k梁棠。這里會對所有符合規(guī)則的帶牌做一個搜索置森，然后評判哪個方案是最優(yōu)的，于是關鍵點就是采用什么評判規(guī)則符糊。

我采用一種基于分值的手牌評價規(guī)則凫海，一手牌，無論多少張男娄，先進行拆牌行贪，然后每個牌組（牌組指單張、順子沪伙、對子等可以一次出掉的牌）都有一個分值瓮顽，最后把所有牌組的分值加起來，形成一個手牌分值围橡。上面所說的接牌搜索過程暖混，會進行反復的拆牌和分值計算，因此拆牌的算法必須非常高效翁授。

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

網(wǎng)上介紹的所有斗地主AI設計，都過于簡單塞赂，用來自娛自樂還行泪勒，直接用于線上產品則遠遠不夠。

拆牌算法

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

1. 如果有火箭宴猾，找出來圆存；
2. 如果有炸彈，找出來（炸彈不拆）仇哆；
3. 如果有2沦辙，全部找出來（2不會參與順子）；
4. 如果有飛機讹剔，找出來（飛機也不拆）油讯；
5. 找出所有的順子，每個順子盡量長延欠；
6. 處理順子
   1. 順子分裂陌兑，現(xiàn)有一個順子345678910，發(fā)現(xiàn)手上還剩下一張6和7由捎，那么順子分裂成34567和678910诀紊；
   2. 順子拆出連對，現(xiàn)有一個順子345678910隅俘，發(fā)現(xiàn)手上還有345邻奠，變成334455和678910更好，就把順子里面的345放回去为居；
   3. 順子拆出三張碌宴，現(xiàn)有一個順子345678，發(fā)現(xiàn)手上還有88蒙畴，那么變成34567和888更好贰镣，就把順子里面的8放回去；
   4. 順子如果蓋住對子膳凝、三張碑隆、連對，如果發(fā)現(xiàn)打散牌組數(shù)更少蹬音，則打散上煤，比如7789910JJJQKK，拆散了更好著淆；
   5. 順子拆出兩頭的對子劫狠，現(xiàn)有一個順子67890JQ，發(fā)現(xiàn)手上還有Q和6永部，那么把孫子里面的Q和6放回去独泞；
   6. 反復進行1）到5），直到?jīng)]有進一步變化苔埋；
7. 剩余的牌里面找出所有的連對懦砂；
8. 查看所有的連對，如果長度超過3组橄，且一端有三條荞膘，把三條拆出來；
9. 剩余的牌里面找出所有的三張晨炕；
10. 延長順子：如果一個順子的兩端外面有一個對子衫画，如果這個對子小于10，則并入順子瓮栗，比如34567+88,那么變成345678+8;
11. 合并順子：相同的順子變成連對削罩，首尾相接的順子連成一個；
12. 剩余的牌里面找出所有對子和單張费奸。

舉個例子弥激，一手牌“333455678910JJK22小王”：

1. 先把炸彈、2愿阐、王拆出來微服，剩下“333455678910JJK”
2. 找順子，得到345678910J缨历，剩下"335JK"
3. 由于順子的左側有3張以蕴，于是順子變成45678910J糙麦，剩下3335JK
4. 由于順子右側的J有一對，于是順子變成45678910,剩下3335JJK
5. 找三張丛肮，得到333赡磅；
6. 剩下的得到5、JJ宝与、K焚廊。

至此，一手牌就拆好了习劫，為了簡化算法咆瘟，我們不拆炸彈，不拆飛機诽里。在主動出牌時袒餐，會按著這個拆牌來出；在接牌時則不會须肆，會依據(jù)對方的牌型來搜索一個更優(yōu)方案匿乃，此時順子、飛機豌汇、炸彈都可能被拆散幢炸，具體細節(jié)下文會講。

帶牌選擇

上面拆好的牌組拒贱，三張和飛機是沒有帶牌的宛徊，在此基礎上選擇帶牌是比較容易的，就是在對子和單張里面選擇最小的牌即可逻澳。

減少單張的拆牌

一個常見的場景是闸天，當我的敵人只剩下一張牌時，此時應該采用一種“讓單張盡量少的策略”斜做，這個策略和常規(guī)策略大體相同苞氮，有兩個不同點：

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

評分規(guī)則

一手牌到底好不好笼吟，我們需要一個量化標準，也就是給手牌評一個分值霸旗。否則沒法決策是否叫地主贷帮，在接牌過程中也沒法決策A方案好，還是B方案好诱告，抑或不要才是最好選擇撵枢。

評分的大體理念是，對一個牌組來說，越能管牌锄禽，分值越大潜必；越不容易被管，分值越大沟绪。而一手牌的分值刮便，則不僅取決于拆出來的牌組的分數(shù)，還取決于拆出來牌組的組數(shù)绽慈，和前者正相關和后者負相關。

為了平衡辈毯，牌組的分值可能是正的坝疼，也可能是負數(shù)，以10為參考點谆沃，單張10為0分钝凶，9為-1分，J為1分唁影。每個牌組有一個maxCard屬性耕陷，單張和對子就是自身，順子和連對是最大那張牌据沈，三帶是有三張的那個牌哟沫，這個很容易理解，相同的牌型比較大小锌介，就是比較maxCard嗜诀。我們評分也基于這個屬性。

這個設定規(guī)則，是在調試過程中依據(jù)經(jīng)驗感覺不斷調節(jié)的出來的惶室。比如對子和三張的額外加分問題温自，是要體現(xiàn)出大對子比如(22)的價值。而順子分值公式拇涤，是基于“順子很難管牌捣作，分數(shù)不宜過高,但是本身也很難被管”這個事實。所以這組規(guī)則沒啥嚴密的邏輯鹅士，也不一定合理券躁。

接下來就是手牌的評分規(guī)則，也就是若干個牌組在一起怎么評分，最初的公式是：sum(牌組分)-PxN也拜，每個輪次設定一個固定的分值P以舒，用牌組分值的和減去P乘以牌組數(shù)量N。這個機制有一個很難解決的問題慢哈，就是P的取值蔓钟，P過大，過于強調輪次的價值卵贱，在牌局初期接牌的時候過于激進（無論出什么牌都導致總分值增加滥沫，因為輪次減少了）；P過小键俱，過于忽略輪次的價值兰绣，在牌局末期出牌過于保守（大牌攥著出不去，因為減少一個輪次加不了幾分）编振。

幾經(jīng)周折缀辩，最后定個兩個規(guī)則：
1、大牌的輪次忽略踪央，因為大牌總是出得去的（我們手上多個炸彈臀玄，不會有任何負面影響），包括王畅蹂、2健无、炸彈；
2魁莉、P的取值是一個列表:{ 6, 6, 6, 5, 5, 5, 4, 4, 4, 3}睬涧，意思是索引1_{3->P=6，索引4}6->P=5旗唁，索引7~9->P=4畦浓；之后P=3，這樣在早期一手大牌出去減分會比較多(這時減少一組牌所得到的輪次分增益比較少)检疫，到后期減分比較少讶请。

總體來說，牌的分值更多具有比較意義屎媳，而不具備絕對意義夺溢。我們在整個AI系統(tǒng)中，除了在叫地主時烛谊，盡量去比較兩個出牌方案的優(yōu)劣风响，而避免把一手牌的分值去和一個常數(shù)進行比較。

出牌策略

出牌策略就是在一種特定模式下的出牌套路丹禀，所以我們識別一個特定模式状勤，就可以編寫一個策略鞋怀。反過來，這個策略也會檢查一下持搜，當前的牌局是否符合對應的模式密似，如果不符合它就不處理，交給下一個策略處理葫盼。

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

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

牌的大小預測

在上面的策略中，提到一組牌是大還是小盅蝗，實際是指鳖链，這手牌對方接住的可能性大還是小。比如我有一個34567墩莫，對方只有3張牌芙委，而且王已經(jīng)出過了，那么我認為這順子是大牌狂秦。

我們合理地利用“出過的牌“灌侣，“我手里的牌”，“別人手上牌的數(shù)量”這個幾個信息裂问，做出上面的判斷侧啼。所謂“合理”牛柒，就是指正常的玩家，也知道這些信息慨菱，也能做出類似的判斷焰络；而不能去作弊開“天眼”。

策略之間的呼應

如果仔細琢磨一下符喝，可以發(fā)現(xiàn)allBig闪彼，foreEnemySingle，enemyOnePoke這幾個策略之間是相互呼應的协饲。這一輪使用了這個策略畏腕，如果順利，下一輪就可能落入另外一個模式茉稠，這也有點像真人的布局謀劃描馅。我在設計策略的時候，有兩個原則：1）策略上下文無關（以前的出牌過程不影響）而线；2）策略之間盡量互相呼應铭污。

接牌策略

接牌是被動的，所以策略相對少一些膀篮。
以農民接牌策略為例：

接牌策略里涧偷，這個兜底的策略是最難寫的，因為這里要決策接還是不接毙死，大體考慮以下幾個因素：

1. 是否隊友的牌燎潮；
2. 我的牌是否非常好；
3. 地主是我的上手還是下手规哲；
4. 對方還剩多少牌跟啤；
5. 出牌大小唉锌；
6. 接牌的大杏绶省；

我設計的兜底策略大體是這樣的：

1. 首先通過搜索找到一個能接牌的最佳牌組袄简，如果找不到腥放，就結束了；
2. 如果是隊友的牌绿语，相對還比較大秃症，我不接
3. 如果是隊友的牌候址，我肯定不用大牌接；
4. 如果是地主的牌种柑，我的牌絕對得好岗仑，肯定接；
5. 如果是地主的牌聚请，接了之后我的牌不變差太多荠雕，接；
6. 如果是地主的牌驶赏，我的接牌比他大得不多（比如王對2）炸卑，接；
7. 如果是地主的牌煤傍，接牌是順子盖文、飛機、連對這類蚯姆，接五续；
8. 如果是地主的牌，我要動用炸彈龄恋，如果他牌還很多返帕，出的又不是王和2之類，不接篙挽；
9. 如果是地主的牌，他的牌很少镊靴，或者他出大牌了铣卡，接。

第一步搜索接牌偏竟，不會考慮拆牌的結果煮落，而是去手牌里面強行搜索，比如要接一對QQ踊谋，我手里有KKK2235蝉仇，那么KK和22會先后被搜索到，然后判斷剩下手牌的評分來比較方案的優(yōu)劣殖蚕。

后面都是一些瑣碎的判斷轿衔，其中“多少分算絕對好牌”，“多少張牌算多”睦疫，都是比較主觀的設定害驹。

贏牌路徑

在出牌策略和接牌策略里，有一個優(yōu)先級最高的策略蛤育，即“贏牌策略”宛官，現(xiàn)在的牌面存在一個能贏的出牌方法葫松。打個比方，我現(xiàn)在手里有3組牌底洗，如果只有一組小牌腋么，那么把它放的最后出就可以了。這個場景下亥揖，判斷一組牌的大小珊擂，是看對手有沒有可能接住它，而不是看它的絕對大小徐块。先把如何“判斷大小”的細節(jié)放在一邊未玻，先看看算法過程。

出牌贏牌路徑判定

1胡控、先掃描一下所有的牌組扳剿，別人能接住的牌組數(shù)，記為s昼激；
2庇绽、如果s=0或1，那么判定成功橙困，只要把僅有的小牌放到后面即可瞧掺；
3、如果s==2凡傅，假設這兩組牌為s1,s2辟狈；那么看剩下的牌里面是否有一組牌能接住s1，如果有夏跷，那么判定成功哼转，此時出s1即可，s2也類似槽华；如果s1和s2都沒有牌能接住壹蔓，判定失敗猫态；
4佣蓉、s>2，判定失敗亲雪。

接牌贏牌路徑判定

1勇凭、先找到一組能接住當前牌的牌組，記為p匆光，找不到則判定失斕紫瘛；
2终息、如果p是對手接不住的牌夺巩，那么看剩下的牌是否滿足“出牌贏牌路徑判定”贞让；
3、如果p是對手能接住的牌柳譬，那么看剩下的牌組里面是否存在相同牌型的的當前最大牌記為l（意思就是肯定能把牌再要回來喳张，比如當前出對子55，p是66美澳，但是我手里還有22）销部，再看剩下的牌（除了p和l）是否滿足“出牌贏牌路徑判定”；

判斷牌的大小

在贏牌路徑判定這個場景下制跟，判斷一組牌的大小舅桩，是看對手有沒有可能接住它，而不是看它的絕對大小雨膨±尢危考慮三個因素：
桌面上還剩什么牌、我的手里有多少牌聊记、對手還有幾張牌撒妈。依據(jù)這三個數(shù)據(jù)能計算出對手能接住某個牌組的概率。

算法大體是這樣的：
1排监、假設桌面上剩下牌的集合記作T狰右，我手里的牌集合就做H，那么E=T-H是敵人手里牌的一個超集舆床，敵人手里的牌張數(shù)是n棋蚌，現(xiàn)在要牌組p能被敵人接住的概率；
2挨队、如果敵人總的牌數(shù)n比p的張數(shù)還要少附鸽，那么p被接的概率等于敵人有火箭的概率；
3瞒瘸、看E里面能否找到能接住p的牌，如果找不到熄浓，那么p被接的概率等于敵人有火箭的概率情臭；
4、如果找到一個牌組q能接住p赌蔑，那么假設q包含的每張牌在敵人手里的概率是e/|E|,以二項分布的公式來計算敵人手里有q的概率俯在；
5、如果能找到多組類似的q娃惯，那么分別計算再以“或的關系”組合起來跷乐。

這個算法計算出的是一個大概的估計值，基本已經(jīng)夠用趾浅，而且我們并不考慮一般“炸彈”的存在愕提，因為真實的玩家也會傾向于忽略有普通炸彈的情況馒稍。

總結

從測試的情況來看，這個AI系統(tǒng)的效果還是可以的浅侨，看起來比較像人在出牌纽谒。這個實現(xiàn)方案有幾個顯著的缺點：
1、單純的對手牌評分局限很大如输，場上的局勢不僅包括我手里有什么牌鼓黔，還包括主動權的變化，桌面剩余牌的變化不见，沒有能找到一個合適的數(shù)據(jù)模型來統(tǒng)一這些因素澳化；
2、由于前一個原因稳吮，導致算法不斷地針對特殊情況打補丁缎谷，上面的羅列的策略內部，或多或少都有一些補丁盖高，導致的后果就是算法的可維護性急劇下降慎陵，而且往往牽一發(fā)而動全身；
3喻奥、不考慮上下文席纽，比如不會針對某個人前面出過什么牌來猜測他手里有什么牌；
4撞蚕、所謂按人的思維來建立策略润梯，實際上就是按作者本人的打牌習慣，因此缺少一些變化甥厦，萬一遇到?jīng)]考慮到的某種牌型纺铭，AI有可能犯傻；
5刀疙、沒有能設計出自動化測試方案舶赔，我讓三個機器人來出牌，人工觀察是否有問題谦秧，調試效率非常的低竟纳。