前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >关于洗牌的研究(三)——洗牌过程建模

关于洗牌的研究(三)——洗牌过程建模

作者头像
magic2728
发布于 2019-09-27 06:41:25
发布于 2019-09-27 06:41:25
1.1K0
举报
文章被收录于专栏:MatheMagicianMatheMagician

写再前面:本系列作品由MathMagician独家首发,一共有七篇,从数学和魔术两个角度对日常生活中“洗牌”这一现象作了挂一漏万的分析。之所以说是挂一漏万,是因为无论数学还是魔术,洗牌中的任何一个小点都够写几篇了。所以,本系列主要选取了一些常见的洗牌方式和相关内容展开作了一些介绍,包括洗牌分类,混乱度评价,过程建模,近似计算,以及几个基本但是及其巧妙的利用洗牌规律设计的魔术。相信聪明的你读完以后,会在数学和魔术上,都对“洗牌”这一现象有着更加深入的认识。

历史文章请戳:

关于洗牌的研究(二)——你的扑克洗乱了吗?

关于洗牌的研究(一)——平常你都是怎么洗牌的?

本篇是第三篇:洗牌过程建模

在上一篇文章中,我们介绍了基于熵的关于洗乱的基本定义,还有对于一次洗牌能否洗乱等问题的一个估算,算是对洗牌这个过程的数学模型有一个比较全面的认识。这一篇中,我们就具体的Riffle shuffle,Hindu Shuffle的过程进行建模,进而分析他们到底要几次才能基本洗乱的问题,其中仍然包括一些近似策略。另外,在确定性洗牌中,对比较特殊的Faro Shuffle的一些特殊的性质,我们也作了一些介绍。

Riffle Shuffle的随机过程模型

1. 分叠过程:两叠张数服从一个Categorical分布,其分出来各张的概率正比于以n / 2为期望,某给定方差的正态分布的概率密度值,方差越小标明分得越均匀;

2. 交叉落牌选择:每次落牌仅能从左右两叠中选择一叠,这服从伯努利分布,其概率要正比于剩余叠的张数的幂函数;

3. 落牌张数:考虑到扑克的粘滞效应,每次落下的牌从哪一叠还取决于上一张落牌所在的叠,故两种建模策略:

A. 对和上一次落牌所在叠进行概率分数加权;

B. 直接考虑每次落下张数服从1 + 伯努利分布,n = 剩余张数 - 1,p使得其下落张数期望为常数;当牌数量不足或为1时候,特殊处理。

由此,得洗牌过程中的随机过程如下公式和图所示:

其中,N为整叠牌的张数,Di为每一次落牌后两叠牌的剩余张数;

A模型中:

Sigma为分牌均匀系数,越大表示在期望为均分的条件下,每次越分布均匀的程度(源于方差);

Arpha为均匀系数,越大表明洗牌人能够均分扑克并尽量两叠均匀下落的程度;

Beta为粘滞系数,越大表明洗牌人越会一次落下一叠很大的牌;

B模型中:

Sigma和Arpha同A模型,n为每次落牌在剩余张数足够时的期望张数,同起到粘滞系数的作用。

图1 Riffle Shuffle分叠位置分布图

其实这些指标的不同取值已经可以判断一个人的洗牌水平,Sigma需要多次试验,而Arpha,Beta,n有一次洗牌就有足够的样本来估计了。

有趣的是,这种建模方法给不出一定洗出Perfect Shuffle的参数,因为那是另外一种技术了。

在完成这些思考的时候,也参考了一些前人的研究,最有名的是这个:Gilbert–Shannon–Reeds model。详情参考:

https://en.wikipedia.org/wiki/Gilbert%E2%80%93Shannon%E2%80%93Reeds_model

步骤和我的一样,但有几个区别:

1. 分叠过程我最开始也是用的二项分布,毕竟天然就是一个离散有限范围空间内的分布,但是无法同时保持期望为对半切开,空间给定,同时还能有可控的方差来表征一个人能否切均匀的能力,所以选用了正态分布离散化后的结果;

2. 落牌的伯努利分布参数正比于剩下张数的思路是很优秀的,我也借鉴,但是添加幂函数则有能表征其强度了;

