ryan_knight_12吧 关注:48,926贴子:2,844,007
  • 6回复贴,共1

【科普】关于311的真随机和伪随机

取消只看楼主收藏回复

边写边发


IP属地:北京1楼2018-08-22 14:32回复
    1.啥是伪随机啥是真随机
    就像伪摇滚、伪球迷一样,伪随机沾上了主观的“伪”字,就有很多种定义方法。在介绍这些方法之前,先看一下产生随机有哪几种。
    ①固定种子、固定公式的随机数序列
    举个例子,我首先拿出一个数X,然后每次对X使用公式 (3X + 4) % 5,再把结果给回X(%指的是求除法的余数)。假设X初始值是0,那么生成的“随机数序列”就是4, 1, 2, 0, 4, 1, 2, 0, 4, 1, 2, 0...
    这就是一个非常简单的随机数生成器了。而X的初始值被称为“种子”。
    但是大家很快就会发现问题,它循环了。4,1,2,0的循环体系使的人们在充分观察之后,可以发现规律并预测出下一个“随机数”。
    这个问题其实也好解决,3,4,5都是太小的数了,我把3,4,5都搞的非常大,循环周期就将会非常长,使的没有任何能看出它其实是循环的。比如在C++的函数库MT19937中,循环周期达到了2^19937-1这么长,基本遍历一整个宇宙的时间都无法重复。
    ②随机种子、固定公式的随机数序列
    上一个例子中,虽然算法(至少表面上)解决了循环的问题,但还有一个问题,那就是每次的结果都是固定的。两次使用同一个公式和种子,得到的结果是完全相同的,这可太不随机了。怎么办?
    解法就是改变种子。如果种子改变了,那么之后的序列就完全不相同,随机的目的就达到了。那么,改变种子该依据什么呢?如果还是使用公式生成,那这个生成随机种子的公式又该用什么随机种子呢?(有点绕,大家可以仔细思考一下)
    一个很好的办法是放弃数学上的公式,改为使用物理特征,比如,时间。如果我使用从1970.1.1至今的秒数作为初始种子,这总不太可能重复了吧?如果大家写过C语言,很可能接触过这行指令:srand(time(0)),它的作用就是上述的种子初始化。
    当然,用时间作为种子在安全上也不是万无一失的。我以前搞信息安全的时候,遇到过以时间为种子的攻击方式,思路是先算出来当前的秒数,然后预测代码会什么时候执行,根据执行时间配合随机种子达成攻击。扯远了,不多说了。我的意思是,如果嫌时间都不安全的话,还可以使用“当前CPU的温度”、“当前内存剩余量的字节数”等等无法探测的物理硬件特征作为种子,使得种子完全随机、安全。
    ③随机种子、随机公式的随机数序列
    总的来说就是在X = (aX + b) % c的公式中,改变每次的X时同时依据X的值改变a,b,c。但是这样的问题在于,如果X不改变,两次的模拟结果仍然是完全相同的。所以这种方法现在用的不多,只作为提一句而已。
    ④现实中的随机
    截止到③,已经基本是计算机模拟随机的极限了。再往上无非是把公式搞得更复杂一些,用“异或”运算代替乘法之类的,换汤不换药。
    那么现实中的随机是什么样的呢?现代物理学的解释是:量子力学。
    就算大家没学过量子力学,应该也多少听过薛定谔的猫、量子纠缠、海森堡测不准原理等名词。从名字就能看出,测都测不准,当然是最高级的随机了。这部分是完全没有公式的真·随机
    当然这部分涉及最尖端的量子物理,我没法讲的很深入,有大学物理基础且有兴趣的同学可以去看下隐变量猜想。贝尔证明了,如果真的有隐变量,那么物理定律的定域性和实在性起码必舍其一,而因为实验和物理学家都不愿意否定这两点,所以现在物理学界认为是真随机。


    IP属地:北京3楼2018-08-22 15:01
    收起回复
      2026-07-14 18:55:41
      广告
      不感兴趣
      开通SVIP免广告
      1.啥是伪随机啥是真随机(2)
      上一部分讲的学理性比较重。我向大家保证下面不会有这么复杂的学术概念了。回到最初的问题,什么是伪随机什么是真随机?归纳一下大概有两种说法。
      第一种说法是,真随机指的是 【已知当前状态,无法预测下一状态的随机】
      按照这种说法,除了现实中的量子力学随机是真随机,其他一切都是伪随机。因为计算机就算有随机种子,也都是有公式的。只要我们知道了某个时刻的X,那么一定可以代入公式求出下一个X。相比之下,量子力学连公式都没有,自然是真随机。
      这种说法也是我们可能曾听到的“计算机没有真随机”的来源。
      但是客观来说,这种说法要求有点太高了。SIRE出了“真随机模式”之后,好多人跑来发帖说计算机没有真随机。我只能说,按照这个定义,你说得对;但另一方面,你这属于抬杠,因电脑游戏领域中,真随机指的另一个定义。


      IP属地:北京7楼2018-08-22 15:06
      回复
        1.啥是伪随机啥是真随机(3)
        第二种定义,也是比较适合游戏领域的定义中,真随机指的是【两次不同的游戏中,生成的随机数序列不同】
        按照这种说法,除了确定公式确定初始种子的①属于伪随机以外,其他的都是真随机。因为只要随机种子变了,那对于我一个游戏玩家来说,之后的所有操作结果也就都完全变了,这样已经算得上真随机了。
        更何况,由于随机数种子大多是“距离1970.1.1的秒数”,这种东西很难精准掌握,那玩家也就很难去“操纵”随机数了。


        IP属地:北京11楼2018-08-22 15:11
        回复
          2.311是怎么写的随机
          前边大家听起来感觉都没在说人话。下面讲点实在的。先说结论:311使用的是①:固定种子固定公式的随机数生成序列。我们下面来看一下逆向之后的游戏源码。
          在游戏中,一共有两个随机数函数。
          第一个随机数函数接受一个0~100的整数输入(记为X),返回一个布尔值(是或者否)。函数以X%返回是,(100-X)%返回否。举个例子,如果输入的X是100,那么函数一定会返回是,如果输入的X是0,则一定会返回否。假如X为70,那70%概率返回是。
          第二个函数接受一个≥2的整数输入(记为X),等概率随机返回0~X-1之间的一个函数。举个例子,假如输入的是2,那么有50%返回1,50%返回0。如果输入的是9,则以各10%概率返回0-9。
          下面我们看一下对应的C代码(经过逆向还原后)。


          IP属地:北京13楼2018-08-22 15:21
          回复
            第一个函数,输入percentage,以percentage%返回真:
            BOOL Random_100(int percentage)
            {
            if ( percentage <= 0 )
            return 0;
            random_value = 1812433253 * random_value + 12345;
            return (random_value >> 16) % 100 < percentage;
            }
            分析一下这个函数。先判断,如果输入的percentage小于0,直接返回(-20%可能就等于不可能咯)。
            如果不是的话,将内存中的random_value乘以一个很大的数,再加上12345赋值回去。这个其实就和我们之前讲的X=(3X+4)%5是一模一样的,只是更复杂了一点。
            最后,我们再将random_value除以2^16,再整除除余100,【就得到了一个0~100的随机数】。如果这个随机数小于我们输入的percentage(概率为percentage / 100),那么就返回真,否则返回假。
            类似的,我们再看一下第二个函数
            // 随机返回一个0 ~ X-1之间的数
            __int16 __cdecl Random_Smallerthan(signed int X)
            {
            if ( X < 2 || !X ) // if X == 0 or 1
            return 0;
            random_value = 1812433253 * random_value + 12345;
            return (random_value >> 16) % X;
            }
            如果X是0或1,直接返回0(因为这种情况下比X更小的只有0)
            如果不是的话,也是对random_value使用同样的公式处理,将结果除以2^16后对X除余。这样,我们就得到了一个0~X-1的随机数。
            思路非常清晰,就是我们刚刚讲到的生成方法①


            IP属地:北京14楼2018-08-22 15:26
            回复
              5.结论
              ①311使用的是固定种子固定公式的随机数生成法。在种子确定了之后,之后的所有序列都是确定的,所以玩家可以SL。
              比如说,生成的序列是50 90 0 30 40...这个序列是确定的,在第一个数50这里,成功率低于50%的操作都会失败。失败或者成功之后,序列移动到下一个数90,所有成功率低于90%的操作都会失败,失败或者成功之后,序列移动到下一个数0,任何操作,只要成功率不为0(比如对着洞察放技能),操作都会成功。
              如果你不进行操作,只是随便看看成功率,那么序列不会移动。
              ②评定不耗费行动力,但又等同于一次操作,会将序列移动到下一格。因此可以使用评定来操纵随机数种子。
              ③RK的真随机模式总会改变种子,因此虽然种子确定之后的所有序列也是确定的,但是由于种子老是在变,玩家没法利用这一点进行SL


              IP属地:北京21楼2018-08-22 15:43
              收起回复