?

Log in

No account? Create an account

Previous Entry | Next Entry

Я уже полгода страдаю на тему, которую я для себя называю "псевдорандомы в программировании". Вот допустим есть множество из примерно 50 элементов и есть функционал, внутри которого пользователь перебирает эти элементы. Разные люди, используя этот функционал, регулярно обращают внимание, что если сделать около 20 повторений (а столько делает средний пользователь), то выборка какая-то недостаточно разнообразная, в ней 2-3 раза встречаются одни и те же элементы. Эта картина входит в клинч с.. ээмм.. скажем так, бытовыми представлениями людей о теории вероятности, и клиент мне все время пишет: "Смотрите, у вас тут баг!" А программисты на это говорят: "это не баг, это псевдорандом". И я-то стараюсь им верить, но они не могут объяснить понятно, чтобы я могла объяснить клиенту!

Вопросы в рамках культпросвета:
1. Может кто-то объяснить, как это получается вообще?
2. Можно с этим как-то бороться? Ну в смысле повышать случайность псевдослучайности, извините?

Comments

( 27 comments — Leave a comment )
dennis_chikin
Feb. 17th, 2016 03:15 pm (UTC)
Это таки баг.

Если повторений быть не должно - уже использованные значения из таблицы должны быть исключены.

Псевдорэндом - имеет место быть, и, да, если значение из длинной последовательности не используется непосредственно "как есть", а подвергается преобразованиям - предсказуемость растет мгновенно и страшно.
Бороться - исследовать качество генератора и его соответствие конкретной цели. Если получается плохое - менять алгоритм и/или период на более другой.

Edited at 2016-02-17 03:17 pm (UTC)
bernh
Feb. 17th, 2016 03:18 pm (UTC)
Если повторений нет, то это вообще не рандом (точнее, как раз такой псевдорандом).

Edited at 2016-02-17 03:18 pm (UTC)
dennis_chikin
Feb. 17th, 2016 03:23 pm (UTC)
Псевдорэндом есть все, что не с физического датчика БШ.
Далее вопрос стоит только в том, нужны повторы, или нет.

Случай с 50 элементов на 20 циклов - там over 96% за то, что даже при беглом взгляде на случайное похоже не будет от слова "совсем".
v_i_y_a
Feb. 17th, 2016 03:23 pm (UTC)
псевдорандом называется псевдорандомом потому что является функцией, результаты которой имитируют равномерно распределенную случайную величину в заданном диапазоне

а на наличие повторений влияет на какой диапазон в итоге масштабируется ее результат

если из диапазона каждый раз исключать уже выпавший результат - можно имитировать случайное вытягивание вариантов без повторений
bernh
Feb. 17th, 2016 03:27 pm (UTC)
Ну я, как раз о том, что чистый рандом, без модификации, как раз таки может давать повторения в количестве (то, на что жалуется Ксеняка).
v_i_y_a
Feb. 17th, 2016 03:30 pm (UTC)
это да
xeniaku
Feb. 17th, 2016 03:23 pm (UTC)
Спасибо за ответы.
А что такое в этом контексте период?
dennis_chikin
Feb. 17th, 2016 03:26 pm (UTC)
https://ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D1%82%D0%BE%D1%80_%D0%BF%D1%81%D0%B5%D0%B2%D0%B4%D0%BE%D1%81%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D1%8B%D1%85_%D1%87%D0%B8%D1%81%D0%B5%D0%BB

Для начала.

upd, подумавши: очень такой примитивненький тестик - вывести результаты работы на экран в виде точек, где координаты - сначала просто берем с генератора, потом - координаты с равным шагом забиты в таблицу, а элемент таблицы извлекаем по "рэндомному" индексу.

ну, то есть for i = 1, n do dot( rnd() * 1000, rnd() * 1000 ) end
и t = {}
for i = 1, 50 do t[i] = i * 20 end
for i = 1, n do dot( t[rnd( 50 )], t[rnd(50)] end

Если с какого-то n на экране получаем красивый регулярный узор - надо что-то менять.

Edited at 2016-02-17 03:39 pm (UTC)
bernh
Feb. 17th, 2016 03:21 pm (UTC)
1. Возьми, скажем, шестигранный кубик и брось его ровно 6 раз. Практические уверен, что какие-то значения выпадут два (а то и три) раза, а какие-то - ни разу.
2. Ну вот, выше пишут про исключение уже выбранных значений.

Edited at 2016-02-17 03:22 pm (UTC)
dennis_chikin
Feb. 17th, 2016 03:30 pm (UTC)
Дайсы, кстати, тоже плохой источник. Чтобы выкидывалось что-то более-менее похожее на случайность, надо долго тренироваться. ;)
bernh
Feb. 17th, 2016 04:54 pm (UTC)
Да нет, можно. Но начиная где-то с тысячи бросков :)
Выборка 20 из 50 ужасно нерепрезетативна..
v_i_y_a
Feb. 17th, 2016 03:27 pm (UTC)
а в чем у заказчика вопрос - повторов не должно быть по логике работы приложения или на его взгляд "недостаточно случайно"?
xeniaku
Feb. 17th, 2016 03:31 pm (UTC)
На взгляд заказчика за 20 попыток он видит все время одно и то же. Я тоже иногда вижу... или нет. В общем не могу понять.

