Barajar un mazo de póker en JavaScript con window.crypto.getRandomValues

shuffle entropy

Question

Una baraja de poker tiene 52 cartas y por lo tanto 52! o aproximadamente 2^226 posibles permutaciones.

Ahora quiero barajar este tipo de cartas a la perfección, con resultados verdaderamente aleatorios y una distribución uniforme, de modo que pueda alcanzar cada una de esas posibles permutaciones y cada una de ellas tenga la misma probabilidad de aparecer.

¿Por qué es esto realmente necesario?

Para los juegos, quizás, realmente no se necesita una aleatoriedad perfecta, a menos que haya dinero para ganar. Aparte de eso, los humanos probablemente ni siquiera percibirán las "diferencias" en la aleatoriedad.

Pero si no me equivoco, si usa funciones de barajadas y componentes RNG comúnmente incorporados en lenguajes de programación populares, a menudo no obtendrá más de 32 bits de entropía y 2^32 estados. Por lo tanto, ¡nunca podrás alcanzar los 52! posibles permutaciones de la baraja al barajar, pero solo sobre ...

0.0000000000000000000000000000000000000000000000000000005324900157%

... de las posibles permutaciones. Eso significa que una gran cantidad de todos los juegos posibles que podrían jugarse o simularse en teoría nunca se verán en la práctica.

Por cierto, puede mejorar aún más los resultados si no restablece el orden predeterminado cada vez antes de barajar, sino que comienza con el orden de la última baraja o mantiene el "desorden" después de un juego y se baraja de allí .

Requisitos:

Entonces, para hacer lo que se describe arriba, uno necesita todos los siguientes tres componentes, por lo que he entendido:

1. Un buen algoritmo de barajado que asegura una distribución uniforme.
2. Un RNG adecuado con al menos 226 bits de estado interno. Ya que estamos en máquinas deterministas, un PRNG será todo lo que obtendremos, y quizás esto debería ser un CSPRNG.
3. Una semilla aleatoria con al menos 226 bits de entropía.

Soluciones:

Ahora es esto alcanzable? ¿Que tenemos?

1. Fisher-Yates shuffle estará bien, por lo que puedo ver.
2. El xorshift7 RNG tiene más de los 226 bits requeridos de estado interno y debería ser suficiente.
3. Usando window.crypto.getRandomValues podemos generar los 226 bits de entropía requeridos para ser usados ​​como nuestra semilla. Si eso no es suficiente, podemos agregar más entropía de otras fuentes .

Pregunta:

¿Son correctas las soluciones (y también los requisitos) mencionados anteriormente? ¿Cómo se puede implementar shuffling usando estas soluciones en JavaScript en la práctica entonces? ¿Cómo combinar los tres componentes en una solución de trabajo?

Supongo que tengo que reemplazar el uso de Math.random en el ejemplo del shuffle de Fisher-Yates con una llamada a xorshift7. Pero ese RNG genera un valor en el rango flotante [0, 1) y necesito el rango entero [1, n] lugar. Al escalar ese rango, no quiero perder la distribución uniforme. Además, quería unos 226 bits de aleatoriedad. Si mi RNG genera solo un único Number , ¿no se reduce esa aleatoriedad a 2 ^ 53 (o 2 ^ 64) bits porque no hay más posibilidades para la salida?

Para generar la semilla para el RNG, quería hacer algo como esto:

var randomBytes = generateRandomBytes(226);

function generateRandomBytes(n) {
    var data = new Uint8Array(
        Math.ceil(n / 8)
    );
    window.crypto.getRandomValues(data);

    return data;
}

¿Es esto correcto? No veo cómo podría pasar randomBytes al RNG como una semilla de ninguna manera, y no sé cómo podría modificarlo para aceptar esto.

Answer 1

Aquí hay una función que escribí que utiliza la mezcla de Fisher-Yates basada en bytes aleatorios provenientes de window.crypto . Dado que Fisher-Yates requiere que se generen números aleatorios en diferentes rangos, comienza con una máscara de 6 bits ( mask=0x3f ), pero gradualmente reduce el número de bits en esta máscara a medida que el rango requerido se reduce (es decir, cada vez que Es una potencia de 2).

function shuffledeck() {
    var cards = Array("A♣️","2♣️","3♣️","4♣️","5♣️","6♣️","7♣️","8♣️","9♣️","10♣️","J♣️","Q♣️","K♣️",
                      "A♦️","2♦️","3♦️","4♦️","5♦️","6♦️","7♦️","8♦️","9♦️","10♦️","J♦️","Q♦️","K♦️",
                      "A♥️","2♥️","3♥️","4♥️","5♥️","6♥️","7♥️","8♥️","9♥️","10♥️","J♥️","Q♥️","K♥️",
                      "A♠️","2♠️","3♠️","4♠️","5♠️","6♠️","7♠️","8♠️","9♠️","10♠️","J♠️","Q♠️","K♠️");
    var rndbytes = new Uint8Array(100);
    var i, j, r=100, tmp, mask=0x3f;

    /* Fisher-Yates shuffle, using uniform random values from window.crypto */
    for (i=51; i>0; i--) {
        if ((i & (i+1)) == 0) mask >>= 1;
        do {
            /* Fetch random values in 100-byte blocks. (We probably only need to do */
            /* this once.) The `mask` variable extracts the required number of bits */
            /* for efficient discarding of random numbers that are too large. */
            if (r == 100) {
                window.crypto.getRandomValues(rndbytes);
                r = 0;
            }
            j = rndbytes[r++] & mask;
        } while (j > i);

        /* Swap cards[i] and cards[j] */
        tmp = cards[i];
        cards[i] = cards[j];
        cards[j] = tmp;
    }
    return cards;
}

