游戏中的随机数：洗牌、加权随机与伪随机分布

问题：随机，但要“对的随机”

游戏里的随机数无处不在：暴击、掉落、地图生成、AI 决策、洗牌发牌。但“调用一下 rand()“会带来一连串问题：

• 无法复现：玩家报告“种子 12345 的地图第三层有 bug”，你却生成不出同一张地图
• 偷偷有偏：洗牌算法看起来很随机，某些排列的出现概率却明显更高
• 感觉不公平：数学上完全正确的 25% 暴击，玩家却总觉得“脸黑”

这一章逐个解决。

可复现的随机数生成器

计算机里的随机数几乎都是伪随机：由一个确定的算法从“种子”推导出一串看起来随机的数。同一个种子，永远得到同一串数，这恰恰是游戏需要的特性：程序化地图、录像回放、帧同步联机都依赖它。

为什么不用标准库

rand() 的范围可能只有 0~32767，质量也参差不齐，还是全局状态，多个系统共享时互相干扰。std::mt19937 本身是确定的，但 std::uniform_int_distribution 等分布的实现没有标准化：同一个种子在 MSVC 和 GCC 上可能得到不同结果。需要跨平台复现时，应该自己掌控从生成器到分布的每一步。

本系列使用 PCG32：只有 16 字节状态，速度快，统计质量好，代码不到 20 行：

cpp/foundations/random/random.h

// PCG32（pcg-random.org）：小、快、统计质量好，并且可以用种子精确复现。
// 游戏里需要"同一个种子生成同一张地图""回放录像"时，就不能用 rand() 或 std::random_device
class Pcg32 {
public:
    explicit Pcg32(uint64_t seed = 0x853c49e6748fea9bULL, uint64_t stream = 0xda3e39cb94b95bdbULL) {
        state_ = 0;
        inc_ = (stream << 1u) | 1u;
        next();
        state_ += seed;
        next();
    }

    uint32_t next() {
        uint64_t old = state_;
        state_ = old * 6364136223846793005ULL + inc_;
        auto xorshifted = static_cast<uint32_t>(((old >> 18u) ^ old) >> 27u);
        auto rot = static_cast<uint32_t>(old >> 59u);
        return (xorshifted >> rot) | (xorshifted << ((~rot + 1u) & 31u));
    }

    // [0, bound) 内的均匀整数。直接 next() % bound 会有偏差，这里拒绝掉"凑不满一轮"的那部分
    uint32_t below(uint32_t bound) {
        uint32_t threshold = (~bound + 1u) % bound;  // = 2^32 mod bound
        for (;;) {
            uint32_t r = next();
            if (r >= threshold) return r % bound;
        }
    }

    int range(int lo, int hi) { return lo + static_cast<int>(below(static_cast<uint32_t>(hi - lo + 1))); }  // 闭区间
    float nextFloat() { return static_cast<float>(next() >> 8) * (1.0f / 16777216.0f); }      // [0, 1)
    double nextDouble() { return static_cast<double>(next()) * (1.0 / 4294967296.0); }       // [0, 1)
    bool chance(double p) { return nextDouble() < p; }

private:
    uint64_t state_;
    uint64_t inc_;
};

注意 below 的写法。直接 next() % 6 是有偏的：2³² 不能被 6 整除，余下的那部分会让小的点数多出现一点点。正确的做法是把“凑不满一整轮”的那部分结果丢掉重抽。

洗牌：一个看起来对、其实错的算法

把一副牌打乱，很多人会这样写：遍历每个位置，和任意一个位置交换。

cpp/foundations/random/random.h

// 错误示范：每个位置都和"任意位置"交换。看起来很随机，但 n^n 种执行路径无法均分到 n! 种排列上
template <class T>
void naiveShuffle(std::vector<T>& items, Pcg32& rng) {
    for (size_t i = 0; i < items.size(); ++i) {
        size_t j = rng.below(static_cast<uint32_t>(items.size()));
        std::swap(items[i], items[j]);
    }
}

问题出在计数上：n 张牌，每步有 n 种选择，共 nⁿ 种执行路径，而排列只有 n! 种。6 张牌时是 46656 条路径对应 720 种排列，46656 不能被 720 整除，所以不可能每种排列概率相等。

