找回密码
 欢迎注册
查看: 9766|回复: 9

[悬赏] 德克萨斯扑克的先验胜利概率分析

[复制链接]
发表于 2010-3-22 21:54:35 | 显示全部楼层 |阅读模式
悬赏52金币未解决
窝窝里的默认应用《德克萨斯扑克》是一个挑战参与者智商的游戏。

基本玩法:

pk1.JPG

比牌规则:

pk2.JPG

游戏流程:

pk3.JPG

游戏举例:

pk4.JPG

我想编写一个辅助程序,帮助我在游戏中做出最理性的决策。

为了简化问题,我们假设只有两个玩家,且先不考虑对方的决策为我们提供的信息。

我们只对手牌和公共牌的所有情况做先验胜利概率分析。

任务一:列出一张$C_52^2*C_52^2$的表,表示两家手牌已知、5张公共牌未知的情况下,我方的先验胜利概率。

完成任务一后,我们就可以根据我方的手牌决定跟注、加注还是放弃。

如果不放弃,就会看到3张公共牌。

任务二:编写一个程序,输入我方2张手牌及3张公共牌的点数和花色,输出$C_47^2$个数,表示对方手牌已知、2张公共牌未知的情况下,我方的胜利概率。

完成任务二后,我们就可以根据我方的手牌及3张已知的公共牌决定跟注、加注还是放弃。

如果不放弃,就会看到第4张公共牌。

任务三:编写一个程序,输入我方2张手牌及4张公共牌的点数和花色,输出$C_46^2$个数,表示对方手牌已知、1张公共牌未知的情况下,我方的胜利概率。

完成任务三后,我们就可以根据我方的手牌及4张已知的公共牌决定跟注、加注还是放弃。

如果不放弃,就会看到第5张公共牌。

任务四:编写一个程序,输入我方2张手牌及5张公共牌的点数和花色,输出3个数,表示5张公共牌已知的情况下,对于对方手牌的$C_45^2$种情况,有多少种情况我方获胜、多少种情况我方落败、多少种情况双方打平。并列出所有我方落败的情况。

完成任务四后,我们就可以根据我方的手牌及5张公共牌决定跟注、加注还是放弃。

任务五:考虑对方的决策。讨论一下能否根据对方跟注或加注的行为,获得额外的信息,帮助我方更好地做决定。

Fans将和大家一起做这五个任务,和大家交流解决思路和实现方法,并对照一下结果,确保结果正确无误。

如果大家对Fans的工作有较大的帮助,将会赢得Fans的奖赏。

希望在辅助程序的帮助下,我们可以在德克萨斯扑克游戏中脱颖而出,在总排行榜中占领一席之位。

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-3-24 21:36:57 | 显示全部楼层
首先,我们分析一下任务一的计算量。

相当于把$52$张牌分成$4$组:

1. $5$张公共牌
2. 我方的$2$张手牌
3. 对方的$2$张手牌
4. 其余的$43$张牌

共有$(52!)/(5!*2!*2!*43!)=2781381002400$种分组方案。

当分组方案确定后,双方输赢也就确定了。

我们对$2781381002400$种具体情况逐一分析。

这样就可以得到手牌已知、公共牌未知的情况下,我方的胜利概率了。

由于分组方案有点多,我们需要提高分析的效率。

即公共牌和双方手牌都已知的情况下,如何用最快的速度判断输赢。

判断输赢的效率直接影响到整个任务一的运行时间。

所以快速判断输赢是完成任务一的关键。

欢迎大家提供思路。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

 楼主| 发表于 2010-3-24 22:52:08 | 显示全部楼层
由于判断输赢涉及到比牌规则的问题。

而图片中的比牌规则说得不够详细。

主要是大家的牌型都相同时,如何进一步比较大小的问题。

Fans很有必要在这里详细说明一下。

1. 皇家同花顺

皇家同花顺的$5$张牌是固定的,所以所有的皇家同花顺大小相同。

2. 同花顺

比较同花顺的大小,只要比较点数最大的牌即可,点数相同则大小相同,忽略花色。

但$A2345$例外,这手牌是最小的同花顺。

3. 四条

先比较四条的点数,四条点数相同则比较剩下的单张牌的点数。

4. 葫芦

先比较三条的点数,三条点数相同则比较对子的点数。

5. 同花

忽略花色,先比较点数最大的牌,然后是点数第二大的牌,依次类推。

6. 顺子

只要比较点数最大的牌即可,点数相同则大小相同,忽略花色。

但$A2345$例外,这手牌是最小的顺子。

7. 三条

先比较三条的点数,点数相同则依次比较$2$张单牌的点数。

8. 两对

先比较大对子的点数,然后是小对子的点数,最后是单牌。

9. 一对

先比较对子的点数,然后依次比较$3$张单牌的点数。

10. 高牌

先比较点数最大的牌,然后是点数第二大的牌,依次类推。

比牌细则在五个任务中都很重要。

如果有不正确的地方,请大家及时指正。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

