Necesidad de un generador aleatorio predecible

Soy un desarrollador de juegos web y tengo un problema con los números aleatorios. Digamos que un jugador tiene un 20% de posibilidades de recibir un golpe crítico con su espada. Eso significa que 1 de 5 golpes debería ser crítico. El problema es que obtuve resultados muy malos en la vida real: a veces los jugadores obtienen 3 crits en 5 hits, a veces ninguno en 15 hits. Las batallas son bastante cortas (3-10 golpes), por lo que es importante obtener una buena distribución aleatoria.

Actualmente uso PHP mt_rand(), pero solo estamos moviendo nuestro código a C ++, así que quiero resolver este problema en el nuevo motor de nuestro juego.

No sé si la solución es algún generador aleatorio uniforme, o tal vez para recordar estados aleatorios anteriores para forzar una distribución adecuada.

Estoy de acuerdo con las respuestas anteriores de que la aleatoriedad real en pequeñas ejecuciones de algunos juegos no es deseable; parece demasiado injusto para algunos casos de uso.

Escribí un simple Shuffle Bag como implementación en Ruby e hice algunas pruebas. La implementación hizo esto:

• Si todavía parece justo o no hemos alcanzado un umbral de tiradas mínimas, devuelve un golpe justo basado en la probabilidad normal.
• Si la probabilidad observada de tiradas pasadas hace que parezca injusto, devuelve un golpe "justo".

Se considera injusto en función de las probabilidades de límite. Por ejemplo, para una probabilidad del 20%, puede establecer el 10% como límite inferior y el 40% como límite superior.

Usando esos límites, descubrí que con ejecuciones de 10 aciertos, el 14.2% de las veces la implementación pseudoaleatoria verdadera produjo resultados que estaban fuera de esos límites . Alrededor del 11% de las veces, se puntuaron 0 golpes críticos en 10 intentos. 3.3% de las veces, 5 o más golpes críticos fueron lanzados de 10. Naturalmente, usando este algoritmo (con un recuento mínimo de 5), una cantidad mucho menor (0.03%) de las carreras "Fairish" estaban fuera de límites. . Incluso si la implementación a continuación no es adecuada (se pueden hacer cosas más inteligentes, sin duda), vale la pena señalar que a menudo sus usuarios sentirán que es injusto con una solución pseudoaleatoria real.

Aquí está la carne de mi FairishBagescrito en Ruby. Toda la implementación y la simulación rápida de Monte Carlo está disponible aquí (resumen) .

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

Actualización: el uso de este método aumenta la probabilidad general de recibir un golpe crítico, a aproximadamente el 22% usando los límites anteriores. Puede compensar esto estableciendo su probabilidad "real" un poco más baja. Una probabilidad del 17.5% con la modificación justa produce una probabilidad observada a largo plazo de aproximadamente el 20%, y mantiene las corridas a corto plazo sintiéndose justas.

Eso significa que 1 de 5 golpes debería ser crítico. El problema es que obtuve resultados muy malos en la vida real: a veces los jugadores obtienen 3 crits en 5 hits, a veces ninguno en 15 hits.

Lo que necesitas es una bolsa aleatoria . Resuelve el problema de que el verdadero azar sea demasiado aleatorio para los juegos.

El algoritmo es más o menos así: pones 1 golpe crítico y 4 golpes no críticos en una bolsa. Luego, aleatoriza su orden en la bolsa y los elige uno a la vez. Cuando la bolsa está vacía, la vuelves a llenar con los mismos valores y la aleatorizas. De esa forma, obtendrá en promedio 1 golpe crítico por cada 5 golpes, y como máximo 2 golpes críticos y 8 golpes no críticos seguidos. Aumente el número de artículos en la bolsa para obtener más aleatoriedad.

Aquí hay un ejemplo de una implementación (en Java) y sus casos de prueba que escribí hace algún tiempo.

Tienes un malentendido de lo que significa aleatorio.

¿Cuál de estos es más aleatorio?

Mientras que la segunda gráfica se ve más uniformemente distribuida, la más aleatoria es en realidad la primera gráfica. La mente humana a menudo ve patrones en la aleatoriedad, por lo que vemos los grupos en la primera gráfica como patrones, pero no lo son, son solo parte de una muestra seleccionada al azar.

Dado el comportamiento que está solicitando, creo que está aleatorizando la variable incorrecta.

