Как получить случайную последовательность чисел? Спойлер:«Никак»

МЕНЮ


Искусственный интеллект
Поиск
Регистрация на сайте
Помощь проекту

ТЕМЫ


Новости ИИРазработка ИИВнедрение ИИРабота разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика

Авторизация



RSS


RSS новости


Год назад я написал свою первую игру на контроллере Arduino. Игрок искал кубик и, проходя лабиринт, должен был успеть съесть его. Еда появлялась в «абсолютно случайном» месте, а время с каждым раундом все уменьшалось. Из-за своего распиздяйства того, что времени доделать игру было мало, она весила очень много, геймплей был никаким, а рандома не было. Последнее я заметил только тогда, когда показывал свою игру людям. Игру доделать хочется, поэтому нужно решить проблему с рандомом, начну с него.
Фотоотчёт с arduino day у нас в паблике

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

СТОП!!! Скорее всего, вы не особо понимаете, что происходит, или думаете, что понимаете. Давайте я начну из далека и объясню некоторые основы рандома.

Как компьютер генерирует случайные числа

Это лучший алгоритм, который я смог найти

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

R(x) = x + 1

Теперь наша последовательность будет такой:
0,1,2,3,4,5,6,7,8…
Не очено похоже на случайную последовательность. Пусть теперь R добавляет константу вместо 1.

1R(x) = x + c

Если с равняется, например, 7, то мы получим ряд 1, 8, 15, 22, … Всё ещё не то. Очевидно, что мы упускаем то, что числа не должны только увеличиваться, они должны быть разбросаны по какому-то диапазону. Нам нужно, чтобы наша последовательность возвращалась в начало — круг из чисел!

Посмотрим на циферблат часов: наш ряд начинается с 1 и идёт по кругу до 12. Но поскольку мы работаем с компьютером, пусть вместо 12 будет 0.

Теперь начиная с 1 снова будем прибавлять 7. Прогресс! Мы видим, что после 12 наш ряд начинает повторяться, независимо от того, с какого числа начать.

Здесь мы получаем очень важно свойство: если наш цикл состоит из n элементов, то максимальное число элементов, которые мы можем получить перед тем, как они начнут повторяться это n.

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

R(x) = (x + c) % m

На этом этапе вы можете заметить, что некоторые числа не подходят для c. Если c = 4, и мы начали с 1, наша последовательность была бы 1, 5, 9, 1, 5, 9, 1, 5, 9, … что нам конечно же не подходит, потому что эта последовательность абсолютно не случайная. Становится понятно, что числа, которые мы выбираем для длины цикла и длины прыжка должны быть связаны особым образом.

Если вы попробуете несколько разных значений, то сможете увидеть одно свойство: m и с должны быть взаимно простыми.

До сих пор мы делали «прыжки» за счёт добавления, но что если использовать умножение? Умножим х на константу a.

R(x) = (ax + c) % m

Свойства, которым должно подчиняться а, чтобы образовался полный цикл, немного более специфичны. Чтобы создать верный цикл:

  1. (а — 1) должно делиться на все простые множители m
  2. (а — 1) должно делиться на 4, если m делится на 4

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

Еще один способ — это получать семя из нового источника каждый раз при запуске программы, как в системных часах. Это пригодится в случае, когда нужно общее рандомное число, как в программе с расположением кубика.

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


Источник: m.vk.com

Комментарии: