Генерирование псевдослучайных чисел на примере создания игры "Сапер"

22

Государственное образовательное учреждение

высшего профессионального образования

«Московский государственный технический университет

им. Н. Э. Баумана»

Калужский филиал

кафедра

«Системы автоматизированного проектирования»

Пояснительная записка

к курсовой работе

по дисциплине:

«Программирование на языке высокого уровня»

на тему:

«Генерирование псевдослучайных чисел на примере создания игры “Сапер”»

Калуга 2007

• Содержание
• Введение3
• 1.Исследовательская часть4
• 1.1.Генерирование псевдослучайных чисел
• 1.2.Целесообразность выбора языка
• 2.Конструкторская часть
• 2.1.Структура проекта.
• 2.2. Программная реализация основных элементов C#.
• 2.2.1.Классы
• 2.2.2.Члены класса
• 3.Технологическая часть
• 3.1.Системные требования
• 3.2.Запуск и процесс игры.
• Заключение
• Литература
• Приложение

ѕ изучить основные подходы при создании Windows приложений;

ѕ приобрести навыки работы с 2D графикой в Windows приложениях в С#;

ѕ исследовать методы генерации псевдослучайных чисел.

Задачей курсовой работы является разработка игры «Сапер» с расположением мин на основе нескольких методов генерации случайных чисел.

Даная тема является актуальной, так как в ходе разработки игры есть возможность изучить процесс создания Windows приложений и работу с 2D графикой, а «генерация случайных чисел -- слишком важное дело, чтобы оставлять её на волю случая» (Джон фон Нейман).

1.Исследовательская часть

Генератор псевдослучайных чисел (ГПСЧ) -- алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению.[1]

Современная информатика широко использует псевдослучайные числа в самых разных приложениях -- от метода Монте-Карло до криптографии. Генераторы псевдослучайных чисел широко используются в имитационном моделировании.

Термин ГПСЧ часто используется для описания ГПСБ (PRBG) -- генераторов псевдослучайных бит, а так же различных поточных шифров. Предназначение ГПСЧ -- генерация последовательностей чисел, которые невозможно отличить от случайных. Никакой детерминированный алгоритм не может генерировать полностью случайные числа, а только лишь аппроксимировать некоторые свойства случайных чисел.

Самые простые аппаратные ГСЧ (АГСЧ) основаны на тех свойствах элементов электронных схем, с которыми так долго и упорно боролись инженеры - схемотехники. Это свойство - собственные шумы электронного прибора.

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

Второму обширному классу АГСЧ лучше всего подойдет название "функциональный". Здесь в качестве "источника энтропии" используются фундаментальные функциональные свойства электронных приборов, например счетчиков Гейгера-Мюллера. Неприятной особенностью подобных устройств является необходимость применения радиоизотопных источников.

Третий класс АГСЧ- это "фундаментальный" класс. Наиболее яркий представитель "фундаментальных" АГСЧ - оптический квантовый генератор случайных чисел". Также существует устройство, в котором фундаментальные физические принципы, наносекундная синхронизация и самая современная электроника подчинены решению самой утилитарной задачи - получению случайных чисел, обновляющихся 100 тыс. раз в секунду.

Четвертый класс АГСЧ можно условно назвать "паразитным персонально-компьютерным". К их свойствам относятся прежде всего тепловые шумы и флуктуации в подсистеме аналогового ввода/вывода звукового адаптера.

В отдельный класс "курьезных" АГСЧ можно выделить специализированных роботов, методично бросающих... обычные игральные кости и оснащенных системой технического зрения для считывания выпавших очков.

Большинство простых арифметических генераторов хотя и обладают большой скоростью, но страдают от многих серьёзных недостатков:

ѕ Слишком короткий период/периоды

ѕ Последовательные значения не являются независимыми

ѕ Некоторые биты «менее случайны», чем другие

ѕ Неравномерное одномерное распределение

ѕ Обратимость

Наиболее распространены линейный конгруэнтный метод, метод Фибоначчи с запаздываниями, алгоритм Блюма, Блюма и Шуба, Вихрь Мерсенна.

Линейный конгруэнтный метод

Данный алгоритм был предложен Д. Х. Лемером в 1948 году. Применяется в простых случаях и не обладает криптографической стойкостью. Используется в качестве стандартного генератора многими компиляторами.

Этот алгоритм заключается в итеративном применении формулы (1):

(1)

где a > 0, c > 0, M > 0 -- некоторые целочисленные константы. Получаемая последовательность зависит от выбора стартового числа X0 и при разных его значениях получаются различные последовательности случайных чисел. В то же время, многие свойства последовательности Xj определяются выбором коэффициентов в формуле и не зависят от выбора стартового числа. Ясно, что последовательность чисел, генерируемая таким алгоритмом, периодична с периодом, не превышающим m. При этом длина периода равна m тогда и только тогда, когда:

1. НОД (c, m) = 1 (то есть c и m взаимно просты);

2. a - 1 кратно p для всех простых p -- делителей m;

3. a - 1 кратно 4, если m кратно 4.

При реализации выгодно выбирать m = 2e, где e -- число бит в машинном слове, поскольку это позволяет избавиться от относительно медленной операции приведения по модулю.