发表于 2010-3-24 23:14:53 | 显示全部楼层
任务一中已知两家手牌没有意义啊(按规则摊牌前任何时候你都不知道对手的牌),应该只需要计算仅知道自己手里两张牌时的先验概率就行了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

发表于 2010-3-27 23:48:51 | 显示全部楼层
今天玩了一会,哈哈
一个葫芦赢了1000多分。。。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

 楼主| 发表于 2010-3-28 16:42:46 | 显示全部楼层
To 楼上两位:

$4#$说得有道理。

$5#$真是幸运。

其实不仅要看到自己的牌有多大,还要看人家是否有可能有更大的牌。(尤其是人家下了很大的注的时候)

所以当你的手牌的胜率不是天下无敌的时候就要小心了。

所以我们要看对方手牌在哪些情况下我方手牌占优势,哪些情况下我方手牌占劣势。

尤其要重点分析使得我方手牌占劣势的情况,根据对方的反应来确认或否认这些情况。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

 楼主| 发表于 2010-3-28 17:21:07 | 显示全部楼层
快速判断输赢的方法:

给成手牌编码。

int类型的整数有$32$个bit位。

我们使用其中$24$个bit位来表示成手牌。

每$4$个bit位分一组,一共有$6$组。

相当于把成手牌编码成$6$个$0$到$15$的整数。

第$1$个整数表示牌型。

其中:

$0$表示散牌;
$1$表示一对;
$2$表示两对;
$3$表示三条;
$4$表示顺子;
$5$表示同花;
$6$表示葫芦;
$7$表示四条;
$8$表示同花顺;
$9$表示皇家同花顺。

其余$5$个整数表示该牌型的附加信息:

皇家同花顺没有附加信息;
同花顺的附加信息为顺子末端的点数,只需用$1$个整数来表示,范围为$5$到$14$。(其中$11$表示$J$、$12$表示$Q$、$13$表示$K$、$14$表示$A$)
四条需要附加$2$个整数,第$1$个整数表示四条的点数,第$2$个整数表示单张的点数。
葫芦需要附加$2$个整数,第$1$个整数表示三条的点数,第$2$个整数表示对子的点数。
同花需要附加$5$个整数,从大到小把$5$张牌的点数列下来。
顺子只需附加$1$个整数,表示顺子末端的点数。
三条需要附加$3$个整数,第$1$个整数表示三条的点数,第$2$个整数表示较大的单张的点数,第$3$个整数表示较小的单张的点数。
两对需要附加$3$个整数,第$1$个整数表示大对子的点数,第$2$个整数表示小对子的点数,第$3$个整数表示单张的点数。
一对需要附加$4$个整数,第$1$个整数表示对子的点数,后面$3$个整数从大到小把$3$张单牌的点数列下来。
散牌需要附加$5$个整数,从大到小把$5$张牌的点数列下来。

示例:

散牌$KQ542$编码成$0x0DC542$;
$88Q97$编码成$0x18C970$;
$A A225$编码成$0x2E2500$;
$888KJ$编码成$0x38DB00$;
不同花的$56789$编码成$0x490000$
同花的$AKJX9$($X$表示点数$10$)编码成$0x5EDBA9$;
$33377$编码成$0x637000$;
$XXXXA$编码成$0x7AE000$
同花的$A2345$编码成$0x850000$;
黑桃的$AKQJX$编码成$0x900000$。

(如有不正确的地方,请指正)

对成手牌编码后,只要比较编码的大小,就知道谁的成手牌最大了。

大家觉得这个方法如何?是否有更好的方法?

#####

接下来还要讨论如何快速地从$2$张底牌和$5$张公共牌中选出最大$5$张牌组成成手牌。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

 楼主| 发表于 2010-3-29 11:02:12 | 显示全部楼层
本帖最后由 KeyTo9_Fans 于 2010-3-29 11:05 编辑

$2$张底牌加$5$张公共牌一共是$7$张牌。

如果直接枚举选哪$5$张牌,则需要讨论$C_7^5=21$种选取方案。

对于每种选取方案,还要根据其牌型对其编码。

这样所花费的时间太多了。

所以我们希望在不枚举选牌方案的前提下,直接从$7$张牌中找到最大的$5$张成手牌。

首先把$7$张牌的信息整理成$5$个数组:

$p[7]$、$c[7]$、$pts[15]$、$col[4]$、$mark[15][4]$。

其中:

$p$数组表示$7$张牌的点数,范围是$1$到$14$(在检查顺子的时候,$A$既可以当$1$点,也可以当$14$点);
$c$数组表示$7$张牌的花色($0$表示方片,$1$表示梅花,$2$表示红桃,$3$表示黑桃);
$pts$数组统计每个点数有多少张牌;
$col$数组统计每个花色有多少张牌;
$mark$数组标记每张牌是否出现,出现则标$1$,没出现则标$0$。

在统计$pts$数组的同时,为变量$p2$、$p3$、$p4$赋值。

其中:

$p2$表示有哪些点数达到了$2$张;
$p3$表示有哪些点数达到了$3$张;
$p4$表示有哪些点数达到了$4$张。

