邱虹坤，郑晓东，王亚杰

(沈阳航空航天大学 a.计算机学院;b.工程训练中心，沈阳 110136)

机器博弈是人工智能领域最重要的研究方向之一，而非完备信息博弈是近期机器博弈研究的热点。现实生活中，处处充满了非完备信息博弈的例子，如拍卖、投标、竞价等。其中，投标过程与桥牌博弈极为相似。因为在投标时，首先要分析对方的可能出价和己方合理出价。这与桥牌中的叫牌相互吻合，同样是通过逐级递增的加价方式来实现互通牌情的过程(包含己方和对方)。而在打牌过程中的赢墩策略也与投标公司的战略相契合，同是在掌握信息有限的情况下进行博弈。因此，对桥牌博弈AI引擎的研究，是极具现实意义的[1]。

目前，更为精准的桥牌模型，逐渐成为研究者们关注的热点之一。在AMMAS2019入选论文中，就有一篇研究了基于神经网络构建叫牌系统的方法[2]。而所有叫牌方式的侧重点无一不是在于消除叫牌时产生的模糊信息，旨在得到唯一且精确的结果。但是连续3年获得冠军的Wbridge5是基于规则的，他们通过消除已有规则中的歧义和冲突来优化自己的系统，这样就会有一定的局限性，把系统的性能的上限局限在了人类已有的知识中。因此，想要继续提升桥牌AI的能力，需要从叫牌、打牌和评估函数3个方面分别给出优化的新思路。即构建精确叫牌体系、分阶段牌局策略及更为准确的评估函数。

1 叫牌优化

1.1 构建精确叫牌体系

桥牌主流的叫牌体系分为2种：自然叫牌体系和精确叫牌体系。传统的程序大多采用自然叫牌体系。自然叫牌法是最为常用的叫牌方式，并且大多数桥牌好手也在使用。但是对于计算机来说，由于其普适性与模糊性，对于同一牌型在不同的特定场合给出的不同叫品，这反而是模糊的[3]。与之相反，对于充满各种定约的精确叫牌体系更加适合程序理解人类的叫牌。

对于叫牌的初始状态，有6.35×1011种可能的牌局。首先对于手牌的大牌点数进行条件分类，细化为14类，再对每一类中的情况进行牌型分类，来决定开叫叫品。此时每一种牌局状况对应唯一叫品，同伴可以通过该叫品准确定位该叫品所对应的牌型及牌点范围[4]。从而构建出精确叫牌体系。

下面给出其中一组示例：11-15 4-4-1-4或4-4-0-5牌型，单缺为D，开叫2D。

pgame->honorCardPoint>=11&&pgame->honorCardPoint <=15

pgame->suit[1].cardnum==1&&pgame->suit[0].cardnum==4 &&pgame->suit[1].cardnum==4

pgame->suit[1].cardnum==0&&pgame->suit[0].cardnum==4 &&pgame->suit[2].cardnum==4

pgame->Open_RecordBid[0]=′2′;

pgame->Open_RecordBid[1]=′2′;

pgame->Open_RecordBid[2]=pgame->position;

sprintf_s(r_bid，80，"BID%c22"，pgame->position);

因为手牌总数为13张，故对于4-4-1-4和4-4-0-5只需要写出其中任意3个即可，返回叫牌结果为2D。

通过结构体数组对于手牌的存储，记录手牌花色、数量、牌型信息，通过record数组实现队友之间互通牌情，从而构建出精确叫牌体系。

1.2 叫牌体系二次优化

上述构建的精确叫牌体系，解决了叫牌模糊的问题，通过大量定约实现精准叫牌，更加适用于计算机。与此同时，大量定约所形成的代码量巨大，通常，仅仅实现部分定约，就需要代码量约 7 000行。代码冗余的问题瞬间暴露得一览无余。

出现此问题的原因在于程序之间的大量重复，比如相似的定约，却需要重新构建完整的if判断逻辑。为了简化代码，增加程序的可维护性和扩充性，提炼出共同因子，用struct Pai[]结构体数组进行表示。

