Como criar um gerador "aleatório" influenciado por eventos anteriores?

37

Eu estou olhando para implementar um sistema baseado em chance que é tendencioso por evento anterior.

Antecedentes: Alguns anos atrás, lembro-me de uma atualização para o World of Warcraft anunciando que eles implementavam uma nova calculadora de chances que contrariava cadeias pontuais de eventos. (por exemplo, fazendo ataques críticos ou esquivando-se várias vezes seguidas). A idéia era que, no caso de você desviar de um golpe, a chance de evitar o próximo golpe seria diminuída, mas funcionaria nos dois sentidos. Não se esquivar de um golpe aumentaria igualmente a chance de se esquivar do próximo golpe. O principal truque aqui foi que, ao longo de várias tentativas, a chance de esquiva ainda corresponderia à porcentagem dada ao jogador em sua ficha de estatísticas.

Esse tipo de sistema me intrigou muito na época, e agora estou na situação de precisar de uma solução desse tipo.

Aqui estão os meus problemas:

  • Suponho que eu seria capaz de encontrar recursos on-line para implementar esse sistema, mas talvez eu não tenha as palavras relevantes para encontrá-lo.
  • Também preciso dessa abordagem para ajustar um sistema que não seja binomial (ou seja, dois resultados), mas que contenha 4 eventos mutuamente exclusivos.

Minha abordagem atual é semelhante à de um sistema de tickets de rifa. Quando ocorre um evento, altero os pesos em favor de todos os outros eventos. Isso poderia funcionar se os quatro eventos fossem igualmente prováveis, mas, no meu caso, precisam ser muito mais prevalentes. Mas como o evento predominante acontece com mais frequência, ele altera os pesos do outro muito mais do que o pretendido e não consigo encontrar os números para as alterações de peso necessárias para manter a contagem média de tickets em torno dos valores iniciais em que o evento foi realizado. dado.

Alguns indicadores de direção ou um exemplo claro seriam muito apreciados.

Sonaten
fonte
4
Se você deseja uma resposta sofisticada ou com muitas nuances, pode ter mais sorte perguntando no Mathematics.SE. Os matemáticos de lá estão à vontade para responder perguntas complicadas sobre probabilidade. math.stackexchange.com
Kevin - Restabelece Monica
11
PRNG
Jon
6
Uma alternativa ao site de Matemática, onde você provavelmente entenderá as respostas, é Programmers.SE . O design do algoritmo não é particularmente tópico no Math e você provavelmente precisará criar um design inicial para obter informações úteis.
Lilienthal
11
Concordo com Kevin e Lilienthal que você pode obter uma resposta melhor lá, mas lendo a resposta de mklingen, percebi que o que está sendo descrito aqui pode ser modelado como uma cadeia de Markov e que pode ser uma ferramenta útil para os desenvolvedores de jogos conhecerem. Vou tentar escrever isso com mais detalhes mais tarde.
Nwellcome
11
Como eu tenho executado os números em algumas das respostas aqui, estou descobrindo que existem várias restrições diferentes e que uma solução que resolve todas elas pode me tornar mais complexa do que o que você precisa. Alguns detalhes mais específicos do seu caso de uso podem ajudar a restringir as melhores opções. Por exemplo, as probabilidades de seus eventos são bastante semelhantes (por exemplo, 5 resultados diferentes com 20% de chance cada) ou muito diferentes (por exemplo, 10% de falha de 80% atingem 10% de crítico)? Deseja minimizar as execuções (por exemplo, 3 erros seguidos) ou aglomerados / esperas (por exemplo, 3 erros em 8 tentativas ou 20 tentativas antes de eu fazer uma crítica)?
DMGregory

Respostas:

19

Basicamente, o que você está pedindo é um gerador de eventos "semi-aleatório" que gere eventos com as seguintes propriedades:

  1. A taxa média na qual cada evento ocorre é especificada antecipadamente.

  2. É menos provável que o mesmo evento ocorra duas vezes seguidas do que aleatoriamente.

  3. Os eventos não são totalmente previsíveis.

