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

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

Справочная информация: Несколько лет назад я помню обновление для World of Warcraft, в котором сообщалось, что они внедрили новый калькулятор случайностей, который будет противодействовать цепочкам событий. (например, нанесение критических ударов или уклонение несколько раз подряд). Идея заключалась в том, что в случае, если вы избежите удара, вероятность того, что вы избежите следующего удара, будет уменьшена, но это сработает в обоих направлениях. Если не увернуться от удара, это в равной степени увеличит вероятность уклонения от следующего удара. Основной трюк здесь заключался в том, что в течение нескольких попыток вероятность уклонения все равно будет соответствовать проценту, указанному игроку в его или ее стат-листе.

Такая система очень заинтриговала меня в то время, и сейчас я нахожусь в ситуации, когда мне нужно такое решение.

Вот мои неприятности:

• Я предполагаю, что смогу найти онлайн-ресурсы по внедрению такой системы, но мне, возможно, просто не хватает соответствующих умных слов для ее поиска.
• Также мне нужен этот подход, чтобы соответствовать системе, которая не является биномиальной (т.е. два результата), но вместо этого содержит 4 взаимоисключающих события.

Мой нынешний подход похож на систему лотерейных билетов. Когда происходит событие, я меняю вес в пользу всех других событий. Это может сработать, если четыре события должны были быть одинаково вероятными, но в моем случае потребности должны быть гораздо более распространенными. Но так как распространенное событие происходит чаще, оно сдвигает веса других намного выше, чем предполагалось, и я не могу найти цифры для сдвигов веса, которые необходимы, чтобы сохранить среднее количество билетов вокруг начальных значений, что событие было данный.

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

По сути, вы запрашиваете «полуслучайный» генератор событий, который генерирует события со следующими свойствами:

1. Средняя скорость, с которой происходит каждое событие, указывается заранее.

2. Одно и то же событие реже встречается дважды подряд, чем случайное.

3. События не полностью предсказуемы.

Один из способов сделать это состоит в том, чтобы сначала реализовать генератор неслучайных событий, который удовлетворяет целям 1 и 2, а затем добавить некоторую случайность для достижения цели 3.

Для генератора неслучайных событий мы можем использовать простой алгоритм дизеринга . В частности, пусть p ₁ , p ₂ , ..., p _n - относительные вероятности событий с 1 по n , и пусть s = p ₁ + p ₂ + ... + p _n - сумма весов. Затем мы можем сгенерировать неслучайную максимально равнораспределенную последовательность событий, используя следующий алгоритм:

1. Сначала пусть e ₁ = e ₂ = ... = e _n = 0.

2. Чтобы сгенерировать событие, увеличьте каждое значение e _i на p _i и выведите событие k, для которого e _k является наибольшим (разрывая связи любым удобным для вас способом).

3. Уменьшите e _k на s и повторите с шага 2.

Например, для трех событий A, B и C с p _A = 5, p _B = 4 и p _C = 1 этот алгоритм генерирует что-то вроде следующей последовательности выходных данных:

A B A B C A B A B A A B A B C A B A B A A B A B C A B A B A

Обратите внимание, что эта последовательность из 30 событий содержит ровно 15 As, 12 B и 3 C. Это не совсем оптимально распределяет - есть несколько вхождений по два в ряд, которых можно было бы избежать - но это близко.

Теперь, чтобы добавить случайность к этой последовательности, у вас есть несколько (не обязательно взаимоисключающих) опций:

• Вы можете последовать совету Филиппа и сохранить «колоду» из N предстоящих событий для некоторого числа N соответствующего размера . Каждый раз, когда вам нужно сгенерировать событие, вы выбираете случайное событие из колоды, а затем заменяете его следующим выводом события с помощью алгоритма дизеринга, описанного выше.

  Применение этого к приведенному выше примеру с N = 3 приводит, например, к следующему:

  A B A B C A B B A B A B C A A A A B B A B A C A B A B A B A

  тогда как N = 10 дает более случайный вид:

  A A B A C A A B B B A A A A A A C B A B A A B A C A C B B B

  Обратите внимание, что из-за тасования общие события A и B заканчиваются намного большим количеством прогонов, тогда как редкие события C все еще довольно хорошо разнесены.

