Necessidade de gerador aleatório previsível

Sou desenvolvedor de jogos na web e tenho um problema com números aleatórios. Digamos que um jogador tenha 20% de chance de receber um acerto crítico com sua espada. Isso significa que 1 em cada 5 ocorrências deve ser crítico. O problema é que obtive resultados muito ruins na vida real - às vezes os jogadores recebem 3 crits em 5 hits, às vezes nenhum em 15 hits. As batalhas são bastante curtas (3-10 acertos), por isso é importante obter uma boa distribuição aleatória.

Atualmente eu uso PHP mt_rand(), mas estamos apenas movendo nosso código para C ++, então quero resolver esse problema no novo mecanismo de nosso jogo.

Não sei se a solução é um gerador aleatório uniforme, ou talvez para lembrar estados aleatórios anteriores para forçar a distribuição adequada.

Concordo com as respostas anteriores de que a aleatoriedade real em pequenas execuções de alguns jogos é indesejável - parece injusta demais para alguns casos de uso.

Eu escrevi um Shuffle Bag simples como implementação em Ruby e fiz alguns testes. A implementação fez o seguinte:

• Se ainda parecer justo ou não tivermos atingido um limite de jogadas mínimas, ele retornará um acerto justo com base na probabilidade normal.
• Se a probabilidade observada de jogadas passadas fizer com que pareça injusta, ela retornará um acerto "justo".

É considerado injusto com base nas probabilidades de fronteira. Por exemplo, para uma probabilidade de 20%, você pode definir 10% como limite inferior e 40% como limite superior.

Usando esses limites, descobri que, com execuções de 10 ocorrências, 14,2% do tempo, a verdadeira implementação pseudoaleatória produzia resultados que estavam fora desses limites . Cerca de 11% das vezes, 0 acertos críticos foram marcados em 10 tentativas. 3,3% das vezes, 5 ou mais acertos críticos foram atingidos em 10. Naturalmente, usando esse algoritmo (com uma contagem mínima de rolagem de 5), uma quantidade muito menor (0,03%) das execuções "Fairish" estava fora dos limites . Mesmo que a implementação abaixo seja inadequada (coisas mais inteligentes podem ser feitas, certamente), vale a pena notar que, notavelmente, com frequência, seus usuários sentem que é injusto com uma solução pseudo-aleatória real.

Aqui está a carne do meu FairishBagescrito em Ruby. Toda a implementação e a rápida simulação de Monte Carlo estão disponíveis aqui (essência) .

def fire!
  hit = if @rolls >= @min_rolls && observed_probability > @unfair_high
    false
  elsif @rolls >= @min_rolls && observed_probability < @unfair_low
    true
  else
    rand <= @probability
  end
  @hits += 1 if hit
  @rolls += 1
  return hit
end

def observed_probability
  @hits.to_f / @rolls
end

Atualização: o uso desse método aumenta a probabilidade geral de obter um acerto crítico, para cerca de 22% usando os limites acima. Você pode compensar isso definindo sua probabilidade "real" um pouco menor. Uma probabilidade de 17,5% com a modificação fairish gera uma probabilidade de longo prazo observada de cerca de 20%, e mantém as corridas de curto prazo se sentindo justas.

Isso significa que 1 em cada 5 ocorrências deve ser crítico. O problema é que obtive resultados muito ruins na vida real - às vezes os jogadores recebem 3 crits em 5 hits, às vezes nenhum em 15 hits.

O que você precisa é de uma sacola aleatória . Resolve o problema do verdadeiro aleatório ser muito aleatório para os jogos.

O algoritmo é mais ou menos assim: você coloca 1 acerto crítico e 4 não críticos em um saco. Então você escolhe aleatoriamente o pedido na sacola e escolhe uma de cada vez. Quando a sacola estiver vazia, você a preenche novamente com os mesmos valores e a randomiza. Dessa forma, você obterá em média 1 acerto crítico por 5 acertos e, no máximo, 2 acertos críticos e 8 não críticos seguidos. Aumente o número de itens na sacola para mais aleatoriedade.

Aqui está um exemplo de implementação (em Java) e seus casos de teste que escrevi há algum tempo.