En lugar de aleatorizar si este golpe será crítico, intente aleatorizar el número de turnos hasta que ocurra el siguiente golpe crítico. Por ejemplo, solo elige un número entre 2 y 9 cada vez que el jugador recibe un crítico, y luego dales su próximo crítico después de que hayan pasado tantas rondas. También puede usar métodos de dados para acercarse a una distribución normal; por ejemplo, obtendrá su próximo crítico en turnos 2D4.

Creo que esta técnica también se usa en juegos de rol que tienen encuentros aleatorios en el supramundo: aleatorizas un contador de pasos y, después de tantos pasos, te golpean nuevamente. Se siente mucho más justo porque casi nunca te golpean dos encuentros seguidos; si eso sucede incluso una vez, los jugadores se irritan.

Primero, defina la distribución "adecuada". Los números aleatorios son, bueno, aleatorios: los resultados que está viendo son completamente consistentes con la (seudo) aleatoriedad.

Ampliando esto, supongo que lo que quieres es un sentimiento de "justicia", por lo que el usuario no puede dar 100 vueltas sin tener éxito. Si es así, haría un seguimiento de la cantidad de fallas desde el último éxito y sopesaría el resultado generado. Supongamos que quiere que 1 de cada 5 rollos "tenga éxito". Entonces generas al azar un número del 1 al 5, y si es 5, genial.

De lo contrario, registre la falla y, la próxima vez, genere un número del 1 al 5, pero agregue, por ejemplo, floor (numFailures / 2). Entonces, esta vez, nuevamente, tienen una probabilidad de 1 en 5. Si fallan, la próxima vez el intervalo ganador es 4 y 5; Una posibilidad de éxito 2 en 5. Con estas opciones, después de 8 fallas, seguramente tendrán éxito.

¿Qué tal reemplazar mt_rand () con algo como esto?

(RFC 1149.5 especifica 4 como el número aleatorio examinado por IEEE estándar).

De XKCD .

Esperemos que este artículo lo ayude: http://web.archive.org/web/20090103063439/http://www.gamedev.net:80/reference/design/features/randomness/

Este método de generar 'números aleatorios' es común en los juegos rpg / mmorpg.

El problema que resuelve es este (extracto):

Una araña de cuchillas está en tu garganta. Golpea y fallas. Golpea de nuevo y fallas de nuevo. Y una y otra vez, hasta que no quede nada de ti para golpear. Estás muerto y hay un arácnido de dos toneladas regodeándose sobre tu cadáver. ¿Imposible? No. ¿Improbable? Si. Pero con suficientes jugadores y con suficiente tiempo, lo improbable se vuelve casi seguro. No era que la araña de la hoja fuera dura, solo era mala suerte. Que frustrante. Es suficiente para que un jugador quiera dejar de fumar.

Lo que quieres no son números aleatorios, sino números que parecen aleatorios para un humano. Otros ya han sugerido algoritmos individuales, que pueden ayudarlo, como Shuffle Bad.

Para un buen análisis detallado y extenso de este dominio, vea AI Game Programming Wisdom 2 . Vale la pena leer todo el libro para cualquier desarrollador de juegos, la idea de "números aparentemente aleatorios" se maneja en el capítulo:

Aleatoriedad filtrada para decisiones de IA y lógica de juego :

Resumen: La sabiduría convencional sugiere que cuanto mejor sea el generador de números aleatorios, más impredecible será tu juego. Sin embargo, según los estudios de psicología, la verdadera aleatoriedad a corto plazo a menudo parece decididamente no aleatoria para los humanos. Este artículo muestra cómo hacer que las decisiones aleatorias de IA y la lógica del juego se vean más aleatorias para los jugadores, mientras se mantiene una fuerte aleatoriedad estadística.

También puede encontrar otro capítulo interesante:

Las estadísticas de números aleatorios

Resumen: Los números aleatorios son los más utilizados por la Inteligencia Artificial y los juegos en general. Ignorar su potencial es hacer que el juego sea predecible y aburrido. Usarlos incorrectamente puede ser tan malo como ignorarlos directamente. Comprender cómo se generan los números aleatorios, sus limitaciones y sus capacidades puede eliminar muchas dificultades de usarlos en su juego. Este artículo ofrece información sobre números aleatorios, su generación y métodos para separar los buenos de los malos.

¿Seguramente cualquier generación de números aleatorios tiene la posibilidad de producir tales carreras? No obtendrá un conjunto de muestras lo suficientemente grande en 3-10 rollos para ver los porcentajes apropiados.

Tal vez lo que quieres es un umbral de piedad ... recuerda los últimos 10 rollos, y si no han tenido un golpe crítico, dales un obsequio. Alisa las hondas y las flechas de la aleatoriedad.

