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

Question

Какой самый эффективный способ использовать пару шестигранных кубиков для получения случайного числа в [1, 4] неравномерно: он должен давать 1 в 40% времени, 2 в 30%, 3 в 20% и 4 в 10%.

Пожалуйста, обоснуйте правильность метода и приведите алгоритм.

Кости могут быть разных цветов.

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

Answer 1

Допустим, два кубика: один белый, один черный.

1. Бросьте две кости, чтобы получить два числа от 1 до 6;
2. Создать новый номер: 6 * (белая кость - 1) + черная кость
3. Это число от 1 до 36. Если оно больше 30, перейдите к 2 и повторите;

Теперь у вас есть то, что вам нужно:

• 1-12 = 1 (12/30 = 40%)
• 13-21 = 2 (9/30 = 30%)
• 22-27 = 3 (6/30 = 20%)
• 28-30 = 4 (3/30 = 10%)

Вам нужны не 4 возможных результата, а 10, потому что это может представлять желаемый взвешенный результат. Два кубика могут дать 36 возможностей разными способами, но вам нужно 10 или кратное 10, как указано выше.

Единственным недостатком этого метода является то, что он вероятностный (имеется в виду, что вы могли бы сидеть и кататься 31+ навсегда, технически), но я не уверен, что существует детерминированное и точное решение.

Answer 2

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

В общем, я второй ответ Клетуса, но используя его алгоритм, вы получите один результат из двух кубиков с вероятностью 5/6, что означает, что ожидаемое «количество результатов на кубик» составляет 5/12 ~ = 0,417. Умножая последнее на энтропию одного из ваших случайных результатов, что

-(0.1*log2(0.1) + 0.2*log2(0.2) + 0.3*log2(0.3) + 0.4*log2(0.4)) ~= 1.846

получаем 0,770. Другими словами, мы используем в среднем 0,770 бит информации от каждого кристалла. Мы можем сделать лучше, чем это.

Например, бросая 9 кубиков, вы получаете 6 ^ 9 = 10077696 возможных результатов. Следуя Cletus, сформируйте число от 0 до 10077695 и сохраняйте его, только если оно находится в диапазоне от 0 до 9999999 (это происходит с вероятностью ~ 0,992). В этом случае у вас есть 7 случайных десятичных цифр с равномерным распределением, и из каждой из них вы можете извлечь случайное число, как в вашей задаче:

0,1,2,3 --> 1
4,5,6   --> 2
7,8     --> 3
9       --> 4

Таким образом, у нас есть 7 случайных результатов на каждые 9 кубиков с вероятностью 0,992 или среднее «количество результатов на кубик» 0,992 * 7/9 ~ = 0,772. Умножив это на энтропию результата, мы получим 1,846 * 0,772 ~ = 1,425. Таким образом, таким образом мы используем в среднем 1,425 битов от каждого кристалла.

Вероятно, мы можем лучше бросать больше кубиков или использовать другую технику. Конечно, верхняя граница - это энтропия матрицы, которая составляет log2 (6) ~ = 2,585 бит.

Answer 3

Ключ: «он должен производить 1 в 40% времени, 2 в 30%, 3 в 20% и 4 в 10%»

Существует 36 возможных результатов броска пары 6-ти кубиков. красный, синий (предположим, некоторые кости)
1 1
1 2
1 3
1 4
1 5
1 6
2 1
2 2
2 3
2 4
2 5
2 6
3 1
3 2
3 3
3 4
3 5
3 6
4 1
4 2
4 3
4 4
4 5
4 6
5 1
5 2
5 3
5 4
5 5
5 6
6 1
6 2
6 3
6 4
6 5
6 6

10% из 36 результатов разбиваются на 3,6 результата ... что невозможно, поэтому вы собираетесь выбросить шесть результатов, чтобы получить 30 результатов, которые делятся на 10. Для удобства отбросьте дублирующиеся роли ( 1-1, 2-2, 3-3, 4-4, 5-5, 6-6)

Так что теперь единица 10%, если 3 результата. Теперь вашим бинам [1-4] нужно соответствующее количество результатов, чтобы составить 40%, 30%, 20%, 10%.

.. или
40% = 12/30 результатов ... поэтому возьмите первые двенадцать случаев ... помните, что дубликаты удаляются = (1,2) - (3,2)
30% = 9/30 результатов ... принять следующие 9 результатов = (3,4) - (5,1)
20% = 6/30 результатов ... принять следующие 6 результатов = (5,2) - (6,2)
10% = 3/30 результатов ... возьмите последние 3 результата = (6,3) - (6,5)

