引入合作竞争关系的桥牌叫牌数据库构建

邱虹坤,郑晓东,王亚杰

(1.沈阳航空航天大学 计算机学院, 沈阳 110136;2.沈阳航空航天大学 工程训练中心, 沈阳 110136)

0 引言

在围棋被攻破之后，机器博弈领域现在唯一尚未被攻破的顶级智力运动(按照国际智力运动会的项目)就只剩下桥牌。桥牌博弈中包含的人类行为难以被计算机理解，特别是叫牌部分，短时间内人工智能很难在桥牌上与人类抗衡[1]。在叫牌过程中，有意义的叫品仅有5×7=35种，但配合熟练的桥手通过这些有限叫品，与不同的牌情相结合可以传递出大量信息，如图1所示。对于AI来说，最难的就是如何在这些叫品中，实现牌局信息的传递，并且尝试理解对手之间传递的信息甚至加以干扰。

目前桥牌叫牌数据库更多在于如何详细地描述自然叫牌法或者精确叫牌法，对于构建桥牌叫牌数据库本身的研究较少，并且目前数据库大多未能考虑在实际牌局中人类牌手通过叫品结果想要传达出来的信息。事实上，对于牌局而言，在不断达成定约过程中所暴露出来的信息恰恰是最重要的。这是解决桥牌博弈问题，必须要经过的一环。由此可见，对于能够存储牌情信息的数据库的设计与研究非常有必要。

图1 有意义叫品

1 数据预处理

在桥牌开局后，每人分配13张手牌。此时每人所掌握的信息，便只有这13张牌，直至在叫牌过程中通过逐渐沟通牌局信息，信息才初步展露。所以在进行信息沟通之前，要将自己的手牌信息整理好，才能在接下来有限叫品空间中实现更为全面的信息沟通[2]。数据预处理流程如图2所示。

图2 数据预处理流程框图

由于手牌有限，所以直接可以推断出来的信息同样有限，可以将其分为3类信息：

2) 4种花色的K，Q，J均为大牌，在吃墩的时候有很大的潜力，对于牌力的提升起到很大作用，称它为大概率吃墩。

3) 对于剩余的小牌，通过某些固定配合，如将吃等，仍然可以赢得墩数。为了尽可能多地分析手牌信息，称它为小概率吃墩。

引入这些标识的目的在于，在叫牌阶段开始前，先通过评估自己的手牌信息，来预测自己能够达成的定约[3]，为后续开始叫牌提供扎实的基础。

2 设计叫牌数据库

2.1 数据库格式

数据库范式分为1NF，2NF，3NF，BCNF，4NF，5NF。符合高一级的范式，必定符合低一级范式。低级的范式容易满足，但同时有可能带来一些操作异常[4]。更高级的范式相对稳定，但可能带来处理速度缓慢和处理逻辑复杂的问题。

如果构建符合1NF的数据库，此时同样的一组手牌信息将会多次重复存储，造成冗余过大，不利于大量叫牌信息的存储。当数据库满足2NF规则时，如果牌局信息中存在传递函数依赖[5]，则会体现为不同的手牌信息可以间接推出同一个结论，造成了空间浪费。对于符合3NF规则的数据库，可以认为其在时间和空间上均可以满足桥牌叫牌数据库的要求。故构建一个符合3NF标准的桥牌叫牌数据库是合理的。

2.2 桥牌叫牌数据库的具体构建

有了数据库的格式规范后，可以开始设计数据库中表的结构，在桥牌中叫牌结果由叫牌阶数和叫牌花色组成。对于不同的手牌信息，数据库应该返回不同的叫牌结果[6]。这时需要用到的信息有数据预处理信息，长套标识，己方预估达成定约的阶数，等等。通过这些信息的多重组合来得到数据元素之间的关系，如图3所示。

图3 数据库元素关系图

数据库需要根据仅有的13张手牌，进行牌力评估，刻画出此时想要传达给队友的信息。比如通过查找对应牌型、牌张信息下的牌力，得到对应推荐的叫牌阶数与花色[7]。同样，在得到队友或者对手的回复后，应该通过其反馈的新一轮叫牌阶数与花色继续更改自己的期望叫牌。