正确的做法是 Fisher–Yates：从后往前，每个位置只和“它自己或它前面”的元素交换。这样恰好有 n! 条路径，一一对应 n! 种排列：

cpp/foundations/random/random.h

// Fisher–Yates 洗牌：从后往前，每个位置只和"它自己以及它前面"的元素交换。O(n)，且每种排列概率相等
template <class T>
void shuffle(std::vector<T>& items, Pcg32& rng) {
    for (size_t i = items.size(); i > 1; --i) {
        size_t j = rng.below(static_cast<uint32_t>(i));  // j ∈ [0, i-1]
        std::swap(items[i - 1], items[j]);
    }
}

图 0.5三个标签页：shuffle 对比两种洗牌，热力图显示每张牌（行）落在每个位置（列）的频率；crit 对比独立随机和伪随机分布的暴击；loot 是一个加权掉落表。按“重置”会得到完全相同的随机序列。单独打开 ↗

在 shuffle 页让演示多跑一会儿（可以把速度调到 8×）。Fisher–Yates 的格子逐渐变成均匀的 16.7%，朴素洗牌却始终保留一条明显的斜纹：第 k 张牌特别容易出现在第 k-1 个位置附近，最大偏差超过 20%。

加权随机：掉落表

“普通 60%、稀有 10%、传说 1%“这类掉落表，标准做法是预先算好权重的前缀和，抽取时生成一个 [0, 总权重) 的随机数，再二分查找它落在哪个区间：

cpp/foundations/random/random.h

// 加权随机（掉落表）：预先算好前缀和，抽取时二分查找，O(log n)
class WeightedTable {
public:
    explicit WeightedTable(const std::vector<double>& weights) {
        double sum = 0;
        for (double w : weights) cumulative_.push_back(sum += w);
    }

    int pick(Pcg32& rng) const {
        double r = rng.nextDouble() * cumulative_.back();
        auto it = std::upper_bound(cumulative_.begin(), cumulative_.end(), r);
        return static_cast<int>(it - cumulative_.begin());
    }

    double probability(int i) const {
        double prev = i == 0 ? 0 : cumulative_[i - 1];
        return (cumulative_[i] - prev) / cumulative_.back();
    }

    int size() const { return static_cast<int>(cumulative_.size()); }

private:
    std::vector<double> cumulative_;
};

预处理 O(n)，每次抽取 O(log n)。权重表很大且抽取极其频繁时，可以改用 别名方法（alias method），抽取降到 O(1)。

演示的 loot 页同时显示期望概率（竖线）和实际频率（条形）。抽得越多，二者越接近，这就是大数定律。但在抽取次数少的时候，传说装备的实际频率可能离 1% 很远，这正是玩家抱怨的来源。

让随机“感觉公平”

洗牌袋

如果希望结果“随机但均匀”，例如掉落方块的游戏希望每 7 个方块里 7 种形状各出现一次，可以把所有结果装进袋子，洗乱后依次取出，取完再装：

cpp/foundations/random/random.h

// 洗牌袋：把一组结果装进袋子，打乱后依次取出，取完再重新装。保证每一轮里每种结果恰好出现一次
template <class T>
class ShuffleBag {
public:
    explicit ShuffleBag(std::vector<T> items) : items_(std::move(items)), next_(items_.size()) {}

    const T& next(Pcg32& rng) {
        if (next_ >= items_.size()) {
            shuffle(items_, rng);
            next_ = 0;
        }
        return items_[next_++];
    }

private:
    std::vector<T> items_;
    size_t next_;
};

伪随机分布（PRD）

独立随机的 25% 暴击，连续 15 次不暴击的概率是 0.75¹⁵ ≈ 1.3%。一场战斗打几百刀，几乎每局都会遇到一次“长期脸黑”。

伪随机分布（Pseudo-Random Distribution）换了一种规则：第 N 次尝试的触发概率是 N × C，一旦触发，N 归零。刚暴击过的下一刀概率很低，越久没暴击概率越高，到 N × C ≥ 1 时必定触发。适当选取常数 C，长期平均概率仍然是 25%。