• Вы можете ввести некоторую случайность непосредственно в алгоритм сглаживания. Например, вместо увеличения e _i на p _i на шаге 2 вы можете увеличить его на p _i × random (0, 2), где random ( a , b ) - это равномерно распределенное случайное число между a и b ; это дало бы результат как следующее:

  A B B C A B A A B A A B A B A A B A A A B C A B A B A C A B

  или вы можете увеличить e _i на p _i + random (- c , c ), что приведет к (для c = 0,1 × s ):

  B A A B C A B A B A B A B A C A B A B A B A A B C A B A B A

  или для с = 0,5 × с :

  B A B A B A C A B A B A A C B C A A B C B A B B A B A B C A

  Обратите внимание, что аддитивная схема имеет гораздо более сильный рандомизирующий эффект для редких событий C, чем для общих событий A и B, по сравнению с мультипликативной; это может или не может быть желательным. Конечно, вы также можете использовать некоторую комбинацию этих схем или любую другую корректировку приращений, если она сохраняет свойство, при котором средний прирост e _i равен p _i .

• В качестве альтернативы, вы можете нарушить вывод алгоритма дизеринга, иногда заменяя выбранное событие k случайным (выбранным в соответствии с необработанными весами p _i ). Пока на шаге 3 вы также используете то же значение k, которое вы выводите на шаге 2, процесс сглаживания будет по-прежнему стремиться к выравниванию случайных колебаний.

  Например, вот несколько примеров выходных данных с вероятностью 10% для каждого события, выбранного случайным образом:

  B A C A B A B A C B A A B B A B A B A B C B A B A B C A B A

  и вот пример с вероятностью 50% для каждого выхода случайным образом:

  C B A B A C A B B B A A B A A A A A B B A C C A B B A B B C

  Вы также можете рассмотреть возможность подачи смеси чисто случайных и размытых событий в пул колоды / микширования, как описано выше, или, возможно, рандомизацию алгоритма сглаживания путем случайного выбора k , взвешенного по e _i s (рассматривая отрицательные веса как ноль).

Ps. Вот несколько совершенно случайных последовательностей событий с одинаковыми средними скоростями для сравнения:

A C A A C A B B A A A A B B C B A B B A B A B A A A A A A A
B C B A B C B A A B C A B A B C B A B A A A A B B B B B B B
C A A B A A B B C B B B A B A B A A B A A B A B A C A A B A

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

^{График нескольких стратегий для генерации полуслучайных подбрасываний монет (в среднем с соотношением головы к хвосту 50:50). Горизонтальная ось - количество сальто, вертикальная ось - совокупное расстояние от ожидаемого соотношения, измеряемое как (головы - хвосты) / 2 = головы - сальто / 2.}

Красные и зеленые линии на графике показывают два алгоритма не на основе колоды для сравнения:

• Красная линия, детерминированное сглаживание : четные результаты всегда являются головами, нечетные результаты - всегда хвостами.
• Зеленая линия, независимые случайные сальто : каждый исход выбирается независимо наугад с вероятностью 50% голов и вероятностью 50% хвостов.

Другие три строки (синяя, фиолетовая и голубая) показывают результаты трех основанных на колодах стратегий, каждая из которых реализована с использованием колоды из 40 карт, которая изначально заполнена 20 картами с «головами» и 20 картами «с хвостами»:

