伪随机数生成

游戏引擎到处要用随机数，但随机数生成器 (RNG) 并不真正随机：它只是给出一个复杂但完全确定、预先定义的序列，因此严格说应叫伪随机数生成器 (PRNG)。好坏取决于周期（多久重复）和能否通过各种公认的随机性测试。GEA 介绍了线性同余、梅森旋转、Marsaglia 的 Mother-of-All / Xorshift / KISS99，以及 PCG。

线性同余生成器 LCG（卷 I 5.7.1）

• 非常快、非常简单；有些平台的 C 标准库 rand() 就用它，但不要假设 rand() 基于任何特定算法——想确定就自己实现。算法细节 GEA 引用《Numerical Recipes in C》，未展开。
• 质量不高：同一种子总是产生完全相同的序列（这是所有 PRNG 的共性）；不满足很多公认的理想标准，如长周期、低位和高位都有足够长的周期、生成值之间没有序列或空间相关性。

梅森旋转 Mersenne Twister（卷 I 5.7.2）

专门为改进 LCG 的问题而设计。GEA 引用 Wikipedia 列出的优点：

1. 周期巨大：$2^{19937}-1$（作者已证明；$2^{19937}\approx4.3\times10^{6001}$），实际应用很少需要更大的；
2. 维度均匀分布阶数很高，连续输出之间的序列相关性可以忽略；
3. 通过大量统计随机性测试，包括严格的 Diehard 测试；
4. 快。

• 网上有多种实现，其中 SFMT（SIMD-oriented Fast Mersenne Twister）用 SIMD 指令进一步提速（见 SIMD 向量化）。

Mother-of-All、Xorshift 与 KISS99（卷 I 5.7.3）

Marsaglia 也是 Diehard 随机性测试集的作者。

PCG（卷 I 5.7.4）

另一个流行的高质量 PRNG 家族：用同余生成器 (congruential generator) 做状态转移（名字里的「CG」），再用置换函数 (permutation) 生成输出（「P」）。

取舍

• 所有这些都是确定性的：同一种子得到同一序列。GEA 把这一点作为 LCG 的缺点提出；书中未讨论把确定性用于回放或网络同步等用途。

Schreiber & Romero 的视角：设计师眼中的伪随机（第 21 章，p.509–523）

本页上面几节（Gregory）讲生成器的算法；Schreiber 与 Romero 从游戏设计角度讲随机为何不够随机，以及由此带来的设计取舍。

实体随机也不完美（p.509–511）："公平的 d6"是理想状态，就像化学中的理想气体或物理中无摩擦无质量的滑轮。点数凹刻的骰子 1 面最重，因而 6 朝上略多；圆角加工不一导致某些面更易继续滚动；多数 d20 略呈椭圆，玩家的"幸运 d20"可能确有其事。抛硬币略偏向起始朝上的一面，转硬币偏差更大。普通的鸽尾式洗牌 (riffle shuffle) 随机化很差：顶/底牌大多留在顶/底附近，单次洗牌保留两叠内部的相对顺序（不可能一次把整副牌倒序），某些洗法重复若干次会回到原序（魔术师借此假洗牌）。宾果球、彩票球的油漆重量不同，儿童桌游的转盘摩擦不均。赌场因而使用公差约 10 微米、油漆等量的昂贵骰子——被怀疑器材作弊可能丢掉牌照，而不公平器材又会被精明的玩家利用；手工洗牌已大多改为洗牌机，机械洗牌机可能比人手更不随机，电子洗牌机按算法逐张排序，同样受下述算法问题影响。对普通玩家，这些缺陷对所有人一视同仁，"足够接近"即可。

种子（p.512–513）：计算机是确定性的，除非用测量混沌物理现象的专用硬件（如放射性衰变；脚注提到 random.org，但依赖第三方真随机数据在业界不实用）。RNG 由一个看似无规律的函数反复迭代得到，起点即种子，一般在游戏启动时设一次；同一种子得到完全相同的结果——测试复现很有用，但正式版若意外如此就糟了。种子的选取要让玩家难以复现：若只用系统时钟的毫秒小数部分（0–999），游戏实际只有 1000 种"洗法"，重复游玩会看到雷同的局，PvP 中有心人能从前几个结果推断种子并预测之后的一切；即使用"午夜以来的毫秒数"也只有 8640 万个种子，玩家每天在同一时段游玩可能两次遇到同一个种子。

联网不同步（p.513）：若双方客户端共用种子各自生成随机数，一处 bug 让一方多生成了一个数而没通知对方，游戏可以照常进行几个回合，直到某次掷骰一边成功一边失败，状态比对出错，双方都以为对方作弊。这类 bug 很难定位。脚注建议游戏逻辑放在服务器上，只保留单一游戏状态；无服务器的直连（如蓝牙）则指定一台设备为权威并广播状态。

存档与读档（p.513–516）：单机游戏无法完全杜绝存读档利用，只能"选择毒药"：