.. теперь проблема в том, что любой дублирующий бросок вызывает повторный бросок, и это может происходить снова и снова, поэтому это неэффективно. Проблема заключается в том, что основание 6 (игральные кости) и основание 10 (10% = 1/10-е) - из-за отсутствия лучшего термина - от простого к другому. Это та же проблема, что и представление 1/10 в двоичном виде. Вы можете приблизиться, независимо от того, сколько битов вы используете = независимо от того, сколько бросков, вы не можете создать идеальный 10% -й бин с 6-ти сторонним штампом.

Вы должны будете использовать 5 или 10 кубиков.

Answer 4

Это на 1 кубик, как я написал для смещенного колеса рулетки для генетического алгоритма , но может быть адаптировано. Это на C #, но легко изменится для Java или других языков на основе C.

Первый запуск с набором значений
Поменяйте местами эти значения на номера 1-6, если вы хотите скопировать фактическую кость.

double[] values =
{
    9,
    66,
    153,
    2,
    42,
    34
};

Затем добавьте проценты, которые вы хотите, чтобы каждый из них отображался .
Например, вы хотите, чтобы 153 был смещен, поэтому он выбирается 25% времени:

double[] percentages = 
{ 
    15, 
    10, 
    25, 
    5, 
    37, 
    8 
};

Теперь установите некоторые диапазоны для процентов.
Это используется для броска костей, поэтому, если выпало 15-25, вы знаете, что оно попало во второй процентный диапазон.

double[] ranges = new double[6];
ranges[0] = percentages[0];
ranges[1] = ranges[0] + percentages[1];
ranges[2] = ranges[1] + percentages[2];
ranges[3] = ranges[2] + percentages[3];
ranges[4] = ranges[3] + percentages[4];
ranges[5] = ranges[4] + percentages[5];

И, наконец, сгенерировать случайное число.
Если это число попадает в один из диапазонов, выберите этот индекс из значений.

static Random _random = new Random();

static void Main(string[] args)
{
    ...

    for (int i = 0; i < percentages.Length; i++)
    {
        int rand = _random.Next(0, 100);
        double x = ranges.First(n => n >= rand);
        int index = ranges.ToList().IndexOf(x);
        Console.WriteLine(values[index]);
    }
}

Я уверен, что есть способы улучшить это, и мне было бы интересно узнать их.

Answer 5

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

Answer 6

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

Например, следующий псевдокод будет производить 1 2/3 времени и 2 1/3 времени.

var randArray = [1, 1, 2];
var randIndex = random(2);
return randArray[randIndex];

Answer 7

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

Во-первых, разделите интервал от 0 до 1 на куски, соответствующие вероятностям: отметьте 0,4, 0,7, 0,9 и 1,0 на числовой строке, которые определяют области с метками от 1 до 4. Вам нужно будет отслеживать число раз вы бросили кости, n, и бегущий счетчик, p. Сначала установите n = 1, p = 0.

1. Бросьте кубик и разделите на 6 * n и добавьте это значение к p. Отметьте это место на числовой линии.
2. Если p и p + 1 / 6n находятся в одной и той же «области» (они не пересекают границы, которые вы определили выше), все готово, а цвет - это цвет области, в которую входит p.
3. В противном случае увеличить n и перейти к 1.

Таким образом, в большинстве случаев вам понадобится только один или два рулона, чтобы выяснить, какой цвет выбран, хотя иногда вам придется катиться больше, если вы окажетесь у границы. С вашими весами 40% времени вам нужен только 1 бросок, 44% раз вам нужно два, 13% вам нужно 3 и примерно 3% времени вам понадобится больше.

Answer 8

Используйте 10-стороннюю матрицу, обозначенную 1,1,1,1,2,2,2,3,3,4. Или вы (по какой-то причине) ограничены шестигранными кубиками? Для компьютерной реализации см. Ответ Бенни Джобигана.

Однако, если вы ограничены двумя шестигранными кубиками, один из способов - сделать 36 маленьких карточек квадратной формы. Отметьте 12 с помощью «1», отметьте 9 с помощью «2», отметьте 6 с помощью «3», отметьте 3 с помощью «4» и оставьте шесть пустыми или отметьте их как «перекатывать».

Разложите 36 карточек в квадрат 6х6. Пометьте каждую строку и столбец числами 1-6 и определите, какой кубик соответствует столбцам, а какой - строкам.

Бросьте кости и найдите карту, которая соответствует выбранной строке и столбцу. Если у карты есть номер, то этот номер вам нужен, если он пустой (или говорит «перекат»), снова бросьте обе кости.

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