Про повторы непонятно. Средний пользователь делает 20 попыток, а не средний может делать 60. Если на 50-й разные варианты кончатся, что будет? Заново все начнется?
dennis_chikin
Feb. 17th, 2016 03:41 pm (UTC)
В зависимости от цели на каком-то шаге таблицу надо переинициализировать.
sergey_cheban
Feb. 17th, 2016 05:22 pm (UTC)
1. Если есть всего 50 вариантов, а человек сделал 60 попыток, то как минимум 10 раз он _неизбежно_ увидит повторы. Жаловаться на это - всё равно что жаловаться на "На улице - сплошные мальчики и девочки, никакого разнообразия полов".
2. Вам что нужно, соблюсти принцип случайного выбора или избежать повторов? Если второе, то покажите своему программисту функцию random_shuffle, и за 50 попыток не будет ни одного повтора (а вот в попытках с 26 по 75 - повторы будут).
3. Можно гонять 50 вариантов по кругу без всякой случайности. Тогда в любых 50 попытках подряд не будет ни одного повтора.
leotsarev
Feb. 17th, 2016 04:03 pm (UTC)
Думать про псевдослучайность тут глупо.
Даже про настоящую не нужно.
Надо думать про то, зачем этот элемент в программе и что он показывает пользователю и зачем.
Возможно, там должно выводится все, но в случайном порядке, например, а как вывели все — снова начали показывать, но в новом случайном порядке.
xeniaku
Feb. 17th, 2016 04:17 pm (UTC)
Думать про это всё приходится потому, что задача программисту поставлена, он ее реализовал, а когда ему указываешь, что она реализована как-то не совсем так, то он говорит "это все псевдослучайность, иначе нельзя, настоящих случайностей в программировании не бывает". И что мне тут делать?
leotsarev
Feb. 17th, 2016 04:22 pm (UTC)
А что в задании написано?
Показывать случайные?
Ну так правильно работает скорее всего.
yarwain
Feb. 17th, 2016 09:26 pm (UTC)
На мой взгляд, если программист такое говорит, он просто не хочет разбираться. Формально он прав: нельзя сгенерить реальный рандом, так как он все равно генерится по определенному алгоритму. Но по сути современные механизмы псевдорандома настолько близки к реальному рандому, что разницы практически никакой.
Просто 20 (и 60, и 160) - это такое маленькое количество для 50 элементов, что на нем никогда не будет равномерного распределения.
Другое дело, если какие-то определенные элементы выпадают много раз в каждой такой выборке, у всех пользователей. Это вот уже повод покопаться в коде.
ukurissimus
Feb. 17th, 2016 04:30 pm (UTC)
Это вообще не имеет отношения к рандому, а имеет отношение к терверу, конкретнее - комбинаторике.
Если из 50 элементов с повторениями случайно выбираются 20, то вероятность что ни разу не повторится равна примерно 1,2 процента.
Как уже писали выше, можно прописать случайный выбор без повторений, тогда ситуация исправится.

см например:
https://ru.wikipedia.org/wiki/%D0%9F%D0%B0%D1%80%D0%B0%D0%B4%D0%BE%D0%BA%D1%81_%D0%B4%D0%BD%D0%B5%D0%B9_%D1%80%D0%BE%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D1%8F

Edited at 2016-02-17 04:34 pm (UTC)
sergey_cheban
Feb. 17th, 2016 05:01 pm (UTC)
Начать можно с этого:
https://xkcd.com/221/
http://dilbert.com/strip/2001-10-25

Если серьёзно:
1. Да, по-настоящему случайная последовательность может выглядеть не случайно. Людям свойственно видеть закономерности даже там, где их на самом деле нет.
2. С другой стороны, возможно, что в программе есть ошибка, которая приводит к неслучайным результатам, и если эту ошибку найти и исправить, то результаты станут лучше, случайнее.