Uma maneira de fazer isso é primeiro implementar um gerador de eventos não aleatórios que satisfaça os objetivos 1 e 2 e, em seguida, adicionar alguma aleatoriedade para satisfazer o objetivo 3.


Para o gerador de eventos não aleatórios, podemos usar um algoritmo de pontilhamento simples . Especificamente, sejam p 1 , p 2 , ..., p n as probabilidades relativas dos eventos 1 a n e s = p 1 + p 2 + ... + p n seja a soma dos pesos. Em seguida, podemos gerar uma sequência de eventos máxima não-aleatória equidistribuída usando o seguinte algoritmo:

  1. Inicialmente, deixe e 1 = e 2 = ... = e n = 0.

  2. Para gerar um evento, incrementar cada e i por p i , ea saída do evento k para o qual e k é maior (quebrando os laços da maneira que quiser).

  3. Decremento e k por s e repetição do passo 2.

Por exemplo, dados três eventos A, B e C, com p A = 5, p B = 4 ep C = 1, esse algoritmo gera algo como a seguinte sequência de saídas:

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

Observe como essa sequência de 30 eventos contém exatamente 15 As, 12 Bs e 3 Cs. Não é bastante otimizada distribui - há algumas ocorrências de dois Como em uma fileira, o que poderia ter sido evitado - mas chega perto.