综合考虑到牌力、牌型对于叫牌过程的影响，归纳出的共同因子可以分成三大类，即存储牌力上下限、存储手牌信息、返回叫牌结果[5]。

这三大类又可以细分为12个小类，即牌点上限、牌点下限、梅花张数、方片张数、黑桃张数、红桃张数、梅花大牌张数、方片大牌张数、黑桃大牌张数、红桃大牌张数、返回的叫牌花色和阶数。如图1所示。

图1 Pai数组具体实现

构建好数组后，每次叫牌不需要再进行n行if查询，只需要对应叫牌查询表，如开叫查询开叫表，争叫查询争叫表即可[6]。此处给出开叫表数组的部分示例(表1)，对于17×12的开叫表，其功能等价于500行左右代码量的if查询。

表1 开叫查询表部分示例

例如，第一行数据应理解为，通过评估函数计算得到的牌力范围在12～15之间时，并且4个花色的牌，数量均大于等于3(表现为average均匀牌型)，并且在梅花上有3张及3张以上大牌，那么开叫1梅花。

此时，如果想继续扩充定约，那么只需要在表格中新增行数据，省去了动辄成百上千行的代码量。至此，叫牌部分模糊性和代码冗余的问题得以解决。

2 打牌优化

2.1 传统经验打牌

传统的桥牌程序大多采用经验出牌，按照经验出牌的程序在遇到特定场景下的牌张组合，着实能打出不错的配合，但几率极小。如果试图穷尽桥牌的打牌组合，按照目前计算机的算力，又难以实现。

值得一提的是，单纯基于经验打牌策略，没有考虑到桥牌中存在的明手这一规则，使得己方相较于对方缺失了13张手牌的信息。而在比赛中，占据1/4的信息量。这部分信息所影响的牌局信息会成指数式增长，直接影响到整轮对局的发展趋势。

2.2 “monte Carlo+Dummy”打牌

针对于桥牌的信息非完备性，或者说对于所有的非完备信息博弈，一个重要的思路就是将非完备转换为完备。目前桥牌的主流算法就是“蒙特卡洛+双明手求解器”[7]打牌。通过蒙特卡洛算法大量生成对于牌型的限制，将这个限制传入到一个约束数组里，通过(爆炸式)生成牌局的方式，使得信息变为完备。此时，可以使用双明手求解器进行求解。

但该思路存在明显的不足之处：当牌局刚刚开始进行时，所掌握的信息极为有限，约束远远不足，爆炸式生成牌局过多，会发生栈溢出[8]。并且生成样本所需时间长，精准度低。通过实验测试，发现在前几墩牌中，程序往往会呈现“乱打”的现象。

该如何解决这个问题呢？如何既能够保证程序不会朝着错误的方向前进，又能进行非完备信息与完备信息之间的转化。给出的方案就是分阶段生成牌局，不同阶段采用不同策略。

2.3 新型混合打牌策略

首先将牌局分为2个阶段[9]，前一部分因为掌握的信息极为有限，适合采用精准度高，要求性高的经验打牌策略，后一部分因为信息逐渐暴露，掌握信息更多，采用蒙特卡洛+双明手求解器打牌方式。

经验打牌：

这里的经验打牌并不指传统的特定牌型下经验打牌，而是通过人为大量分析对局得到的。值得注意的是，在不同方位下，程序的打牌策略应该是完全不同的。

比如首攻，它的打牌原则应该是：穿强击弱。攻击己方最强的或者对方最弱的。通过存储己方叫牌信息，掌握己方叫过的花色，比如在和上，己方有过叫品，而对方在上也有过叫品，那么根据穿强击弱的原则[10]，此时应该主打的花色为。

下面给出伪代码，其功能是在程序中养成出顶张连续大牌的习惯。

bignum ←0

/*设置临时变量来存放大牌数量*/

for i ←0 to num do

if(putCard[i]/4)>0 then

bignum++;

if bignum>=5 then

for i ←0 to num do

if(putCard[i]/4)>0 then

