关于桥牌的取胜策略何犬华陈传波(华中科技大学计算机科学与技术学院，武汉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若干概念约定桥牌运动中的四位牌手于牌桌的东西南北四方就座，东西为一家，南北为i家，南家为定约人，北家为明手，西家首攻。初始牌局：在桥牌运动中，发牌完毕后，各家手中均有13张牌，称52张牌在各家手中的分布状态、南北方定约的阶数s及花色F诸信息的集合为初始牌局。其中1WsW7,FE{C,D,H,S,NT}。将52张牌分为四堆,每堆13张的分法有种，因不叫、加倍和再加倍三种叫品不能成为定约，故南北方定约的种数一共只有35种(1C〜7NT),由此可知初始牌局一共有u1.88x10如种。终止牌局：在桥牌运动中，当13墩牌全部打完后，设南北方的赢墩为w,则称w、南北方定约的阶数s以及花色F诸信息的集合为终止牌局。k阶牌局：在桥牌运动中，设已打完k墩牌且南北方赢墩为w,则称k,w,南北方定约的阶数s及花色F,剩下的52-4R张牌在各家手中的分布状态以及第k+1墩由谁出牌诸信息的集合为k阶牌局。显然，初始牌局即0阶牌局，终止牌局即13阶牌局。容易计算出所有k(kH0&kH13)阶牌局的个数，宙于52・4k张牌分为张数相等的四堆的分法种数为戈C；抚氏，南北家的赢墩可能为0~k共k+1种情形，并且在第k+1墩时，东西南北四家均町能先出牌，考虑到南北方定约的阶数s及花色F,k阶牌局的个数-•共有4伙+1)35©；金(?茫；疋茫：6黑'。若给定初始牌局，由于四家乎中的13张牌均已确定，并考虑到南北方定约的阶数s及花色F均已知，所以对应的k阶牌局的数冃一共只有4伙+1)C：厂C：厂C：厂G异=4(k+1)(G；)4o南北方完成定约sF称南北方胜，东西方击宕南北方的定约称东西方胜。一个k阶牌局，若剩下的13-k墩牌中无论东西方采用何种打法，南北方均存在某种策略，使得其总赢墩达到或超过s+6,则称这个k阶牌局为南北方胜牌局，否则称为东汕方胜牌局。2桥牌的取胜策略2.1牌局的胜负判定从数学意义上讲，竞技桥牌运动是一种带有猜测性质的博弈山刀，各牌手要根据自己手中的牌情、叫牌过程中获得的信息、前血已岀牌的信息以及搭档和对手的打牌风格等等來决定自C的出牌，这需要较高的智憩和临场应变能力。但若各牌手互知彼此之间牌的分布信息，则桥牌运动就变成了一•种完全动态信息博弈门1。在下面的讨论中，假定南北方定约为SF,四家的牌全部摊开，西家首攻，现考虑南北方是否有取胜策略。定理任意初始牌局要么为南北方耽牌局，要么为东西方胜牌局，并且存在判定给定初始牌局是否为南北方胜牌局的算法。下血利用倒推法逐步证明这个定理。显然，一副牌到达终止牌局后，南北方要么完成定约，要么被击宕，并H很容易判定南北方是完成了定约还是被击宕：若w2s+6,则南北方胜，否则东西方胜。由于终止牌局不可能为和局，由此可断定任意一个k阶牌局包括初始牌局也要么为南北方胜牌局，要么为东西方胜牌局。对于任意一个12阶牌局，在打最后一墩牌Z前各家手中唯一的一张牌已经确定，并且谁先出牌也已经确定，故这墩牌是南北家的赢墩或东西家的赢墩也确定了，由于前12墩牌中南北家的赢墩w已...