Agora, para adicionar aleatoriedade a essa sequência, você tem várias opções (não necessariamente mutuamente exclusivas):

  • Você pode seguir o conselho de Philipp e manter um "deck" de N eventos futuros, para um número N de tamanho apropriado . Toda vez que você precisa gerar um evento, escolhe um evento aleatório no baralho e o substitui pela próxima saída de evento pelo algoritmo de pontilhamento acima.

    A aplicação disso no exemplo acima, com N = 3, produz, por exemplo:

    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

    enquanto N = 10 produz a aparência mais aleatória:

    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

    Observe como os eventos comuns A e B terminam com muito mais execuções devido ao embaralhamento, enquanto os eventos C raros ainda são razoavelmente bem espaçados.

  • Você pode injetar alguma aleatoriedade diretamente no algoritmo de pontilhamento. Por exemplo, em vez de incrementar e i por p i na etapa 2, você pode incrementá-lo por p i × aleatório (0, 2), onde aleatório ( a , b ) é um número aleatório distribuído uniformemente entre a e b ; isso produziria uma saída como a seguinte:

    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

    ou você pode incrementar e i por p i + aleatório (- c , c ), o que produziria (para 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

    ou, para c = 0,5 × s :

    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

    Observe como o esquema aditivo tem um efeito aleatório muito mais forte para os eventos raros C do que para os eventos comuns A e B, em comparação com o evento multiplicativo; isso pode ou não ser desejável. Obviamente, você também pode usar alguma combinação desses esquemas ou qualquer outro ajuste nos incrementos, desde que preserve a propriedade de que o incremento médio de e i é igual a p i .

  • Como alternativa, você pode perturbar a saída do algoritmo de pontilhamento, substituindo algumas vezes o evento escolhido k por um aleatório (escolhido de acordo com os pesos brutos p i ). Desde que você também use o mesmo k na etapa 3 e emita na etapa 2, o processo de pontilhamento ainda tenderá a uniformizar as flutuações aleatórias.

    Por exemplo, aqui está um exemplo de saída, com 10% de chance de cada evento ser escolhido aleatoriamente:

    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

    e aqui está um exemplo com 50% de chance de cada saída ser aleatória:

    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

    Também poderia considerar que alimenta uma mistura de eventos puramente aleatórios e pontilhadas numa plataforma / piscina de mistura, como descrito acima, ou talvez randomizar o algoritmo pontilhado escolhendo k aleatoriamente, como pesadas pelo e i s (tratamento de pesos negativos como zero).

Ps. Aqui estão algumas sequências de eventos completamente aleatórias, com as mesmas taxas médias, para comparação:

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

Tangente: Como houve um debate nos comentários sobre se é necessário, para soluções baseadas em decks, permitir que o deck esvazie antes de ser reabastecido, decidi fazer uma comparação gráfica de várias estratégias de preenchimento de decks:

Enredo
Traçar várias estratégias para gerar lançamentos de moedas semi-aleatórios (com proporção de 50:50 de cara para coroa), em média. Eixo horizontal é o número de inversões, o eixo vertical é a distância cumulativa da razão esperada, medida como (cara - coroa) / 2 = cara - coroa / 2.

As linhas vermelha e verde no gráfico mostram dois algoritmos não baseados em baralho para comparação:

  • Linha vermelha, pontilhamento determinístico : resultados pares são sempre cabeças, resultados pares são sempre caudas.
  • Linha verde, inversões aleatórias independentes : cada resultado é escolhido de forma independente e aleatória, com 50% de chance de cara e 50% de chance de coroa.

As outras três linhas (azul, roxo e ciano) mostram os resultados de três estratégias baseadas no baralho, cada uma implementada usando um baralho de 40 cartas, que é inicialmente preenchido com 20 cartas "chefes" e 20 cartas "caudas":

  • Linha azul, preenchida quando vazia : as cartas são sorteadas aleatoriamente até que o baralho esteja vazio e, em seguida, o baralho é reabastecido com 20 cartas "cara" e 20 cartas "caudas".
  • Linha roxa, preencha quando estiver meio vazio : as cartas são sorteadas aleatoriamente até o baralho ter 20 cartas sobrando; então o baralho é complementado com 10 cartas "cara" e 10 cartas "coroa".
  • Linha ciana, preenchimento contínuo : as cartas são sorteadas aleatoriamente; os draws com números pares são imediatamente substituídos por uma carta "heads" e os draws com números ímpares com uma carta "tails".

Obviamente, o gráfico acima é apenas uma realização de um processo aleatório, mas é razoavelmente representativo. Em particular, você pode ver que todos os processos baseados em baralho têm um viés limitado e permanecem razoavelmente perto da linha vermelha (determinística), enquanto a linha verde puramente aleatória acaba se afastando.

(De fato, o desvio das linhas azul, roxa e ciana do zero é estritamente limitado pelo tamanho do baralho: a linha azul nunca pode se afastar mais de 10 passos do zero, a linha roxa pode apenas 15 passos do zero e a linha ciana pode se afastar no máximo 20 passos do zero.Claro, na prática, qualquer uma das linhas que realmente atingem seu limite é extremamente improvável, pois há uma forte tendência para que elas retornem mais perto de zero se vagarem muito longe fora.)

À primeira vista, não há diferença óbvia entre as diferentes estratégias baseadas no baralho (embora, em média, a linha azul fique um pouco mais próxima da linha vermelha e a linha ciana fique um pouco mais distante), mas uma inspeção mais detalhada da linha azul revela um padrão determinístico distinto: a cada 40 desenhos (marcados pelas linhas verticais cinza pontilhadas), a linha azul encontra exatamente a linha vermelha no zero. As linhas roxa e ciana não são tão estritamente restritas e podem ficar longe de zero a qualquer momento.

Para todas as estratégias baseadas no baralho, o recurso importante que mantém a variação limitada é o fato de que, embora as cartas sejam retiradas aleatoriamente do baralho, o baralho é reabastecido deterministicamente. Se as cartas usadas para recarregar o baralho fossem escolhidas aleatoriamente, todas as estratégias baseadas no baralho se tornariam indistinguíveis da escolha aleatória pura (linha verde).

Ilmari Karonen
fonte
Resposta muito elaborada. A adição de fatores aleatórios ao algoritmo de pontilhamento parece direta. :)
Sonaten
Decidiu ir com sua resposta. :) Mas eu recomendo que você coloque as adições da visão geral do método no topo. O que vou fazer, com base na sua resposta, é tentar a solução "Vermelha" e "Roxa".
Sonaten 5/03/2015
53

