Как работает программа рандомайзер

Разбор алгоритмов генерации псевдослучайных чисел

Я работаю программистом в игровой студии IT Territory, а с недавних пор перешел на направление экспериментальных проектов, где мы проверяем на прототипах различные геймплейные гипотезы. И работая над одним из прототипов мы столкнулись с задачей генерации случайных чисел. Я хотел бы поделиться с вами полученным опытом: расскажу о псевдогенераторах случайных чисел, об альтернативе в виде хеш-функции, покажу, как её можно оптимизировать, и опишу комбинированные подходы, которые мы применяли в проекте.

Случайными числами пользовались с самого зарождения математики. Сегодня их применяют во всевозможных научных изысканиях, при проверке математических теорем, в статистике и т.д. Также случайные числа широко используются в игровой индустрии для генерирования 3D-моделей, текстур и целых миров. Их применяют для создания вариативности поведения в играх и приложениях.

Как работает Random в играх

Есть разные способы получения случайных чисел. Самый простой и понятный — это словари: мы предварительно собираем и сохраняем набор чисел и по мере надобности берём их по очереди.

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

Сегодня мы с вами поговорим о генераторах псевдослучайных чисел — вычисляемых функциях. К ним предъявляются следующие требования:

• Длинный период. Любой генератор рано или поздно начинает повторяться, и чем позже это случится, тем лучше, тем непредсказуемее будет результат.
• Портируемость алгоритма на различные системы.
• Скорость получения последовательности. Чем быстрее, тем лучше.
• Повторяемость результата. Это очень важный показатель. От него зависят все компьютерные игры, которые используют генераторы миров и различные системы с аналогичной функциональностью. Воспроизводимость даёт нам общий контент для всех, то есть мы можем генерировать на отдельных клиентах одинаковое содержимое. Также мы можем генерировать контент на лету в зависимости от входных данных, например, от местоположения игрока в мире. Ещё повторяемость случайных чисел используется для сохранения конкретного контента в виде зерна. То есть мы можем держать у себя только какое-то число или массив чисел, на основе которых будут генерироваться нужные нам параметры для заранее отобранного контента.

Зерно

Зерно — это основа генерирования. Оно представляет собой число или вектор чисел, который мы отправляем при инициализации генератора.

var random = new Random(0); var rn0 = random.Next(); var rn1 = random.Next(); var rn2 = random.Next();

На иллюстрации просто инициализирован стандартный генератор случайных чисел из стандартной библиотеки C#. При инициализации отправляем в него некоторое число — seed (зерно), — в данном случае это 0. Затем по очереди берём по одному числу методом Next . Но тут мы столкнёмся с первой проблемой: генерирование всегда будет последовательным. Мы не можем получить сразу i-тый элемент последовательности. Для получения второго элемента последовательности необходимо сначала задать зерно, потом вычислить нулевой элемент, за ним первый и только потом уже второй, третий и i-й.

Решить эту проблему можно будет с помощью разделения одного генератора на несколько отдельных.

var X = 0; var Y = 1; var Z = 2; var rs0 = new Random(X); var rs1 = new Random(Y); var rs2 = new Random(Z);

То есть берём несколько генераторов и задаём им разные зёрна. Но тут мы можем столкнуться со второй проблемой: нельзя гарантировать случайность i-тых элементов разных последовательностей с разными зёрнами.

На иллюстрации изображён результат генерирования нулевого элемента последовательности с помощью стандартной библиотекой C#. Мы постепенно меняли зерно от 0 до N.

Качество генератора

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

private static uint GetBytePart(uint i, int byteIndex) < return ((i >> (8 * byteIndex)) % 256 + 256) % 256; > public static Color GetColor(uint i) < float r = GetBytePart(i, 0) / 255f; float g = GetBytePart(i, 1) / 255f; float b = GetBytePart(i, 2) / 255f; return new Color(r, g, b); >

Второй тип изображений — это пространственная интерпретация сгенерированной последовательности. Мы берём первые два бита числа (Х и Y), затем считаем количество попаданий в заданные точки и при визуализации вычитаем из 1 отношение количества попаданий в конкретный пиксель к максимальному количеству попаданий в какой-то другой пиксель. Черные пиксели — это точка, куда мы попадаем чаще всего, а белые — куда мы либо почти, либо совсем не попали.

