Алгоритмы неформально. Инструкция для начинающих питонистов - [42]

Идея умного игрока, пытающегося выиграть в рулетку, будет полезной для оценки любого ГПСЧ. Если рулеткой будет управлять настоящая случайность, то ни один игрок не сможет уверенно выиграть в нее. Но любую незначительную слабость (или отклонение от истинной случайности) нашего ГПСЧ достаточно умный игрок сможет обратить в свою пользу. Даже если вы создаете ГПСЧ для цели, не имеющей никакого отношения к рулетке, спросите себя: «А если я использую ГПСЧ для управления рулеткой, не проиграю ли я все свои деньги?» Интуитивно понятный тест рулетки позволяет судить о том, насколько хорош или плох любой конкретный ГПСЧ. Наш ЛКГ пройдет проверку, если количество запусков не превысит 32, но после этого игрок сможет заметить повторяющуюся последовательность и начнет делать ставки с идеальной точностью. ЛКГ не проходит тест рулетки из-за своей малой периодичности. А значит, будет полезно позаботиться о том, чтобы ГПСЧ имел большой период. Но в случае с рулеткой, имеющей всего 32 сектора, период детерминированного алгоритма не может быть более 32. Вот почему ГПСЧ часто оценивается не по большому, а по полному периоду. Возьмем ГПСЧ, который будет получен в результате вызова list_random(1,2,24):

[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 1]

В этом случае период равен 12. Этого может быть достаточно только для очень простых целей, но данный период не является полным, поскольку не включает все возможные значения в диапазоне. И снова умный игрок заметит, что на рулетке не выпадают четные числа (не говоря уже о том, что нечетные числа следуют очень простой закономерности), и повысит свой выигрыш за ваш счет.

С большим полным периодом связана идея равномерного распределения, при котором все числа в диапазоне ГПСЧ генерируются с равной вероятностью. Выполнение команды list_random(1,18,36) дает следующий результат:

[1, 19, 1, 19, 1, 19, 1, 19, 1, 19, 1, 19, 1, 19, 1, 19, 1, 19, 1, 19, 1, 19, 1, 19, 1, 19, 1, 19, 1, 19, 1, 19, 1, 19, 1, 19, 1]

Здесь 1 и 19 выпадают с 50%-ной вероятностью в результатах ГПСЧ, а у всех остальных чисел вероятность составляет 0 %. С таким неравномерным ГПСЧ задача игрока предельно упрощается. С другой стороны, в случае list_random(29,23,32) все числа генерируются с вероятностью около 3,1 %.

Как видите, математические критерии оценки ГПСЧ отчасти связаны друг с другом: отсутствие большого или полного периода может быть причиной неравномерности распределения. С более практической точки зрения этим математические свойства важны только из-за того, что наша интернет-рулетка будет терять деньги. Если же формулировать в более общем виде, то единственный действительно важный критерий для ГПСЧ — возможность выявления закономерностей в результатах.

К сожалению, возможность обнаружения закономерностей трудно компактно сформулировать на математическом или научном языке. Таким образом, большой полный период и равномерное распределение интересуют нас как признаки, предоставляющие информацию об обнаружении закономерностей.

Разумеется, это не все признаки, по которым можно судить о наличии закономерностей. Возьмем ЛКГ, определяемый вызовом list_random(1,1,37). Команда выдает следующий список:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 0, 1]

Результат характеризуется большим периодом (37), полным периодом (37) и равномерным распределением (каждое число появляется в выводе с вероятностью 1/37). Тем не менее в нем легко обнаруживается закономерность (число каждый раз увеличивается на 1, пока не достигнет 36, после чего повторяется от 0). Генератор соответствует математическим критериям, которые мы приняли, но определенно не проходит тест рулетки.

Тесты Diehard

Не существует одного универсального теста, который бы показывал, существует ли в ГПСЧ закономерность, которая может быть использована для взлома. Ученые разработали много нетривиальных тестов для оценки устойчивости набора случайных чисел к поиску закономерностей (другими словами, к его способности пройти тест рулетки). Одна из таких подборок — так называемые тесты Diehard — состоит из 12 тестов, которые оценивают набор случайных чисел с определенных позиций. Если набор чисел проходит все тесты Diehard, то считается, что эти числа очень близки к истинной случайности. Один из тестов Diehard, называемый тестом пересекающихся сумм, берет весь список случайных чисел и вычисляет суммы последовательных элементов списка. Набор таких сумм должен следовать математической закономерности, которая называется колоколообразной, или гауссовой кривой. Реализация функции, генерирующей список пересекающихся сумм на языке Python, выглядит так:

def overlapping_sums(the_list,sum_length):

    length_of_list = len(the_list)

    the_list.extend(the_list)

    output = []

    for n in range(0,length_of_list):

        output.append(sum(the_list[n:(n + sum_length)]))

    return(output)

Применение этого теста к новому случайному списку может выглядеть следующим образом:

import matplotlib.pyplot as plt