Não jogue dados, jogue cartas.

Pegue todos os resultados possíveis do seu RNG, coloque-os em uma lista, embaralhe-os aleatoriamente e retorne os resultados na ordem aleatória. Quando você estiver no final da lista, repita.

Os resultados ainda serão distribuídos uniformemente, mas os resultados individuais não serão repetidos, a menos que o último da lista também seja o primeiro do próximo.

Quando isso é um pouco previsível para o seu gosto, você pode usar uma lista com no número de resultados possíveis e colocar cada resultado possível nela nantes de embaralhar. Ou você pode reorganizar a lista antes que ela seja iterada completamente.

Philipp
fonte
11
pesquisa "shuffle bag" (até neste site)
jhocking 25/02
3
É assim que muitos jogos de Tetris evitam deixar o jogador faminto por peças importantes por muito tempo. É importante esvaziar o saco / baralho, como Philipp sugere antes de inserir novos cartões, se você quiser controlar as ocorrências durante um intervalo definido. Ao reinserir os cartões à medida que avança (ou reajustar pesos), você pode distorcer a distribuição de probabilidade de maneiras difíceis de calcular e fáceis de errar.
DMGregory
2
@DMGregory: Na verdade, é perfeitamente bom misturar novas cartas antes do baralho ser esvaziado (e, de fato, eu recomendaria fazer isso para tornar os resultados mais naturais e difíceis de prever). O importante é ter certeza de que a fração (média) de novos cartões arrastou para o convés é igual a fração desejado que você quer desenhar fora dele.
Ilmari Karonen
4
Illmari Karonen: ao substituir itens, você pode perder os benefícios da bolsa aleatória em termos de limitação de execuções de resultados idênticos ou longas lacunas entre resultados específicos. Se a sua taxa de substituição for igual à distribuição de probabilidade desejada, você estará provavelmente na mesma posição de gerar cada resultado independentemente de forma aleatória. Se não for igual à distribuição de probabilidade desejada, você poderá distorcer as probabilidades efetivas de maneiras difíceis de prever e equilibrar de acordo - o solicitante descreve a dificuldade com exatamente esse problema.
DMGregory
2
Concordou com @DMGregory. Ao embaralhar novas cartas, você invalida o próprio sistema. O sistema de distribuição de cartas é específico e perfeitamente adequado ao resultado desejado. Por exemplo, quando você remove uma rainha (para usar cartões tradicionais, por exemplo) a partir do convés, a probabilidade de desenhar uma rainha diminui, ea probabilidade de desenhar um cartão de outro do que uma rainha aumenta. É um sistema de auto-ajuste, se você preferir.
Volte 27/02
17

Você pode tentar um gráfico aleatório de Markov . Considere cada evento que pode ocorrer como um nó em um gráfico. Em cada evento, faça um link para o outro evento que possa vir depois dele. Cada um desses links é ponderado por algo chamado probabilidade de transição . Em seguida, você executa uma caminhada aleatória do gráfico de acordo com o modelo de transição.

Por exemplo, você pode ter um gráfico que represente o resultado de um ataque (acerto crítico, esquiva etc.). Inicialize o nó inicial com um escolhido aleatoriamente, de acordo com as estatísticas do jogador (basta "rolar os dados"). Em seguida, no próximo ataque, decida o que acontecerá em seguida, dado o modelo de transição.

É necessário tomar cuidado para decidir como ponderar as transições. Por um lado, todas as transições que saem de um nó precisam somar uma probabilidade de 1. Uma coisa simples que você pode fazer é fazer uma transição de cada nó para outro nó, com pesos equivalentes à probabilidade de que esses eventos ocorram a priori , dado que o evento atual não pode ocorrer novamente.

Por exemplo, se você tiver três eventos:

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

Você pode configurar o modelo de transição para que um acerto crítico não ocorra novamente simplesmente redistribuindo sua massa de probabilidade para os outros eventos de maneira uniforme:

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