La mejor solución podría estar probando el juego con múltiples diferentes no esquemas aleatorios y elegir el que haga más felices a los jugadores.

También puede intentar una política de retroceso para el mismo número en un encuentro dado, por ejemplo, si un jugador tira un a 1en su primer turno, acéptelo. Para obtener otro 1, deben tirar 2 1s seguidos. Para obtener un tercio 1, necesitan 3 seguidos, hasta el infinito.

Desafortunadamente, lo que está pidiendo es efectivamente un generador de números no aleatorio, porque desea que se tengan en cuenta los resultados anteriores al determinar el siguiente número. No es así como funcionan los generadores de números aleatorios, me temo.

Si desea que 1 de cada 5 golpes sea crítico, simplemente elija un número entre 1 y 5 y diga que ese golpe será crítico.

mt_rand () se basa en una implementación de Mersenne Twister , lo que significa que produce una de las mejores distribuciones aleatorias que puede obtener.

Aparentemente, lo que quieres no es aleatoriedad, por lo que debes comenzar especificando exactamente lo que quieres. Probablemente se dará cuenta de que tiene expectativas contradictorias: que los resultados deben ser verdaderamente aleatorios y no predecibles, pero al mismo tiempo no deben mostrar variaciones locales de la probabilidad establecida, pero luego se vuelve predecible. Si estableces un máximo de 10 no críticos en una fila, entonces acabas de decirle a los jugadores "si has tenido 9 no críticos en una fila, el siguiente será crítico con un 100% de certeza". bueno no molestar con aleatoriedad en absoluto.

En un número tan pequeño de pruebas, debe esperar resultados como este:

La verdadera aleatoriedad solo es predecible en un tamaño de conjunto enorme, de modo que es bastante posible lanzar una moneda y obtener caras 3 veces seguidas la primera vez, sin embargo, con unos pocos millones de lanzamientos terminará con aproximadamente 50-50.

Veo muchas respuestas que sugieren hacer un seguimiento de los números generados previamente o barajar todos los valores posibles.

Personalmente, no estoy de acuerdo, que 3 críticas seguidas es malo. Tampoco estoy de acuerdo en que 15 no-crits seguidos es malo.

Solucionaría el problema, modificando la probabilidad crítica por sí mismo, después de cada número. Ejemplo (para demostrar la idea):

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
}

Cuanto más tiempo no recibas un crítico, más posibilidades tendrás de que tu próxima acción critique. El reinicio que incluí es completamente opcional y necesitaría pruebas para saber si es necesario o no. Puede ser o no deseable dar una mayor probabilidad de un crítico para más de una acción consecutiva, después de una larga cadena de acción no crítica.

Solo tirando mis 2 centavos ...

Las pocas respuestas principales son excelentes explicaciones, por lo que me centraré en un algoritmo que le da control sobre la probabilidad de "malas rayas" sin ser nunca determinista. Esto es lo que creo que deberías hacer:

En lugar de especificar p , el parámetro de una distribución de Bernoulli, que es su probabilidad de un impacto crítico, especifique un y b , los parámetros de la distribución beta, el "conjugado previo" de la distribución de Bernoulli. Debe realizar un seguimiento de A y B , el número de golpes críticos y no críticos hasta el momento.

Ahora, para especificar un y b , garantizar que a / (a + b) = p, la probabilidad de que un golpe crítico. Lo bueno es que (a + b) cuantifica qué tan cerca desea que esté A / (A + B) para p en general.

Haces tu muestreo así:

Sea p(x)la función de densidad de probabilidad de la distribución beta. Está disponible en muchos lugares, pero puede encontrarlo en GSL como gsl_ran_beta_pdf.

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

Elija un golpe crítico mediante el muestreo de una distribución de bernoulli con probabilidad p_1 / (p_1 + p_2)

Si usted encuentra que los números aleatorios tienen demasiados "malas rachas", ampliar un y b , pero en el límite, como una y b ir hasta el infinito, tendrá el enfoque de la bolsa aleatoria descrito anteriormente.

Si implementa esto, ¡hágamelo saber cómo va!

Si desea una distribución que desaliente los valores de repetición, puede usar un algoritmo simple de rechazo de repetición.

p.ej

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 rechaza los valores de repetición el 95% del tiempo, lo que hace que las repeticiones sean poco probables pero no imposibles. Estadísticamente es un poco feo, pero probablemente producirá los resultados que desea. Por supuesto, no impedirá una distribución como "5 4 5 4 5". Podrías ponerte más elegante y rechazar el penúltimo (digamos) el 60% del tiempo y el último último (digamos) el 30%.

