一种基于规则的斗地主AI设计

2018-11-20 本文已影响350人 longhuihu

设计目标

要取得良好效果，首先要搞清楚一个问题：我们想得到一个什么样的斗地主AI？
我们的AI是用在手游产品当中，在真实玩家不足时为用户提供陪玩服务，这个目标决定了这个AI要具备以下两个核心特点：
1、执行效率高，要为在线运行为玩家提供服务，不能给服务器太大压力；
2、模拟人的思维方式，让AI看起来像一个中等水平的玩家，而不是追求很高的胜率。

斗地主的AI一般有三个核心部分：拆牌、出牌、接牌。要提高算法的执行效率，在这三个环节就不能完全依赖深度搜索的策略，在本设计方案中，所有的策略基本都是“静态规则+有限搜索”的套路。打个比方，在拆牌过程中，我拆出了三张、对子、单张之后，在给三张配带牌的时候怎么选择呢？我只会对单张、对子做一下简单的筛选，而不会去考虑是否把某个顺子的尾部拆出来当带牌会更优。

要让AI看起来像人，其实就是把常见的一些出牌套路用算法表达出来。这里运用策略模式来组织代码，不同的策略有不同的优先级，理论上，我们可以通过不断地添加策略来完善这个AI。打个比方，对于出牌，假设我们有以下三条策略（实际算法当然不止三条）：1)只剩一手牌策略，直接出完就赢了，2）只有一手小牌，其他全部大牌，小牌放到最后，其他从小往大出；3）小牌优先策略，找出最小的牌来出。这几个策略的优先级就是1>2>3。

“搜索”在接牌过程中用得比较频繁，比如别人出一个三带一，我手上的牌拆出来是三带一对，那么是把这个对子拆掉呢，还是另外找一个单张。打个比方如果手上是"QQQkk345678"，那么显然是带一张3比较好，如果手上是“QQQKK56789”,那么应该拆对k。这里会对所有符合规则的带牌做一个搜索，然后评判哪个方案是最优的，于是关键点就是采用什么评判规则。

我采用一种基于分值的手牌评价规则，一手牌，无论多少张，先进行拆牌，然后每个牌组（牌组指单张、顺子、对子等可以一次出掉的牌）都有一个分值，最后把所有牌组的分值加起来，形成一个手牌分值。上面所说的接牌搜索过程，会进行反复的拆牌和分值计算，因此拆牌的算法必须非常高效。

上面介绍了这个斗地主AI的核心设计思路，其中评分规则参考了这篇文章：https://blog.csdn.net/sm9sun/article/details/70787814；拆牌算法参考了这篇文章：http://www.360doc.com/content/11/0108/09/2617151_84917660.shtml，在此对两位作者表示感谢。

网上介绍的所有斗地主AI设计，都过于简单，用来自娱自乐还行，直接用于线上产品则远远不够。

拆牌算法

拆牌算法总体上是一个基于牌型优先级的查找过程：

如果有火箭，找出来；
如果有炸弹，找出来（炸弹不拆）；
如果有2，全部找出来（2不会参与顺子）；
如果有飞机，找出来（飞机也不拆）；
找出所有的顺子，每个顺子尽量长；
处理顺子
1. 顺子分裂，现有一个顺子345678910，发现手上还剩下一张6和7，那么顺子分裂成34567和678910；
2. 顺子拆出连对，现有一个顺子345678910，发现手上还有345，变成334455和678910更好，就把顺子里面的345放回去；
3. 顺子拆出三张，现有一个顺子345678，发现手上还有88，那么变成34567和888更好，就把顺子里面的8放回去；
4. 顺子如果盖住对子、三张、连对，如果发现打散牌组数更少，则打散，比如7789910JJJQKK，拆散了更好；
5. 顺子拆出两头的对子，现有一个顺子67890JQ，发现手上还有Q和6，那么把孙子里面的Q和6放回去；
6. 反复进行1）到5），直到没有进一步变化；
剩余的牌里面找出所有的连对；
查看所有的连对，如果长度超过3，且一端有三条，把三条拆出来；
剩余的牌里面找出所有的三张；
延长顺子：如果一个顺子的两端外面有一个对子，如果这个对子小于10，则并入顺子，比如34567+88,那么变成345678+8;
合并顺子：相同的顺子变成连对，首尾相接的顺子连成一个；
剩余的牌里面找出所有对子和单张。

举个例子，一手牌“333455678910JJK22小王”：

先把炸弹、2、王拆出来，剩下“333455678910JJK”
找顺子，得到345678910J，剩下"335JK"
由于顺子的左侧有3张，于是顺子变成45678910J，剩下3335JK
由于顺子右侧的J有一对，于是顺子变成45678910,剩下3335JJK
找三张，得到333；
剩下的得到5、JJ、K。

