洗牌逻辑的相关发散

作者 Zhe Wang 日期 2017-01-02
洗牌逻辑的相关发散

最近没太忍住,原本打算戒赌,尽量少跟狐朋狗友们玩德州的,又重新参与了进来。用的一款叫微扑克的app。结果半小时一场的牌局,一天“酣畅淋漓”的玩上几局,赢一次没几个钱,一输就输很多。而且半个小时的场,才多少个round,出现顺子、同花、葫芦的频次非常高,导致手里捏着两对或者三条这种准大牌都不敢轻易下注,这让我对游戏的随机性产生了深深的质疑。说到这里可能就有人会骂我了,说,嘿,你这个人怎么就这么虚伪,明明是自己打牌的策略有问题,非得赖游戏。好吧,我想说其实纸牌游戏的随机性,是可以通过统计来验真伪的。只不过尝试去做这种校验,真的很难,因为每场牌局,普通玩家所能拿到的统计数据,差不多也就输赢了多少筹码,别无他耳。除非你能把人家洗牌的源代码拿出来看一看。是不是很难?当然很难。
所以,秉承着“玩一个东西就尽量冠冕堂皇的给自己一个心安的理由”的原则,也来说说,如果是我们自己来写一款德州扑克,第一个重点环节,也就是洗牌,如何实现真正意义的随机。
关于这个问题呢,我记得几个月前左耳朵耗子还转发了一篇文章,今天特地翻了好久才找到,《数组的完全随机排列》写的已经比较详尽了。在把这篇文章的核心观点列出来之前,我们先来思考一个其实很简单但也很核心的问题,如果是你,怎么样用计算机逻辑去实现一次标准的洗牌?
先简单的想一想。
其实经典的洗牌算法思路非常的自然,用通俗易懂的话来说明就是“一张一张的抽”。
上述的那篇文章用后半篇幅来叙述了这种算法,难能可贵的是,作者还用数学归纳法证明了这种算法是完全随机的,完全随机的充要条件即每张牌出现在任意位置是等概的。这种精益求精的精神还是难能可贵的。
那上述这篇文章的上半篇幅讲了什么呢?它说明了一个比较有意思的结论,即js中使用Array.prototype.sort来进行洗牌都是伪随机,或者说依赖于排序算法的随机都是伪随机。排序的复杂度由高到底,复杂度在O(n^2)排序无非冒泡、比较和插入。以拥有最完整比较次数n*(n-1)/2的冒泡排序为例,我也做了一个简单的验证,以下是代码。(原谅我terminal上node.js版本已经太低了,变量声明还只能用这么傻的方式)。


var pokers, aver, i, arr;
pokers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
aver = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];

Array.prototype.bubbleSort = function (cmp) {
var p, q, prev, next;
for (p = 0; p < this.length; p ++) {
for (q = 1; q < this.length - p; q++) { next = this[q]; prev = this[q - 1]; if (cmp) { if (cmp(prev, next)) { this[q] = prev; this[q - 1] = next; } } else { if (prev > next) {
this[q] = prev
this[q - 1] = next;
}
}

}
}
return this;
}

function shuffle (arr) {
return arr.bubbleSort(function () {
return Math.random() > 0.5;
});
}

for (i = 0; i < 1000; i++) {
arr = shuffle(pokers.slice(0));

arr.forEach(function (v, k) {
aver[k] += v;
});
};

console.log(aver.map(function (v) {
return v/1000;
}));

按照每个位置的等概理论,aver数组最后应该都是接近(0+9)*10/2的值,4.5。而结果呢,我们看下截图:
https://libcafe.com/img/card_0.png

其实这种结果很好理解的,我们回顾下冒泡的过程,对于数组的第一个元素,它“被分配到”数组最后一个位置的概率有多少呢。其实就看整个循环链中的第一次循环即可,第一个元素0,“被分配到”数组最后一个位置的概率其实只有(0.5)^9,根本就不等于1/10。显然,这种随机是伪随机。
这就是数学里面常说的,你要证伪,只需要证明一个例外即可。好了,作为一名代码糙工,我就不继续在数学话题上班门弄斧了。
同理,也可以比较容易说明选择和插入也是伪随机。
但至于o(nln(n))这类排序呢,类似快排、堆排,上述文章虽然给出了快排的例子,也验证了随机是伪随机,但没有太多的说明理由。**文章的观点是,这类排序的实际比较次数通常远小于n(n-1)/2,因此是伪随机。这个理由说的有些过于宽泛,估计需要数学专业的大牛来从更宏观的层面解释一下了。至少是有些超过我能力范畴的。 那依赖排序生成的随机算法是不是可以经过改造变为真随机呢**
我觉得是可以的。以冒泡排序为例,我们改造的核心思想是,让每次比较,其概率阈值是动态的。推导冒泡排序的概率阈值,最终我们用矩阵来表示的话如下:

https://libcafe.com/img/card_1.jpg

其实这个矩阵的得来是比较简单,根据必要条件最后一个位置上的元素“被分配到”各个位置是等概的可以推算出来。但是,目前我没有通过数学方法来证明它的正确性,而只是通过代码执行的统计来做验证。但是讲真,为得到这个矩阵,一度走偏了很多,甚至尝试用线代去推导。😅
所以我们代码改造如下:

var pokers, aver, i, arr;

pokers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

aver = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];

Array.prototype.bubbleSort = function (cmp) {

var p, q, prev, next;

for (p = 0; p < this.length; p ++) {
for (q = 1; q < this.length - p; q++) { next = this[q]; prev = this[q - 1]; if (cmp) { // 增加两个参数 if (cmp(prev, next, p, q - 1, this.length)) { this[q] = prev; this[q - 1] = next; } } else { if (prev > next) {
this[q] = prev
this[q - 1] = next;
}
}

}
}

return this;
}

function matrix (m, n, num) {
var u, d;
u = (n < (num - m - 1)) ? (n + 1) : 0;
d = n + 2;
return u/d;
}

function shuffle (arr) {

return arr.bubbleSort(function (prev, next, m, n, num) {
// 修改比较阈值
return Math.random() < matrix(m, n, num);
});

}

for (i = 0; i < 30000; i++) {
arr = shuffle(pokers.slice(0));

arr.forEach(function (v, k) {
aver[k] += v;
});
};

console.log(aver.map(function (v) {
return v/30000;
}));

我们进行三万次的洗牌,得到每个位置的统计均值,如下图
https://libcafe.com/img/card_2.png
符合预期,基本可以验证这种洗牌方式是完全随机的。

介绍一种讨巧的洗牌方式

这种讨巧的洗牌方式思路也比较简单,即给每张牌打上一个随机值标识,根据随机值标识,进行排序。
代码如下:

var pokers, aver, i, arr;

pokers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

aver = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];


function shuffle (arr) {

return arr.map(function (v) {

return {
value: v,
flag: Math.random()
}

}).sort(function (p, n) {

return p.flag > n.flag;

}).map(function (v) {

return v.value;

});

}

for (i = 0; i < 30000; i++) {
arr = shuffle(pokers.slice(0));

arr.forEach(function (v, k) {
aver[k] += v;
});
};

console.log(aver.map(function (v) {
return v/30000;
}));

其统计的结果如下图:
https://libcafe.com/img/card_3.png
可见这种算法也是完全随机的。

洗牌逻辑的相关发散就点到为止。下次争取讨论下不同起手下的概率预期。好了,先不说了,牌局就要开始了,科科。