Una evaluación de window.crypto bibliotecas de window.crypto realmente merece su propia pregunta, pero de todos modos ...

El flujo pseudoaleatorio provisto por window.crypto.getRandomValues() debe ser lo suficientemente aleatorio para cualquier propósito, pero es generado por diferentes mecanismos en diferentes navegadores. Según una encuesta de 2013 :

• Firefox (v. 21+) usa NIST SP 800-90 con una semilla de 440 bits. Nota: Este estándar se actualizó en 2015 para eliminar el algoritmo PRNG de curva elíptica Dual_EC_DRBG (posiblemente de puerta trasera).

• Internet Explorer (v. 11+) usa uno de los algoritmos compatibles con BCryptGenRandom (longitud de semilla =?)

• Safari, Chrome y Opera utilizan un cifrado de flujo ARC4 con una semilla de 1024 bits.

Editar:

Una solución más limpia sería agregar un método genérico de orden shuffle() al prototipo de matriz de Javascript:

// Add Fisher-Yates shuffle method to Javascript''s Array type, using
// window.crypto.getRandomValues as a source of randomness.

if (Uint8Array && window.crypto && window.crypto.getRandomValues) {
    Array.prototype.shuffle = function() {
        var n = this.length;

        // If array has <2 items, there is nothing to do
        if (n < 2) return this;
        // Reject arrays with >= 2**31 items
        if (n > 0x7fffffff) throw "ArrayTooLong";

        var i, j, r=n*2, tmp, mask;
        // Fetch (2*length) random values
        var rnd_words = new Uint32Array(r);
        // Create a mask to filter these values
        for (i=n, mask=0; i; i>>=1) mask = (mask << 1) | 1;

        // Perform Fisher-Yates shuffle
        for (i=n-1; i>0; i--) {
            if ((i & (i+1)) == 0) mask >>= 1;
            do {
                if (r == n*2) {
                    // Refresh random values if all used up
                    window.crypto.getRandomValues(rnd_words);
                    r = 0;
                }
                j = rnd_words[r++] & mask;
            } while (j > i);
            tmp = this[i];
            this[i] = this[j];
            this[j] = tmp;
        }
        return this;
    }
} else throw "Unsupported";

// Example:
deck = [ "A♣️","2♣️","3♣️","4♣️","5♣️","6♣️","7♣️","8♣️","9♣️","10♣️","J♣️","Q♣️","K♣️",
         "A♦️","2♦️","3♦️","4♦️","5♦️","6♦️","7♦️","8♦️","9♦️","10♦️","J♦️","Q♦️","K♦️",
         "A♥️","2♥️","3♥️","4♥️","5♥️","6♥️","7♥️","8♥️","9♥️","10♥️","J♥️","Q♥️","K♥️",
         "A♠️","2♠️","3♠️","4♠️","5♠️","6♠️","7♠️","8♠️","9♠️","10♠️","J♠️","Q♠️","K♠️"];

deck.shuffle();

Answer 2

Combinando esta respuesta de aquí con esta respuesta de otra pregunta , parece que la siguiente podría ser una versión más general y modular (aunque menos optimizada):

// Fisher-Yates
function shuffle(array) {
    var i, j;

    for (i = array.length - 1; i > 0; i--) {
        j = randomInt(0, i + 1);
        swap(array, i, j);
    }
}

// replacement for:
//     Math.floor(Math.random() * (max - min)) + min
function randomInt(min, max) {
    var range = max - min;
    var bytesNeeded = Math.ceil(Math.log2(range) / 8);
    var randomBytes = new Uint8Array(bytesNeeded);
    var maximumRange = Math.pow(Math.pow(2, 8), bytesNeeded);
    var extendedRange = Math.floor(maximumRange / range) * range;
    var i, randomInteger;

    while (true) {
        window.crypto.getRandomValues(randomBytes);
        randomInteger = 0;

        for (i = 0; i < bytesNeeded; i++) {
            randomInteger <<= 8;
            randomInteger += randomBytes[i];
        }

        if (randomInteger < extendedRange) {
            randomInteger %= range;

            return min + randomInteger;
        }
    }
}

function swap(array, first, second) {
    var temp;

    temp = array[first];
    array[first] = array[second];
    array[second] = temp;
}

Answer 3

Personalmente creo que podrías moverte fuera de la caja un poco. Si está preocupado por la aleatoriedad, puede buscar una clave de API en random.org ( https://api.random.org/json-rpc/1/ ) o analizarla desde un enlace como este: https://www.random.org/integer-sets/?sets=1&num=52&min=1&max=52&seqnos=on&commas=on&order=index&format=html&rnd=new .

Claro, sus conjuntos de datos podrían ser interceptados, pero si obtiene unos pocos cientos de miles de conjuntos de ellos y luego barajen esos conjuntos, estaría bien.