至此，一手牌就拆好了，为了简化算法，我们不拆炸弹，不拆飞机。在主动出牌时，会按着这个拆牌来出；在接牌时则不会，会依据对方的牌型来搜索一个更优方案，此时顺子、飞机、炸弹都可能被拆散，具体细节下文会讲。

带牌选择

上面拆好的牌组，三张和飞机是没有带牌的，在此基础上选择带牌是比较容易的，就是在对子和单张里面选择最小的牌即可。

减少单张的拆牌

一个常见的场景是，当我的敌人只剩下一张牌时，此时应该采用一种“让单张尽量少的策略”，这个策略和常规策略大体相同，有两个不同点：

"延长顺子“这一步不执行；
带牌选择的时候，优先选择单张

评分规则

一手牌到底好不好，我们需要一个量化标准，也就是给手牌评一个分值。否则没法决策是否叫地主，在接牌过程中也没法决策A方案好，还是B方案好，抑或不要才是最好选择。

评分的大体理念是，对一个牌组来说，越能管牌，分值越大；越不容易被管，分值越大。而一手牌的分值，则不仅取决于拆出来的牌组的分数，还取决于拆出来牌组的组数，和前者正相关和后者负相关。

为了平衡，牌组的分值可能是正的，也可能是负数，以10为参考点，单张10为0分，9为-1分，J为1分。每个牌组有一个maxCard属性，单张和对子就是自身，顺子和连对是最大那张牌，三带是有三张的那个牌，这个很容易理解，相同的牌型比较大小，就是比较maxCard。我们评分也基于这个属性。

牌型	分值	备注
单牌	maxCard-10
对子	maxCard-10	如果为正，+50%
三张	maxCard-10	如果为正，+100%
三带	maxCard-10	如果为正，+50%,因为带牌了比三张加得少
顺子	Max(0,(maxCard-10)/2)
连对	同上
飞机	同上
飞机带	同上，如果带牌的分数为正，把带牌的分数也加上
炸弹	固定9
火箭	12

这个设定规则，是在调试过程中依据经验感觉不断调节的出来的。比如对子和三张的额外加分问题，是要体现出大对子比如(22)的价值。而顺子分值公式，是基于“顺子很难管牌，分数不宜过高,但是本身也很难被管”这个事实。所以这组规则没啥严密的逻辑，也不一定合理。

接下来就是手牌的评分规则，也就是若干个牌组在一起怎么评分，最初的公式是：sum(牌组分)-PxN，每个轮次设定一个固定的分值P，用牌组分值的和减去P乘以牌组数量N。这个机制有一个很难解决的问题，就是P的取值，P过大，过于强调轮次的价值，在牌局初期接牌的时候过于激进（无论出什么牌都导致总分值增加，因为轮次减少了）；P过小，过于忽略轮次的价值，在牌局末期出牌过于保守（大牌攥着出不去，因为减少一个轮次加不了几分）。

几经周折，最后定个两个规则：
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系统中，除了在叫地主时，尽量去比较两个出牌方案的优劣，而避免把一手牌的分值去和一个常数进行比较。

出牌策略

出牌策略就是在一种特定模式下的出牌套路，所以我们识别一个特定模式，就可以编写一个策略。反过来，这个策略也会检查一下，当前的牌局是否符合对应的模式，如果不符合它就不处理，交给下一个策略处理。

有些策略适用于农民，有些适用于地主，这里我们罗列一下农民的出牌策略，按优先级从搞到低：

策略	适用模式	出牌
oneHand	手里只剩一组牌	出完即赢
allBig	手里只有一组小牌,其他大牌	先出大的，再出小的
foreEnemySingle	敌人只有两张牌，我有绝对的大单，其他都是对子	出单，迫使对方出单
letFirend	我下手是队友，只有一张牌，且我有<10的牌	出小单张
smallAndLong	有些小的顺子、连对、飞机	先出这些
fewPoke	牌比较少的时候	优先出单张以外的牌
enemyOnePoke	地主一张牌时，我在他上手	尽量出其他牌型，否则从大往小
enemyOnePoke	地主一张牌时，我在他下手	如果有对子，而且单张很多，出非最小单张，期望和对家配合，否则同上
smallFirst	兜底的策略	小牌优先出

理论上，如果我们找到新的模式，就可以创建新的策略添加到这个列表，我们的AI也就越完善。

牌的大小预测

在上面的策略中，提到一组牌是大还是小，实际是指，这手牌对方接住的可能性大还是小。比如我有一个34567，对方只有3张牌，而且王已经出过了，那么我认为这顺子是大牌。

我们合理地利用“出过的牌“，“我手里的牌”，“别人手上牌的数量”这个几个信息，做出上面的判断。所谓“合理”，就是指正常的玩家，也知道这些信息，也能做出类似的判断；而不能去作弊开“天眼”。

策略之间的呼应