Você entendeu errado o que significa aleatório.

Qual destes é mais aleatório?

Enquanto o segundo gráfico parece distribuído de maneira mais uniforme, o mais aleatório é realmente o primeiro gráfico. A mente humana geralmente vê padrões aleatórios, então vemos os grupos no primeiro gráfico como padrões, mas não são - são apenas parte de uma amostra selecionada aleatoriamente.

Dado o comportamento que você está pedindo, acho que você está randomizando a variável errada.

Em vez de escolher aleatoriamente se esse acerto será crítico, tente escolher o número de turnos até o próximo acerto crítico ocorrer. Por exemplo, escolha um número entre 2 e 9 toda vez que o jogador fizer uma crítica e, em seguida, faça a próxima crítica depois que muitas rodadas tiverem passado. Você também pode usar métodos de dados para se aproximar de uma distribuição normal - por exemplo, você terá sua próxima crítica nos turnos 2D4.

Acredito que essa técnica seja usada em RPGs que também têm encontros aleatórios no mundo superior - você aleatoriamente um contador de passos e, depois de muitos passos, é atingido novamente. Parece muito mais justo, porque você quase nunca é atingido por dois encontros seguidos - se isso acontecer uma vez, os jogadores ficam irritados.

Primeiro, defina a distribuição "adequada". Números aleatórios são, bem, aleatórios - os resultados que você está vendo são inteiramente consistentes com a (pseudo) aleatoriedade.

Expandindo isso, presumo que o que você deseja é um sentimento de "justiça", para que o usuário não possa fazer 100 voltas sem sucesso. Nesse caso, eu acompanharia o número de falhas desde o último sucesso e ponderaria o resultado gerado. Vamos supor que você queira que 1 em 5 rolos seja "bem-sucedido". Então, você gera aleatoriamente um número de 1 a 5 e, se for 5, ótimo.

Caso contrário, registre a falha e, da próxima vez, gere um número de 1 a 5, mas adicione, por exemplo, floor (numFailures / 2). Então, desta vez, novamente, eles têm uma chance de 1 em 5. Se eles falharem, na próxima vez que o intervalo vencedor for 4 e 5; uma chance de 2 em 5 de sucesso. Com essas opções, após 8 falhas, elas certamente terão sucesso.

Que tal substituir mt_rand () por algo assim?

(RFC 1149.5 especifica 4 como o número aleatório padrão verificado pelo IEEE.)

Do XKCD .

Espero que este artigo o ajude: http://web.archive.org/web/20090103063439/http://www.gamedev.net:80/reference/design/features/randomness/

Esse método de geração de 'números aleatórios' é comum em jogos de rpg / mmorpg.

O problema que resolve é este (extrato):

Uma aranha-lâmina está na sua garganta. Acerta e você sente falta. Ele bate novamente e você sente falta novamente. E de novo e de novo, até que não haja mais nada para você acertar. Você está morto e há um aracnídeo de duas toneladas se vangloriando de seu cadáver. Impossível? Não. Improvável? Sim. Mas, com jogadores suficientes e tempo suficiente, o improvável se torna quase certo. Não era que a aranha da lâmina estivesse dura, era apenas azar. Que frustrante. É o suficiente para fazer um jogador querer desistir.

O que você quer não são números aleatórios, mas números que parecem aleatórios para um humano. Outros já sugeriram algoritmos individuais, que podem ajudá-lo, como Shuffle Bad.

Para uma boa análise detalhada e extensa desse domínio, consulte AI Game Programming Wisdom 2 . Vale a pena ler todo o livro para qualquer desenvolvedor de jogos; a idéia de "números aparentemente aleatórios" é tratada no capítulo:

Aleatoriedade filtrada para decisões de IA e lógica de jogo :

Resumo: A sabedoria convencional sugere que, quanto melhor o gerador de números aleatórios, mais imprevisível será o seu jogo. No entanto, de acordo com estudos de psicologia, a verdadeira aleatoriedade a curto prazo muitas vezes parece decididamente incomum para os seres humanos. Este artigo mostra como fazer com que decisões aleatórias de IA e lógica de jogo pareçam mais aleatórias para os jogadores, mantendo uma forte aleatoriedade estatística.