3 引入合作与竞争向量

在非完备信息博弈中，桥牌由于存在队友之间的合作与竞争，难以通过已有的算法对其进行表示。这里提出了一种在数据库中，对牌局行为给予合作竞争标识的机制。

通过叫牌方位判断给予队友和对手标识。对于北->东->南->西分别标识0,1,2,3。此时设某人行动方位为X，自己行动方位为Y，则 |Y-X|%2=0，此时两者为队友，否则为对手。

合作向量主要表达信息为：所要达成的定标位置。如己方在黑桃上点力强劲，队友叫到3，己方发现自己上牌力同样优秀，此时直接叫到5，甚至更高。这本身是无可厚非的，但会导致本来可以传递更多信息的叫牌空间被浪费[8]。在叫牌中叫牌空间共35格，所以为了能够节约叫牌空间，在合作关系中引入一个“over”标志伪代码为：

while(pass数量<3):

{

over->0

if BIDnext.order-BIDnow.decor>1：

over->1

BID赋予其他含义

else:

BID表示当前所叫牌的花色与阶数

}

图4 叫品机会损失示意图

通过合作向量的使用，可以最大限度地发挥桥牌叫品的信息传递功能，通过空分复用的方式来表达多种含义，增加了有限叫牌空间中叫牌意义的表示能力[10]。

竞争向量主要用来对敌方叫牌信息进行干扰，通过观察连续出现次数最多的相关花色，判断对方想要达成的花色优先级。伪代码为：

While(pass数量<3)

{

Init花色优先级队列

If (|Y-X|%==2):

{

开发者应及时在微信推送下方留言区与读者进行互动，这样有利于了解读者的想法，采纳读者的建议，并据此完善公众号的服务。

记录敌方连续叫品:

记录每个花色出现次数

}

update花色优先级队列

if：(敌方优先级最高花色=我方)

do：合作

else：{

敌方当前花色优先级降低

}

}

此时将合作与竞争向量和花色优先级队列融合引入数据库中，使得数据可以表达此时牌局中的对局情况，通过记录合作与竞争之间的次数来更详细地表达当前牌局信息。

4 引入模糊数学

4.1 模糊数学在桥牌上的理解

模糊数学是解决界限不分明问题的数学工具，被广泛应用于模糊决策、模糊识别等领域。而桥牌比赛的叫牌阶段中，桥手会将自己手牌的信息传递给自己队友或者用其来迷惑对手，此时某单一叫品所能表达的含义是模糊的，无法通过一一对应的方式描述。同理，在对手之间捕捉到的信息，往往与表面上看到的不符。此时信息的特点可以归结为非单一和非具体的，由此观之，桥牌叫牌中展现出的模糊性是不可避免的。

但是这不应该理解为“模模糊糊”，基于模糊数学的思想来解决桥牌叫牌问题应该理解为：通过精确的数学手段对桥牌叫牌所表达的信息进行刻画，并且该刻画过程应该是极为严密的。

4.2 模糊数学在桥牌上的应用

桥牌的叫牌部分无法通过的二值逻辑对其进行描述，此时引入模糊数学中的一个重要概念——模糊集合[11]。对于模糊集合来说，给定范围内元素具有隶属关系，对于它的隶属关系不能通过简单的“是”或“否”来表示，而应该用一段区间来刻画其隶属程度。

如表1所示，当获得同伴想要达成的阶数信息时，结合己方手牌牌力，以不同概率的形式将己方的支持程度传递出去。值得注意的是，事实上这里的概率应该与手牌的牌力、牌情等信息存在某种函数关系，这一过程会涉及很多专业桥牌知识。在这里只通过人为经验给出部分区间下，不同应答的隶属程度。

表1 叫牌阶数信息表

手牌的牌力直接影响着最终能否达成的定约高度，手牌的牌张信息影响着最终定约停留的花色。越是强力的花色，越希望最终定约可以停留在此花色上。同样，这种希望也不是单一的，即可能希望停留在，又希望停留在，但这2个希望的概率是不一样的。通过不同花色优先级对希望的隶属程度进行刻画[12]。叫牌花色信息如表2所示。