• Синяя линия, заполняется, когда пусто : карты вытягиваются случайным образом до тех пор, пока колода не опустеет, затем колода заполняется 20 картами с «головами» и 20 картами с «хвостами».
• Фиолетовая линия, заполняется, когда наполовину пуст : карты вытягиваются случайным образом, пока в колоде не осталось 20 карт; затем колода пополняется 10 картами "головы" и 10 картами "хвостов".
• Голубая линия, заполнять непрерывно : карты раздаются случайным образом; Дроу с четными номерами немедленно заменяется картой "головы", а дро с нечетными номерами - картой "хвосты".

Конечно, приведенный выше график - это всего лишь одна реализация случайного процесса, но он достаточно представительный. В частности, вы можете видеть, что все основанные на колоде процессы имеют ограниченное смещение и остаются довольно близко к красной (детерминированной) линии, тогда как чисто случайная зеленая линия в конечном итоге отклоняется.

(Фактически, отклонение синих, фиолетовых и голубых линий от нуля строго ограничено размером колоды: синяя линия никогда не может отклоняться более чем на 10 шагов от нуля, фиолетовая линия может быть удалена только на 15 шагов от нуля). и голубая линия может отклоняться не более чем на 20 шагов от нуля. Конечно, на практике любая из линий, фактически достигающих своего предела, крайне маловероятна, поскольку у них есть сильная тенденция возвращаться ближе к нулю, если они отклоняются слишком далеко. выкл.)

На первый взгляд, нет очевидной разницы между различными стратегиями на основе колоды (хотя, в среднем, синяя линия остается несколько ближе к красной линии, а голубая линия остается немного дальше), но более тщательное изучение синей линии действительно выявляет отчетливый детерминированный паттерн: каждые 40 розыгрышей (отмеченных пунктирными серыми вертикальными линиями) синяя линия точно встречает красную линию в нуле. Фиолетовые и голубые линии не так строго ограничены и могут держаться подальше от нуля в любой точке.

For all the deck-based strategies, the important feature that keeps their variation bounded is the fact that, while the cards are drawn from the deck randomly, the deck is refilled deterministically. If the cards used to refill the deck were themselves chosen randomly, all of the deck-based strategies would become indistinguishable from pure random choice (green line).

Don't roll dice, deal cards.

Take all possible results of your RNG, put them in a list, shuffle it randomly, and return the results in the randomized order. When you are at the end of the list, repeat.

The results will still be uniformly distributed, but individual results won't repeat unless the last of the list also happens to be the first of the next one.

When this is a bit too predictable for your taste, you could use a list which is n times the number of possible results and put each possible result into it n times before shuffling. Or you could reshuffle the list before it is iterated completely.

You could try a Markov Random Graph. Consider each event that can occur to be a node in a graph. From each event, make a link to each other event that could possibly come after it. Each of these links is weighted by something called the transition probability. Then, you perform a random walk of the graph according to the transition model.

For instance, you can have a graph that represents the outcome of an attack (critical hit, dodge, etc.). Initialize the starting node to one picked at random given the player's stats (just "roll the dice"). Then, on the next attack, decide what happens next given the transition model.

Care needs to be taken to decide how to weight the transitions. For one thing, all the transitions coming out of a node need to add up to a probability of 1. One simple thing you could do is make a transition from every node to every other node, with weights equivalent to the probability that those events happen a priori, given that the current event cannot occur again.

For instance, if you have three events:

  Critical, P = 0.1
  Hit,      P = 0.3
  Miss,     P = 0.6

You can set up the transition model such that a critical hit does not occur again simply by redistributing its probability mass to the other events uniformly:

  Critical -> Critical,   P = 0.0
  Critical -> Hit,        P = 0.35
  Critical -> Miss,       P = 0.65

EDIT: As the comments say below, this model is not complicated enough to get the desired behavior. Instead, you may have to add multiple additional states!

Here's an implementation I created in C# which will:

• Activate events based on probabilities
• Adjust those probabilities to decrease chances of recurring events
• Not stray too far from original probabilities