Você também pode encontrar outro capítulo interessante:

Estatísticas de números aleatórios

Resumo: Os números aleatórios são mais utilizados pela Inteligência Artificial e pelos jogos em geral. Ignorar seu potencial é tornar o jogo previsível e chato. Usá-los incorretamente pode ser tão ruim quanto ignorá-los completamente. Compreender como os números aleatórios são gerados, suas limitações e recursos, pode remover muitas dificuldades de usá-los no seu jogo. Este artigo oferece informações sobre números aleatórios, sua geração e métodos para separar os bons dos ruins.

Certamente qualquer geração de números aleatórios tem a chance de produzir tais execuções? Você não obterá uma amostra grande o suficiente em 3 a 10 rolos para ver as porcentagens apropriadas.

Talvez o que você queira seja um limiar de misericórdia ... lembre-se dos últimos 10 lançamentos e, se eles não tiveram um golpe crítico, dê a eles um brinde. Alise as fundas e flechas da aleatoriedade.

Sua melhor solução pode ser testar com vários esquemas não aleatórios diferentes e escolher o que torna os jogadores mais felizes.

Você também pode tentar uma política de retirada para o mesmo número em um determinado encontro, por exemplo, se um jogador jogar um 1no primeiro turno, aceitá-lo. Para obter outro, 1eles precisam rolar 2 1s seguidos. Para obter um terceiro, 1eles precisam de 3 em sequência, ad infinitum.

Infelizmente, o que você está solicitando é efetivamente um gerador de números não aleatórios - porque você deseja que os resultados anteriores sejam levados em consideração ao determinar o próximo número. Não é assim que funcionam os geradores de números aleatórios.

Se você quiser que 1 em cada 5 hits seja crítico, basta escolher um número entre 1 e 5 e dizer que esse hit será crítico.

O mt_rand () é baseado em uma implementação do Mersenne Twister , o que significa que gera uma das melhores distribuições aleatórias que você pode obter.

Aparentemente, o que você deseja não é aleatoriedade, então você deve começar especificando exatamente o que deseja. Você provavelmente perceberá que tem expectativas conflitantes - que os resultados devem ser verdadeiramente aleatórios e não previsíveis, mas, ao mesmo tempo, não devem exibir variações locais a partir da probabilidade declarada -, mas se tornam previsíveis. Se você definir um máximo de 10 não-créditos consecutivos, então você acabou de dizer aos jogadores "se você teve 9 não-créditos consecutivos, o próximo será crítico com 100% de certeza" - você pode bem, não se preocupe com a aleatoriedade.

Em um número tão pequeno de testes, você deve esperar resultados assim:

A verdadeira aleatoriedade só é previsível em um tamanho enorme, de tal forma que é bem possível jogar uma moeda e ganhar cara três vezes seguidas pela primeira vez, no entanto, após alguns milhões de lançamentos, você terá aproximadamente 50-50.

Vejo muitas respostas sugerindo acompanhar os números gerados anteriormente ou embaralhar todos os valores possíveis.

Pessoalmente, eu não concordo, que 3 créditos consecutivos são ruins. Nem concordo que 15 não-crits seguidos sejam ruins.

Eu resolveria o problema, modificando a chance do próprio crítico, após cada número. Exemplo (para demonstrar a ideia):

int base_chance = 20;
int current_chance = base_chance;

int hit = generate_random_number(0, 100) + 1; // anything from 1 to 100
if(hit < current_chance)//Or whatever method you use to check
{
    //crit!
    if(current_chance > base_chance)
        current_chance = base_chance; // reset the chance.
    else
        current_chance *= 0.8; // decrease the crit chance for the NEXT hit.
}
else
{
    //no crit.
    if(current_chance < base_chance)
        current_chance = base_chance; // reset the chance.
    else
        current_chance *= 1.1; // increase the crit chance for the NEXT hit.
    //raise the current_chance
}