3. 落牌其实有个很明显的点原文没有建模到是连续落牌,表明每次选择并非独立的,这里把历史条件考虑进来,或增加每次落牌张数因素构建粒度更粗的过程来描述,是更加贴合真实过程的。

站在巨人的肩膀上,一定可以看得更高,更远。

Hindu Shuffle的随机过程模型

每次以恒定参数的Poisson分布拿走顶部牌叠(假设每次抽的牌张数分布不随着剩余牌减少而变化),何时张数不够则全部拿走结束洗牌,这样的一族随机过程加上最后的Reverse操作即可模拟一次印度洗牌。

比如,给定poisson期望为5,加一得6张为一次期望的洗牌张数,即平均以9叠左右反序整个扑克牌(不是严格9叠,因为最后一叠往往不足量)。

公式描述如下:

其中,lamda为泊松系数,Reverse函数为序列翻转函数。

Faro Shuffle的函数过程模型

Faro Shuffle在我们的分类中属于非确定洗牌,本质上牌的熵增为0,所以可以看作并没有洗牌的效果。

其洗一次牌的过程是一个确定性过程,并且可以神奇的找到其恢复成原状的规律:

其中牌张数为偶数2N(否则无法均分进而无法完美洗牌),另外,ord函数在数学上叫做Multipicative Order,恰好即为所求。

对于没有大小王的一副扑克牌,N = 26,故out faro的恢复洗牌数量是8次,而in faro居然要52次之多,看起来这个数值随着牌的张数增加并没有什么规律,这看起来就是一个随机数发生器,而一副扑克牌在out faro下能够8次就完全恢复,不得不说这是一个奇迹搬的巧合。而加了大小王的out faro多了两张牌恰好和没有大小王的in faro结论相同,也要52次,失之毫厘,误差千里啊!

好了有了这些模型以后,我们就可以给出基于上一篇讲的用熵来度量不确定度的方案来具体估计到底洗多少次才能洗乱了,然而这件事情并不简单,在完成这个洗牌混乱评价的定义和过程建模以后,其真实的计算过程远比我们想的复杂。

研究了这么多洗牌方法和混乱度,这里我们放松一下,简单讨论一个前面提到的相关问题:

扑克游戏,一定要洗乱才公平吗?

其实,我们一般的扑克游戏的所谓公平,并不需要洗得完全混乱,只要对玩家和拿到的牌点是独立的,那这个游戏就是公平的。这一点,只需要起牌顺序是随机的就能够做到,至于牌没有洗乱其实是造成斗地主之类的两房差距悬殊而已,但并不是不公平,只是这是一个靠运气多过靠实力的游戏而已。然而依次摸牌过程又相当于一次系统抽样,其实真的没有洗也无所谓了,何况QQ斗地主上还有不洗牌玩法,通过不洗牌加批次抽样使得牌的点数分布差异更大(差异要根据游戏种类来,在斗地主游戏中其实是这副牌好打得程度,即平均胜率),但并不影响游戏的公平性。

那不洗乱的扑克牌到底对游戏有什么伤害呢?

其实这不影响公平,但影响玩家实力发挥的程度。

一个游戏是否依赖实力还是运气则是建立在公平条件下另一个更深的评价维度,可以定义为实力系数(正数)a,有

P(L1 win L2) = logistic(a(L1 - L2))

L1,2为对战双方的实力评分,取正数,其差的绝对值期望应该校正到相等才能相互比较a。a越大则表示实力强的一方完胜,弱的一方完全没有机会,实际上王者荣耀这类实时竞技游戏的玩家匹配大多用的这个方法来评价胜率的。

a如果很大,这一极端就是围棋了。完全信息博弈下,几乎没有任何随机扰动,每一盘棋几乎由你的水平决定而没有临时的运气成分,哪怕先手和后手的一点点的系统误差都在计算目数的时候校正了。

而a接近0的极端就是三公或者石头剪刀布了,他们虽然公平,但是并不存在什么实力的事。

适中的a比如斗地主,升级,德州扑克,麻将等,既有实力成分,又免不了一定运气成分。

需要那么一点点运气加实力的游戏由于双方获胜概率不会悬殊,往往会增加前面说的熵,那么理论上对人们的吸引程度更大(完全随机的又会因为不感兴趣而直接不关注,熵再大也没用),我想足球篮球风靡世界多半和这个有关吧,而围棋再精妙,不搞出个人工智能AlphaGo来,恐怕也难以受到大面积关注。