Если я понял Вашу проблему правильно, то очень похоже, что Вы столкнулись с так называемым парадоксом дней рождения: https://ru.wikipedia.org/wiki/%D0%9F%D0%B0%D1%80%D0%B0%D0%B4%D0%BE%D0%BA%D1%81_%D0%B4%D0%BD%D0%B5%D0%B9_%D1%80%D0%BE%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D1%8F
ksotar
Feb. 17th, 2016 09:57 pm (UTC)
Психология пользователей и вероятность очень странно комбинируются, бывает. Самое крутое, что я про это видел, это лекция Сида Мейера.

Вот забавная выдержка из выдержек оттуда:
"Probably where it became most clear to me that player psychology had nothing to do with rational thought was putting together the battle system in Civ rev. in Civ rev we'd show you before a battle what the odds were. As a mathematician this is a 3 to 1 battle [pic] but players feel they're going to win the battle. “I had this battle, it was 3:1 and I LOST!” The player would say, “no no you don't understand. 3 is big, 1 is small. I had the big number, I should have won!”

So we adjusted our system to make the battles more like what the players expected. This time the player had 1, and the AI had the big gigantic 3. And lo, the player won. And I said “doesn't that feel wrong to you”? And the player said, “no? Not at all? I had tactics”! So we made more adjustments. “Now are you happy with the way combat works”? And it's around 3:1 or 4:1 where players pretty much expect to win every time.

We can live with that. So we asked: anything else? Are you okay losing a 2:1 battle every now an then? “Yes. But I had a 20:10 battle. I had ten more than them! I lost!” I say, “isn't that 2 to 1?” “NO! that’s 20 to ten! Whole different odds!” So we adjusted again. You have ten more. That's a lot. So now.. are you happy?

“So I had this 2:1 battle. I lost. That was okay. But after that I had another 2:1 battle and I lost again, how can this be??? The computers' out to get me!”

So we take into account the results of previous battles when we do battle calc. We don't do this just to make the player happy, but when the battles start to feel wrong, the player starts to lose the suspension of disbelief, the player will get distracted. Something really clear: the interaction between logic, science and math.. and psychology... it's counterintuitive. Including the psychological part of things in game design is going to mean running into these counterintuitive things. This can be to your advantage, as you'll see. "
mjurphy
Feb. 18th, 2016 01:25 pm (UTC)
Отлично ;) пошел читать статью
ksotar
Feb. 18th, 2016 02:34 pm (UTC)
Это выдержки, а я как фанат посмотрел запись выступления :)
yudaev
Mar. 11th, 2016 06:57 am (UTC)
Если 20 раз выбрать по одному элементу из 50, возвращая выбранный элемент обратно, то какие-то элементы таки будут встречаться 2-3 раза с вероятностью более 0.5. См. "Парадокс дня рождения". Граница того, что вероятность одного повтора превысит 0.5 проходит примерно на выборе одного элемента из 50-ти 9 раз: 1.2*sqrt(50).

По реализации: у вас псевдорандом и это неплохо. Но два вопроса:
- как он инициализируется?
- какая функция рандома используется?

Еще вопрос пользователю. Пусть мы на каждом шаге независимо и равновероятно выбираем 0 и 1. Пусть мы делаем 8 шагов. Эксперимент проводим один раз. Сравнить вероятности того, что мы получим последовательности
а) 01011001
б) 11111111
xeniaku
Mar. 11th, 2016 09:57 am (UTC)
Про псевдорандом я не знаю, спрошу разработчика. А почему это важно?

На последний вопрос ответ: вероятности равные, хотя, конечно, пользователи, которые без спец. подготовки, в жизни в это не поверят! Я тоже без спец. подготовки, но я читала Канемана и уже привыкла немного к такого рода парадоксальным вещам.
yudaev
Mar. 11th, 2016 10:23 am (UTC)
Потому что псевдорандом можно инициализировать, например, так
random.init(time() % 10)
где time() возвращает текущее время в секундах. И будет у вас 10 вариантов последовательности :)
Или вместо этого - текущее время суток, а программа всегда запускается в 9 утра.
И еще масса способов совершить ошибку. Впрочем, обычно ее всё же не совершают.

Я бы поставил на то, что всё дело в парадоксе дня рождения. Если кратко, то вот:
https://en.wikipedia.org/wiki/Birthday_problem
- секция Square approximation
и ниже
- The generalized birthday problem
- Reverse problem


Edited at 2016-03-11 10:27 am (UTC)
( 27 comments — Leave a comment )

Profile

2017
xeniaku
Ксеняка

Latest Month

November 2017
S M T W T F S
   1234
567891011
12131415161718
19202122232425
2627282930  
Powered by LiveJournal.com
Designed by Julie Kurylo