Quanto mais tempo você não recebe um crítico - maior a chance que você tem para sua próxima ação. A redefinição que incluí é totalmente opcional e precisaria ser testada para saber se é necessária ou não. Pode ou não ser desejável fornecer uma probabilidade mais alta de um crítico para mais de uma ação consecutiva, após uma longa cadeia de ações não críticas.

Apenas jogando em meus 2 centavos ...

As poucas respostas principais são ótimas explicações, portanto, vou me concentrar apenas em um algoritmo que lhe dá controle sobre a probabilidade de "estrias ruins" e nunca se torna determinístico. Aqui está o que eu acho que você deve fazer:

Em vez de especificar p , o parâmetro de uma distribuição de Bernoulli, que é a sua probabilidade de um acerto crítico, especifique um e b , os parâmetros da distribuição beta, o "conjugado antes" da distribuição Bernoulli. Você precisa acompanhar A e B , o número de ocorrências críticas e não críticas até o momento.

Agora, para especificar um e b , garantir que a / (a + b) = p, a chance de um acerto crítico. O mais interessante é que (a + b) quantifica quão perto você deseja que A / (A + B) esteja de p em geral.

Você faz sua amostragem assim:

deixar que p(x)a função densidade de probabilidade da distribuição beta. Está disponível em muitos lugares, mas você pode encontrá-lo na GSL como gsl_ran_beta_pdf.

S = A+B+1
p_1 = p((A+1)/S)
p_2 = p(A/S)

Escolha um acerto crítico por amostragem de uma distribuição bernoulli com probabilidade p_1 / (p_1 + p_2)

Se você achar que os números aleatórios tem muitos "maus estrias", ampliar a e b , mas no limite, como um e b ir ao infinito, você terá a abordagem saco aleatório descrito anteriormente.

Se você implementar isso, informe-me como vai!

Se você deseja uma distribuição que desencoraje valores repetidos, você pode usar um algoritmo simples de rejeição repetida.

por exemplo

int GetRand(int nSize)
{
    return 1 + (::rand() % nSize);
}
int GetDice()
{
    static int nPrevious=-1;
    while (1) {
        int nValue = GetRand(6);
        // only allow repeat 5% of the time
        if (nValue==nPrevious && GetRand(100)<95)
            continue;
        nPrevious = nValue;
        return nValue;
    }
}

Este código rejeita valores de repetição 95% das vezes, tornando as repetições improváveis, mas não impossíveis. Estatisticamente, é um pouco feio, mas provavelmente produzirá os resultados desejados. Obviamente, isso não impedirá uma distribuição como "5 4 5 4 5". Você pode ficar mais chique e rejeitar o segundo último (digamos) 60% do tempo e o terceiro último (digamos) 30%.

Não estou recomendando isso como um bom design de jogo. Simplesmente sugerindo como conseguir o que deseja.

Não está realmente claro o que você deseja. É possível criar uma função que, nas primeiras 5 vezes em que você a chame, retorne os números de 1 a 5 em uma ordem aleatória.

Mas isso não é realmente aleatório. O jogador saberá que receberá exatamente um 5 nos próximos 5 ataques. Pode ser o que você deseja e, nesse caso, você simplesmente precisa codificá-lo. (crie uma matriz que contenha os números e depois embaralhe-os)

Como alternativa, você pode continuar usando sua abordagem atual e supor que seus resultados atuais sejam devidos a um gerador aleatório ruim. Observe que nada pode estar errado com seus números atuais. Valores aleatórios são aleatórios. às vezes você obtém 2, 3 ou 8 do mesmo valor em uma linha. Porque eles são aleatórios. Um bom gerador aleatório apenas garante que, em média, todos os números serão retornados com a mesma frequência.

Obviamente, se você estiver usando um gerador aleatório ruim, isso pode ter distorcido seus resultados e, nesse caso, simplesmente mudar para um gerador aleatório melhor deve resolver o problema. (Confira a biblioteca Boost.Random para obter melhores geradores)

