关于桥牌的取胜策略

收稿日期：2003-08-14作者简介：何大华(1973-)，男，博士研究生；武汉；华中科技大学计算机学院(430074)；emal:[e-mail]-1-关于桥牌的取胜策略何大华陈传波（华中科技大学计算机科学与技术学院，武汉430074）摘要：在桥牌运动中，若将四家的牌摊开来打，则存在判定初始牌局是否为南北方胜牌局(或东西方胜牌局)的算法，当南北方(或东西方)客观上存在取胜策略时，则存在算法来实现其取胜步骤。本文给出的算法不仅在可计算性意义上是最好的算法，并且计算量小。关键词：桥牌,博弈,可计算性,计算复杂性中图分类号：TP18TheWinningStrategyforBridgeGameHEDa-HuaCHENChuan-Bo(CollegeofComputerSci.&Tech.,HuazhongUniversityofSci.&Tech.,Wuhan430074)Abstract:ThereexistsanalgorithmtodecideiftheinitialconfigurationisaSouth-North-Winningconfiguration(orEast-West-Winningconfiguration)ifallthefourplayersinbridgegameknowthedetailedinformationaboutthecardsdistribution,andthealgorithmcanimplementthisprocedurefortheSouth-Northside(orEast-Westside)iftheSouth-Northside(orEast-Westside)canactuallywin.Thealgorithmproposedinthispaperisthebestintheopinionofcomputability,anditisalsoefficient.Keywords:bridge,gamblingandchess,computability,computationalcomplexity1若干概念约定桥牌运动中的四位牌手于牌桌的东西南北四方就座，东西为一家，南北为一家，南家为定约人，北家为明手，西家首攻。初始牌局：在桥牌运动中，发牌完毕后，各家手中均有13张牌，称52张牌在各家手中的分布状态、南北方定约的阶数s及花色F诸信息的集合为初始牌局。其中1≤s≤7，F∈{C,D,H,S,NT}。将52张牌分为四堆，每堆13张的分法有1313132613391352CCCC种，因不叫、加倍和再加倍三种叫品不能成为定约，故南北方定约的种数一共只有35种(1C~7NT)，由此可知初始牌局一共有30131313261339135210.88135CCCC种。终止牌局：在桥牌运动中，当13墩牌全部打完后，设南北方的赢墩为w，则称w、南北方定约的阶数s以及花色F诸信息的集合为终止牌局。k阶牌局：在桥牌运动中，设已打完k墩牌且南北方赢墩为w，则称k，w，南北方定约的阶数s及花色F，剩下的52-4k张牌在各家手中的分布状态以及第k+1墩由谁出牌诸信息的集合为k阶牌局。显然，初始牌局即0阶牌局，终止牌局即13阶牌局。容易计算出所有k(k≠0&k≠13)阶牌局的个数，由于52-4k张牌分为张数相等的四堆的分法种数为kkkkkkkkCCCC1313132261333913452，南北家的赢墩可能为0~k共k+1种情形，并且在第k+1墩时，东西南北四家均可能先出牌，考虑到南北方定约的阶数s及花色F，k阶牌局的个数一共有kkkkkkkkCCCCk131313226133391345235)1(4。若给定初始牌局，由于四家手中的13张牌均已确定，并考虑到南北方定约的阶数s及花色F均已知，所以对应的k阶牌局的数目一共只有4131313131313131313))(1(4)1(4kkkkkCkCCCCk。南北方完成定约sF称南北方胜，东西方击宕南北方的定约称东西方胜。一个k阶牌局，若剩下的13-k墩牌中无论东西方采用何种打法，南北方均存在某种策略，使得其总赢墩达到或超过s+6，则称这个k阶牌局为南北方胜牌局，否则称为东西方胜牌局。2桥牌的取胜策略2.1牌局的胜负判定从数学意义上讲，竞技桥牌运动是一种带有猜测性质的博弈[1,2]，各牌手要根据自己手中的牌情、叫牌过程中获得的信息、前面已出牌的信息以及搭档和对手的打牌风格等等来决定自己的出牌，这需要较高的智慧和临场应变能力。但若各牌手互知彼此之间牌的分布信息，则桥-2-牌运动就变成了一种完全动态信息博弈[2]。在下面的讨论中，假定南北方定约为sF，四家的牌全部摊开，西家首攻，现考虑南北方是否有取胜策略。定理任意初始牌局要么为南北方胜牌局，要么为东西方胜牌局，并且存在判定给定初始牌局是否为南北方胜牌局的算法。下面利用倒推法逐步证明这个定理。显然，一副牌到达终止牌局后，南北方要么完成定约，要么被击宕，并且很容易判定南北方是完成了定约还是被击宕：若w≥s+6，则南北方胜，否则东西方胜。由于终止牌局不可能为和局，由此可断定任意一个k阶牌局包括初始牌局也要么为南北方胜牌局，要么为东西方胜牌局。对于任意一个12阶牌局，在打最后一墩牌之前各家手中唯一的一张牌已经确定，并且谁先出牌也已经确定，故这墩牌是南北家的赢墩或东西家的赢墩也确定了，由于前12墩牌中南北家的赢墩w已知，故若最后一墩牌为南北家的赢墩，则当w+1≥s+6时该牌局为南北方胜牌局，否则为东西方胜牌局，若最后一墩牌为东西家的赢墩，则当w≥s+6时该牌局为南北方胜牌局，否则为东西方胜牌局。引理若存在算法判断任意k+1阶牌局是否为南北方胜牌局，则存在算法判断任意k阶牌局是否为南北方胜牌局。设kP为给定初始牌局演化而来的任意一个k阶牌局，下面讨论kP如何过渡到某个1kP。第k+1墩由某一家先出牌，该墩牌所有可能的合法出牌情形可用一棵深度为4的树表示，树根为kP，每个叶子节点为由kP出发可能演化而来的某个k+1阶牌局，我们把第k+1墩牌出完1张、2张或3张时各家手中牌的分布状态称为过渡牌局。为方便起见，假定每一家恰有2种出牌选择（实际上至多可能有13-k种），并且上家出牌后，下家也恰有2种跟牌选择，于是对应的k+1阶牌局可有16种，如图1。如图1(a)，kP为博弈树根节点，设轮到北家出牌，北家有2种选择，故北家出牌后可能出现2种过渡牌局，即树中第一层子节点，以方框表示，对于北家的任意一种出牌选择，东家分别有2种跟牌选择，东家出牌之后，可能出现4种过渡牌局，同理，南家出牌之后，可能出现8种过渡牌局，当西家出牌之后，则可能出现16种k+1阶牌局。由于假定存在算法判断任意k+1阶牌局是否为南北方胜牌局，故可拒此给出在k阶牌局kP下南北方存在取胜策略的一个充分条件：北家存在一种出牌选择，使得对于东家任意合法的跟牌，南家均存在一种合法的跟牌选择，使得西家任意合法的跟牌都使牌局进入一个南北方胜牌局1kP。图1a给出了一个南北方必胜的例子，过渡节点方框中的符号为存在量词，为全称量词，叶子节点上的实心-3-小圆圈表示南北方胜牌局，空心小圆圈则可为南北方胜牌局或东西方胜牌局。轮到北家出牌时，他可让牌局到达标的节点，东家跟牌后必定到达标的节点，而后南家均可让过渡牌局到达标的节点，并且这个节点的所有子节点均为南北方胜牌局，故无论西家如何跟牌，必定到达南北方胜牌局1kP。南家先出牌情形类似（略）。在k阶牌局kP下，若轮到东家先出牌，则博弈树如图1(b)所示，也可给出南北方存在取胜策略的一个充分条件：对于东家的任意出牌选择，南家均存在一种合法的跟牌，使得对于西家任意合法的跟牌，北家均存在一种合法的跟牌使牌局进入南北方胜牌局。图1(b)给出了一个南北方必胜的例子。西家先出牌的情形类似（略）。下面给出南北方存在取胜策略的充要条件。先看一个含有四个变量的公式博弈[3]),,,(22112211yxyxQyxyxG，其中2211,,,yxyx为逻辑变量，其取值为0或1，Q为CNF公式[4]，易知G的否定式可表示为)1(),,,(~),,,(~~2211221122112211yxyxQyxyxyxyxQyxyxG将1x的取值范围扩充为多值，并且表示北家可能的出牌选择，相应地，1y的取值范围为东家可能的跟牌选择，2x的取值范围为南家可能的跟牌选择，2y的取值范围为西家可能的跟牌选择，),,,(2211yxyxQ的取值为：若北家出1x，东家出1y，南家出2x，西家出2y后牌局1kP为南北方胜牌局，则),,,(2211yxyxQ为真，否则为假。G为真表示在牌局kP下南北方有取胜策略，为假表示东西方有取胜策略。若北家先出牌时南北方取胜的充分条件成立，则显然G为真，若不成立，则G~为真，由式)1(，G~为真可表述为：对于北家的任意出牌选择，东家均存在一种合法的跟牌，使得对于南家任意合法的跟牌，西家均存在一种合法的跟牌使牌局进入东西方胜牌局，此时东西方取胜的充分条件成立。由此可见，在北家先出牌的情况下，以上给出的南北方存在取胜策略的充分条件实际上也是充要条件。再看另一个公式博弈),,(22,112211vuvuWvuvuF，其中2211,,,vuvu为逻辑变量，其取值为0或1，F为CNF公式，易知F的否定式可表示为)2(),,(~),,(~~22,11221122,112211vuvuWvuvuvuvuWvuvuF类似于以上的分析，也可得到南北方存在取胜策略的充要条件。由于存在算法判断13阶和12阶牌局是否为南北方胜牌局，由以上引理，存在算法判断任意11阶、10阶、…、1阶牌局和初始牌局是否为南北方胜牌局，因此定理得证。2.2取胜策略的算法描述上面证明了存在算法判定初始牌局是否为南北方胜牌局，实际上已经给出了客观能够取胜时如何取胜的具体步骤，现给出初始牌局为南北方胜牌局时南北方如何取胜的算法描述。(a)列出由指定初始牌局能够演化而来的所有牌局，并将其中的终止牌局分为两类，一类为南北方胜牌局，一类为东西方胜牌局。(b)利用引理中给出的方法，依次确定每一个12阶、11阶、…、1阶牌局是南北方胜牌局还是东西方胜牌局。(c)南北双方互相配合各出一张牌，使牌局进入一个南北方胜的1阶牌局。(d)第2墩、第3墩、…、第13墩的出牌采用第3步相同的方法，使牌局进入一个高一阶的南北方胜牌局。(e)当各牌手出完第13张牌后，其终止牌局为南北方胜牌局。2.3算法的运算量由于桥牌是一个规模固定的问题，故上述算法不能讨论其计算复杂性，下面粗略估算其运算量。由前可知，给定初始牌局时k阶牌局的数目不超过413))(1(4kCk，故所有牌局的总数将不超过245757))(1(41131413kkCk种，出第k+1墩牌之前，每人手中有13-k张牌，第-4-k+1墩牌出完至多产生4)13(k种结果，故确定每个kP是否为南北方胜牌局只需在一棵深度为4、叶子节点总数不超过2856113)13(44k的博弈树中寻找一条取胜路径，故利用引理所述的方法从南北方胜牌局kP选择一条路径到达南北方胜牌局1kP只需常数时间，故决定全部牌局是否南北方胜牌局耗费的时间将小于245757，而这个计算量是现代计算机绝对能胜任的。而且在实际中，这245757种牌局中将有大量的不合法的牌局，这些牌局是不必考虑的，故实际的计算时间会远小于分析值。3结束语尽管桥牌博弈具有公式博弈的某种性质，而公式博弈是PSPACE完全的，但由于桥牌的规模固定，本质上只是一个实例，故不能讨论其复杂性。本文给出的算法不仅在可计算性[4]意义上已是最好的算法，而且在计算速度上也是优越的。若定约后由计算机替代南北方来打牌，则该算法可保证南北方客观上可胜时一定取胜，且出牌速度快。本文的算法只要稍作修改，还可以保证南北方客观上能完成定约时赢得最多的墩数，