No estoy recomendando esto como un buen diseño de juego. Simplemente sugiriendo cómo lograr lo que quieres.

No está realmente claro lo que quieres. Es posible crear una función tal que las primeras 5 veces que la llame, devuelva los números 1-5 en un orden aleatorio.

Pero eso no es realmente al azar. El jugador sabrá que obtendrá exactamente un 5 en los próximos 5 ataques. Sin embargo, podría ser lo que desea, y en ese caso, simplemente tiene que codificarlo usted mismo. (crear una matriz que contenga los números y luego barajarlos)

Alternativamente, puede seguir usando su enfoque actual y asumir que sus resultados actuales se deben a un mal generador aleatorio. Tenga en cuenta que nada puede estar mal con sus números actuales. Los valores aleatorios son aleatorios. a veces obtienes 2, 3 u 8 del mismo valor en una fila. Porque son al azar. Un buen generador aleatorio solo garantiza que, en promedio, todos los números se devolverán con la misma frecuencia.

Por supuesto, si ha estado utilizando un generador aleatorio incorrecto, eso podría haber sesgado sus resultados, y si es así, simplemente cambiar a un generador aleatorio mejor debería solucionar el problema. (Consulte la biblioteca Boost.Random para obtener mejores generadores)

Alternativamente, puede recordar los últimos N valores devueltos por su función aleatoria y sopesar el resultado por esos. (un ejemplo simple sería, "por cada aparición del nuevo resultado, hay un 50% de posibilidades de que descartemos el valor y obtengamos uno nuevo"

Si tuviera que adivinar, diría que seguir con la aleatoriedad "real" es su mejor opción. Asegúrate de usar un buen generador aleatorio, y luego continúa como lo estás haciendo ahora.

Puede crear una lista que contenga los números del 1 al 5 y ordenarlos por aleatoriedad. Luego, simplemente revise la lista que creó. Tiene la garantía de encontrarse con cada número al menos una vez ... Cuando haya terminado con los primeros 5, simplemente cree otros 5 números ...

Recomiendo un sistema de porcentaje progresivo como el que usa Blizzard: http://www.shacknews.com/onearticle.x/57886

En general, lanza un RNG y luego lo compara con un valor para determinar si tiene éxito o no. Eso puede verse así:

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

Todo lo que necesita hacer es agregar un aumento progresivo en la probabilidad de base ...

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

Si necesita que sea más elegante, es bastante fácil agregar más. Puede limitar la cantidad que progresiva puede obtener para evitar una probabilidad crítica del 100% o restablecerla en ciertos eventos. También puede aumentar el aumento progresivo en cantidades más pequeñas en cada impulso con algo como el cambio progresivo + = (1 - cambio progresivo) * ESCALA donde ESCALA <1.

Bueno, si te interesan un poco las matemáticas, probablemente puedas probar la distribución exponencial

Por ejemplo, si lambda = 0.5, el valor esperado es 2 (¡vaya a leer ese artículo!), Significa que probablemente golpeará / crit / lo que sea cada 2º turno (como 50%, ¿eh?). Pero con tal distribución de probabilidad, definitivamente perderá (o hará lo contrario) en el turno 0 (el que ya había ocurrido y se reinició turn_counter), tiene una probabilidad del 40% de golpear el próximo turno, alrededor del 65% posibilidad de hacerlo en el segundo turno (siguiente después del siguiente), alrededor del 80% para golpear en el tercero y así sucesivamente.

El propósito de esa distribución es que si uno tiene un 50% de probabilidad de golpe y falla 3 veces seguidas, él seguramente (bueno, más del 80% de probabilidad, y aumenta cada próximo turno). Conduce a resultados más "justos", manteniendo el 50% de probabilidad general sin cambios.

Tomando tu 20% de probabilidad de crítico, tienes

• 17% al crítico 1er turno
• 32% al crítico 2do turno, si no ocurre ningún crítico en todos los anteriores.
• 45% al ​​crítico 3er turno, si no ocurre ningún crítico en todos los anteriores.
• 54% al crítico 4to turno, si no ocurre ningún crítico en todos los anteriores.
• ...
• 80% al crítico octavo turno, si no ocurre ningún crítico en todos los anteriores.

Todavía tiene una probabilidad del 0.2% (frente a ese 5%) de 3 crits + 2 no crits en 5 turnos consecuentes. Y hay un 14% de posibilidades de 4 no críticos consecuentes, 5% de 5, 1.5% para 6, 0.3% para 7, 0.07% para 8 no críticos consecuentes. Apuesto a que es "más justo" que 41%, 32%, 26%, 21% y 16%.

Espero que todavía no te aburras hasta la muerte.

¿Qué hay de hacer que la posibilidad de crítico dependa de los últimos N ataques? Un esquema simple es algún tipo de cadena de markov: http://en.wikipedia.org/wiki/Markov_chain pero el código es muy simple de todos modos.

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;

Por supuesto, debe hacer sus cálculos porque la probabilidad de un crítico es menor que la probabilidad de un crítico una vez que sabe que ha habido suficientes turnos desde el último

OP,

Más o menos, si quieres que sea justo, no será aleatorio.

El problema de tu juego es la duración real del partido. Cuanto más larga sea la coincidencia, menos aleatoriedad verá (los crits tenderán a ser del 20%) y se acercará a sus valores previstos.

Tienes dos opciones, precalcula los ataques en base a tiradas anteriores. ¿Cuál obtendrás un crítico cada 5 ataques (en base al tuyo del 20%), pero puedes hacer que el orden ocurra al azar.

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

Ese es el patrón que quieres. Así que haz que elija al azar de esa lista, hasta que esté vacío, ellos lo recrearán.

Ese es un patrón que creé para mi juego, funciona bastante bien, para lo que quiero que haga.

su segunda opción, sería, aumentar la posibilidad de crítico, probablemente verá un número más par al final de todos los ataques (suponiendo que sus combates terminen bastante rápido). Cuanto menos% de probabilidad, más RNG obtendrás.

Estás mirando una distribución lineal, cuando probablemente quieras una distribución normal.

Si recuerdas que cuando eras joven jugaba D&D, se te pidió que tiraras varios dados de n lados y luego sumaras los resultados.

Por ejemplo, tirar un dado de 4 x 6 lados es diferente a tirar dados de 1 x 24 lados.

City of Heroes en realidad tiene un mecánico llamado "rompe-rayas" que resuelve exactamente este problema. La forma en que funciona es que después de una cadena de fallas de una longitud relacionada con la probabilidad más baja de golpear en la cadena, se garantiza que el próximo ataque sea un golpe. Por ejemplo, si pierde un ataque con más del 90% de probabilidad de golpear, su próximo ataque golpeará automáticamente, pero si su probabilidad de golpe es menor como 60%, entonces necesitará tener varias fallas consecutivas para desencadenar el "Streakbreaker" (I no sé los números exactos)

este es realmente predecible ... pero nunca puedes estar seguro.

¿Qué tal ponderar el valor?

Por ejemplo, si tiene un 20% de probabilidad de golpe crítico, genere un número entre 1 y 5 con un número que represente un golpe crítico, o un número entre 1 y 100 con 20 números siendo un golpe crítico.

Pero mientras trabaje con números aleatorios o pseudoaleatorios, no hay forma de evitar potencialmente los resultados que está viendo actualmente. Es la naturaleza de la aleatoriedad.

Reacción sobre: ​​"El problema es que obtuve resultados muy malos en la vida real: a veces los jugadores obtienen 3 crits en 5 hits, a veces ninguno en 15 hits".

Tienes una probabilidad de entre 3 y 4% de no obtener nada en 15 golpes ...

Propondría el siguiente "dado de devolución retrasado al azar":

• Mantenga dos matrices, una ( in-array) inicialmente llena con los valores de 0 a n-1, la otra ( out-array) vacía
• Cuando se solicita un resultado:
  • devolver un valor aleatorio de todos los valores definidos enin-array
  • mover este valor de in-arrayaout-array
  • mover un elemento aleatorio (sobre todos los elementos, incluido el indefinido) de out-arraynuevo ain-array

Esto tiene la propiedad de que "reaccionará" más lentamente cuanto mayor sea n . Por ejemplo, si desea una probabilidad del 20%, establecer n en 5 y obtener un 0 es "menos aleatorio" que establecer n en 10 y obtener un 0 o 1, y hacer que sea 0 a 199 de 1000 será casi indistinguible de la aleatoriedad verdadera en una muestra pequeña. Tendrá que ajustar n al tamaño de su muestra.

Precalcule un golpe crítico aleatorio para cada jugador.

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

Creo que tal vez estás usando la función de distribución aleatoria incorrecta. Probablemente no desee una distribución uniforme sobre los números. Pruebe una distribución normal en su lugar para que los golpes críticos se vuelvan más infrecuentes que los golpes 'regulares'.

Trabajo con Java, así que no estoy seguro de dónde puedes encontrar algo para C ++ que te dé números aleatorios con una distribución normal, pero tiene que haber algo por ahí.