Формула (2) для вычисления n-й члена последовательности, зная только 0-й

(2)

Метод Фибоначчи с запаздываниями.

Особенности распределения случайных чисел, генерируемых линейным конгруэнтным алгоритмом, делает невозможным их использование в статистических алгоритмах, требующих высокого разрешения.[2]

В связи с этим линейный конгруэнтный алгоритм постепенно потерял свою популярность и его место заняло семейство фибоначчиевых алгоритмов, которые могут быть рекомендованы для использования в алгоритмах, критичных к качеству случайных чисел.

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

Один из широко распространённых фибоначчиевых датчиков основан на следующей итеративной формуле (3):

X(k) = \left\{ \begin{matrix} X(k-a)-X(k-b), & \mbox{if } X(k-a)\geq X(k-b); \\ X(k-a)-X(k-b)+1, & \mbox{if } X(k-a) < X(k-b);\end{matrix}\right. (3)

где X(k) -- вещественные числа из диапазона [0, 1),

a, b -- целые положительные числа, называемые лагами.

Для работы фибоначчиеву датчику требуется знать max(a, b) предыдущих сгенерированных случайных чисел. При программной реализации для хранения сгенерированных случайных чисел используется конечная циклическая очередь на базе массива. Для старта фибоначчиевому датчику требуется max(a, b) случайных чисел, которые могут быть сгенерированы простым конгруэнтным датчиком.

Рекомендуются следующие значения: a = 55, b = 24; a = 17, b = 5;

a = 97, b = 33.

Алгоритм Блюма, Блюма и Шуба (Blum Blum Shub, BBS)

Предложен в 1986 году Ленор и Мануэлем Блюм и Майклом Шубом.

BBS заключается в применении формулы (4):

xn+1 = (xn)2 mod M (4)

где M=p*q является произведением двух больших простых p и q.

На каждом шаге алгоритма выходные данные получаются из xn путём взятия либо бита чётности, либо одного или больше наименее значимых бит xn.

Два простых числа, p и q, должны быть оба сравнимы с 3 по модулю 4 и НОД(?(p-1), ?(q-1)) должен быть мал.

Интересной особенностью этого алгоритма является то, что для получения xn необязательно вычислять все n - 1 предыдущих чисел, если известно начальное состояние генератора x0 и числа p и q. n-ное значение может быть вычислено "напрямую" используя формулу (5):

xn = x0 (2 ^ n) mod ((p-1)(q-1)) mod M (5)

Вихрь Мерсенна (Mersenne twister)

Разработан в 1997 японскими учёными Макото Мацумото и Такудзи Нисимура. Он обеспечивает быструю генерацию высококачественных псевдослучайных чисел, так как изначально был разработан с учётом ошибок, найденных в других алгоритмах.

Существуют по меньшей мере два общих варианта алгоритма, различающихся только размером использующегося простого числа Мерсенна. Новейший и наиболее распространённый называется Mersenne Twister MT 19937.

MT 19937 имеет следующие ожидаемые свойства:

1. Он был разработан с целью иметь огромный период, размером 219937 ? 1.

2. Он имеет высокий порядок пространственного эквираспространения.

3. Он значительно быстрее, чем все остальные генераторы, за исключением статистически-дефектных генераторов.

4. Он статистически случаен во всех выходных битах.

Генерирование случайных чисел с помощью класса Random в С#.

Чтобы сгенерировать последовательность псевдослучайных чисел, используется класс Random. Начало такой последовательности определяется некоторым начальным числом, которое автоматически предоставляется классом Random или задается явным образом.

В классе Random определены следующие два конструктора:

public Random()

public Random(int seed)

С помощью первой версии конструктора создается объект класса Random, который для вычисления начального числа последовательности случайных чисел использует системное время. При использовании второй версии конструктора начальное число задается в параметре seed.

Класс Random (сокращено)

//Конструкторы

Random ()

Random(int а);

//Методы экземпляра

int Next () ;

int Next(int макс_значение) ;

int Next(int мин_значение, int макс_значение) ;

double NextDouble() ;

Конструкторы возвращают случайные объекты, которые образуют последовательность псевдослучайных чисел. Методы Next возвращают следующее число в последовательности, возможно, между заданными значениями. NextDouble возвращает число в диапазоне от 0.0 до 1.0.

Сравнив методы получения псевдослучайных чисел для реализации в программе, я выбрал, помимо метода, основанного на использовании системного класса Random, линейный конгруэнтный метод и алгоритм Блюма, Блюма и Шуба, исходя из преимуществ этих методов перед другими:

ѕ более простое математическое представление, а следовательно и программная реализация;

ѕ возможность получения любого числа, располагая только значением стартового.

1. Возможность создания Windows приложений.

2. Создание максимально возможного удобства в работе

3. Поддержка других языков программирования и платформ

4. Большое количество библиотек

5. Простота изучения языка на основе имеющихся знаний.

Первый критерий резко отсекает большое количество различных языков, т. к. программа должна иметь удобный и современный интерфейс пользователя. Поддержка многих языков программирования и платформ позволит пользователю усовершенствовать данный проект на различных языках. Большое количество библиотек дает возможность значительно уменьшить исходный код программы.

Страницы: 1, 2, 3, 4, 5