但是,赌场里面的猜大小,21点之类的游戏连公平都算不上,更靠不了实力了,实力顶多输的少一点而已。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-04-12,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 MatheMagician 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
关于洗牌的研究(一)——平常你都是怎么洗牌的?
写再前面:本系列作品由MathMagician独家首发,一共有七篇,从数学和魔术两个角度对日常生活中“洗牌”这一现象作了挂一漏万的分析。之所以说是挂一漏万,是因为无论数学还是魔术,洗牌中的任何一个小点都够写几篇了,这点篇幅不可能绝对全面。所以,本系列主要选取了一些常见的洗牌方式和相关内容展开作了一些介绍,包括洗牌分类,混乱度评价,过程建模,近似计算,以及几个基本但是及其巧妙的利用洗牌规律设计的魔术。相信聪明的你读完以后,会在数学和魔术上,都对“洗牌”这一现象有着更加深入的认识。
magic2728
2019/09/27
1.4K0
关于洗牌的研究(一)——平常你都是怎么洗牌的?
关于洗牌的研究(二)——你的扑克洗乱了吗?
写再前面:本系列作品由MathMagician独家首发,一共有七篇,从数学和魔术两个角度对日常生活中“洗牌”这一现象作了挂一漏万的分析。之所以说是挂一漏万,是因为无论数学还是魔术,洗牌中的任何一个小点都够写几篇了。所以,本系列主要选取了一些常见的洗牌方式和相关内容展开作了一些介绍,包括洗牌分类,混乱度评价,过程建模,近似计算,以及几个基本但是及其巧妙的利用洗牌规律设计的魔术。相信聪明的你读完以后,会在数学和魔术上,都对“洗牌”这一现象有着更加深入的认识。
magic2728
2019/09/27
9480
关于洗牌的研究(二)——你的扑克洗乱了吗?
关于洗牌的研究(四)——洗牌混乱度计算
写再前面:本系列作品由MathMagician独家首发,一共有七篇,从数学和魔术两个角度对日常生活中“洗牌”这一现象作了挂一漏万的分析。之所以说是挂一漏万,是因为无论数学还是魔术,洗牌中的任何一个小点都够写几篇了。所以,本系列主要选取了一些常见的洗牌方式和相关内容展开作了一些介绍,包括洗牌分类,混乱度评价,过程建模,近似计算,以及几个基本但是及其巧妙的利用洗牌规律设计的魔术。相信聪明的你读完以后,会在数学和魔术上,都对“洗牌”这一现象有着更加深入的认识。
magic2728
2019/09/27
1K0
关于洗牌的研究(四)——洗牌混乱度计算
关于洗牌的研究(七)——从数学到魔术之鸽尾洗牌
写再前面:本系列作品由MathMagician独家首发,一共有七篇,从数学和魔术两个角度对日常生活中“洗牌”这一现象作了挂一漏万的分析。之所以说是挂一漏万,是因为无论数学还是魔术,洗牌中的任何一个小点都够写几篇了。所以,本系列主要选取了一些常见的洗牌方式和相关内容展开作了一些介绍,包括洗牌分类,混乱度评价,过程建模,近似计算,以及几个基本但是及其巧妙的利用洗牌规律设计的魔术。相信聪明的你读完以后,会在数学和魔术上,都对“洗牌”这一现象有着更加深入的认识。
magic2728
2019/09/27
9880
关于洗牌的研究(六)——从数学到魔术之完美洗牌
写再前面:本系列作品由MathMagician独家首发,一共有七篇,从数学和魔术两个角度对日常生活中“洗牌”这一现象作了挂一漏万的分析。之所以说是挂一漏万,是因为无论数学还是魔术,洗牌中的任何一个小点都够写几篇了。所以,本系列主要选取了一些常见的洗牌方式和相关内容展开作了一些介绍,包括洗牌分类,混乱度评价,过程建模,近似计算,以及几个基本但是及其巧妙的利用洗牌规律设计的魔术。相信聪明的你读完以后,会在数学和魔术上,都对“洗牌”这一现象有着更加深入的认识。
magic2728
2019/09/27
1.3K0
Gilbreath原理中的数学与魔术(一)——Gilbreath Shuffle & First Principle
从本期开始再次进入久违的数学魔术系列,这期给大家准备的是经典的数学魔术原理Gilbreath Principle!经过陆陆续续历时半年多才整理出了这个系列的全部数学原理,魔术内容以及视频拍摄,各位数学和魔术爱好者们千万不要错过,精彩马上开始!
magic2728
2021/09/27
5530
魔术《4 Kings 折纸》的三重境界(四)——魔术效果的突破
就像数学总是走在所有科学的前沿,因为思绪飞扬的速度一定是最快的。那在数学魔术里,我们也可尝试一把用理论来倒推魔术效果的实验。
magic2728
2023/11/22
1480
魔术《4 Kings 折纸》的三重境界(四)——魔术效果的突破
关于洗牌的研究(五)——从数学到魔术之印度洗牌
写再前面:本系列作品由MathMagician独家首发,一共有七篇,从数学和魔术两个角度对日常生活中“洗牌”这一现象作了挂一漏万的分析。之所以说是挂一漏万,是因为无论数学还是魔术,洗牌中的任何一个小点都够写几篇了。所以,本系列主要选取了一些常见的洗牌方式和相关内容展开作了一些介绍,包括洗牌分类,混乱度评价,过程建模,近似计算,以及几个基本但是及其巧妙的利用洗牌规律设计的魔术。相信聪明的你读完以后,会在数学和魔术上,都对“洗牌”这一现象有着更加深入的认识。
magic2728
2019/09/27
6920
Si Stebbins Stack中的数学与魔术(六)——魔术《周而复始的世界》
在本系列前面的4篇作品中,我们从数学和实际操作角度对Si Stebbins Stack的各种性质作了全面的介绍,上一篇讲到了其第一个经典应用《恐怖透视术》,相关内容请回顾:
magic2728
2021/04/02
6010
Gilbreath原理中的数学与魔术(八)——Ultimate Gilbreath Principle终极应用魔术《四季魔术》等
在前面的系列文章中,我们已经通过7篇文章的论述,详细介绍了Gilbreath两个原理的理论和魔术应用,相关内容请戳:
magic2728
2021/10/26
4330
Gilbreath原理中的数学与魔术(八)——Ultimate Gilbreath Principle终极应用魔术《四季魔术》等
当代数恒等式遇上魔术(一)
在前面的系列文章中《加加减减的奥秘——从数学到魔术的思考》系列文章中,我们已经提到过关于预测未来的一个基本思路:寻找不变量。即无论观众如何选择,最后总有某些性质是和这些选择无关的(比如通过一个运算和其逆运算),由此产生一些神奇的魔术效果。
magic2728
2019/09/27
6750
卡牌大师:玩转“洗牌算法”,幸运女神在微笑 (*^_^*)
承接上一篇:理解 P/NP 问题时,我产生了一种已经触碰到人类认知天花板的错觉?!
掘金安东尼
2022/09/22
4360
卡牌大师:玩转“洗牌算法”,幸运女神在微笑 (*^_^*)
序列周期性与魔术(三)——经典应用与改良
在前面的文章中,我们从数学里的周期性入手,分析了序列周期性在对称群下的本质,以及如何把这一基本性质应用到魔术中的例子。
magic2728
2020/06/10
3960
对称与魔术初步(三)——经典魔术《total conincidence》的数学原理等
今天我们来看另外几个对称呈现相关的经典作品,重点讲第一个,因为这个作品无论是从呈现对称效果的宏大性上,还是里面数学原理和魔术结合之巧妙上,都是那么的天衣无缝!
magic2728
2022/03/17
3970
约瑟夫问题与魔术(六)——《自我匹配的奇迹》魔术赏析
转眼写到第6篇了。我们这个系列只有一个很小的主题——约瑟夫问题,最开始还担心内容不足,但是一番研究下来发现还是小看数学和魔术的创新和改造能力了。相比较于以前动辄对称,加减,逆运算等很大的议题,深入到更加具体的话题里也使得我们的内容更容易理解。
magic2728
2020/11/03
4810
序列周期性与魔术(四)——周期序列数学性质深入探秘
假设有一个m个人参加,每人依次发牌,每人总共n张牌游戏,总共需要mn张牌,编号为1:mn。任何一个人所发得的牌构成一个牌组(集合),我们只关心其组合,不关心其排列。
magic2728
2020/06/16
7630
序列周期性与魔术(二)——扑克牌叠里的周期性
其中,我们谈到一叠扑克牌在位置平移操作下的数学结构是最基础的群——循环群(Cyclic Group),记作Cn,n即为我们的周期:
magic2728
2020/06/04
8020
约瑟夫问题与魔术(五)——魔术《自我匹配的奇迹》中的数学原理
上一个魔术算是应用约瑟夫原理入门级别的作品,只是用上罢了。前面说了,约瑟夫过程在扑克牌叠上只是一个复杂但又确定的操作过程,应用时候一方面要防止枯燥无聊,另一方面最好再结合一切其他的魔术或数学方法一起使用,才能锦上添花,画龙点睛,发挥这个原理的最大作用。
magic2728
2020/11/03
8440
BZOJ1965: [Ahoi2005]SHUFFLE 洗牌(exgcd 找规律)
为了表彰小联为Samuel星球的探险所做出的贡献,小联被邀请参加Samuel星球近距离载人探险活动。 由于Samuel星球相当遥远,科学家们要在飞船中度过相当长的一段时间,小联提议用扑克牌打发长途旅行中的无聊时间。玩了几局之后,大家觉得单纯玩扑克牌对于像他们这样的高智商人才来说太简单了。有人提出了扑克牌的一种新的玩法。 对于扑克牌的一次洗牌是这样定义的,将一叠N(N为偶数)张扑克牌平均分成上下两叠,取下面一叠的第一张作为新的一叠的第一张,然后取上面一叠的第一张作为新的一叠的第二张,再取下面一叠的第二张作为新的一叠的第三张……如此交替直到所有的牌取完。 如果对一叠6张的扑克牌1 2 3 4 5 6,进行一次洗牌的过程如下图所示: 
attack
2018/07/27
3370
BZOJ1965: [Ahoi2005]SHUFFLE 洗牌(exgcd 找规律)
对称、群论与魔术(六)——经典魔术《对称找牌》
在前面的文章中,我们聊完了对称性的呈现和群论描述,以及从简单到复杂的在扑克牌上,对称性的具体分析,相关内容请戳:
magic2728
2022/05/18
3910
对称、群论与魔术(六)——经典魔术《对称找牌》
推荐阅读
关于洗牌的研究(一)——平常你都是怎么洗牌的?
1.4K0
关于洗牌的研究(二)——你的扑克洗乱了吗?
9480
关于洗牌的研究(四)——洗牌混乱度计算
1K0
关于洗牌的研究(七)——从数学到魔术之鸽尾洗牌
9880
关于洗牌的研究(六)——从数学到魔术之完美洗牌
1.3K0
Gilbreath原理中的数学与魔术(一)——Gilbreath Shuffle & First Principle
5530
魔术《4 Kings 折纸》的三重境界(四)——魔术效果的突破
1480
关于洗牌的研究(五)——从数学到魔术之印度洗牌
6920
Si Stebbins Stack中的数学与魔术(六)——魔术《周而复始的世界》
6010
Gilbreath原理中的数学与魔术(八)——Ultimate Gilbreath Principle终极应用魔术《四季魔术》等
4330
当代数恒等式遇上魔术(一)
6750
卡牌大师:玩转“洗牌算法”,幸运女神在微笑 (*^_^*)
4360
序列周期性与魔术(三)——经典应用与改良
3960
对称与魔术初步(三)——经典魔术《total conincidence》的数学原理等
3970
约瑟夫问题与魔术(六)——《自我匹配的奇迹》魔术赏析
4810
序列周期性与魔术(四)——周期序列数学性质深入探秘
7630
序列周期性与魔术(二)——扑克牌叠里的周期性
8020
约瑟夫问题与魔术(五)——魔术《自我匹配的奇迹》中的数学原理
8440
BZOJ1965: [Ahoi2005]SHUFFLE 洗牌(exgcd 找规律)
3370
对称、群论与魔术(六)——经典魔术《对称找牌》
3910
相关推荐
关于洗牌的研究(一)——平常你都是怎么洗牌的?
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档