Weighted Random: взвешенный случайный выбор

Weighted Random — выбор из набора с разными вероятностями для элементов. Основа большинства игровых механик.

Алгоритм

Дан массив весов [w₁, w₂, ..., wₙ]. Вычислить сумму S = Σwᵢ. Сгенерировать r = random(0, S). Итерировать: находить первый индекс, где кумулятивная сумма ≥ r. Возвращать соответствующий элемент. Сложность O(n) на выбор.

Оптимизации

Prefix sum + binary search: O(log n) на выбор после O(n) prep. Alias method (Vose): O(1) на выбор после O(n) prep. Reservoir sampling: для потоков. Выбор зависит от частоты обновления весов и количества выборок.

Применение в слотах

Reel strips: символы на барабанах распределены неравномерно. Bonus wheels: секторы разного размера. Random multipliers: чаще малые (2×, 3×), редко большие (100×). Всё это weighted random.

Тонкости реализации

Точность float: при малых вероятностях (10⁻⁶ и меньше) используйте integer weights и integer RNG. Балансировка: сумма весов = удобное число (10⁶). Аудит: log каждого выбора для регуляторов. Bias-free implementation критична для сертификации.