c++ - para - Necesidad de generador aleatorio predecible
numero aleatorio google (30)
Soy un desarrollador de juegos web y tengo un problema con números aleatorios. Digamos que un jugador tiene un 20% de probabilidad de obtener un golpe crítico con su espada. Eso significa que 1 de cada 5 visitas debe ser crítico. El problema es que tengo muy malos resultados 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 ++, entonces 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 previos para forzar la distribución adecuada.
Eso significa que 1 de cada 5 visitas debe ser crítico. El problema es que tengo muy malos resultados 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 de mezcla . Resuelve el problema de que el verdadero azar sea demasiado aleatorio para los juegos.
El algoritmo es más o menos así: pones 1 crítico y 4 hits no críticos en una bolsa. Luego, aleatoriza su pedido en la bolsa y los selecciona de uno en uno. Cuando la bolsa está vacía, la vuelve a llenar con los mismos valores y la asigna al azar. De esta forma obtendrás un promedio de 1 golpe crítico por cada 5 golpes, y como máximo 2 golpes críticos y 8 no críticos seguidos. Aumente la cantidad de elementos 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.
¿Qué hay de reemplazar mt_rand () con algo como esto?
(RFC 1149.5 especifica 4 como el número aleatorio estándar vetado por IEEE).
De XKCD .
¿Qué pasa con la posibilidad de que el 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 posibilidad de una crítica es menor que la posibilidad de una crítica una vez que sabe que ha habido suficientes turnos desde la última
¿Seguramente cualquier generación de números aleatorios tiene la posibilidad de producir tales carreras? No va a obtener 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 misericordia ... recuerda los últimos 10 rollos, y si no han tenido un golpe crítico, dales un regalo de promoción. Alise las correas y las flechas de la aleatoriedad.
Bueno, si te gustan las matemáticas un poco, probablemente puedas probar la distribución exponencial
Por ejemplo, si lambda = 0.5, el valor esperado es 2 (¡lee ese artículo!), Significa que probablemente toques / crit / lo que sea cada 2 ° turno (como 50%, ¿eh?). Pero con esa distribución de probabilidad, definirás que solo fallas (o haces lo contrario) en el 0º turno (el uno, en el cual ya ocurrió y turn_counter ha sido reseteado), tienes un 40% de probabilidad de golpear el siguiente turno, alrededor del 65% posibilidad de hacerlo el 2º (siguiente después del próximo) giro, aproximadamente el 80% para golpear el 3er y así sucesivamente.
Todo el propósito de esa distribución es si uno tiene un 50% de probabilidad de golpe y falle 3 veces seguidas, él tendrá el golpe (bueno, más del 80% de probabilidad, y aumenta cada turno siguiente). Conduce a resultados más "justos", manteniendo inalterable el 50% de posibilidades generales.
Tomando su 20% de probabilidad de crítico, tiene
- 17% a crit 1er turno
- 32% para criticar 2º turno, si no hay crítico en todos los anteriores.
- 45% para criticar 3er turno, si no hay crítico en todos los anteriores.
- 54% para criticar 4º turno, si no hay crítico en todos los anteriores.
- ...
- 80% para crit 8vo turno, si no hay crítico en todos los anteriores.
Todavía es aproximadamente el 0,2% (frente a los 5%) de probabilidad de 3 crits + 2 no crits en 5 turnos consecutivos. Y hay un 14% de probabilidad de 4 consecuentes no críticos, 5% de 5, 1.5% para 6, 0.3% para 7, 0.07% para 8 consecuentes no críticos. Apuesto a que es "más justo" que el 41%, 32%, 26%, 21% y 16%.
Espero que todavía no te aburras hasta la muerte.
Dado el comportamiento que está pidiendo, creo que está aleatorizando la variable incorrecta.
En lugar de aleatorizar si este golpe será crítico, intente aleatorizar el número de vueltas hasta que ocurra el siguiente golpe crítico. Por ejemplo, solo elige un número entre 2 y 9 cada vez que el jugador se vuelve crítico, y luego dales su siguiente crítica después de que hayan pasado muchas rondas. También puede usar métodos de dados para acercarse a una distribución normal; por ejemplo, obtendrá su siguiente nivel crítico en 2D4 giros.
Creo que esta técnica se usa también en juegos de rol que también tienen encuentros aleatorios en el otro mundo: aleatorizas un contador de pasos y, luego de muchos pasos, te vuelves a golpear. Se siente mucho más justo porque casi nunca te golpean dos encuentros seguidos; si eso ocurre una sola vez, los jugadores se ponen irritables.
En un número tan pequeño de pruebas, debe esperar resultados como ese:
La verdadera aleatoriedad solo es predecible a través de un gran tamaño de conjunto, de modo que es bastante posible lanzar una moneda y obtener cabezas tres veces seguidas la primera vez, sin embargo, en unos pocos millones de vueltas terminarás con aproximadamente 50-50.
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 de rpg / mmorpg.
El problema que resuelve es este (extracto):
Una araña de cuchilla está en tu garganta. Golpea y extrañas. Golpea de nuevo y echas de menos otra vez. 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 que se regodea con tu cadáver. ¿Imposible? No. Improbable? Sí. Pero si se les dan suficientes jugadores y se les da suficiente tiempo, lo improbable se vuelve casi seguro. No era que la araña de la cuchilla fuera dura, solo era mala suerte. Que frustrante. Es suficiente para hacer que un jugador quiera dejarlo.
Estoy de acuerdo con las respuestas anteriores de que la aleatoriedad real en pequeñas tiradas de algunos juegos no es deseable, parece demasiado injusta para algunos casos de uso.
Escribí una implementación simple de Shuffle Bag como en Ruby e hice algunas pruebas. La implementación hizo esto:
- Si todavía parece correcto o no hemos alcanzado un umbral de rollos mínimos, devuelve un golpe justo basado en la probabilidad normal.
- Si la probabilidad observada de las tiradas del pasado hace que parezca injusta, devuelve un golpe de "fair-ifying".
Se considera injusto según las probabilidades de los límites. Por ejemplo, para una probabilidad del 20%, puede establecer un 10% como límite inferior y un 40% como límite superior.
Utilizando esos límites, descubrí que con ejecuciones de 10 aciertos, el 14.2% de las veces la verdadera implementación pseudoaleatoria producía resultados que estaban fuera de esos límites . Aproximadamente el 11% del tiempo, se marcaron 0 impactos críticos en 10 intentos. 3.3% del tiempo, 5 o más impactos críticos fueron desembarcados de 10. Naturalmente, usando este algoritmo (con un conteo mínimo de rollos de 5), una cantidad mucho más pequeña (0.03%) de las ejecuciones "Fairish" estuvieron 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 notoriamente sus usuarios sentirán que es injusto con una solución pseudoaleatoria real.
Aquí está la carne de mi FairishBag escrita en Ruby. La implementación completa y la simulación rápida de Monte Carlo están disponibles aquí (gist) .
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 obtener un golpe crítico, hasta aproximadamente el 22% utilizando los límites anteriores. Puede compensar esto al establecer su probabilidad "real" un poco más bajo. Una probabilidad del 17.5% con la modificación Fairish produce una probabilidad observada a largo plazo de alrededor del 20% y mantiene las sensaciones a corto plazo como justas.
Lamentablemente, lo que está pidiendo es efectivamente un generador de números no aleatorio, porque quiere que se tengan en cuenta los resultados previos al determinar el siguiente número. No es así como funcionan los generadores de números aleatorios, me temo.
Si quieres que 1 de cada 5 visitas sea crítico, simplemente elige un número entre 1 y 5 y di que ese golpe será crítico.
Las primeras respuestas son excelentes explicaciones, así que solo me centraré en un algoritmo que le dé control sobre la probabilidad de "malas rachas" sin llegar a ser nunca determinista. Esto es lo que creo que debes hacer:
En lugar de especificar p , el parámetro de una distribución de Bernoulli, que es su probabilidad de un golpe crítico, especifique a 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 , la cantidad de hits críticos y no críticos hasta el momento.
Ahora, para especificar ayb , asegúrese de que a / (a + b) = p, la probabilidad de un golpe crítico. Lo bueno es que (a + b) cuantifica qué tan cerca quieres que sea A / (A + B) para ser p en general.
Tú 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 encuentra que los números aleatorios tienen demasiadas "rayas defectuosas", amplíe aa y b , pero en el límite, como ayb van al infinito, tendrá el enfoque de bolsa aleatoria descrito anteriormente.
Si implementa esto, ¡por favor hágame saber cómo va!
Lo que quieres no son números aleatorios, sino números que parecen aleatorios para un ser 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á su juego. Sin embargo, de acuerdo con estudios de psicología, la verdadera aleatoriedad en el 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, manteniendo al mismo tiempo 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 utilizados principalmente 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 números aleatorios, sus limitaciones y sus capacidades puede eliminar muchas dificultades de su uso en el juego. Este artículo ofrece información sobre números aleatorios, su generación y métodos para separar los buenos de los malos.
No está muy 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 aleatorio. El jugador sabrá que obtendrá exactamente un 5 en los próximos 5 ataques. Aunque podría ser lo que quieras, y en ese caso, simplemente tienes que codificarlo tú mismo. (crea una matriz que contiene los números y luego baraja)
Alternativamente, puede seguir usando su enfoque actual y asumir que sus resultados actuales se deben a un generador aleatorio incorrecto. 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 aleatorios. Un buen generador aleatorio solo garantiza que, en promedio, todos los números serán devueltos con la misma frecuencia.
Por supuesto, si has estado usando un generador aleatorio malo, eso podría haber sesgado tus 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, podría recordar los últimos valores N devueltos por su función aleatoria, y pesar el resultado por esos. (Un ejemplo simple sería, "por cada aparición del nuevo resultado, hay un 50% de probabilidad de que debamos descartar el valor y obtener uno nuevo"
Si tuviera que adivinar, diría que seguir con la aleatoriedad "real" es tu mejor opción. Asegúrate de usar un buen generador aleatorio y sigue funcionando de la manera que lo estás haciendo ahora.
OP,
Bastante, si quieres que sea justo, no va a ser al azar.
El problema de tu juego es la duración real del partido. The longer the match is, the less randomness you are going to see(crits will tend to be 20%) and its going to approach your intended values.
You got two options, pre-calculate the attacks based on previous rolls. Which will you get one crit every 5 attacks(based on yours 20%), but you can make the order it occurs random.
listOfFollowingAttacks = {Hit,Hit,Hit,Miss,Crit};
That''s the pattern you want. So make it choose randomly from that list, until its empty, them re-create it.
That''s a pattern I created for my game, it works quite well, for what I want it to do.
your second option, would be, increase the chance to crit, you are probably going to see a more even number in the end of all attacks(presuming that your matches ends rather quickly). The less % chance, the more RNG''d you get.
Primero, defina la distribución "apropiada". Los números aleatorios son, bueno, aleatorios; los resultados que estás viendo son totalmente consistentes con (pseudo) aleatoriedad.
Ampliando esto, supongo que lo que quieres es una sensación de "equidad", por lo que el usuario no puede dar 100 vueltas sin éxito. De ser así, realizaría un seguimiento del número de fallas desde el último éxito y ponderaré el resultado generado. Supongamos que quieres 1 en 5 tiradas para "tener éxito". Entonces generas aleatoriamente un número del 1 al 5, y si es 5, genial.
De lo contrario, registre el error y, la próxima vez, genere un número del 1 al 5, pero agregue, por ejemplo, floor (numFailures / 2). Así que 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 de 2 en 5. Con estas opciones, después de 8 fallas, están seguros de tener éxito.
Puede crear una lista que contenga los números del 1 al 5 y ordenarlos por aleatoriedad. Luego solo revisa la lista que creaste. Usted 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 Blizzard usa: http://www.shacknews.com/onearticle.x/57886
En general, usted tira 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 necesitas hacer es agregar un aumento progresivo en la posibilidad 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 progresivaChance puede obtener para evitar una posibilidad crítica del 100% o restablecerla en ciertos eventos. También puede tener progresivoCambio de aumento en cantidades más pequeñas cada impulso con algo así como progressiveChance + = (1 - progressiveChance) * SCALE donde SCALE <1.
Si desea una distribución que desaliente los valores de repetición, podría usar un algoritmo de rechazo de repetición simple.
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 produzca los resultados que desea. Por supuesto, no evitará una distribución como "5 4 5 4 5". Podrías hacerte más elegante y rechazar la segunda (digamos) el 60% del tiempo y la tercera (digamos) el 30%.
No estoy recomendando esto como un buen diseño de juego. Simplemente sugiriendo cómo lograr lo que quieres.
Su mejor solución podría ser la prueba de juego con múltiples esquemas diferentes no aleatorios y elegir el que haga más felices a los jugadores.
También puede probar una política de retroceso para el mismo número en un encuentro determinado, por ejemplo, si un jugador tira un 1 en su primer turno, acéptelo. Para obtener otro 1 necesitan lanzar 2 1 s seguidos. Para obtener un tercer 1 , necesitan 3 en una fila, ad infinitum.
Tienes una mala interpretación de lo que significa al azar.
¿Cuál de estos es más aleatorio?
Mientras que el segundo argumento se ve distribuido de manera más uniforme, el más aleatorio es en realidad el primer argumento. La mente humana a menudo ve patrones en la aleatoriedad, por lo que vemos los cúmulos en la primera trama como patrones, pero no lo son: son solo parte de una muestra seleccionada al azar.
Veo muchas respuestas que sugieren hacer un seguimiento de los números generados previamente o mezclar todos los valores posibles.
Personalmente, no estoy de acuerdo, que 3 critits in a row sean malos. Tampoco estoy de acuerdo con que 15 no críticos en una fila sean malos.
Resolvería el problema, modificando la probabilidad crítica de 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 obtengas un crítico, mayor será la probabilidad de que tengas para tu próxima acción. El reinicio que incluí es completamente opcional y necesitaría pruebas para saber si es necesario o no. Puede o no ser deseable dar una probabilidad más alta de un crítico para más de una acción en una fila, después de una larga cadena de acción no crítica.
Solo lanzando mis 2 centavos ...
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 en absoluto, así que deberías 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 exhibir variaciones locales de la probabilidad establecida, pero luego se vuelve predecible. Si establece un máximo de 10 no crits en una fila, entonces le acaba de decir a los jugadores "si ha tenido 9 no crits en una fila, el siguiente será crítico con 100% de certeza": puede así que no te molestes con la aleatoriedad en absoluto.
City of Heroes actually has a mechanic called the "streakbreaker" that solves exactly this problem. The way it works is that after a string of misses of a length related to the lowest to-hit probability in the string, the next attack is guaranteed to be a hit. For example if you miss an attack with over 90% to hit chance then your next attack will auto hit, but if your hit chance is lower like 60% then you''ll need to have several consecutive misses to trigger the "streakbreaker" (I don''t know the exact numbers)
How about weighting the value?
For example, if you have a 20% chance to critical hit, generate a number between 1 and 5 with one number representing a critical hit, or a number between 1 and 100 with 20 numbers being a critical hit.
But as long as you are working with random or pseudorandom numbers, there''s no way to potentially avoid the results you are currently seeing. It''s the nature of randomness.
I would propose the following "randomly delayed putback die":
- Maintain two arrays, one (
in-array) initially filled with the values from 0 to n-1, the other (out-array) empty - When a result is requested:
- return a random value from all defined values in
in-array - move this value from
in-arraytoout-array - move one random (over all elements, including the undefined!) element from
out-arrayback intoin-array
- return a random value from all defined values in
This has the property that it will "react" more slowly the bigger n is. For example, if you want a 20% chance, setting n to 5 and hitting on a 0 is "less random" than setting n to 10 and hitting on a 0 or 1, and making it 0 to 199 out of 1000 will be almost indistinguishable from true randomness over a small sample. You will have to adjust n to your sample size.
Reaction on: "The problem is I got very bad real life results -- sometimes players get 3 crits in 5 hits, sometimes none in 15 hits."
You have a chance of somewhere between 3 and 4 % of getting nothing in 15 hits...
You are looking at a linear distribution, when you probably want a normal distribution.
If you remember back in your youth playing D&D, you were asked to roll multiple n-sided die, then sum the results.
For instance, rolling 4 x 6-sided die is different than rolling 1 x 24-sided dice.
this one is really predictable... but you can never be sure.
Creo que quizás estés usando la función de distribución aleatoria incorrecta. Probablemente no quieras una distribución pareja sobre los números. Pruebe una distribución normal para que los hits críticos se vuelvan más raros que los éxitos ''normales''.
Trabajo con Java, así que no estoy seguro de dónde puedes encontrar algo para C ++ que te brinde números aleatorios con una distribución normal, pero tiene que haber algo por ahí.
Pre-calcule un golpe crítico al azar 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
// ...
}