I've added a few comments so that you can see what I'm doing.

    int percentageEvent1 = 15; //These are the starter values. So given a scenario, the
    int percentageEvent2 = 40; //player would have around a 15 percent chance of event
    int percentageEvent3 = 10; //one occuring, a 40 percent chance of event two occuring
    int percentageEvent4 = 35; //10 percent for event three, and 35 percent for event four.

    private void ResetValues()
    {
        percentageEvent1 = 15;
        percentageEvent2 = 40;
        percentageEvent3 = 10;
        percentageEvent4 = 35;
    }

    int resetCount = 0; //Reset the probabilities every so often so that they don't stray too far.

    int variability = 1; //This influences how much the chance of an event will increase or decrease
                           //based off of past events.

    Random RandomNumberGenerator = new Random();

    private void Activate() //When this is called, an "Event" will be activated based off of current probability.
    {
        int[] percent = new int[100];
        for (int i = 0; i < 100; i++) //Generate an array of 100 items, and select a random event from it.
        {
            if (i < percentageEvent1)
            {
                percent[i] = 1; //Event 1
            }
            else if (i < percentageEvent1 + percentageEvent2)
            {
                percent[i] = 2; //Event 2
            }
            else if (i < percentageEvent1 + percentageEvent2 + percentageEvent3)
            {
                percent[i] = 3; //Event 3
            }
            else
            {
                percent[i] = 4; //Event 4
            }
        }
        int SelectEvent = percent[RandomNumberGenerator.Next(0, 100)]; //Select a random event based on current probability.

        if (SelectEvent == 1)
        {
            if (!(percentageEvent1 - (3 * variability) < 1)) //Make sure that no matter what, probability for a certain event
            {                                                //does not go below one percent.
                percentageEvent1 -= 3 * variability;
                percentageEvent2 += variability;
                percentageEvent3 += variability;
                percentageEvent4 += variability;
            }
        }
        else if (SelectEvent == 2)
        {
            if (!(percentageEvent2 - (3 * variability) < 1))
            {
                percentageEvent2 -= 3 * variability;
                percentageEvent1 += variability;
                percentageEvent3 += variability;
                percentageEvent4 += variability;
            }
        }
        else if (SelectEvent == 3)
        {
            if (!(percentageEvent3 - (3 * variability) < 1))
            {
                percentageEvent3 -= 3 * variability;
                percentageEvent1 += variability;
                percentageEvent2 += variability;
                percentageEvent4 += variability;
            }
        }
        else
        {
            if (!(percentageEvent4 - (3 * variability) < 1))
            {
                percentageEvent4 -= 3 * variability;
                percentageEvent1 += variability;
                percentageEvent2 += variability;
                percentageEvent3 += variability;
            }
        }

        resetCount++;
        if (resetCount == 10)
        {
            resetCount = 0;
            ResetValues();
        }

        RunEvent(SelectEvent); //Run the event that was selected.
    }

Hope this helps, please do suggest improvements to this code in the comments, thanks!

Let me generalize mklingen's answer a bit. Basically, you want to implement the Gambler's Fallacy, though I'll provide a more general method here:

Say there are n possible events with probabilities p_1, p_2, ..., p_n. When event i happened, its probability shall rescale with a factor 0≤a_i≤1/p_i (the latter is important, otherwise you end up with a probability greater than one and the other events must have negative probabilities, which basically mean "anti"-events. Or something), though typically a_i<1. You could for example choose a_i=p_i, which means the probability of an event happening a second time is the original probability the event happening precisely two times in a row, e.g. a second coin toss would have a probability of 1/4 instead of 1/2. On the other hand, you can also have some a_i>1, which would mean triggering a "stroke of luck/misfortune".

Все остальные события должны оставаться одинаково вероятными относительно друг друга, то есть все они должны быть пересчитаны одним и тем же фактором b_iтак, чтобы сумма всех вероятностей была равна единице, т.е.

