XVI Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке. Летняя площадка 2022
Рандомайзер
Автор работы награжден дипломом победителя III степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение
Главная особенность истинной рандомности — то, что она приводит к непредсказуемым результатам. У подхода несколько плюсов, но есть и минусы — последовательно может выпасть как несколько положительных результатов, так и несколько отрицательных. Игроку это может показаться несправедливым.
«Когда я задался целью получить действительно случайное число, то не нашел для этого ничего лучшего, чем обычная игральная кость» — писал в 1890 году Фрэнсис Гальтон в журнале Nature. «После того, как кости встряхивают и бросают в корзинку, они ударяются друг о друга и о стенки корзинки столь непредсказуемым образом, что даже после легкого броска становится совершенно невозможным предопределить его результат».
Актуальность темы:
Как мы можем сгенерировать равномерную последовательность случайных чисел? Случайность, столь прекрасная в своём многообразии, часто встречается в живой природе, но её не всегда легко было извлечь искусственным путём. Самые древние из игральных костей были найдены на Среднем Востоке, и они датируются примерно 24 столетием до нашей эры. Другим примером может быть Китай, где ещё в 11 столетии до нашей эры применялось разбивание ударом черепашьего панциря, с дальнейшей интерпретацией размера полученных случайных частей. Столетиями позже люди разрубали несколько раз стебли растений и сравнивали размеры полученных частей.
Но к середине 40-ых годов ХХ столетия человечеству понадобилось значительно больше случайных чисел, чем можно было получить от бросков костей или разрезания стеблей.
Цель исследования: Создание и применение рандомайзера для различных игр на базе конструктора Lego Mindstorms EV3.
Задачи исследования:
Познакомиться с историей появления генератора случайных чисел;
Изучить понятие и принцип жребия;
Проанализировать значение случайности в жизни человека;
Сконструировать и запрограммировать модель рандомайзера для использования в различных играх.
В качестве источников информации мы использовали информационные сайты. При оформлении проекта мы брали идеи из большой книги «LEGO Идеи: новая жизнь старых деталей» [1], при конструировании движимых частей проекта нам помогли книги и методические пособия о простых и сложных механических передачах, подробно о зубчатых передачах [2], при создании программ мы руководствовались учебными пособиями по образовательной робототехнике [3].
Глава 1. Случайность или предопределённость.
1.1 История появления генератора случайных чисел
Создатель теории вероятностей, французский математик Паскаль, в 17 веке впервые упоминает в одной из своих работ термин генератор случайных чисел. Под таким генератором он подразумевал подбрасывание костей или подбрасывание монеты. Эти свои простые генераторы он использовал для сбора статистических данных для проверки своей теории вероятностей.
Сейчас в качестве генератора случайных чисел используется радиоактивный распад какого-нибудь радиоактивного вещества. Какие-нибудь измерения такого распада, типа шелчки счетчика Гейгера и т. п. В калькуляторах и компьютерах используются в качестве генераторов случайных чисел обычно какие-нибудь строго детерминированные итерационные процессы, спектр которых представляет собой идеальный белый шум. Но так как компьютеры и калькуляторы работают с ограниченным числом цифр после запятой, то через какое-то (хотя и очень большое) время компьютерный генератор случайных чисел зацикливается и начинает повторять те числа, которые были в самом начале и в том же самом порядке. Таким образом, компьютерные генераторы случайных чисел являются не настоящими генераторами случайных чисел, а их спектр имеет одну выделенную частоту повторения всей последовательности. Но на временах много меньших этого периода повторения спектр с большой долей точности является белым шумом.
Эти компьютерные генераторы случайных чисел были придуманы еще в конце 19 и начале 20 века в работах многих математиков, в частности в работах Пуанкаре. Как только появились компьютеры в 40-х годах 20 века, так эти генераторы тут же были реализованы в виде компьютерных программ. В принципе и природные генераторы, основанные на радиоактивном распаде, тоже повторяют предыдущие числа, если очень долго подождать, так как измерительные приборы тоже работают с ограниченной точностью. Но природный генератор хорош тем, что, повторив один раз одно из чисел, он дальше не повторяет ту последовательность, которая шла за этим числом ранее. Поэтому спектр такого процесса уже точно является белым шумом на любых временах.
Но к середине 40-ых годов ХХ столетия человечеству понадобилось значительно больше случайных чисел, чем можно было получить от бросков костей или разрезания стеблей. Американский аналитический центр RAND создал машину, которая была способна генерировать случайные числа с помощью использования случайного генератора импульсов (что-то вроде электронной рулетки). Они запустили её и через какое-то время получили достаточное количество случайных чисел, которые опубликовали в виде книги "Один миллион случайных чисел и сто тысяч нормальных отклонений".
То, что сегодня может показаться абсурдным арт-проектом, в то время было серьёзным прорывом. Впервые учёным стала доступна действительно большая последовательность действительно случайных чисел. В 1951 году случайность наконец была формализована и воплощена в реальном компьютере Ferranti Mark 1, который поставлялся со встроенным генератором случайных данных на основе дробовых шумов и инструкцией, позволяющей получить 20 случайных бит. Этот функционал был разработан Аланом Тьюрингом. Его коллега Кристофер Стрэчи применил его для создания «генератора любовных писем». Вот пример текста, который был сгенерирован данной программой:
JEWEL LOVE
MY LIKING HUNGERS FOR YOUR ADORABLE INFATUATION.
YOU ARE MY EROTIC ARDOUR.: MY FOND RAPTURE. MY THIRST
SIGHS FOR YOUR INFATUATION. MY HEART SEDUCTIVELY WISHES YOUR
BREATHLESS LONGING.
YOURS CURIOUSLY
M. U. C.
Но генератор случайных чисел Тьюринга не делал программистов тех лет счастливыми, поскольку привносил в и так новые и нестабильные компьютерные системы фактор ещё большей нестабильности. Желая добиться стабильной работы некоторой программы — без отладчиков и со случайными данными — никогда нельзя было достичь повторяемости результатов. Тогда возникла следующая мысль: «А что, если генератор случайных чисел может быть представлен в виде некоторой детерминированной функции?» Тогда получилось бы, что, с одной стороны, генерируемые числа имели бы признаки случайных, но с другой стороны, при одинаковой инициализации генератора данные последовательности были бы каждый раз одни и те же. Так появились генераторы псевдослучайных чисел (ГПСЧ).
Большинство популярных процессоров в 90-ых годах не имели специальной инструкции для генерации случайных чисел, так что выбор хорошего начального значения для генератора псевдослучайных чисел имел очень важное значение. Это вылилось в проблемы с безопасностью, когда Phillip Hallam-Baker обнаружил, что в браузере Netscape (доминирующем в то время) реализация SSL использовала для инициализации ГПСЧ комбинацию текущего времени и ID своего процесса. Он показал, как хакер может легко подобрать это значение и расшифровать SSL-трафик. Угадывание начального значения алгоритма генерации псевдослучайных чисел — до сих пор популярная атака, хотя с годами она стала слегка сложнее. Вот пример удачной атаки, опубликованный на Hacker News в 2009 году.
В 1997 году программисты были ограничены в способах получения по-настоящему случайных чисел, так что команда SGI создала LavaRand, который состоял из вебкамеры, направленной на пару лава-ламп, стоявших рядом на столе. Картинка с этой камеры была отличным источником энтропии — Настоящим Генератором Случайных Чисел, таким же, как у Тьюринга. Но в этот раз получалось генерировать 165 Кб случайных чисел в секунду. Изобретение было тут же запатентовано.
В 1999 году Intel добавил аппаратный генератор случайных чисел в чипсет i810. Это было хорошо, поскольку данная реализация давала по-настоящему случайные числа (на основе температурных шумов), но работало не настолько же быстро, как программные ГПСЧ, так что большинство криптоприложений всё ещё используют ГПСЧ, которые теперь, по крайней мере, можно инициализировать начальным значением от аппаратного генератора случайных чисел.
В 2012 году INTEL добавил в свои чипы инструкции RDRAND и RDSEED, позволяющие получить настоящие случайные числа на основе тех же колебаний температуры, но теперь уже на скорости до 500 Мб/с, что должно бы сделать применение программных ГПСЧ ненужным. Но в обществе бродят слухи и сомнения в честности этих инструкций. Нет ли в них специально сделанной закладки для NSA? Никто не может сказать этого точно. Вернее, кто-то, наверное, может, но он точно не напишет об этом в Твиттере.
Сегодня люди всё ещё ведут дискуссии о том, какой именно генератор случайных чисел стоит использовать в той или иной системе, ядре ОС, языке программирования, криптографической библиотеке и т.д. Есть много вариантов алгоритмов, заточенных на скорость, экономию памяти, безопасность. И каждый из них постоянно подвергается атакам хакеров и специалистов по безопасности. Но для ежедневных задач, не связанных с безопасностью, вы вполне можете положиться на данные из /dev/random или функции rand(), доступных на большинстве платформ. Это даст вам достаточно большую и случайную последовательность данных, которая бы сделала в своё время счастливым Алана Тьюринга [4].
1.2 Понятие и принцип жребия
Жребий — это условный знак, какой-нибудь предмет, например, дощечка, картонка или одного размера палочки. Правила заключаются в том, чтобы участники игры не спорили, кому водить или кому начинать игру, какой группе где стоять, бросают жребий.
Если нужно выбрать вожака в игре, берут столько одинаковых палочек, сколько участников игры. На одной ставят заметку. Все палочки кладут в коробку или ящичек, перемешивают, и затем играющие по очереди берут по одной. Кто вытянет жребий с условной заметкой, тому и быть ведущим, начинать игру.
Бывают и другие жеребьевки. Их называют угады. Один из играющих берет жребий и за спиной прячет его в руке. В какой руке жребий, никто не должен знать. Затем жеребьевщик, держа руки за спиной, говорит: «Кто вынет жребий, тому водить!» К нему подходят двое из играющих, жеребьевщик спрашивает: «Кто в правой, кто в левой руке берет?» Один берет в правой, другой в левой руке. Жеребьевщик разжимает пальцы и показывает, в какой руке жребий. Угадавший выигрывает спор.
1.3 Значение случайности в жизни человека
Случа́йность — это результат вероятного и непредсказуемого событий, проявление неотъемлемого дополнения к законам необходимости.
Представления о случайности зародились при самых первых попытках осознания человеком своего бытия и стали неизбежными при объяснении поведения человека, его судьбы. С понятием случайности связан вопрос о свободе воли человека, издавна занимавший различных мыслителей. Отрицание случайности неизбежно приводило к фатализму, представлению о предопределенности всего происходящего в мире. Везет, не везет: насколько случайности определяют социальный успех. Людей всегда интересовала роль случайности в их жизни, в успехах и неудачах. Случайности часто оказываются закономерностями, которые человек не может предсказать.
Существуют ли в нашей Вселенной случайные события или все предопределено заранее? Все совпадения в нашей жизни — это случайность или закономерность? Предлагаю попробовать разобраться с этими вопросами. Сразу оговорюсь, что статья никак не претендует на звание научной и является всего лишь попыткой осмысления реальности с использованием математического аппарата. Кому интересно, читаем дальше.
Если рассматривать Вселенную как нелинейную динамическую систему, состояние которой в момент времени t может быть описано множеством происходящих событий, и предположить наличие причинно-следственных связей между событиями момента времени t и событиями момента времени t-1 (другими словами наличие зависимости между текущим и предыдущим состояниями системы), то мы вынуждены будем прийти к выводу о том, что какое-то событие (или множество одновременных событий, что по сути можно рассматривать как единое событие, определяющее начальное состояние системы) послужило началом и причиной бытия. Как следствие оно породило множество других событий, каждое из которых множество следующих и так далее до текущего момента.
Таким образом Вселенную можно представить в виде системы нелинейных дифференциальных уравнений. Чем большее число параметров будет учтено, тем большее число уравнений она будет содержать и тем ближе такая математическая модель будет к реальной. То есть при увеличении числа параметров и уравнений системы до бесконечности получим полную математическую модель Вселенной. Даже простые нелинейные динамические системы с тремя параметрами демонстрируют очень сложное поведение, которое практически не отличимо от случайного. Можно представить, как будет вести себя система с числом параметров, стремящимся к бесконечности.
Теперь можно попробовать разобраться с вопросом существования случайных процессов и событий в нашей Вселенной. Процесс есть ни что иное как последовательность событий, поэтому случайным процессом будем называть последовательность случайных событий (либо случайную последовательность событий, суть от этого не меняется). Но, как видно из вышеприведенного определения, случайность возможна только при наличии независимых процессов или событий, а это противоречит нашей модели, в которой все события и процессы являются взаимозависимыми. Взаимозависимость обусловлена начальным состоянием системы, поскольку в нелинейных динамических системах даже малое изменение начального состояния приводит к непредсказуемому поведению системы в целом и каждого из параметров в отдельности. Стало быть, нет возможности изменить только один из параметров, не затронув при этом остальные, следовательно, все последующие состояния системы зависят от предыдущих. Таким образом приходим к выводу о невозможности существования независимых событий в нашей модели. А это значит, что в ней не существует случайности. А что же существует? Система состоит из огромного количества нелинейных элементов, каждый из которых обладает свободой выбора и с определенной вероятностью оказывает положительное либо отрицательное влияние на систему (другими словами способствует росту либо энтропии, либо негэнтропии). Таким образом мы можем говорить лишь о вероятности того или иного события, исходя из цепочки предшествующих причинно-следственных связей. И здравствуй квантовая физика, и термодинамика [5].
Теория вероятности очень часто доказуема лишь в теории, но на практике в настоящей жизни нам может не хватить и нескольких сотен лет для того, чтобы все эксперименты наконец, привели к желаемому результату. Поэтому создав свой рандомайзер, мы понимали, что вероятность будет очень сложно рассчитать, и решили использовать его именно как устройство в целях помочь определить наши роли в команде, игре, или же позволить механизмам вместо нас выдать результат игральной кости. Этот процесс оказался очень весёлым и увлекательным как для взрослых, так и для детей, ведь вся суть игры – это повеселиться и отлично провести время вместе, поверив в случайность выигрыша или обычное везение!
Глава 2. Умное устройство для игр.
2.1 Модель рандомайзера для использования в различных играх
Наша модель рандомайзера включает в себя коробку для перемешивания игральных костей (Рисунок 2.1.1 Приложения), бумажек или других элементов для игры, конвейер для подачи прямо в руки участнику (Рисунок 2.1.2 Приложения), а также модуль EV3 с 2 датчиками касания для управления всем процессом рандома (Рисунок 2.1.3 Приложения). В начале на модуле мы запускаем уже приготовленную нами программу, нажимаем правый датчик касания, и элементы перемешиваются, выдавая результат на конвейер (Рисунок 2.1.4 Приложения). После этого с помощью левого датчика касания мы запускаем движение конвейера, чтобы выдать результат участнику в руки. Таким образом, процесс можно повторять столько раз, сколько это необходимо для игроков.
В модели установлено:
1 модуль EV3 для управления процессом рандомайзера;
1 большой мотор для смешивания элементов в коробке (Рисунок 2.1.5 Приложения);
1 средний мотор для движения конвейера;
2 датчика касания для запуска смешивания и конвейера поочерёдно.
Программа работает следующим образом (Рисунок 2.1.6 Приложения):
При запуске программа ожидает нажатия одного из датчиков касания;
При нажатии датчика касания 2, на дисплее модуля отображается знак вопроса, звук, и срабатывает большой мотор D внутри коробки для смешивания элементов, отпустив датчик, мы останавливаем мотор;
При нажатии датчика касания 1, на дисплее модуля отображается знак вопроса, звук, и срабатывает средний мотор A, и конвейер двигается, отпустив датчик, мы останавливаем мотор (Рисунок 2.1.7 Приложения).
В данной модели присутствуют следующие механизмы: зубчатая передача, система рычагов, червячная и осевая передачи. Видео нашего проекта: https://drive.google.com/file/d/1GPuL19S5Yb8BO24KLD0Haqj8p9pA_p23/view?usp=drivesdk
Заключение
Познакомившись с историей появления генератора случайных чисел, мы выяснили, что компьютерные генераторы случайных чисел являются не настоящими генераторами случайных чисел, а их спектр имеет одну выделенную частоту повторения всей последовательности.
Изучив понятие и принцип жребия, мы подчеркнули тот факт, что правила жребия заключаются в том, чтобы участники игры не спорили, кому водить или кому начинать игру, какой группе где стоять, они просто бросают жребий. Это позволяет участникам избежать недопонимания с самого начала игры и довериться воле случая. Таким образом, случайность выбора того или иного участника поддерживает интерес к игре.
В результате, мы пришли к выводу, что случайность в жизни человека имеет большее значение, чем предопределённость. Пусть нам и нравятся моменты, когда всё складывается словно по намеченному плану, случайность же придаёт нашей жизни больше красок, дарит смысл и даёт возможность поверить, что даже если человеку не везло всю жизнь в каких-либо сферах, однажды ему всё равно повезёт, а в игре это особенно приятно. Вот, почему даже взрослым всегда будут нравится игры.
В итоге, мы сконструировали и запрограммировали модель рандомайзера для использования в различных играх на базе конструктора Lego Mindstorms EV3, и считаем, что наш проект может найти отличное применение в играх для детей и взрослых, а также в экспериментах расчёта теории вероятности на уроках математики!
Список используемой литературы:
LEGO Книга идей: новая жизнь старых деталей: 181 удивительный механизм и устройство; [пер. с англ. А. Аревшатян]. – Москва, Издательство «Эсмо», 2015. - 200 с.;
Богданова С.М., Попова Е.Е. Благодаря механическим передачам Lego- конструкции оживают / С.М. Богданова, Е.Е. Попова// «Новые информационные технологии в нефтегазовой отрасли и образовании»: материалы VII Международной научно-технической конф. 2017 С. 160-163. Режим доступа- https://elibrary.ru/item.asp?id=30700400
Курс «Машины и механизмы», курс «Основы робототехники», Школа интеллектуального развития «Мистер Брейн», - Режим доступа - https://vk.com/mrbrain_tmn;
Интернет источники:
https://habr.com/ru/company/infopulse/blog/329778/
https://habr.com/ru/post/241009/
Приложение
Рисунок 2.1.1 – Коробка для смешивания элементов
Рисунок 2.1.2 – Сборка конвейера
Рисунок 2.1.3 – Датчики касания
Рисунок 2.1.4 – Готовый конвейер
Рисунок 2.1.5 – Большой мотор внутри коробки
Рисунок 2.1.6 – Работа над коробкой
Рисунок 2.1.7 – Наша программа