var max = 0; for (var i = 0; i

Сравнение генераторов

Стандартные средства C#

Ниже я сравнил стандартный генератор из библиотеки С# и линейную последовательность. Первый столбец слева — это случайная последовательность от 0 до N в рамках одного зерна. В центре вверху показаны нулевые элементы случайных последовательностей при разных зёрнах от 0 до N. Вторая линейная последовательность — это числа от 0 до N, которые я визуализировал нашим алгоритмом.

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

Линейный конгруэнтный генератор (LCG)

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

const long randMax = 4294967296; state = 214013 * state + 2531011; state ^= state >> 15; return (uint) (state % randMax);

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

const long randMax = 2147483648; state = 65539 * state + 0; return (uint) (state % randMax);

Этот генератор страшен тем, что умножает одно большое число на другое и берёт остаток от деления на 2 31 . В результате формируется вот такая красивая картинка.

XorShift

Давайте теперь посмотрим на более свежую разработку — XorShift. Этот алгоритм просто выполняет операцию Xor и сдвигает байт в несколько раз. У него тоже будет прослеживаться паттерн для i-тых элементов последовательностей.

state ^= state > 17; state ^= state

Вихрь Мерсенна

Неужели не существует генераторов без паттерна? Такой генератор есть — это вихрь Мерсенна. У этого алгоритма очень большой период, из-за чего появление паттерна на некотором количестве чисел физически невозможно. Однако и сложность этого алгоритма достаточно велика, в двух словах его не объяснить.

ulong x; if (mti >= NN) < // generate NN words at one time for (var i = 0; i < NN — MM; i++) < x = (mt[i] LM); mt[i] = mt[i + MM] ^ (x >> 1) ^ MAG01[(int) (x > for (var i = NN — MM; i < NN — 1; i++) < x = (mt[i] LM); mt[i] = mt[i + (MM — NN)] ^ (x >> 1) ^ MAG01[(int) (x > x = (mt[NN — 1] LM); mt[NN — 1] = mt[MM — 1] ^ (x >> 1) ^ MAG01[(int) (x mti = 0; > x = mt[mti++]; x ^= (x >> 29) x ^= (x > 43; return x;

Unity — Random

Из других разработок стоит упомянуть генератор от компании Unity — Random, который используется в наборе стандартных библиотек для работы с Unity. При использовании первых элементов последовательности для разных зёрен у него будет прослеживаться паттерн, но при увеличении индекса паттерн исчезает и получается действительно случайная последовательность.

Перемешанный конгруэнтный генератор (PCG)

Противоположностью юнитёвского Random’a является перемешанный конгруэнтный генератор. Его особенность в том, что для первых элементов с различными зёрнами отсутствует ярко выраженный паттерн. Но при увеличении индекса он всё же возникает.

Длительность последовательного генерирования

Это важная характеристика генераторов. В таблице приведена длительность для алгоритмов в миллисекундах. Замеры проводились на моём MacBook Pro 2019 года.

0..n

0 seed 0..n

100 seed 0..n

Вихрь Мерсенна работает дольше всего, но даёт качественный результат. Стандартный генератор Random из библиотеки C# подходит для задач, в которых случайность вторична и не имеет какой-то значимой роли, то есть его можно использовать в рамках одного зерна.

LCG (линейный конгруэнтный генератор) — это уже более серьёзный алгоритм, но требуется время на подбор нужных коэффициентов, чтобы получить адекватный паттерн. XorShift — самый быстрый алгоритм из всех рассмотренных. Его можно использовать там, где нужно быстро получить случайное значение, но помните про ярко выраженный паттерн с повторяющимся значением. Unity Random и PCG (перемешанный конгруэнтный генератор) сопоставимы по длительности работы, поэтому в разных ситуациях мы можем менять их местами: для длительных последовательностей использовать Unity, а для коротких — PCG.

Альтернатива генераторам — хеш-функции

Хеш-функции (функции свёртки) по определённому алгоритму преобразуют массив входных данных произвольной длины в строку заданной длины. Они позволяют быстрее искать данные, это свойство используется в хеш-таблицах. Также для хеш-функций характерна равномерность распределения, так называемый лавинный эффект. Это означает, что изменение малого количества битов во входном тексте приведёт к лавинообразному и сильному изменению значений выходного массива битов. То есть все выходные биты зависят от каждого входного бита.

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

Вот пример использования хеш-функции: можно либо создать конкретный класс, отправить туда зерно и постепенно запрашивать только конкретные состояния, либо написать статичную функцию, и отправить туда сразу и зерно, и конкретное состояние. Слева показан алгоритм работы MD5 из стандартной библиотеки C#.

var hash = new Hash(0); var rn0 = hash.GetHash(0); var rn1 = hash.GetHash(1); var rn2 = hash.GetHash(12); var rn3 = hash.GetHash(13, 5); var rn4 = Hash.GetHash(0, 0); var rn5 = Hash.GetHash(0, 1); var rn6 = Hash.GetHash(0, 12); var rn7 = Hash.GetHash(0, 13, 5);

Сделать генератор на основе хеш-функции можно так. Непосредственно при инициализации генератора задаём зерно, увеличиваем счётчик на 1 при запросе следующего значения и выводим результат хеша по зерну и счётчику.

class HashRandom < private int seed; private int counter; public HashRandom(int seed) < this.seed = seed; >public uint Next() < return Hash.GetHash(seed, counter++); >>

Одни из самых популярных хеш-функций — это MurMur3 и WangHash.

MurMur3 не создаёт паттернов при использованиии i-тых элементов разных последовательностей при разных зёрнах. У WangHash статистические показатели образуют заметный паттерн. Но любую функцию можно прогнать через себя два раза и получить улучшенные показатели, как это показано в правом крайнем столбце WangDoubleHash.

Также сегодня активно развивается и набирает популярность алгоритм xxHash.

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

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

0..n

0 seed 0..n

Источник: habr.com

Генератор случайных чисел для розыгрыша в Инстаграм: как он работает и как выиграть в таком конкурсе

Получи нашу книгу «Контент-маркетинг в социальных сетях: Как засесть в голову подписчиков и влюбить их в свой бренд».

Подпишись на рассылку и получи книгу в подарок!

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

Больше видео на нашем канале — изучайте интернет-маркетинг с SEMANTICA

Содержание скрыть

• Для чего он нужен

• Принцип

• Giveaway
• Подарок за действие
• Выбор лучшего

• Random.org
• RandStuff
• Рандомус
• Online-generators
• Giveaway-generator
• Giveawation

Для чего он нужен

Организуя акцию с раздачей подарков, необходимо предоставить юзерам действительно честный процесс выбора. Делается это по-разному в зависимости от потребностей. Кому-то хватает простого объявления результата, другие же предпочитают более «вещественные» доказательства проведения жеребьевки. В таком случае просторы интернета предлагают множественные вариации, среди которых пользователь может определить наиболее привлекательный и подходящий генератор случайных чисел и людей в Инстаграм для онлайн-конкурса.

Что дает такое средство:

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

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

Принцип

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

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

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

Виды соревнований

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

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

Giveaway

Подобная схема давно обжилась на просторах инстаграм-аккаунтов. Заключается она в объединении нескольких спонсоров (людей, гарантирующих приз) в одну программу с целью привлечения подписчиков в блог, а также усиления интереса к публикациям. Чем привлекательны конкурсы:

• несколько спонсоров гарантируют более ценные подарки;
• известные инстаграмщики вместе выступают гарантом честности;
• задания для выигрыша не будут усложняться.

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

Подарок за действие

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

• сделать репост сообщения;
• пригласить друзей;
• поставить определенные отметки.

Нередко условия усложняются или комбинируются для придания заинтересованности. Гораздо привлекательней выступит «игра» с разнообразными по сути задачами, нежели простые действия. В таком случае и приз может быть ощутимым.

Выбор лучшего

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

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

Как выбрать победителя в Инстаграме

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

Достаточно представлять себе некоторые азы реализации подобных мероприятий:

• формирование игры и особых правил;
• уникальность – необычные действия, их обобщенность (хештеги);
• поддержка участников и напоминание о проводимых розыгрышах;
• ведение статистики.

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

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

При этом все участники получат значимое подтверждение честности.

Что использовать

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

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

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

Далее подтверждаются выбранные критерии, и запускается алгоритм, непосредственно отвечающий за реализацию.

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

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

Подборка генераторов

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

Вопрос в том, как провести конкурс в Инстаграм генератором случайных победителей, решается определением следующих критериев для инструмента:

• популярность среди блогеров (немаловажный фактор);
• универсальность предлагаемых платформ (вариации, условия, возможности);
• необходимость вложения средств (напрямую влияет на популярность);
• функционал и гарантии.

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

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

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

Random.org

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

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

• рандомный подбор целых чисел в заданном диапазоне;
• генерация последовательности всех цифр в рамках;
• определение строки символов конкретного размера.

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

RandStuff