1 = a_i*p_i + b_i*(1-p_i)  # Σ_{j≠i) p_j  = 1 - p_i
⇒ b_i = (1 - a_i*p_i) / (1 - p_i).   (1)

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

Позволять

        / p_i * b_i * p_j  (j≠i)
p_ij = <
        \ a_i * (p_i)²     (j=i)

Обозначим вероятность события, jпроизошедшего после события, iи отметим, что p_ij≠p_jiесли b_i=b_j (2)(что (1)подразумевается a_j = 1 - a_i*p_i + (1-a_i)*p_i/p_j). Это также то, что требует теорема Байеса, и это также подразумевает

Σ_j p_ij = p_i * b_i * (1 - p_i) + a_i * (p_i)²
         = b_i * p_i + (a_i - b_i) * (p_i)²
         = p_i  # using (1)

просто как хотелось. Просто отметьте, как это означает, что один a_iисправляет все остальные.

Now let's see what happens when we apply this procedure multiple times, i.e. for sequences of three and more events. There are basically two options for the choice of the third event's rigged probabilities:

a) Forget about the first event and rig as if only the second one occurred, i.e.

         / p_ij * a_j * p_j  (j=k)
p_ijk = <
         \ p_ij * b_j * p_l  (j≠k)

Note that this usually violates Bayes, since e.g. p_jik≠p_ikj in most cases.

б) Используйте использование вероятностей p_ij(для фиксированных i) в качестве новых вероятностей, pi_jиз которых вы получаете новые вероятности pi_jkдля события, kкоторое произойдет следующим. Вне ai_jзависимости от того, изменили вы или нет, зависит от вас, но имейте в виду, что новое bi_jопределенно отличается от измененного pi_j. С другой стороны, выбор, ai_jвероятно, ограничен, требуя, чтобы все перестановки ijkпроисходили с одинаковой вероятностью. Посмотрим...

         / p_ij * bi_j * pi_k  (j≠k)
p_ijk = <
         \ (p_ij)² * ai_j      (j=k)

         / b_i * bi_j * p_i * p_j * pi_k  (i≠j≠k≠i)
         | b_i * ai_j * p_i * (p_j)²      (i≠j=k)
      = <  a_i * (p_i)² * bi_i * pi_k     (i=j≠k)
         | b_i * p_i * bi_j * p_k * pi_i  (i=k≠j)
         \ a_i * ai_i * (p_i)² * pi_i     (i=k=j)

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

Боюсь, мое продолжение по этому вопросу придется подождать некоторое время ...

I think the best option is to use random-weighted item selection. There's an implementation for C# here, but they can be easily found or made for other languages as well.

The idea would be to reduce an option's weight every time it's picked, and increase it every time it's not picked.

For example, if you decrease the weight of the picked-option by NumOptions-1 and increase the weight of every other option by 1 (being careful to remove items with weight < 0 and readd them when they rise above 0), every option will be picked approximately the same number of times over a long period, but recently-picked options will be much less likely to be picked.

The problem with using a random ordering, as suggested by many other answers, is that after every option but one has been picked, you can predict with 100% certainty what option will be picked next. That's not very random.

My answer is incorrect, my test was flawed.

I'm leaving this answer here for the discussion and comments that point out the flaws in this design, but the actual test was incorrect.

What you're looking for is a weighted weight: the weights for your four possible outcomes need to be further adjusted (weighted) by previous outcomes, while still remaining the proper weights overall.

The easiest way to accomplish this is to alter all of the weights for each roll by decreasing the weight for the specific value rolled and increasing the other weights.

As an example, lets say you have 4 weights: Fumble, Miss, Hit, and Crit. Lets also say your desired overall weights for them are Fumble = 10%, Miss = 50%, Hit = 30%, and Crit = 10%.