Edição: Como os comentários dizem abaixo, este modelo não é complicado o suficiente para obter o comportamento desejado. Em vez disso, pode ser necessário adicionar vários estados adicionais!

mklingen
fonte
11
O esquema de ponderação que você propõe não preserva as probabilidades desejadas para cada estado. Fazendo um teste empírico com esses números, as perdas acontecem cerca de 41% das vezes e os críticos cerca de 25%, bem longe dos valores de entrada. A transição para os estados restantes proporcionalmente às suas probabilidades (por exemplo, Miss tem 25% de chance de ir para Crit e 75% de chance de acertar) se sai um pouco melhor, com uma taxa de 44% de Miss e 17% de Crit, mas ainda é não reflete as probabilidades desejadas na entrada.
DMGregory
Eu esqueci a regra dos bayes :( Será recalculado novamente mais tarde. Pode não ser possível manter a distribuição de probabilidade anterior, porque o modelo de transição como está deixa de fora possíveis sequências como CCHM ou CHHM ou o muito provável MMHM, etc.
mklingen
A restrição "não repita" pode amarrar suas mãos aqui, no que diz respeito a pesos extremos altos e baixos. Se você deseja que 1 em 10 tentativas seja Crítica, a única maneira de obter esse método é alternar 5 Misses e 5 hits, o que distorce as probabilidades de hits e erros em relação à média. Nenhuma sequência sem erros consecutivos pode satisfazer os requisitos da entrada aqui.
DMGregory
4
@mklingen, eu concordo com o DMGregory, o "estritamente sem repetições" não é desejável aqui. Em vez disso, eles querem que a probabilidade de cadeias longas do mesmo resultado seja menos provável do que seria com uma probabilidade aleatória uniforme. Você pode fazer isso com uma cadeia de Markov (que é direcionada) que se parece com isso . Isso usa vários estados para representar eventos repetidos, onde as probabilidades de fazer a transição de "Hit 1" para "Hit 2" e "Hit 2" para "Hit 3+" diminuem e as probabilidades de fazer a transição de volta para "Hit 1" e "Crit 1 "subir.
Nwellcome
@nwellcome é uma ótima idéia.
26615 mklingen
3

Aqui está uma implementação que eu criei em C # que:

  • Ativar eventos com base em probabilidades
  • Ajuste essas probabilidades para diminuir as chances de eventos recorrentes
  • Não está muito longe das probabilidades originais

Adicionei alguns comentários para que você possa ver o que estou fazendo.

    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.
    }

Espero que isso ajude, por favor, sugerir melhorias para este código nos comentários, obrigado!

Superdoggy
fonte
11
Esse esquema de reponderação tende a levar os eventos a serem equivalentes. Redefinir os pesos periodicamente é realmente apenas um band-aid que limita o quanto fica ruim, garantindo que 1 em cada 10 lançamentos não obtenha nenhum benefício com a reponderação. Além disso, uma observação do algoritmo: você está desperdiçando muito trabalho preenchendo uma tabela de 100 entradas para fazer sua seleção aleatória. Em vez disso, você pode gerar um teste aleatório e repetir seus 4 resultados, somando as probabilidades à medida que avança. Assim que a rolagem for menor que a soma, você terá o seu resultado. Não é necessário preenchimento de mesa.
DMGregory
3

Deixe-me generalizar um pouco a resposta de mklingen . Basicamente, você deseja implementar a falácia do jogador , embora eu forneça um método mais geral aqui:

Digamos que haja neventos possíveis com probabilidades p_1, p_2, ..., p_n. Quando o evento iaconteceu, sua probabilidade será redimensionada com um fator 0≤a_i≤1/p_i(o último é importante, caso contrário, você terá uma probabilidade maior que um e os outros eventos deverão ter probabilidades negativas , o que basicamente significa " anti ". Ou algo assim), embora tipicamente a_i<1. Você pode, por exemplo a_i=p_i, escolher , o que significa que a probabilidade de um evento acontecer uma segunda vez é a probabilidade original de que o evento aconteça exatamente duas vezes seguidas, por exemplo, um segundo sorteio teria uma probabilidade de 1/4 em vez de 1/2. Por outro lado, você também pode ter alguns a_i>1, o que significaria desencadear um "golpe de sorte / infortúnio".