完美的存档系统是游戏设计中尚未解决的问题：玩家要么操纵过去（读档重掷），要么操纵未来（试一次再读档获得预知）。但它仍必须由设计师来设计——否则会落到某位程序员手里，按最容易写的方式实现。设计师能做的是了解可能的利用并让游戏其余部分把影响降到最低：例如允许随处存档又不想经济被轻易打破，就不要做能短时间翻倍财富的赌场，或严格限制赌场收益，或在赌场周围大范围禁止存档。桌游没有存读档，因此不存在这个问题。

洗牌算法（p.516–518）：

• 新手常用的"随机挑两张交换，重复几千次"既低效又不随机：任何一张牌总有非零概率从未被选中，因此出现在原位的概率永远略高于其他位置，交换次数越多这个偏差越小，但永远不为零。
• 正确做法：从未选过的牌中随机挑一张放到下一个位置，即下面的循环（Fisher–Yates 洗牌，原书未用此名），每张牌一次随机数和一次交换：

for (int i=DECK_SIZE-1; i>0; i--) {
    int r = rand()%(i+1);
    tmp = Deck[i]; Deck[i] = Deck[r]; Deck[r] = tmp;
}

• 支线 21.2 的变体把 rand()%(i+1) 改成 rand()%DECK_SIZE（每个位置可与整副牌中任意一张交换）。用 3 张牌验证：变体共有 $3^2=9$ 条等概率的路径（原书循环 i 从 2 到 1，执行两次），要分配到 $3!=6$ 种排列上，9 不能被 6 整除，因此必然不均匀；正确算法的路径数为 $3\times2=6$，恰好每种排列一条。（本条为本 wiki 的推算，原书只给出提示。）
• 种子空间不够大：64 位整数有 $2^{64}\approx1.8\times10^{19}$ 个，而 52 张牌有 $52!\approx8.07\times10^{67}$ 种排列，绝大多数理论上可能的洗牌结果永远不会出现。$\log_2 52!\approx225.6$，需要 226 位（原书说按 2 的幂即 256 位机器）；$\log_2 60!\approx272.1$，256 位也不够处理万智牌 60 张的套牌；100 张需要约 525 位（支线 21.3，本 wiki 计算）。若种子来自"午夜以来的毫秒数"，种子空间只有约 8600 万，手边的电脑几秒内就能搜完；玩家只要猜出种子生成方式和 RNG 算法（如 C++ 标准库的 rand()），不需要几个结果就能定位序列并完全预测之后的结果。脚注警告：赌场有出色的实时统计，能迅速区分幸运儿与作弊者，后果可能是终身禁入乃至刑事或民事诉讼。涉及大笔金钱的赌博游戏或高水平竞技比赛，必须额外确保随机数无法被破解。

结论与练习：完全随机的"随机数"是理想情况，"足够接近"的标准取决于休闲游戏、高额竞技还是受严格监管的博彩业。支线 21.1 用电子表格 =RAND() 生成 1000 对数画散点图，作为快速粗略的 RNG 检验；21.4 自己写 200 次抛硬币程序，研究所用 RNG 和种子生成方式，把种子空间缩小到几百万以内后预先算出所有序列并搜索匹配，看需要几次抛掷才能唯一确定种子；21.5 分析一款游戏的存档系统（何时能存、种子是否保存、存档能否复制）并列出所有可行的利用及其实用程度。（本章讨论题在提取文本中缺失第 1、3、9 题及第 9 题前半，未能读到。）

两种观点对照

说明：可达到的洗牌结果数取决于 RNG 的内部状态位数和种子的熵，而不是 CPU 字长。梅森旋转 MT19937 有 19937 位状态（Matsumoto & Nishimura, ACM TOMACS 8(1), 1998），64 位机器也能使用。原书"需要 256 位的计算机"的说法不准确，正确的结论是需要至少约 226 位熵的种子和足够大的生成器状态。原书关于"用 32/64 位种子时绝大多数排列无法出现"的结论本身是正确的。

补充核对：鸽尾式洗牌"要洗好多次才够随机"——Bayer 与 Diaconis（Annals of Applied Probability 2(2), 1992）证明 52 张牌约需 7 次鸽尾式洗牌才接近均匀。硬币偏向起始朝上的一面：Bartoš 等人 2023 年的 35 万次实验测得约 50.8%（arXiv:2310.04153），与原书一致。

PBRT 的视角：PCG 与无偏有界整数（PBRT 4e B.2.12）

• pbrt 使用 PCG（O'Neill 2014）：通过严格的统计随机性测试，实现又很紧凑。用户可提供两个 64 位值：一个从 $2^{63}$ 条序列中选一条（每条长 $2^{64}$），另一个是序列内的起始偏移。Advance() 可以把状态跳过任意步数，operator- 给出两个生成器之间相差的步数。
• 有界整数：pbrt 前两版用 Uniform<int32_t>() % b，当 $2^{32}$ 不是 $b$ 的倍数时偏向较小的值。第 4 版先用 32 位运算求出 $\text{threshold}=2^{32}\bmod b$，Uniform() 返回值小于 threshold 就丢弃重抽，剩下的取值个数恰为 $b$ 的整数倍，再取模就无偏了。