C 没有简单的解析解，但“平均概率”随 C 单调递增，可以二分查找：

cpp/foundations/random/random.h

// 伪随机分布（PRD）：第 N 次尝试的触发概率是 N·C，触发后 N 归零。
// 平均概率仍是 p，但"连续不触发"和"连续触发"都变少了
inline double prdAverageProbability(double c) {
    double expectedAttempts = 0;  // 两次触发之间的期望尝试次数
    double notYet = 1;            // 前 n-1 次都没触发的概率
    for (int n = 1; notYet > 0; ++n) {
        double pn = std::min(1.0, n * c);
        expectedAttempts += n * notYet * pn;
        notYet *= 1 - pn;
    }
    return 1 / expectedAttempts;
}

// 由名义概率 p 反求常数 C：平均概率随 C 单调递增，用二分查找
inline double prdConstant(double p) {
    double lo = 0, hi = p;
    for (int i = 0; i < 64; ++i) {
        double mid = (lo + hi) / 2;
        (prdAverageProbability(mid) < p ? lo : hi) = mid;
    }
    return (lo + hi) / 2;
}

class PrdRoll {
public:
    explicit PrdRoll(double p) : c_(prdConstant(p)) {}

    bool roll(Pcg32& rng) {
        ++attempts_;
        if (rng.chance(attempts_ * c_)) {
            attempts_ = 0;
            return true;
        }
        return false;
    }

    double constant() const { return c_; }

private:
    double c_;
    int attempts_ = 0;
};

常用概率对应的 C 值，以及最长可能的连续不触发次数：

名义概率 p	常数 C	最长连续不触发
5%	0.00380	263
10%	0.01475	67
15%	0.03222	31
20%	0.05570	17
25%	0.08474	11
30%	0.11895	8
40%	0.20155	4
50%	0.30210	3

切到演示的 crit 页：两条时间线的暴击率都接近 25%，但独立随机的时间线上有明显的空白和扎堆，PRD 的暴击分布均匀得多。下方直方图中，独立随机的间隔有一条很长的尾巴，PRD 的间隔则集中在 3~6 之间，而且不会超过 12。

PRD 也有代价

PRD 让“连续暴击”变少了，暴击的节奏更可预测。熟练的玩家可以利用这一点，例如先打小兵“攒概率”，再去打英雄。是否使用、用在哪些机制上，是设计决策而不仅是技术决策。

常见陷阱

问题	原因	解决
每次运行结果都一样，或每次都不同	种子固定写死，或每次都用当前时间	种子作为显式参数传入，需要随机时再取时间或系统熵
骰子 1~2 点出现得稍多	next() % n 的取模偏差	用拒绝采样的 below(n)
洗牌结果有偏	和任意位置交换	使用 Fisher–Yates
回放和原局对不上	多个系统共用一个随机数生成器，调用顺序变了	每个系统使用独立的生成器（不同 stream）
nextFloat() 偶尔返回 1.0	用 next() / 4294967295.0 得到闭区间	只取高 24 位再乘以 2⁻²⁴，得到 [0, 1)

在游戏中的应用

• 程序化生成：Roguelike 的种子地图，本质上就是把种子交给 PCG 这类生成器（见第四卷）。
• 帧同步联机：所有客户端用同一个种子、同样的调用顺序，才能得到同样的随机结果。
• 暴击、闪避、触发类被动：PRD 是 MOBA 和 ARPG 中的常见做法。
• 抽卡保底：在加权随机之外再加一层“N 次未出必出”的计数器，原理和 PRD 相近。

练习

1. 用 ShuffleBag 实现一个“7-bag”方块生成器，并统计任意两个相同方块之间最多间隔几个方块。
2. 实现别名方法（alias method），并与 WeightedTable 比较 100 万次抽取的耗时。
3. 修改 PrdRoll，让它在玩家死亡或切换场景时不重置计数。这会带来什么问题？

延伸阅读

• Melissa O’Neill，PCG, A Family of Better Random Number Generators
• Keith Schwarz，Darts, Dice, and Coins: Sampling from a Discrete Distribution：加权随机与别名方法的详细讲解
• Wikipedia，Fisher–Yates shuffle：包含朴素洗牌偏差的分析