张志刚

（辽宁科技大学网络信息中心，鞍山　114051）

双明手桥牌打牌辅助分析程序研究

张志刚

（辽宁科技大学网络信息中心，鞍山114051）

0　引言

随着人工智能技术的迅速发展，棋类游戏领域的计算机实现研究已经日趋完善。尤其是中国象棋、国际象棋、围棋的人工智能程序已经发展到了能和人类的大师级棋手直接对弈，并能够取得胜利。“深蓝”就是一个最好的证明。但是，对于牌类游戏的研究，特别是桥牌的计算机程序的实现，却没有达到棋类的智能程度。其主要原因就是，棋类游戏的信息是清晰明了的，可以用一定的数据结构直接提供给计算机进行智能决策；但是牌类游戏，尤其是桥牌其信息具有不完整性，即除了目前已经打出的牌和明手牌外，不知道其他牌友中有什么牌，因此，计算机程序必须通过部分牌局信息推断可能的牌型，从而做出下一步打法的决策。信息的不完整性和不对称性，使得牌类游戏的求解在搜索策略上不能完全等同于或直接利用棋类游戏的技术，同时，也增加了牌类游戏的求解运算开销。这就是牌类游戏的研究没有赶超棋类游戏的主要原因。

对于牌类游戏的研究，桥牌计算机程序最具典型性，桥牌的搜索空间［1］和求解难度都比较大，目前的搜索方法有好多种。本文描述的是采用基本的回溯剪枝策略设计的双明手桥牌的自动打牌系统。在双明手情况下，所有的信息不完整和不对称的情况都不存在，所以可以使用基本的剪枝策略就可以找出自动打牌的步骤。

1　系统设计

双明手桥牌打牌辅助分析程序主要是将用户输入的牌局信息，可以是全部，可以是部分牌以及定约情况输入给系统，系统会自动进行打牌，给出一种取胜的策略［2］。

定理1任意初始牌局要么为南北方取胜牌局，要么为东西方取胜牌局，并且存在判定给定初始牌局是否为南北方取胜还是东西方取胜。

引理1若存在算法判定任意k+1阶牌局是否是南北方取胜牌局，则存在算法判断任意k阶牌局是否为南北方取胜牌局。

上述定理和引理描述了桥牌取胜的必然性，在文献［1］中给出了定理的详细证明过程。文献中取胜策略算法的运算量是比较大的，本文没有采用，而是使用带有位运算的回溯剪枝策略来迅速获得给定牌局的解，并辅以可视化实现，便于牌手进行结果的分析。

程序工作流程如下：

首先，读入牌局信息。牌局信息包括：将牌的花色、当前哪家出牌、南北家要赢多少墩、目前还需要几墩牌才能结束和四家手中的牌详细信息。

然后，系统根据目前的牌局信息进行自动打牌，代理机会尽力搜索利于南北方赢墩的策略打牌。根据定理1和引理1可以断定，肯定存在一个取胜打牌序列，如果南北方不能获胜，则系统会尽量减少宕墩数目。

最后，将计算出的打牌次序显示出来。

2　打牌算法

该程序的采用的是深度优先的alpha-beta搜索来实现。算法处理过程如下：

（1）读入基础数据：包括将牌花色，剩余圈数，南北因该完成的定约，本圈牌权者，及本轮其要出的牌，牌手手中剩余的牌。

（2）整理剩余牌的数据，对数据进行排序与处理。

（3）如果本轮牌权所有者指定了要出的牌，检查其合理性，如果有则作为第一张牌，如果没有则退出过程，提示出错。

（4）深度搜索打牌序列，打出第一张牌后，产生下家的出牌，产生的原则：

如果当前出牌者不是庄家，并且他有本轮首发花色的牌，则选择同花色的最小牌；否则选择非将牌花色最大牌。相反，如果是庄家出牌，选择出牌的原则与之相反。

（5）确定本轮打牌的赢家，继续下一轮出牌，转（4）。

（6）如果完成定约则输出合理的打牌序列，否则输出没有可行解。

3　系统的实现

上述算法通过CB加以实现，程序界面形式如图1所示。

图1　分析程序界面

用户可以手动输入牌局信息或者通过文件读入文件。文件的格式如下：

