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

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 2/3 времени и 2 1/3 времени.

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

Answer 4

Ключ: "он должен производить 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 5

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

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

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

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

Answer 6

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

Answer 7

Используйте 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 и определите, какой кубик соответствует столбцам, а какой - строкам.

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

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

Answer 8

Это для 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]);
    }
}

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