Como alternativa, você pode se lembrar dos últimos N valores retornados por sua função aleatória e pesar o resultado por eles. (um exemplo simples seria "para cada ocorrência do novo resultado, há 50% de chance de descartarmos o valor e obter um novo"

Se eu tivesse que adivinhar, diria que ficar com a aleatoriedade "real" é sua melhor aposta. Certifique-se de usar um bom gerador aleatório e continue seguindo o caminho que está fazendo agora.

Você pode criar uma lista contendo os números de 1 a 5 e ordená-los por aleatoriedade. Depois, basta percorrer a lista que você criou. Você tem a garantia de encontrar todos os números pelo menos uma vez ... Quando terminar os 5 primeiros, crie outros 5 números ...

Eu recomendo um sistema de porcentagem progressiva como o Blizzard usa: http://www.shacknews.com/onearticle.x/57886

Geralmente você rola um RNG e depois o compara com um valor para determinar se é bem-sucedido ou não. Isso pode se parecer com:

if ( randNumber <= .2 ) {
   //Critical
} else {
   //Normal
}

Tudo que você precisa fazer é adicionar um aumento progressivo na chance básica ...

if (randNumber <= .2 + progressiveChance ) {
   progressiveChance = 0;
   //Critical
} else {
   progressiveChance += CHANCE_MODIFIER;
   //Normal hit
}

Se você precisar que seja mais sofisticado, é muito fácil adicionar mais. Você pode limitar o valor que o ProgressChance pode obter para evitar uma chance crítica de 100% ou redefini-la em determinados eventos. Você também pode ter um aumento progressivo de Chance em quantidades menores a cada aumento com algo como progressivo Chance + = (1 - progressivo Chance) * ESCALA onde ESCALA <1.

Bem, se você gosta um pouco de matemática, provavelmente pode tentar a distribuição exponencial

Por exemplo, se lambda = 0,5, o valor esperado é 2 (leia o artigo!), Significa que você provavelmente acertará / crit / o que quer que seja a cada 2 turnos (como 50%, não é?). Mas com essa distribuição de probabilidade, você definitivamente perderá (ou fará o oposto do que quer que seja) no 0º turno (aquele em que o evento já ocorreu e o turn_counter foi redefinido), terá 40% de chance de acertar o próximo turno, cerca de 65% chance de fazê-lo 2º (próximo após o próximo) turno, cerca de 80% para atingir o 3º e assim por diante.

Todo o objetivo dessa distribuição é que, se alguém tiver 50% de chance de acerto e errar três vezes seguidas, ele será acertado (bem, mais de 80% de chance e aumenta a cada turno seguinte). Isso leva a resultados mais "justos", mantendo inalterada a chance de 50%.

Tomando sua chance de 20% de crítico, você tem

• 17% para o 1º turno crítico
• 32% para o 2º turno crítico, se nenhum crítico ocorrer em todos os anteriores.
• 45% para o 3º turno crítico, se nenhum crítico ocorrer em todos os anteriores.
• 54% para o 4º turno do crítico, se nenhum crítico ocorrer em todos os anteriores.
• ...
• 80% para o 8º turno crítico, se nenhum crítico ocorrer em todos os anteriores.

Ainda tem cerca de 0,2% (vs 5%) de chance de 3 crits + 2 non-crits em 5 turnos subsequentes. E há 14% de chance de 4 não-críticos resultantes, 5% de 5, 1,5% para 6, 0,3% para 7, 0,07% para 8 não-críticos resultantes. Aposto que é "mais justo" que 41%, 32%, 26%, 21% e 16%.

Espero que você ainda não esteja entediado até a morte.

Que tal fazer a chance de crítica depender dos últimos N ataques. Um esquema simples é algum tipo de cadeia de markov: http://en.wikipedia.org/wiki/Markov_chain, mas o código é muito simples de qualquer maneira.

IF turns_since_last_critical < M THEN 
   critial = false
   turns_since_last_critical++;
ELSE
   critial = IsCritical(chance);
   IF Critial THEN
       turns_since_last_critica = 0;
   ELSE
       turns_since_last_critica++;
   END IF;
END IF;

É claro que você deve fazer suas contas porque a chance de um crítico é menor do que a chance de um crítico, uma vez que você sabe que foram turnos suficientes desde o último

OP,

Basicamente, se você quer que seja justo, não será aleatório.

O problema do seu jogo é a duração real da partida. Quanto mais longa a correspondência, menor a aleatoriedade que você verá (os créditos tendem a ser de 20%) e ela se aproxima dos valores pretendidos.

Você tem duas opções: pré-calcule os ataques com base nas jogadas anteriores. O que você recebe um crítico a cada 5 ataques (com base nos seus 20%), mas pode fazer com que a ordem ocorra aleatoriamente.

listOfFollowingAttacks = {Acerto, Acerto, Acerto, Miss, Crit};

Esse é o padrão que você deseja. Portanto, faça-o escolher aleatoriamente a partir dessa lista, até que esteja vazio, eles o recriam.

Esse é um padrão que eu criei para o meu jogo, funciona muito bem para o que eu quero que ele faça.

sua segunda opção seria aumentar a chance de crit, você provavelmente verá um número mais equilibrado no final de todos os ataques (presumindo que suas partidas terminem rapidamente). Quanto menos% de chance, mais RNG você recebe.

Você está olhando para uma distribuição linear, quando provavelmente deseja uma distribuição normal.

Se você se lembra de quando jogava D&D na sua juventude, foi solicitado que você jogasse vários dados de n lados, e então somava os resultados.

Por exemplo, rolar dados de 4 x 6 lados é diferente de rolar 1 x dados de 24 lados.

City of Heroes, na verdade, tem um mecânico chamado "streakbreaker" que resolve exatamente esse problema. A maneira como funciona é que, após uma série de erros de comprimento relacionados à menor probabilidade de acerto na cadeia, o próximo ataque é garantido. Por exemplo, se você perder um ataque com mais de 90% de chance de acerto, seu próximo ataque será acertado automaticamente, mas se sua chance de acerto for menor como 60%, você precisará ter vários erros consecutivos para acionar o "streakbreaker" (eu não sabe os números exatos)

este é realmente previsível ... mas você nunca pode ter certeza.

Que tal pesar o valor?

Por exemplo, se você tiver 20% de chance de acerto crítico, gere um número entre 1 e 5 com um número representando um acerto crítico ou um número entre 1 e 100 com 20 números sendo um acerto crítico.

Mas enquanto você estiver trabalhando com números aleatórios ou pseudo-aleatórios, não há como evitar os resultados que está vendo no momento. É a natureza da aleatoriedade.

Reação sobre: ​​"O problema é que obtive resultados muito ruins na vida real - às vezes os jogadores recebem 3 crits em 5 hits, às vezes nenhum em 15 hits".

Você tem uma chance de algo entre 3 e 4% de não conseguir nada em 15 hits ...

Eu proporia o seguinte "dado morto temporariamente adiado":

• Mantenha duas matrizes, uma ( in-array) inicialmente preenchida com os valores de 0 a n-1, a outra ( out-array) vazia
• Quando um resultado é solicitado:
  • retornar um valor aleatório de todos os valores definidos emin-array
  • mova esse valor de in-arrayparaout-array
  • mova um elemento aleatório (sobre todos os elementos, incluindo o indefinido!) de out-arrayvolta parain-array

Isso tem a propriedade de que "reagirá" mais lentamente quanto maior for o n . Por exemplo, se você deseja uma chance de 20%, definir n como 5 e acertar um 0 é "menos aleatório" do que definir n como 10 e acertar um 0 ou 1 e torná-lo de 0 a 199 em 1000 será quase indistinguível da aleatoriedade verdadeira em uma amostra pequena. Você precisará ajustar n ao tamanho da amostra.

Pré-calcule um acerto crítico aleatório para cada jogador.

// OBJECT
//...
// OnAttack()
//...
c_h = c_h -1;
if ( c_h == 0 ) {
 // Yes, critical hit!
 c_h = random(5) + 1 // for the next time
 // ...
}

Acho que talvez você esteja usando a função de distribuição aleatória errada. Você provavelmente não quer uma distribuição uniforme sobre os números. Tente uma distribuição normal para que os hits críticos se tornem mais incomuns que os hits 'regulares'.

Eu trabalho com Java, então não tenho certeza de onde você pode encontrar algo para C ++ que lhe dê números aleatórios com uma distribuição normal, mas deve haver algo por aí.