一、猜扑克牌游戏介绍
小伙伴们喝酒时通常会玩一些小游戏,根据游戏胜负来决定谁被罚酒,猜扑克是其中一种常见的游戏。游戏规则如下:
游戏一般2人参与,游戏道具为一副扑克牌,任意一张扑克牌代表一个点数,A、2~10、J、Q、K分别代表1~13点(通常还会加入大小王,这里简单起见先不考虑)。
甲从一副扑克牌中任意抽出一张,自己查看后请乙猜测牌中数字。通常乙有3次机会,每次猜测后,若猜中甲抽出的牌,则乙胜利,游戏结束;否则甲根据情况告知乙的猜测偏大或者偏小,直到3次机会全部用完乙都没有猜中,则甲胜。
一直困惑我比较久的问题是第一次先猜哪个数字胜利的概率比较大,从喝酒的经验看,这个数并不一定是正中间的点数7。最近看到猜数字的编程题时突然想到这个小游戏,所以决定编程探究一下。
二、游戏胜利概率
假设乙每次猜测都是最优解答,从编程的角度看,这个游戏胜利的概率可以通过递归计算出来。问题可以简化为求n个连续数字猜测t次,胜利的概率。
如果t 大于等于 n,那很显然,胜利概率是1;
如果t 为 1,胜利概率为 1 / n;
如果不属于上述两种情况,我们可以把当前情况简化到上述两种情况。第一次猜测可以猜1~n中的任意数字x,胜利的情况可分为以下三种:
- 直接胜利概率为1 / n;
- 如果第一次没有猜中,那有可能是猜测比结果偏大或者偏小,如果偏大并且后续猜胜利的概率为 (x - 1) / n * (x - 1个连续数字猜t - 1次胜利的概率);
- 如果猜测较结果偏小并且后续猜测胜利的概率为 (n - x) / n * (n - x个数字猜t - 1次胜利的概率)。
所以猜测x的胜率为以上三种胜率之和;x的所有取值,对应的胜利概率最大者,即为最佳猜法。
三、编程实现
用一个映射表r存储n个数字猜k次的胜率,map数组存储n个数字猜k次第一次猜i的胜率:
function guessPoker (n, k, r = {}, map = {}) {
let key = `${n}-${k}`
if (key in r) return r[key]
if (k >= n) {
r[key] = 1
} else if (k == 1) {
r[key] = 1 / n
} else {
let maxRatio = 0
for (let i = 1; i <= n; i++) {
let winRatio = 1 / n + guessPoker(i - 1, k - 1, r) * (i - 1) / n + guessPoker(n - i, k - 1, r) * (n - i) / n
map[`${n}-${k}-${i}`] = winRatio
maxRatio = Math.max(maxRatio, winRatio)
}
r[key] = maxRatio
}
return r[key]
}
let r = {}, map = {}
console.log(guessPoker(13, 3, r, map))
console.log(JSON.stringify(map))
打印出来发现13个数字中猜3次,胜率是
0.5384615384615385 //胜率
// map的打印
{
"13-3-1":0.3076923076923077,
"13-3-2":0.38461538461538464,
"13-3-3":0.46153846153846156,
"13-3-4":0.5384615384615385,
"13-3-5":0.5384615384615385,
"13-3-6":0.5384615384615385,
"13-3-7":0.5384615384615385,
"13-3-8":0.5384615384615385,
"13-3-9":0.5384615384615385,
"13-3-10":0.5384615384615385,
"13-3-11":0.46153846153846156,
"13-3-12":0.38461538461538464,
"13-3-13":0.3076923076923077
}
并且从map的打印看,13个数字猜3次,第一次猜第1个的胜率约是0.30,猜第二个的胜率约是0.38,而猜测4~10的概率竟然是一样的!都是接近0.54。
这样看来,猜扑克牌游戏对乙方会更有利一些。