If you use a random number generator (RNG) to produce values between 1 and 100, and then compare that value to where it falls within this range (1-10 Fumble, 11-60 miss, 61-90 hit, 91-100 crit), you're generating an individual roll.

Если при выполнении этого броска вы сразу же корректируете эти диапазоны в зависимости от полученного значения, вы будете взвешивать будущие броски, но вам также необходимо уменьшить вес броска на то же самое total amount that you increase the other weights by. So in our example above, you would reduce the rolled weight by 3 and increase the other weights by 1 each.

If you do this for each roll, you will still have the chance of streaks, but they will be greatly reduced, because for each roll you are increasing the chance that future rolls will be anything other than what the current roll is. You can increase this effect, and thereby further reduce the chance of streaks, by increasing/decreasing the weights by a greater factor (e.g. reduce current by 6 and increase others by 2).

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

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

Note that this example was produced using the .NET System.Random class, which is not really one of the better RNGs out there, so you probably can get more accurate results by using a better RNG. Also note that 32000 was the maximum results I could graph with this tool, but my test tool was able to generate over 500 million results with the same overall patterns.

You could do what is essentially a filter. Keep track of the past n events. The probability is the some of some filter applied to those events. The 0th filter is the base probability, if 0 then you dodged, if 1 you failed. Let's say the base was 25%, and the filter decreases by half each iteration. Your filter would then be:

[.25 .125 .0625 .03125] 

Feel free to continue if you wish. The overall probability of this scheme is slightly higher than the base probability of .25. In fact, the probability, given the same scheme, is (I'm calling x the real probability, p is the probability input):

x=p+(1-x)*(p/2+p/4+p/8)

Solving for x, one finds the answer is p(1+1/2+1/4+1/8)/(1+p(1/2+1/4+1/8), or for our given case, x=0.38461538461. But what you really want is to find p, given x. That turns out to be a more difficult problem. If you assumed an infinite filter, the problem becomes x+x*p=2*p, or p=x/(2-x). So increasing your filter, you could then solve for a number p which will on average give you the same results, but at a rate dependent on how much success has recently happened.

Basically, you use the previous values to determine what the acceptance threshold is this round, and take a random value. Then produce the next random value given the filter.

Just like you proposed yourself, one of the approaches to this is to implement a weighted random. The idea is to make a random number (or outcome) generator where weights and outcomes can be modified.

Here is an implementation of this in Java.

import java.util.Map;
import java.util.Random;

/**
 * A psuedorandom weighted outcome generator
 * @param <E> object type to return
 */
public class WeightedRandom<E> {

    private Random random;
    private Map<E, Double> weights;

    public WeightedRandom(Map<E, Double> weights) {
        this.random = new Random();
        this.weights = weights;
    }

    /**
     * Returns a random outcome based on the weight of the outcomes
     * @return
     */
    public E nextOutcome() {
        double totalweight = 0;

        // determine the total weigth
        for (double w : weights.values()) totalweight += w;

        // determine a value between 0.0 and the total weight
        double remaining = random.nextDouble() * totalweight;

        for (E entry : weights.keySet()) {
            // subtract the weight of this entry
            remaining -= weights.get(entry);

            // if the remaining is smaller than 0, return this entry
            if (remaining <= 0) return entry;
        }

        return null;
    }

    /**
     * Returns the weight of an outcome
     * @param outcome the outcome to query
     * @return the weight of the outcome, if it exists
     */
    public double getWeight(E outcome) {
        return weights.get(outcome);
    }

    /**
     * Sets the weight of an outcome
     * @param outcome the outcome to change
     * @param weight the new weigth
     */
    public void setWeight(E outcome, double weight) {
        weights.put(outcome, weight);
    }
}

EDIT In the case where you want to adjust the weights automatically, for example increase the chance of A when the result was B. You can either,

1. Change the behaviour of the nextOutcome() method, so it modifies the weight according to the result
2. Use setWeight() to modify the weight of according to the result.