Todos os outros eventos devem permanecer igualmente prováveis ​​em relação um ao outro, ou seja, todos devem ser redimensionados pelo mesmo fator b_i modo que a soma de todas as probabilidades seja igual a um, ou seja,

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)

Até agora, tão simples. Mas agora vamos adicionar outro requisito: Considerando todas as seqüências possíveis de dois eventos, as probabilidades de evento único extraídas delas devem ser as probabilidades originais.

Deixei

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

denote a probabilidade de um evento jacontecer após um evento ie observe que, a p_ij≠p_jimenos que b_i=b_j (2)(o que (1)implica a_j = 1 - a_i*p_i + (1-a_i)*p_i/p_j). Isso também é o que o teorema de Bayes exige e também implica

Σ_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)

apenas como desejado. Apenas observe como isso significaa_i corrige todos os outros.


Agora vamos ver o que acontece quando aplicamos esse procedimento várias vezes, ou seja, para seqüências de três ou mais eventos. Existem basicamente duas opções para a escolha das probabilidades fraudulentas do terceiro evento:

a) Esqueça o primeiro evento e monte como se apenas o segundo tivesse ocorrido,

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

Observe que isso geralmente viola Bayes, uma vez que, por exemplo, p_jik≠p_ikjna maioria dos casos.