index=i;

这样做有非常明显的好处。如图2所示牌局。

图2 牌局示意图

这幅牌局是叫的2◆，南北两家主打◆，如果北家攻击一张◆K，那么此时在固定了攻击连续大牌中的顶张，作为其队友(南家)完全可以意识到队友的K是其在◆上最大的一张牌，立刻反推出他一定有◆J◆Q◆K，并且没有◆A。再加上自己手里没有◆A，那么◆A一定在对方手里，通过这一张大牌，可以实现传递牌情信息量是原来的数倍[11]。

其余的各家都根据位置的不同，有其对应专属的打牌策略，所以在这里只列出首攻的部分打牌函数，其余类似但不相同，不做赘述。

在开局时，根据经验打牌旨在抢得一个良好的开局，但随着牌局情况的逐渐复杂，将很难再用经验去描述打牌过程。此时，应该采用具有完备信息博弈能力的蒙特卡洛算法加上双明手求解器进行求解的策略(图3)。

图3 蒙特卡洛算法+双明手求解器策略图

对于打牌来说，其主要的2个限制条件分别为“经验打牌策略所带来的复杂程度”以及“完备信息求解的准确性”。此时问题转化为“当牌局进行到何种程度时，由经验打牌转换为蒙卡算法+求解器求解”。

这里设置2个变量：N(牌的总数，在桥牌中为52)，D(牌局进行的轮数，在桥牌中为13)。

不妨假设，每位牌手在打牌时打出任意一张牌的可能性是相同的。此时则有，打出任意张牌的概率为：P打牌=1/(13-D+1)，而对于进行中的牌局来说，牌是动态的，即第一次出牌时牌张总数为N，那么下一次出牌，牌的总数为N-1，在每一墩中，牌况总数最多为：W牌况=(N)(N-4(D-1)-1)(N-4(D-1)-2)(N-4(D-1)-3)。此时可以将牌况的复杂程度近似看成是D的4次方函数。

这里对于每一墩的可能牌况为：V可能=C2X(X=N-13-4D)，表示目前仍然未知的牌中，选择两张(自己和队友每人一张)打出。这里减去的13是指，明手信息的13张牌可以被所有牌手看到，即可利用的信息。由于求解器的算法已经固定。求解器的能力正比于牌局预测的准确度。比值可以取K，给出一个衡量牌局准确性的指标(任何牌局适用)：S=K(N-13-4D)2/2-N4。将相关数据带入可以得到解，当进行到第三轮时，由经验分析策略转变为求解器分析可以获得的程序，准确度最高，收益最大[12]。

至此，提供了叫牌与打牌的新型策略。相应的，也需要一个更为精确的评估函数作为支撑。

3 评估函数优化

传统的评估函数采用高伦计点法来评估一手牌的力量，即A=4，K=3，Q=2，J=1。但如果牌值评估只做到这种程度，其准确性显然不足以满足中级以上桥手的需求。

为此，分为3点进行评估函数优化：

1)短门上的大牌进行调整(主要体现为扣点)；

2)长门上的调整(主要体现为加点)；

3)定约不同时的调整。

随机生成了一副牌局(随机数种子为135246)，以其中的北家为例进行说明：

假设北家手牌中的大牌和小牌分别如图4与图5所示。

图4 大牌

图5 小牌

采用如下方法对评估函数进行优化。

第一步，使用高伦计点法评估。

3*J+1*K+2*A=3*1+1*3+2*4=14

第二步，进行扣点。

由于单张大牌有被击落的可能性，所以对于KQJ分别扣1点。而单张的A由于不会被击落，所以只扣半个点。如果是双张时，那么KQJ扣半个点，A不扣点。A-num=1，牌点-0.5；KQJ-num=1，牌点-1；KQJ-num>1，牌点-0.5。

此时就有：单张红桃K，单张黑桃J分别扣1点，双张的梅花JA和方片JA，各扣半个点。

总计扣：1+1+0.5+0.5=3

此时牌点为：14+(-3)=11

第三步，进行加点。