文件的第一行数字4表示将牌花色，0-S，1-H，2-D，3-C，4-NT；第二个数字6表示剩余圈数，即目前的牌局还需要多少轮打牌才能结束；第三个数字5表示南北方还需要赢多少墩牌才能完成定约，如果想知道东西方的情况，处理以下数据就可以了；第四个数字表示当前的牌权在东西南北那家，0-北1-东2-南3-西；文件接下来的四行数据分别表示北东南西，四家手中目前剩余的牌，不用排列大小，系统会自动排序。最后一行数据表示目前牌权获得者想出哪一张牌，如果不想出的话就输入XX。

根据上面的数据说明，可以看出，此程序的功能可以实现中途打牌或全局打牌的情况，基本上比较灵活。用户可以根据自己的需要来准备响应的数据就可以了。如果用户不想通过文件读入数据的话可以在界面上直接输入数据。为了提高程序的友好度，程序提供了按要求随机生成牌局数据，但是叫牌和首攻信息最好用户的输入，因为随机产生数据不一定符合叫牌的常规，也就是说可以是错误的叫牌结论。在此并没有加入叫牌的判断逻辑。数据准备完毕就可以运行程序来求出合理的打牌序列，看是否能够找到完成定约的打牌序列。此程序只要找到完成所需的墩数的打牌序列就会退出，不会计算超墩的情况。

4　实验分析

为了测试本程序算法的能力，在网上找了一些具体的打牌实例，通过本程序进行自动生成打牌序列。以下是在网上找到的一个比较困难牌局：

程序生成的打牌序列如下：

将牌是：Hearts；

West出第一张牌是QS；

南北家需得墩数：13；

定约是否能完成：Yes；

程序找到打牌序列如图2所示。

图2　程序生成的打牌序列

为了找到合理打牌序列，此程序运行了大约3分钟，最终还是找到了一个合理打牌序列。虽然找到了合理的打牌序列，但是时间还是比较长。

为了测试算法的平均效率执行情况，将网上的数据经过整理都处理成完成定约，即将东西方完成定约的直接转换成南北方完成定约的情况。所以测试数据在打牌的过程中都是成功完成定约情况。以下是数据实验分析结果见表1。

表1　实验数据分析表

数据表1中最短时间基本上不到1秒钟，通过平均运算时间可以看出程序会在2秒钟左右计算出打牌的序列。在随机生成数据中，因为包括叫牌在内的数据都是随机生成的没有考虑到叫牌的因素，所以运行的时间比真实的数据稍长，但基本上在3秒钟左右也会得出结论。

该算法采用的是对双明手桥牌的进行深度搜索，从实验数据中可以看出性能不是很好，但是为进一步研究和实现自动化桥牌程序设计奠定了研究条件。

5　结语

给出了一个采用深度优先的alpha-beta搜索技术实现的玩家打牌分析程序，该程序可以帮助玩家辅助决策打牌。本程序稍作修改就可以实现最基本的人机博弈，为将来非确定性的推理问题的研究工作奠定了基础。

［1］王彩霞，战学刚，迟呈英．桥牌游戏搜索空间的研究．微计算机信息［J］，2007（23），10-2：199-200．

［2］何大华，陈传波．关于桥牌的取胜策略．华中科技大学学报［J］，2004，7．

Double Dummy Bridge Play；Depth-First；alpha-beta Search Method

Research on Double-Dummy Bridge Playing Cards-Assisted Analysis Program

ZHANG Zhi-gang

（The Network and Information Center，University of Science and Technology，Liaoning 114051）

1007-1423（2015）34-0047-04

10.3969/j.issn.1007-1423.2015.34.013

张志刚（1980-），男，内蒙古赤峰人，硕士，工程师，研究方向为自然语言处理、算法设计与分析

2015-11-03

2015-11-17

桥牌计算机自动打牌程序的设计与实现关键在于问题空间的搜索，而桥牌的搜索空间非常大，而对于传统的蛮力搜索则面临较大困难，因此提出解决双明手桥牌的深度优先的alpha-beta搜索算法，并采用C++Builder程序设计语言加以实现。实验证明，该算法具有深入研究的价值，同时为计算机桥牌游戏智能化研究打下理论基础。

双明手桥牌；深度优先；alpha-beta搜索算法

The key problem of design and implementation of the computer automatically playing the Bridge Game lies in the search space，and bridge game's search space is very large，and the traditional brute-force search method cannot easily solve it，and therefore proposes to solve double dummy bridge the depth-first alpha-beta search algorithm，uses C++Builder programming language to implement the algorithm，the experiments show that the algorithm has in-depth study of value.It is a fundamental study for the intelligent computer bridge game.