表2 叫牌花色信息表

此时，通过引入模糊数学中模糊集合的概念，使用不同的隶属关系来解释桥牌叫牌过程中同一叫品表现不同含义的情景，并通过经验分析给出不同情景下所对应的隶属程度值。

5 实验测试

5.1 对比结果说明

新数据库与传统自然叫牌法或精确叫牌法对应的数据库在存储信息能力上的对比：

1) 使用更少的存储单元：自然叫牌法需要将4种花色的手牌数量全部存储。事实上更应该关心的是不同花色之间的强弱之分，牌张更多、牌点更强劲的花色显然更值得达成定约。此时可以用一个花色优先级来取代4种花色的手牌数量。(注：这里花色优先级所对应的数字，是将4种花色的牌力优先级按照S，H，D，C进行排序的一种排列组合，如1对应S>H>D>C，2对应S>H>C>D，这样相当于用1个存储单元存储了传统数据库中4个存储单元的信息。)

2) 增加合作与竞争关系：新数据库增加了额外含义标识。对遇到对手和队友叫牌的不同情况可以回应不同叫品，使有限的叫品空间被充分利用。

3) 与数据预处理关系密切：由于加入数据预处理部分，新数据库的表达能力与数据预处理的结果联系密切。这意味着在数据预处理部分的能力越强，数据库的存储信息能力也变得越强。而传统数据库能力仅与自然叫牌法，或精确叫牌法相关。

4) 引入模糊数学概念：传统数据库每条记录严格对应一个结果，而在任何一种牌局的情况下，叫品结果应该有多种可能性。这里通过经验对这种可能性予以评估，能够更真实刻画牌局情况。

5.2 实例分析

这里随机生成一副手牌，如图5所示，对其进行叫牌分析(以开叫为例)。

图5 随机手牌

此副手牌大牌点为4+3+2+1+1=11(A=4，K=3，Q=2，J=1；10及以下的牌不计算点力)，牌型为5-4-2-2。精确叫牌法所对应数据库格式如表3所示。

表3 精确叫牌法对应传统数据库格式(开叫为例)

此时按照精确叫牌法应该选择1H。可以传递出来的信息有：牌点在11～15之间，红桃有5张套。对应在数据库中则会经过如下分析：

表4 新数据库对应格式(开叫为例)

该数据库格式可以传递出来的信息有：在这副手牌中一定能打赢的牌有几张、大概率打赢的有几张、有几率打赢的有几张。这副牌预期能够达到某种定约、达到这个定约的概率是多少。相较于传统的自然、精确叫牌法数据库所能存储、表示的信息更为丰富。此外，由于数据预处理与概率的引入，计算机可以通过计算来更准确了解此时牌局的进行过程。而这部分，更取决于预处理部分以及隶属函数的准确程度，可以通过计算机强大的算力和桥手的丰富经验可以提升，使其不再仅仅局限于叫牌体系的扩充。

当然，引入了模糊集合概念之后，同样也带来了新的问题，比如不同手牌信息下对应的隶属程度数值应该与手牌信息存在某种函数关系，而不是单一的某些区间某些值。这些需要更多的桥牌专业知识来支持，通过具体分析多种牌局实例，来构建不同状态下，对应吃墩可能性的函数关系。此外，若数据库扩展到一定规模后，可能会存在搜索超时等问题，这些都需要后续继续研究。

6 结论

本文将数据库智能化的思想与桥牌叫牌数据库构建相结合，通过引入更多元素实现对于桥牌叫牌过程更为详细的刻画。通过概率问题，对叫牌中存在的单一叫品传递多种信息问题进行解决，是解决桥牌问题中的模糊性的重要一步。

数据库能够表示越多、越详细的信息，可以使桥牌AI环节减轻负担。此时AI可以更多地将注意力放在算法上，一定程度上忽略底层桥牌规则。相较于人类桥牌选手之间的默契配合，该数据库还有很大优化空间，捕捉更多的动作细节进行描述，使AI能够更贴切地模拟人类选手打牌。