如果仔细琢磨一下，可以发现allBig，foreEnemySingle，enemyOnePoke这几个策略之间是相互呼应的。这一轮使用了这个策略，如果顺利，下一轮就可能落入另外一个模式，这也有点像真人的布局谋划。我在设计策略的时候，有两个原则：1）策略上下文无关（以前的出牌过程不影响）；2）策略之间尽量互相呼应。

接牌策略

接牌是被动的，所以策略相对少一些。
以农民接牌策略为例：

策略	适用模式	出牌
oneHand	手里只剩一组牌，且能接	接牌
jieAndWin	接完之后，进入上面的allBig模式	接牌
enemyOnePoke	地主一张牌，在我下手	除非队友出牌足够大，否则尽量用大牌接
letFriend	队友下手，且只有一张牌，我有<10的牌	尽量大牌接
normal	兜底的策略

接牌策略里，这个兜底的策略是最难写的，因为这里要决策接还是不接，大体考虑以下几个因素：

是否队友的牌；
我的牌是否非常好；
地主是我的上手还是下手；
对方还剩多少牌；
出牌大小；
接牌的大小；

我设计的兜底策略大体是这样的：

首先通过搜索找到一个能接牌的最佳牌组，如果找不到，就结束了；
如果是队友的牌，相对还比较大，我不接
如果是队友的牌，我肯定不用大牌接；
如果是地主的牌，我的牌绝对得好，肯定接；
如果是地主的牌，接了之后我的牌不变差太多，接；
如果是地主的牌，我的接牌比他大得不多（比如王对2），接；
如果是地主的牌，接牌是顺子、飞机、连对这类，接；
如果是地主的牌，我要动用炸弹，如果他牌还很多，出的又不是王和2之类，不接；
如果是地主的牌，他的牌很少，或者他出大牌了，接。

第一步搜索接牌，不会考虑拆牌的结果，而是去手牌里面强行搜索，比如要接一对QQ，我手里有KKK2235，那么KK和22会先后被搜索到，然后判断剩下手牌的评分来比较方案的优劣。

后面都是一些琐碎的判断，其中“多少分算绝对好牌”，“多少张牌算多”，都是比较主观的设定。

赢牌路径

在出牌策略和接牌策略里，有一个优先级最高的策略，即“赢牌策略”，现在的牌面存在一个能赢的出牌方法。打个比方，我现在手里有3组牌，如果只有一组小牌，那么把它放的最后出就可以了。这个场景下，判断一组牌的大小，是看对手有没有可能接住它，而不是看它的绝对大小。先把如何“判断大小”的细节放在一边，先看看算法过程。

出牌赢牌路径判定

1、先扫描一下所有的牌组，别人能接住的牌组数，记为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）是否满足“出牌赢牌路径判定”；

判断牌的大小

在赢牌路径判定这个场景下，判断一组牌的大小，是看对手有没有可能接住它，而不是看它的绝对大小。考虑三个因素：
桌面上还剩什么牌、我的手里有多少牌、对手还有几张牌。依据这三个数据能计算出对手能接住某个牌组的概率。

算法大体是这样的：
1、假设桌面上剩下牌的集合记作T，我手里的牌集合就做H，那么E=T-H是敌人手里牌的一个超集，敌人手里的牌张数是n，现在要牌组p能被敌人接住的概率；
2、如果敌人总的牌数n比p的张数还要少，那么p被接的概率等于敌人有火箭的概率；
3、看E里面能否找到能接住p的牌，如果找不到，那么p被接的概率等于敌人有火箭的概率；
4、如果找到一个牌组q能接住p，那么假设q包含的每张牌在敌人手里的概率是e/|E|,以二项分布的公式来计算敌人手里有q的概率；
5、如果能找到多组类似的q，那么分别计算再以“或的关系”组合起来。

这个算法计算出的是一个大概的估计值，基本已经够用，而且我们并不考虑一般“炸弹”的存在，因为真实的玩家也会倾向于忽略有普通炸弹的情况。

总结

从测试的情况来看，这个AI系统的效果还是可以的，看起来比较像人在出牌。这个实现方案有几个显著的缺点：
1、单纯的对手牌评分局限很大，场上的局势不仅包括我手里有什么牌，还包括主动权的变化，桌面剩余牌的变化，没有能找到一个合适的数据模型来统一这些因素；
2、由于前一个原因，导致算法不断地针对特殊情况打补丁，上面的罗列的策略内部，或多或少都有一些补丁，导致的后果就是算法的可维护性急剧下降，而且往往牵一发而动全身；
3、不考虑上下文，比如不会针对某个人前面出过什么牌来猜测他手里有什么牌；
4、所谓按人的思维来建立策略，实际上就是按作者本人的打牌习惯，因此缺少一些变化，万一遇到没考虑到的某种牌型，AI有可能犯傻；
5、没有能设计出自动化测试方案，我让三个机器人来出牌，人工观察是否有问题，调试效率非常的低。