资源描述:
《关于桥牌的取胜策略》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、关于桥牌的取胜策略何犬华陈传波(华中科技大学计算机科学与技术学院,武汉430074)摘要:在桥牌运动中,若将四家的牌摊开來打,则存在判定初始牌局是否为南北方胜牌局(或东汕方胜牌局)的算法,当南北力(或东西方)客观上存在取胜策略时,则存在算法来实现其取胜步骤。木文给出的算法不仅在可计算性意义上是最好的算法,并且计算量小。关键词:桥牌,博弈,可计算性,计算复杂性中图分类号:TP18TheWinningStrategyforBridgeGameHEDa-HuaCHENChuan-Bo(CollegeofComputerSci
2、.&Tech.,HuazhongUniversityofSci.&Tech.,Wuhan430074)Abstract:ThereexistsanalgorithmtodecideiftheinitialconfigurationisaSouth-North-Winningconfiguration(orEast-West-Winningconfiguration)ifallthefourplayersinbridgegameknowthedetailedinformationaboutthecardsdistribu
3、tion,andthealgorithmcanimplementthisprocedurefortheSouth-Northside(orEast-Westside)iftheSouth-Northside(orEast-Westside)canactuallywin.Thealgorithmproposedinthispaperisthebestintheopinionofcomputability,anditisalsoefficient.Keywords:bridge,gamblingandchess,compu
4、tability,computationalcomplexity1若干概念约定桥牌运动中的四位牌手于牌桌的东西南北四方就座,东西为一家,南北为i家,南家为定约人,北家为明手,西家首攻。初始牌局:在桥牌运动中,发牌完毕后,各家手中均有13张牌,称52张牌在各家手中的分布状态、南北方定约的阶数s及花色F诸信息的集合为初始牌局。其中1WsW7,FE{C,D,H,S,NT}。将52张牌分为四堆,每堆13张的分法有种,因不叫、加倍和再加倍三种叫品不能成为定约,故南北方定约的种数一共只有35种(1C〜7NT),由此可知初始牌局一共
5、有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种
6、情形,并且在第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阶牌局为
7、南北方胜牌局,否则称为东汕方胜牌局。2桥牌的取胜策略2.1牌局的胜负判定从数学意义上讲,竞技桥牌运动是一种带有猜测性质的博弈山刀,各牌手要根据自己手中的牌情、叫牌过程中获得的信息、前血已岀牌的信息以及搭档和对手的打牌风格等等來决定自C的出牌,这需要较高的智憩和临场应变能力。但若各牌手互知彼此之间牌的分布信息,则桥牌运动就变成了一•种完全动态信息博弈门1。在下面的讨论中,假定南北方定约为SF,四家的牌全部摊开,西家首攻,现考虑南北方是否有取胜策略。定理任意初始牌局要么为南北方耽牌局,要么为东西方胜牌局,并且存在判定给定初
8、始牌局是否为南北方胜牌局的算法。下血利用倒推法逐步证明这个定理。显然,一副牌到达终止牌局后,南北方要么完成定约,要么被击宕,并H很容易判定南北方是完成了定约还是被击宕:若w2s+6,则南北方胜,否则东西方胜。由于终止牌局不可能为和局,由此可断定任意一个k阶牌局包括初始牌局也要么为南北方胜牌局,要么为东西方胜牌局。对于任意一个12阶