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

Question

[br1an]

Добрый день, уважаемые :)
Есть такая задача:
Люди делают ставки предметами (предметы оцениваются по цене, цена как правило дробное число = 0.55, 34.22 и т.д), через какое-то время должен выбраться победитель случайным образом, НО с учетом того шанса на победу (чем больше ставка - тем больше шанс победить).
Примеры таких сайтов - csgojackpot.com, csgoup.ru
Мы реализовали данный алгоритм вот так https://gist.github.com/Riateche/3038910
Но есть сомнения, т.к очень и очень часто выигрывают люди с небольшим шансом (можно конечно оправдать, что мол рандом)
Подскажите пожалуйста, правильный ли алгоритм мы используем (учитывая что число случайное - целое, а отрезки шансов в алгоритме - дробные)? И есть ли более подходящие системы случайного выбора победителя, основанные на шансе победы?

Answer 1

[Rsa97]

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

Comments

[Миша Коган]

Можно, если не сложно какой код в итоге вышел? Можно на любом языке

Answer 2

[Mrrl]

Лучше брать дробное случайное число:
double r=frand()*total_chance_sum.
(как сегодня называется frand() я не знаю - должно выдавать случайное число от 0 до 1). Условие current_sum <= r не нужно, оно выполняется всегда.
Если хотите повысить шансы тех, кто делал большие ставки - можете возвести эти ставки в квадрат (т.е. если цены - 0.5, 1, 2, то шансы на победу будут 1/21, 4/21, 16/21). Не знаю, хорошо ли это.

Вообще, не очень понятно, как работает
current_sum += items[i].chance
если сумма целая, а ставка дробная. Она не ругается на потерю точности?

Comments

[br1an]

Забыл уточнить, что код, на который я указал ссылку - не наш
Мы аналогично реализовали на php его, это ничего не меняет конечно :)
Поменял на дробное случайное число, прогнал 10 000 итераций по одной игре сначала с целым случайным числом, потом с дробным - в целом примерно одинаково (но согласен с вами, лучше дробное - больше вероятность попасть в отрезок). Сам по себе алгоритм считает правильно - из 10тыс. итераций человек с шансом 64.8% выиграл 64хх-65хх раз.

На счет возведения в квадрат, на самом деле интересное предложение, даже не подумали об этом, но с другой стороны становится немного не честно :)

Наглядно алгоритм работает так (на целом случайном числе):
Есть массив со ставками, для каждой ставки расчитывается вероят. выигрыша и далее идем по отрезкам (P.S в данной игре есть человек с win rate 64.8%, и его ставка первая в массиве)

#тестовый прогон 1
Rand num: 85
0 <= 85 && 85 < 64.81548175515
64.81548175515 <= 85 && 85 < 71.579658241207
71.579658241207 <= 85 && 85 < 72.097209972869
72.097209972869 <= 85 && 85 < 72.443744630717
72.443744630717 <= 85 && 85 < 72.8757878217
72.8757878217 <= 85 && 85 < 73.339334180161
73.339334180161 <= 85 && 85 < 73.663366566902
73.663366566902 <= 85 && 85 < 75.517551983983
75.517551983983 <= 85 && 85 < 77.182718486724
77.182718486724 <= 85 && 85 < 77.623762584138
77.623762584138 <= 85 && 85 < 78.042304431401
78.042304431401 <= 85 && 85 < 78.825382747698
78.825382747698 <= 85 && 85 < 79.459946214343
79.459946214343 <= 85 && 85 < 81.012601499864
81.012601499864 <= 85 && 85 < 81.480648293099
81.480648293099 <= 85 && 85 < 82.385238731371
82.385238731371 <= 85 && 85 < 83.150315216363
83.150315216363 <= 85 && 85 < 83.465346720144
83.465346720144 <= 85 && 85 < 83.793879576028
83.793879576028 <= 85 && 85 < 84.153915578433
84.153915578433 <= 85 && 85 < 85.013501521433
Победил человек с шансом 0.85958594300064%

#тестовый прогон 2
Rand num: 17
0 <= 17 && 17 < 64.81548175515
Победил человек с шансом 64.81548175515%

#тестовый прогон 3
Rand num: 75
0 <= 75 && 75 < 64.81548175515
64.81548175515 <= 75 && 75 < 71.579658241207
71.579658241207 <= 75 && 75 < 72.097209972869
72.097209972869 <= 75 && 75 < 72.443744630717
72.443744630717 <= 75 && 75 < 72.8757878217
72.8757878217 <= 75 && 75 < 73.339334180161
73.339334180161 <= 75 && 75 < 73.663366566902
73.663366566902 <= 75 && 75 < 75.517551983983
Победил человек с шансом 1.8541854170811%

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

[Mrrl]

br1an: Ну, если у одного человека ставка составляет 44% от общей суммы, а у остальных 49 - по 1.3%, то с вероятностью больше половины должен победить кто-то из этих остальных. На то и вероятность, и это совершенно нормально.

Answer 3

[Данил Антошкин]

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

Comments

[br1an]

Да, такая статистика есть.
Можно же проверить ещё другим путем - сделать n тысяч итераций по одной игре и посчитать, кто сколько раз победил?
Мы такое делали, например в игре у человека 64.8% шанс на победу, из 100000 итераций, он побеждает 64хх-65хх раз.
Доказывает ли это работоспособность алгоритма?

[Данил Антошкин]

br1an: Ну мне кажется что это больше похоже на рандом