计算21点在摸五张的情况下不爆牌的概率
21点游戏,在摸五张牌的情况下,不爆牌的概率。/ Calculating the probability of no burst while fetching 5 cards in blackjack.
详细 / Details
21点游戏,英文:Blackjack,是使用扑克牌玩的赌博游戏。
A可作1点或11点,2-10作该牌之点数,J、Q、K作10点。
玩家初始手上有2张牌。
如果玩家要牌后,其手上拥有的牌的总点数超过21点,便要揭开手上所拥有的牌,称为爆牌。
反之若其手上拥有的牌的总点数不超过21点,该玩家可决定是否继续要牌。
假设一个玩家为了完成某项挑战,一定会选择要牌三次,那么对于一局游戏来说,他要牌三次仍未爆牌的概率是多少?
背景 / Background
最近在玩R星开发的《荒野大镖客2》游戏,遇到了一个“赌徒系列挑战”之8:
当时耗费了2个小时不停地玩21点,终于完成了这个挑战。
这个挑战在网上被吐槽不少,只要在搜索引擎搜索“赌徒8”,全都是喷这个挑战的。大家都认为这个挑战的运气成分太大,而且完成这个挑战非常困难。
我突发奇想,想计算一下要牌3次还不爆牌的概率。(要牌3次就是有5张手牌)发现这是一个很好的概率题。
当然,对于真正的赌徒8挑战来说,想要算出完成赌徒8需要的期望局数,并不是3/不爆牌的概率。题目对于真正的游戏有一些简化。(尝试抽出最挑战大脑的部分,忽略其他细节,细节写在下面了。)
首先,不爆牌并不意味着能赢过庄家,庄家仍有可能比你的5张牌更接近21点;
其次,这个游戏没有办法在已经达到21点的时候继续要牌。譬如你起手牌为A
和K
,那么游戏会自动让你停牌,虽然这个时候你仍有可能摸5张牌而不爆,但是游戏机制决定你在这种情况下没办法继续摸牌了。
分析
一共有52张牌。A,2,3,4,5,6,7,8,9,10,J,Q,K各四张。
因为题目要求是不爆牌,所以A看做11点是没有意义的,直接把A当做1点即可。
52张牌中任意选5张,一共有C(52,5)种可能,即2598960种。
剩下的只需要枚举出所有的不爆牌的情形即可。
Solution01
使用模拟的方法,模拟1000000次情形,并统计不爆牌的次数,得出一个近似概率。
不是特别准确,但是也可以当做一个近似值。但是要真正较真的话,这是一个错误的解法。
实测:
1 | $ go run ./s01/main.go |
Solution02
暴力枚举
通过迭代的方式,枚举出每一种方法,并计算出总的不爆牌的方法数目,最终除以总方法数,得到概率值。
该方法的核心点在于模拟。
算法复杂度
以总牌数为 M
, 需要摸的牌数为 N
,阈值为 T
。
时间复杂度
O(M^N)
指数级别,复杂度与阈值无关。
空间复杂度
很少,使用函数迭代,还有一个记录扑克的数组,勉强算是消耗 O(M+N)
的空间而已,
实测
1 | go run ./s02/main.go |
Solution03
状态保留
我们调用numOfPossibleCases
函数的时候发现,很多参数一模一样的被调用了很多次。
我们建立一个HashMap保存一下状态,当遇到已经吊用过的函数时候,直接返回即可,不需要再次计算。
达到免除重复计算的剪枝效果。
算法复杂度
以总牌数为 M
, 需要摸的牌数为 N
,阈值为 T
。
时间复杂度
O(N*T*M^2)
将指数级别的复杂度降到了多项式级别。
空间复杂度
需要用一个 HashMap
来暂存状态
复杂度为O(N*T*M)
实测:
1 | go run ./s03/main.go |
Solution04
动态规划
var dp [maxCardsToPick + 1][maxThreshold + 1][maxStart + 1]int
dp[i][j][k]的含义为:摸i张牌,最大不超过j,从第k张开始到最后一张牌是可选的范围,那么有几种摸牌的可能性。
状态转移方程:
1 | dp[i][j][k] = ∑ (l from k to totalNum) dp[i-1][j-pokers[l]][l+1] |
算法复杂度
以总牌数为 M
, 需要摸的牌数为 N
,阈值为 T
。
时间复杂度
O(N*T*M^2)
将指数级别的复杂度降到了多项式级别。
空间复杂度
建立了一个三维数组 var dp [maxCardsToPick + 1][maxThreshold + 1][maxStart + 1]int
复杂度为O(N*T*M)
1 | go run ./s04/main.go |
Solution05
优化空间复杂度的动态规划
因为三维数组的每一层只和前面一层有关系,因此可以通过翻转的方式,减少内存消耗。
算法复杂度
以总牌数为 M
, 需要摸的牌数为 N
,阈值为 T
。
时间复杂度
和 Solution04 一致
空间复杂度
建立了一个三维数组 var dp [2][maxThreshold + 1][maxStart + 1]int
复杂度为O(T*M)
1 | go run ./s05/main.go |
代码库位置 https://github.com/pkumza/coding/tree/master/q01
附:测试环境
1 | MacBook Pro |