一种基于规则的斗地主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设计,都过于简单,用来自娱自乐还行,直接用于线上产品则远远不够。

拆牌算法

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

  1. 如果有火箭,找出来;
  2. 如果有炸弹,找出来(炸弹不拆);
  3. 如果有2,全部找出来(2不会参与顺子);
  4. 如果有飞机,找出来(飞机也不拆);
  5. 找出所有的顺子,每个顺子尽量长;
  6. 处理顺子
    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),直到没有进一步变化;
  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。

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

带牌选择

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

减少单张的拆牌

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

  1. "延长顺子“这一步不执行;
  2. 带牌选择的时候,优先选择单张

评分规则

一手牌到底好不好,我们需要一个量化标准,也就是给手牌评一个分值。否则没法决策是否叫地主,在接牌过程中也没法决策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},意思是索引13->P=6,索引46->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 兜底的策略

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

  1. 是否队友的牌;
  2. 我的牌是否非常好;
  3. 地主是我的上手还是下手;
  4. 对方还剩多少牌;
  5. 出牌大小;
  6. 接牌的大小;

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

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

第一步搜索接牌,不会考虑拆牌的结果,而是去手牌里面强行搜索,比如要接一对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、没有能设计出自动化测试方案,我让三个机器人来出牌,人工观察是否有问题,调试效率非常的低。

上一篇下一篇

猜你喜欢

热点阅读