从羊了个羊看随机数的生成原理

　　你的《羊了个羊》第二关通关了吗？
　　作为一款三消类的休闲小游戏，《羊了个羊》虽然在玩法上并没有多大创新，但却以其相邻关卡间巨大的游戏难度落差成功出圈。讨论度提高的同时，也招致了一些批评的声音，主要是指责《羊了个羊》毫无游戏性可言，罪状无一例外都提到同一个词—— 「随机性」 。
　　简单讲就是，三消类的游戏虽然看起来是一堆混乱无序的元素，但大体遵循一些默认的游戏规则，比如 「每种元素的数量以及所有元素的总数量一定数字3的倍数」 ，以保证所有的元素最终都能配对消除并获胜，只是每种元素出现的时机是随机的而已。
　　但《羊了个羊》偏偏＂不讲武德＂，它让每种元素出现的概率都是随机的，也就是批评者口中的＂真随机性＂，这样导致的结果就是，你分配到的牌局可能从一开始就是个死局，等你玩到最后才发现根本无法完全消除。
　　最后的无解情况.png
　　今天我们不讨论《羊了个羊》＂武德＂问题，但既然提到了游戏中的随机性问题，那我们就想站在程序的角度来好好说道说道了~
　　大家好，我是玩羊玩到晚上要数羊睡觉的椎锋陷陈，今天我们要分享的主题是 「随机数的生成原理」 。
　　可能有读者要产生疑惑了，我们讨论的不是游戏中的随机性问题吗，怎么变成了随机数的生成原理了？这是因为，随机数本身就是随机性所产生的结果，又是反过来指导游戏行为的依据，比如《羊了个羊》中每回合出现的元素种类，所以引申出来讨论随机数的生成原理并不生硬。
　　这里我们首先要探究的一个问题就是，游戏中产生的随机数，是真的随机数吗？很遗憾，并不是，这里面大部分产生的都是 「伪随机数」 。 伪随机数是什么？
　　计算机是确定性的，这意味着其产生的所有行为，都是由其预先编写的所有指令所决定的，仅依赖一个确定性的事物，是无法产生一个随机性的结果的。
　　随机数.png
　　我们拿到的所谓随机数，只是看起来随机而已，也就是说， 「只是符合统计学上对于随机性认定的要求，但随机数的产生过程却是确定的」 。
　　什么意思呢？
　　首先， 「伪随机数生成器内部制定了一个算法，本质上就是一个数学公式」 。公式所得到的随机数集是一个序列，「序列中的每一个随机数，都是由前一个随机数代入相同的公式计算得出的」 。
　　而序列的起始值，我们称之为 「种子数」 ，决定了整个随机数序列的所有数值。
　　所以，理论上，我们只要知道伪随机数生成器的种子数和内部算法，就可以推演出整个随机数序列。因此，伪随机数生成器是不安全的，不能用于安全系数要求高的场合，比如登录时默认的随机密码生成，但对于《羊了个羊》这一类的休闲小游戏来讲还是没啥问题的。
　　那么，伪随机数生成器都有哪些算法呢？  伪随机数生成器算法平方取中法
　　平方取中法是由冯·诺伊曼提出的一种产生均匀伪随机数的算法，算法的原理很简单，首先选定一个种子数，假设是一个四位数字，比如4321。
　　接着，正如算法的名字所表述，先对种子数进行平方4321^2=18671041，再取中间四位数字18[6710]41，从而得到序列下一项6710。
　　如果平方后不足八位，则在数字的前面填充0直至满八位，如241^2=58081=00[0580]81=0580。
　　随后重复这个过程，就能持续生成多个位于0到9999之间的随机数。  线性同余生成器
　　不过，这显然不能满足我们需要生成伪随机数的多数场景。目前生成伪随机数的最佳算法，是一种叫做 「马特赛特旋转演算法」 的现代算法，其基于更简单的「线性同余生成器」 ，一种常见的伪随机数生成器。
　　线性同余生成器要求有4个输入，除了固定要求的种子数之外，还有 「模数m、乘数a以及增量c」 。
　　计算方式是种子数乘以a再加上c，然后把计算结果对m进行求模，也即除以m并取余数。
　　线性同余生成器.png
　　随后重复这个过程，就可以得到余下的随机数序列，得到的随机数将位于0到m-1之间。
　　算法过程我们了解了，但线性同余生成器又是凭借什么优势，在伪随机数生成这方面更受青睐的呢？  线性同余生成器的优势
　　其实，无论是哪一种伪随机数生成器算法，除了前面所提到的安全性问题之外，还有一个相同的天然缺陷，那就是其生成的随机数序列，无论长短，最终都会重复出现，即形成一个循环。
　　因此就有了 「周期」 的说法，所谓周期，指的就是「在两次循环之间出现的不同随机数项的数目」 。
　　原因我们前面已经讲了：恒定的计算公式，以及依赖于前一个随机数。
　　我贴一部知名恐怖电影的海报你们就懂了：
　　恐怖游轮.png
　　而线性同余生成器的优势在于，其周期的长度是m-1，即取决于模数m，只要保证m的取值尽量大，比如2的32次方，就能极大地延长随机数重复的周期，但也只是延长，本质上仍无法避免。
　　那么，真的就无解了吗？既然有伪随机数的说法，那有没有真随机数呢？
　　还是有的。  真随机数怎么得到？
　　既然从内部无法自我解决，那就寻求外部的帮助吧，也即接受一个我们认为是随机性的外部事物的输入作为种子数，从而使得经过计算机处理之后的结果也是随机的，这个外部事物就是——自然界的噪声。
　　这个 「噪声」 是物理学上的含义，指的是一切不规则的信号，而不一定是声音。
　　比如RANDOM.ORG这个网站，就是以大气噪声，也即自然界雷暴活动所产生的电磁辐射作为随机性的外部事物的输入，借此提供各项服务以满足各种各样需要生成真随机数的场景。
　　闪电击中广州塔.png
　　既然需要外部事物的输入，那也就意味着 「需要额外的硬件设备支持」 ，以收集和测量随机的物理现象或普通事件。但也不用把它想象的过于高大上，诸如鼠标、键盘的点击都可以作为随机事件的种子数。
　　另一方面，由于搜集外部的数据需要时间，也导致了真随机数生成器的另外一个缺点—— 「不够快」 。以及，由于随机性的外部事物的输入很难重现，也将导致我们「无法复现随机数生成过程」 ，测试流程常常无法正常进行。
　　不过，己之缺点即是彼之优点， 「对于伪随机数生成器来说，不需要外部设备支持、计算效率高、可复现则是其明显的优势」 。
　　好了，这个就是今天要分享的内容。
　　总结一下，《羊了个羊》每种元素的随机生成使用的仍然是 「伪随机数生成器」 ，因此说它＂真随机性＂其实并不太准确。
　　而其宣传所谓的通关率不到0.1%，与游戏难度本身关系不大，你无法通过大概率是你刚好被分配到的牌局没有达到三消类游戏通关的基本要求。
　　「最后，祝你是那0.1%的幸运儿，游戏如是，生活也如是。」
　　通关截图.png  参考
　　How to Generate Pseudorandom Numbers | Infinite Series https://www.youtube.com/watch?v=C82JyCmtKWg
　　作者:椎锋陷陈
　　来源:微信公众号:椎锋陷陈
　　出处:https://mp.weixin.qq.com/s/ULJzyBO2iMiB5Wvc6OnKRg