你尚未登录,仅允许查看本站部分内容。请登录使用邀请码注册
zswang

伪随机数的妙用 1个回复 专栏 @ 业务

zswang 发布于 1 年前

伪随机数的妙用


作者:王集鹄 2015年12月15日

背景

大部分计算机上的伪随机数,并不是真正的随机数,只是重复的周期比较大的数列,是按一定的「算法」和「种子值」生成的。参考:随机数生成器

如果「随机数生成器」的「算法」和「种子值」相同,那么生成的「随机数序列」则是相同的,这就是「伪随机」的规律

不妨写个代码验证一下
正好 .NET 提供了可以指定随机种子的 Random 类。
在线调试)如下:

var rand1 = new Random(1024);
var rand2 = new Random(1024);
var flag = true;
for (var i = 0; i < 1000; i++) {
    if (rand1.next() != rand2.next()) {
        flag = false;
        break;
    }
}
Console.WriteLine(flag); // True

结果符合预期:相同种子值两个随机数序列完全相同。

脑洞

利用「伪随机生成器」这个特性,我们就可以用很少的字节生成非常大的恒定随机数序列

应用场景

那些情况会用到恒定随机数序列?

各种带随机性的游戏

  • 「俄罗斯方块」出现方块的形状序列

http://jsbin.com/riyibenazu/edit?html,console

<script src="http://jhtmls.com/jrands/jrands.js"></script>
<script>
'use strict';
let next2015 = jrands(2015); // 随机种子值指定为 2015
const next = (x) => parseInt(next2015() * 7);
let blocks = [];
for (let i = 0; i < 100; i++) {
  blocks.push(next());
}
console.log(blocks.join('')); // 2014635212545523621... 诸位看到的也是这个结果
</script>
  • 「泡泡龙」掉落泡泡的颜色序列

http://jsbin.com/jilipiliva/edit?html,console

<script src="http://jhtmls.com/jrands/jrands.js"></script>
<script>
'use strict';
const colors = ['red', 'yellow', 'gray', 'blue', 'white', 'green', 'none'];
let next2016 = jrands(2016); // 随机种子值指定为 2016
const next = (x) => colors[parseInt(next2016() * colors.length)];
let balls = [];
for (let i = 0; i < 100; i++) {
  balls.push(next());
}
console.log(balls.join(',')); // "none,gray,none,none,gray,gray,yellow,green.."
</script>
  • 「爱消除」排列的图案
  • 「帝国时代」随机地形
  • 「麻将」、「扑克」牌的顺序
  • 「连连看」随机双份图案

随手写一个洗牌算法。
思路:就是给每一张牌分配一个排序权重。

http://jsbin.com/welilisolo/edit?html,console

<script src="http://jhtmls.com/jrands/jrands.js"></script>
<script>
'use strict';
let next2017 = jrands(2017); // 随机种子值指定为 2017

// 一幅完整的牌
let cards = [];
for (var i = 0; i < 54; i++) {
  cards.push(i);
}

cards = cards.map((value) => ({
  value: value,
  ranking: next2017() // 随机生成排序权值
}))
  .sort((a, b) => a.ranking - b.ranking) // 按排序权值排序
  .map((item) => item.value);
console.log(cards.join(',')); // "9,45,47,3,26,41,42,11,35,..."
</script>

数据加密

随机数出现的序列是很难预测的,这和加密要达到的目的很类似,总之就是让人很难找到变化的规律。

http://jsbin.com/magibakape/edit?html,console

<script src="http://jhtmls.com/jrands/jrands.js"></script>
<script>
'use strict';
const randomXor = (text, seed) => {
  let next = jrands(seed);
  let result = '';
  for (var i = 0; i < text.length; i++) {
    result += String.fromCharCode(text.charCodeAt(i) ^ parseInt(256 * next()));
  }
  return result;
};
console.log(randomXor(randomXor('Hello World!', 2018), 2018));
// > Hello World!
</script>

如果要提高加密的复杂度,可以增加几个随机种子或者随机种子再随机生成等等手段。

总结

这个脑洞其实是在十多年前写多人对战的俄罗斯方块时想出来的,已经有实际应用。

优势

  • 能用最少的内容存储海量恒定随机数序列

缺点

  • 如果「随机算法」和「随机种子值」都被截获,那所有结果就是能预测的。

由于 JavaScript 里的 Math.random 显然不能指定「种子值」,所以按 .NET Random 类写了一个小库,jrands 随手安利一下。

推荐阅读

  • qgy18

    伪随机数还是很有用的,刚好前几天看到这篇文章《游戏中的网络同步机制——Lockstep》,写到:

    游戏开始前,参与游戏的玩家电脑协商确定一个随机种子,就可以保证在游戏进行过程中大家产生的随机数序列是相同的,也就可以保证计算结果一致。

    #1
登录后回复,如无账号,请使用邀请码注册