b) Use as probabilidades p_ij(para fixas i) como novas probabilidades a pi_jpartir das quais você obtém as novas probabilidades pi_jkde que o evento kaconteça a seguir. A decisão de modificar ai_jou não depende de você, mas esteja ciente de que as novas bi_jsão definitivamente diferentes devido à modificação pi_j. Por outro lado, a escolha de ai_jprovavelmente é restrita, exigindo todas as permutações de ijkocorrência com a mesma probabilidade. Vamos ver...

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

         / b_i * bi_j * p_i * p_j * pi_k  (ijki)
         | b_i * ai_j * p_i * (p_j      (ij=k)
      = <  a_i * (p_i * bi_i * pi_k     (i=jk)
         | b_i * p_i * bi_j * p_k * pi_i  (i=kj)
         \ a_i * ai_i * (p_i * pi_i     (i=k=j)

e permutações cíclicas dos mesmos, que devem ser iguais para os respectivos casos.

Receio que minha continuação disso tenha que esperar um pouco ...

Tobias Kienzler
fonte
Testando isso empiricamente, isso ainda resulta em uma distorção das probabilidades de entrada em muitas execuções. Se a_i / p_i = 0,5, por exemplo, (e usando números da resposta de mklingen), uma taxa de erro de entrada de 60% se torna uma taxa observada de 50,1%, e uma taxa crítica de entrada de 10% é observada em 13,8%. Você pode verificar isso levando a matriz de transição resultante a uma alta potência. Escolher proporções de a_i: p_i mais próximas de 1 resulta em menos distorção, mas também em menos eficácia na redução de execuções.
DMGregory
@DMGregory good point: você não pode simplesmente assumir os poderes da matriz de transição. Expandirei minha resposta mais tarde sobre isso
Tobias Kienzler 27/02
@DMGregory Comecei a descrever o processo completo (variante b)), mas fica bastante tedioso e atualmente estou com pouco tempo: /
Tobias Kienzler
1

Eu acho que a melhor opção é usar a seleção de itens com peso aleatório. Há uma implementação para C # aqui , mas eles podem ser facilmente encontrados ou criados para outros idiomas.

A idéia seria reduzir o peso de uma opção toda vez que ela é escolhida e aumentá-la toda vez que não é escolhida.

Por exemplo, se você diminuir o peso da opção selecionada NumOptions-1e aumentar o peso de todas as outras opções em 1 (cuidado para remover itens com peso <0 e lê-los quando eles ultrapassarem 0) , todas as opções serão selecionadas aproximadamente o mesmo número de vezes durante um longo período, mas as opções escolhidas recentemente terão muito menos probabilidade de serem escolhidas.


O problema do uso de uma ordem aleatória, conforme sugerido por muitas outras respostas, é que, após cada opção, mas uma foi escolhida, é possível prever com 100% de certeza qual opção será escolhida a seguir. Isso não é muito aleatório.

BlueRaja - Danny Pflughoeft
fonte
1

Minha resposta está incorreta, meu teste falhou.

Estou deixando esta resposta aqui para a discussão e comentários que apontam as falhas neste design, mas o teste real estava incorreto.

O que você procura é um peso ponderado: os pesos para seus quatro resultados possíveis precisam ser mais ajustados (ponderados) pelos resultados anteriores, enquanto ainda permanecem os pesos adequados em geral.

A maneira mais fácil de fazer isso é alterar todos os pesos de cada rolo, diminuindo o peso do valor específico rolado e aumentando os outros pesos .

Como exemplo, digamos que você tenha 4 pesos: Fumble, Miss, Hit e Crit. Vamos também dizer que os pesos gerais desejados para eles são Fumble = 10%, Miss = 50%, Hit = 30% e Crit = 10%.

Se você usar um gerador de números aleatórios (RNG) para produzir valores entre 1 e 100 e comparar esse valor com o local em que está dentro desse intervalo (1-10 Fumble, 11-60 miss, 61-90 hit, 91-100 crit ), você está gerando um rolo individual.

Se, ao fazer essa rolagem, você imediatamente ajustar esses intervalos com base no valor rolado, ponderará as rolagens futuras, mas também precisará reduzir o peso rolado pela mesma quantidade total em que você aumenta os outros pesos. Portanto, em nosso exemplo acima, você reduziria o peso rolado em 3 e aumentaria os outros pesos em 1 cada.

Se você fizer isso para cada rolagem, ainda terá chances de riscos, mas eles serão bastante reduzidos, porque a cada rolagem você aumenta a chance de rolagens futuras serem algo diferente do rol atual. Você pode aumentar esse efeito e, assim, reduzir ainda mais a chance de riscos, aumentando / diminuindo os pesos por um fator maior (por exemplo, reduzir a corrente em 6 e aumentar os outros em 2).

Eu executei um aplicativo rápido para validar essa abordagem e, após 32000 iterações com esses pesos, ele produz os seguintes gráficos. O gráfico superior mostra os valores imediatos de 4 pesos em cada rolo, e o gráfico inferior mostra a contagem da soma de cada tipo de resultado acumulado até esse ponto.

Como você pode ver, os pesos flutuam levemente em torno dos valores desejados, mas os pesos gerais permanecem dentro dos limites desejados e, após o estabelecimento da variedade inicial dos números iniciais, os resultados se ajustam quase perfeitamente às porcentagens desejadas.

Observe que este exemplo foi produzido usando a classe .NET System.Random, que não é realmente um dos melhores RNGs existentes no mercado, portanto, você provavelmente poderá obter resultados mais precisos usando um RNG melhor. Observe também que 32000 foram os resultados máximos que pude representar graficamente com essa ferramenta, mas minha ferramenta de teste foi capaz de gerar mais de 500 milhões de resultados com os mesmos padrões gerais.

David C Ellis
fonte
Observe que isso só funciona se os seus + 1s / -3s forem aplicados em relação aos pesos originais, em vez dos pesos usados ​​mais recentemente. (Modificar continuamente os pesos de maneira uniforme assim os leva a ser equiprobáveis). Embora isso mantenha a probabilidade no alvo a longo prazo, faz muito pouco para reduzir as execuções. Dado que perdi uma vez, a chance de perder mais duas vezes seguidas é de 22% com esse esquema, contra 25% com empates independentes. Aumentar a mudança de peso para obter um efeito maior (digamos +3 / -9) resulta na distorção da probabilidade de longo prazo.
DMGregory
Na verdade, os dados apresentados acima aplicam o +1 / -3 ao peso mais recente cada vez que um rolo é processado. Portanto, se você perder uma vez no peso inicial de 50%, o próximo peso de perda será de 47% e se você perder de novo, o peso a seguir será de 44% e assim por diante. Reduz as execuções (a métrica separada foi rastrear execuções, encontrada até uma redução de 24% nas execuções), mas elas ainda são inevitáveis, pois esse esquema ainda tem uma grande chance de deixar cada um dos quatro pesos com uma probabilidade diferente de zero ( por exemplo, quatro crits consecutivos deixariam o peso crítico com zero chance de ocorrer).
David C Ellis
Se essa era sua intenção, sua implementação tem um erro. Veja o gráfico - O peso do fumble apenas oscila entre 7 e 11, sem valores fora disso. Fiz uma simulação usando a modificação contínua que você descreve, e os gráficos são drasticamente diferentes, com as probabilidades de cada estado convergindo para 25% cada uma nas primeiras cem tentativas.
DMGregory
Dangit, na verdade, foi bugado como você apontou. Bem, acerte essa resposta.
David C Ellis
@DavidCEllis você está dizendo que sua implementação foi falha ou a ideia em si é? Minha intuição de volta ao guardanapo chegou aproximadamente ao modelo que você descreve (ajustar uma probabilidade quando desenhada, gradualmente restaura todas as probabilidades aos seus valores originais ao longo do tempo) e ainda faz sentido para mim.
dimo414
0

Você poderia fazer o que é essencialmente um filtro. Acompanhe os últimos n eventos. A probabilidade é de alguns filtros aplicados a esses eventos. O 0º filtro é a probabilidade básica, se 0, você se esquivou, se 1, você falhou. Digamos que a base seja de 25% e o filtro diminua pela metade a cada iteração. Seu filtro seria então:

[.25 .125 .0625 .03125] 

Sinta-se livre para continuar, se desejar. A probabilidade geral desse esquema é um pouco maior que a probabilidade básica de 0,25. De fato, a probabilidade, dado o mesmo esquema, é (estou chamando x de probabilidade real, p é a entrada de probabilidade):

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

Resolvendo para x, encontra-se a resposta p(1+1/2+1/4+1/8)/(1+p(1/2+1/4+1/8)ou, para o nosso caso x=0.38461538461,. Mas o que você realmente quer é encontrar p, dado x. Isso acaba sendo um problema mais difícil. Se você assumiu um filtro infinito, o problema se torna x+x*p=2*p, ou p=x/(2-x). Assim, aumentando seu filtro, você poderia resolver um número p que, em média, fornecerá os mesmos resultados, mas a uma taxa dependente de quanto sucesso aconteceu recentemente.

Basicamente, você usa os valores anteriores para determinar qual é o limite de aceitação nesta rodada e usa um valor aleatório. Em seguida, produza o próximo valor aleatório, considerando o filtro.

PearsonArtPhoto
fonte
-1

Assim como você se propôs, uma das abordagens para isso é implementar uma aleatória ponderada. A idéia é criar um gerador de número aleatório (ou resultado) onde pesos e resultados possam ser modificados.

Aqui está uma implementação disso em 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 No caso em que você deseja ajustar os pesos automaticamente, por exemplo, aumente a chance de A quando o resultado for B. Você também pode,

  1. Altere o comportamento do nextOutcome()método, para que ele modifique o peso de acordo com o resultado
  2. Use setWeight()para modificar o peso de acordo com o resultado.
erikgaal
fonte
Acho que você pode ter interpretado mal a pergunta: o OP não está perguntando como gerar resultados aleatórios ponderados, mas como ajustar os pesos para reduzir a probabilidade de o mesmo resultado ocorrer várias vezes seguidas.
Ilmari Karonen
Entendo, mudei algumas das minhas respostas para explicar como isso seria possível usando este sistema.
22415 erikgaal