В очередной раз столкнулся с тем, что разработчик игры (в качестве демо-версии программных функций) использовал генератор случайных чисел "в лоб", что повлекло за собой повторы ходов (игра была "морской бой", и клетка, по которой стрелял компьютер определялось как Math.floor(Math.random()*100), что подразумевает бесконечное повторение ходов). Поэтому хочу предложить простой и эффективный способ создать последовательность случайных чисел без повторения. Этот способ основан на перестановках в ряду натуральных чисел с использованием Math.ramdom() для выбора второго числа. Ну и поскольку много по этому вопросу не скажешь, в продолжение статьи - о сходящихся рядах случайных чисел! (Впервые о таком слышите? Это потому что я прямо сейчас это придумал.)
1. Генерация последовательности случайных чисел без повторов
Часто для генерации хода компьютера используют функцию random(), которая в следующем вызове может сгенерировать число, уже использованное в игре. Это бывает не удобно. Вот простой скрипт, который создает последовательность случайных чисел без повторов.
<!doctype html>
<html>
<head>
<meta charset="utf-8">
<title>Desk of cards</title>
<style type="text/css">
body, div {font: 11px Verdana;}
</style>
</head>
<body>
<script type="text/javascript">
var numOfCards = 36;
// создаем массив, где значения ячеек приравнено их индексам
var arr = [];
for(var n=0; n<numOfCards; n++){
arr[n] = n;
}
// затем проходим по этому массиву и выполняем
// перестановки случайным образом.
for(n=1; n<arr.length; n++){
var rnd = Math.floor(Math.random()*(arr.length));
var temp = arr[n];
arr[n] = arr[rnd];
arr[rnd] = temp;
}
// и теперь мы располагаем массивом, содержащим случайные
// числа без повторов (колода карт, бочонки лото и т.д.)
// далее, используюя счетчик ходов (переменную throwCounter)
// мы всегда будем иметь под рукой случайное число,
// не повторяющее предыдущие.
var throwCounter = 0; // throwCounter < numOfCards
var deskOfCards = [
"6 ♠", "6 ♣", "6 ♦", "6 ♥",
"7 ♠", "7 ♣", "7 ♦", "7 ♥",
"8 ♠", "8 ♣", "8 ♦", "8 ♥",
"9 ♠", "9 ♣", "9 ♦", "9 ♥",
"10 ♠", "10 ♣", "10 ♦", "10 ♥",
"В ♠", "В ♣", "В ♦", "В ♥",
"Д ♠", "Д ♣", "Д ♦", "Д ♥",
"К ♠", "К ♣", "К ♦", "К ♥",
"Т ♠", "Т ♣", "Т ♦", "Т ♥"
];
// Подпись к таблице (легенда)
document.write("Номер хода / случайное значение / выпавщая карта <br><br>");
// Вывод всей колоды "карта за картой".
for(n=1; n<arr.length; n++){
throwCounter++; // устанавливаем номер хода (повышаем счетчик ходов)
var rnd = arr[throwCounter-1]; // забираем следующее случайное значение
var div = document.createElement('div'); // отображаем
document.body.appendChild(div);
div.innerHTML = (throwCounter<10?" ":"")
+ "<b>" + throwCounter + "</b>" + ". "
+ (rnd<10?" ":"") + "<i>" + rnd + "</i>"
+ " " + deskOfCards[rnd];
}
</script>
</body>
</html>Как видим, всё получилась. Используя счетчик ходов и обращаясь к каждому последующему элементу массива, мы получаем последовательность случайных чисел без повторов. Удобно использовать, если нужно сгенерировать последовательность карт в колоде, бочонков для лото, последовательность ячеек для обстрела в игре "морской бой", или любой другой проиндексированной череды ходов.
Алгоритм не оптимизирован, но прост и эффективен. Буду рад поиграть в игры, где вы его используете. И прошу простить мне некоторый архаизм в написании кода.
Вот пример пасьянса с использованием этого способа формирования колоды. Здесь можно его посмотреть (https://github.com/UznikTmy/PagesForPublic/ => PrisonerSolitaire ), а здесь поиграть (https://uzniktmy.github.io/PagesForPublic/PrisonerSolitaire/index.html ).
2. Сходящаяся последовательность случайных чисел (генерация совпадений)
Раз уж речь зашла о рядах случайных чисел, поделюсь еще одной последовательностью: парные значения случайных значений (совпадения случайных величин; длины серии между выпадением одной и той же случайной величины).
Начну с известного: функция random() имеет нормальное распределение. То есть, одно и то же выбранное нами значение при большом количестве бросков выпадет столько же раз, сколько и любое другое.
Слева показан график "нормального распределения". Мы видим, что "1" выпала 169 раз из 1000-е бросков, "2" - 177, и так далее. По теории, каждое значение находится среди 6 возможных. А значит, и выпадать должно в каждом шестом случае. (Здесь важно не путать: оно не обязано выпадать в каждом шестом броске - об этом далее, я упомяну "регулярность" или "частотность" выпадения чисел, и будут даны комментарии. Сейчас идет речь о том, что выпадений каждого из шести событий равноценно, а значит в длинной серии реализации бросков заданное значение появится в том же объеме, который оно занимает в ряду возможностей - 1/6. Поэтому здесь, говоря "в каждом шестом", имеется в виду не развертывание бросков, а количество упоминаний в состоявшемся ряду).
По теории, каждое значение должно выпадать в каждом 6-ом броске, то есть на 1000 бросков должно прийтись 1/6*1000 = 166.67 выпадений каждой грани. В реальности это число отличается, однако при бесконечном количестве бросков - совпадет.
Справа - сходящееся распределение. Здесь показано сколько раз "выпадала" та или иная серия: один бросок, два броска и так далее. Серия - это количество бросков между выпадением одной и той же случайной величины. Другими словами, номер броска, в котором в следующий раз выпало то же значение. Мы видим, что значения близкие к единице выпадают чаще, чем отдаленные. То есть, бросить кубик той же гранью сразу после того, как она выпала - более вероятно чем в 10-й, 100-й или 1000-ый раз. (Вероятность равна количеству успешных бросков к общему числу бросков, в данном случае, это 200/1000 для варианта "сразу", 167/1000 для варианта "через раз" и так далее, стремительно уменьшаясь.)
Откуда это все взялось? И зачем это? Расскажу все по порядку.
Довелось мне исследовать вопрос "совпадения" случайных чисел. Модель простая: у вас есть игральный кубик, вы загадываете число и бросаете кубик. Будет ли в этих совпадениях какая-либо закономерность? Как себя ведут вообще эти серии? Получить короткую серию более вероятно, чем длинную? Если число не выпадает после 10-и, 100-а, 1000-и бросков, в праве ли мы ожидать, что в следующем броске больше шансов, что оно выпадет? Мы ведь знаем, что это число должно появиться, и его появление составляет примерно 1 к 6. Можем ли мы сказать, что через каждые 6 бросков число должно снова появляться? Что число должно выпадать в среднем в каждом шестом броске? Что есть какая частота появления числа, какая-то регулярность в появлении случайных чисел?
Оказывается, нет. Чем больше бросков мы делаем, тем больше отклонение от "ожидаемого" выпадения. Наибольшая вероятность "выбросить" заданное число - в первом броске. В каждом последующем - "размах" вариантов стремительно растет, и вероятность получить ожидаемое - стремительно низка. (То есть, в первом броске событие находится среди 6 возможных, то во втором - уже среди 36, а в третьем - среди 216 и так далее). Частота стремительно "плывет", начиная с 1/6, затем становится 1/36... С каждым последующим броском вместо установления регулярности происходит ее "размывание". Итак, частота появления заданной величины (например, единицы) отсутствует. Мы можем только сказать, что чаще одно и то же число выпадает сразу или через малое число бросков, и редко встречаются случаи, когда серии - длинные.
На языке JavaScript этот опыт выглядит так:
function throwDice(){
var user = Math.floor(Math.random()*6)+1; // загаданное число
var comp = Math.floor(Math.random()*6)+1; // бросок кубика
var is = user==comp; // вердикт: совпадение или нет
return {user: user, comp: comp, is: is};
}Однако, разницы нет, будем мы каждый раз загадывать новое число или мы брать фиксированное, например, единицу. Таким образом, мы можем просто отслеживать, на каком броске повторно выпало значение грани "единица" (длина серии). ("Бросок" - это получение случайного числа (выпадение грани), "серия" - это количество бросков от выпадения заданного значения до выпадения его же снова (грани игрального кубика). Серия может быть от единицы до бесконечности.)
И теперь я предлагаю переключить свое снимание не на значения выпавших чисел (грани кубика), а на длину серии. Код такой реализации будет выглядеть так.
function throwDice(){
for(var i=0; i<1000; i++){
var rnd = Math.floor(Math.random()*6)+1;
if(rnd==1) return (i+1);
}
return throwDice();
}
throwDice(); // запуск одной серииПояснение. Генерация последовательности заключена в цикл, чтобы избежать "зависания": если 1000 "бросков" не достаточно, мы сбрасываем эту реализацию и начинаем новую.
(Особенность нашего восприятие - в том, что мы пытаемся выявить регулярность, структурируем, соотносим происходящие события с "идеальной моделью". Кажется, что должна же быть какая-то частотность, периодичность в появлении совпадений? Но попытка наложить "сетку", где размечены каждый шестой бросок, выглядит как еще большая путаница; реальные измерения "выходят за мыслимые пределы". Попытка вычислить отклонения реального номера броска от расчетного ни к чему не привели. Соотнесение последовательности выпадения "совпадений" с нормированной структурой (разница между расчетным номером броска и реальным номером броска) не показала какого-либо согласования регулярностью и фактической реализацией. Имеет смысл говорить только о длине серии, но безотносительно к "прогнозируемой перbодичности".)
Итак, теперь мы рассматриваем длину серии, как случайное число. (То есть, раньше мы делали бросок и смотрели выпавшее на грани значение, а теперь мы ждем выпадения "единицы", производя подсчет бросков - и это количество бросков и становятся для нас предметом исследования).
Рассматривая статистику полученных значений, мы увидим такую картину. По оси абсцисс отложены количество бросков до выпадения единицы на кубике (длина серии), по оси ординат - сколько раз "случилась" серия такой длины.
График описывается функцией fq = (1/5)*(5/6)^n, где n - длина серии, которую мы исследуем, как случайное число, fq - сколько раз повторилась такая серия. Откуда формула? Вот вывод: вероятность выпадения "единицы" в первом броске равна 1/6, во втором - (5/6)*(1/6), в третьем (5/6)*(5/6)*(1/6) и т.д. Или же
(1/6) * (5/6)^(n-1) = (1/5)*(5/6) * (5/6)^(n-1) = (1/5) * (5/6)^n
См. рисунок выше.
Из графика видно, что статистика вполне описывается представленной функцией. Из этого можно заключить, что совпадение случайных чисел - согласуются с (теорией) математической моделью, описывающей (поведение) случайные события. Из этого следует, что данное явление той же природы, как любое другое, называемое «случайным» Оно представляет собой лишь разновидность случайного события, без каких‑либо особенности. То, что два случайных события совпали, не накладывает на это обстоятельство никаких дополнительных ограничений. (Как если бы мы зачерпнули воду в Волге и вылили ее в Москва-реку, и это не привело бы ни к чему, а вода осталась бы водой. Но нам кажется, что встречаются две сущности: Волжская и Московская, и это, как в случае народов, не всегда проходит гладко. Можно это назвать «психическим искажением».)
Выводы и применение
Вывод можно сделать такой, что совпадения случайных чисел носят столь же случайный характер, как и сами случайные события. Ни закономерности, ни мистики в этом нет: закономерности нет, потому что такова природа случайных явлений, а мистики нет, так как данное явления описывается Теорией вероятностей и принципом "больших чисел". Никакой "потусторонней воли" обнаружить не удалось. "Сразу" совпадения загаданного числа со случайным чаще, чем "потом". То есть, серии короткой длины встречаются чаще, чем длинные серии. Например, выше вероятность, что снова угадать выпавшее значение удастся сразу, чем после 100-й и 1000-й попытки. Но нам всегда кажется, что рано или поздно-то "единичка" обязательно выпадет, и чем дольше мы ждем, тем больше вероятность, что именно сейчас. Но практика показывает что, наши ожидания никак не приближают успех. Увы, ожидания только усиливают напряжение и сильнее искажают представление о действительности. И раз уж зашла речь о психологии восприятия случайных событий, то надо напомнить, что восприятие случайных событий связано с ожиданиями и жертвами, терпением и затратами, и это накладывает эмоциональный отпечаток, искажает прогностическую модель.
Правильный (безэмоциональный, отстраненный) прогноз больше соответствует реализации явлений в беспристрастной природе. На этом отличии и основывается мистицизм: ощущение, что за случайными событиями стоит чья-то воля, обман ожиданий. В этом и состоит искажение прогноза и восприятия: как уровень громкости звука описывается логарифмической функцией, а не, как нам кажется, линейной, так и прогнозирование будущего: ожидания искажают образ мира, происходит "вычитывание" в события того, чего в них нет, и образ мира не соответствует реальному ходу событий. Думаю, в случайных явлениях больше художественной пользы, чем прагматической.
Практическое же применение таково. Данный способ генерации позволяет образовывать "скопления" случайных значений. В следующем примере представлен "генератор созвездий", которым я хочу в заключение наглядно продемонстрировать применение этого способа генерации случайных величин. В статическом или динамическом варианте. Все упомянутые материалы доступны на github (https://github.com/UznikTmy/PagesForPublic/) и github pages (https://uzniktmy.github.io/PagesForPublic/).