此副牌在梅花上有AJ带头的6张好套，那么应该考虑到它所带来的赢墩潜力[13]，所以在这里可以+2.5。n张好套对应着(n/2-0.5)的赢墩潜力。

此时牌点为：11+(+2.5)=13.5

第四步，通过该局的王牌来进行加点。

如果在这局中梅花成为王牌，那么作为北家占据了大部分优势还应该再+2。即王牌花色为己方最强花色，牌力+2，为己方较强花色，牌力+1。

此时牌点为：13.5+2=15.5

最终得到的牌值，看似与起初差距不大(14—>15.5)，但是所考虑到的信息较于以前是更为完善的，这里考虑到了牌型、牌张、牌况对于牌力的影响，更吻合牌局中的实际情况。

4 实验

为检测新型打牌模型所带来的优化效果，设置2组对照实验。第1组实验是优化后的引擎与传统引擎对局(注：传统程序指2020年辽宁省计算机博弈竞赛一等奖获奖程序)，检验博弈引擎的综合能力。第2组实验是分别采用新型混合打牌策略和经验打牌策略进行对局。为避免叫牌差异所导致的影响，二者在相同叫牌体系下对弈。此外，由于精确叫牌体系和自然叫牌体系分属2个体系，无法直接比较好坏，故不设置打牌相同情况下叫牌准确度的对比(注：所有参与对比实验的程序均采用优化后的评估函数)。

这里对局是指，让两套程序在同一幅牌中均与测试程序对局，分别记录两套程序赢得的分数，并进行对比，借此检验优化引擎后桥牌程序的实战能力。

4.1 叫牌准确度测试实验

优化前后的程序分别与测试程序(优化前后程序均自主开发)对局500轮，共计1 000轮对局，检验优化后桥牌程序的综合能力是否有提升(图6)。

图6 综合能力测试结果

从图6中可以看出，橙色的线在蓝色线上方，比如在传统程序得到100分时，优化后的程序可以得到200分左右，而在传统程序得到-100分时，优化后的程序，往往可以负分更少，甚至少许赢分。那么根据测试结果，可以看出经过优化后的桥牌AI程序，有着更强的综合能力。

4.2 打牌能力测试实验

整体优化后的程序同叫牌部分优化的程序分别与测试程序对局500轮，共计1 000轮对局，检验优化后桥牌程序的打牌能力是否有提升(图7)。由于在同一叫牌体系下，得分相似的可能性较大，所以直接取绝对值进行比较。

图7 打牌能力对比曲线

这里取绝对值旨在更好地区分打牌能力，对于正分，取原本值，对于负分，在同一组牌局下，负的越少，证明能力越强，所以取同组中负分更多的绝对值进行表示。对照组程序和优化后程序均采用同样的叫牌策略，即精确叫牌法。在这里出现部分牌局下得分相同的情况，因为采用完全相同的叫牌，定约相同，得分相同的可能增大。从图7中可以看出，橘黄色的线在蓝色线的上方，即在采用相同叫牌策略下，优化后打牌策略要远远优于传统打牌策略。

通过上述实验，说明经过优化后，桥牌AI引擎对于牌局的分析更为准确，拥有更强的打牌能力。

5 结论

将经验性的代码与求解器混合，实现分阶段模拟牌局。首先，采用开局经验、中局和残局进行完备信息处理。接着，通过数学推导，计算得到分割不同策略界线的位置。最后，等信息暴露更完全，再进行策略转换，使得程序打牌能力更为稳定。此外，对于大量if造成的代码冗余问题，其关键部分在于存储牌局信息数据结构的设计。通过牌局信息分析，将所需信息抽象成结构体数组，对于程序的规范性与可维护性有极大帮助。通过多角度多方位优化，桥牌博弈AI的牌力获得较大提升，大大提高了获胜几率。

现实中，企业或国家间的竞争与合作是典型的非完备信息问题，与桥牌博弈极为相似。因此，构建桥牌混合策略模型，研究桥牌AI，对解决现实中的合作竞争关系问题具有重要的现实意义。