初始时$p2$、$p3$、$p4$都为$0$。

一旦某个点数$p$达到$2$张,则$p2$=($p2$<<$4$)|$p$;
一旦某个点数$p$达到$3$张,则$p3$=($p3$<<$4$)|$p$;
一旦某个点数$p$达到$4$张,则$p4$=$p$。

在统计$col$数组的同时,为变量$c5$赋值。

初始时$c5=-1$。

一旦某个花色$c$达到$5$张,则$c5$=$c$。

好了,现在大概可以直接找到最大的$5$张成手牌并为其编码了。

如果$c5=3$则检查$mark[14][3]$到$mark[10][3]$是否全为$1$。是则说明有皇家同花顺,判断到此结束;否则继续。
如果$c5> -1$则依次检查$mark[14][c5]$到$mark[1][c5]$,一旦有连续$5$个标记为$1$,则说明有同花顺,根据顺子末端的点数为其编码,结束;否则继续。
如果$p4>0$则说明有四条,检查$p$数组,找出最大的单张牌,编码,结束。
如果$p3>15$或者($p3>0$且$p2>15$)则说明有葫芦,根据$p3$和$p2$的值为其编码,结束。
如果$c5> -1$则说明有同花,根据$mark[14][c5]$到$mark[2][c5]$为其编码,结束。
依次检查$pts[14]$到$pts[1]$,一旦有连续$5$个点数的个数大于$0$,则说明有顺子。根据顺子末端的点数为其编码,结束。
如果$p3>0$则说明有三条,检查$p$数组,找出两个最大的单张,编码,结束。
如果$p2>15$则说明有两对,根据$p2$的值和$p$数组,编码,结束。
如果$p2>0$则说明有对子,根据$p2$的值和$p$数组,编码,结束。
找出$5$个最大的单张,编码,结束。

不知道上述流程是否严密。

如有疏漏或不正确的地方,请指正。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

 楼主| 发表于 2010-4-2 12:12:20 | 显示全部楼层
分析了所有对子和$10$以上的单张,结果如下:
  1. pt c pt c     win       lose      draw
  2. 14 0 14 1: 1767157282 306046758 24368360
  3. 13 0 13 1: 1709675710 363500874 24395816
  4. 12 0 12 1: 1658267316 413873816 25431268
  5. 11 0 11 1: 1608413414 463039368 26119618
  6. 10 0 10 1: 1558308030 511370014 27894356
  7. 9 0  9 1: 1499323720 568961236 29287444
  8. 8 0  8 1: 1441768314 624197028 31607058
  9. 7 0  7 1: 1386393872 678327976 32850552
  10. 6 0  6 1: 1329379928 732647636 35544836
  11. 5 0  5 1: 1272777818 785931546 38863036
  12. 4 0  4 1: 1209118142 846575230 41879028
  13. 3 0  3 1: 1146703018 906828052 44041330
  14. 2 0  2 1: 1082650606 967593762 47328032
  15. 14 0 13 0: 1331920695 723152301 42499404
  16. 14 0 13 1: 1292337853 761510248 43724299
  17. 14 0 12 0: 1315525264 738351324 43695812
  18. 14 0 12 1: 1274853304 777745425 44973671
  19. 13 0 12 0: 1296084489 741397665 60090246
  20. 13 0 12 1: 1254240506 781201457 62130437
  21. 14 0 11 0: 1298350683 752719319 46502398
  22. 14 0 11 1: 1256518491 793091064 47962845
  23. 13 0 11 0: 1278645197 756153947 62773256
  24. 13 0 11 1: 1235608060 796974365 64989975
  25. 12 0 11 0: 1237785157 796400815 63386428
  26. 12 0 11 1: 1192563025 839425016 65584359
  27. 14 0 10 0: 1280946285 766356759 50269356
  28. 14 0 10 1: 1237925999 807647178 51999223
  29. 13 0 10 0: 1261705545 769729925 66136930
  30. 13 0 10 1: 1217494041 811485143 68593216
  31. 12 0 10 0: 1220601812 810271048 66699540
  32. 12 0 10 1: 1174180425 854258945 69133030
  33. 11 0 10 0: 1185956322 844437553 67178525
  34. 11 0 10 1: 1137736368 890259434 69576598
复制代码
这个结果与百度百科中

http://bk.baidu.com/view/947708.htm

只玩$10$手牌:

$A A$,$KK$,$AK$,$Q Q$,$JJ$,$T T$,$99$,$88$,$AQ$,$77$

的说法基本一致。

不同之处是$AK$和$AQ$应排到$77$后面,$66$的先验胜率反而比$AQ$大。

不知道程序是否有误,因为google上面没有这样的分析数据。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

发表于 2015-3-16 18:05:50 | 显示全部楼层
将7张牌做tally运算:即统计点数出现的频率,排序, 然后根据牌型的大小,由大到小依次做真假判定。如果一方是真,一方是假,判定结束。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 20:49 , Processed in 0.055476 second(s), 18 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表