Apakah java.util.Random benar-benar acak? Bagaimana saya bisa menghasilkan 52! (faktorial) kemungkinan urutan?

Saya telah menggunakan Random (java.util.Random)untuk mengocok setumpuk 52 kartu. Ada 52! (8.0658175e + 67) kemungkinan. Namun, saya telah menemukan bahwa seed untuk java.util.Randoma long, yang jauh lebih kecil pada 2 ^ 64 (1,8446744e + 19).

Dari sini, saya curiga apakah java.util.Random ini benar-benar acak ; apakah ini benar-benar mampu menghasilkan semua 52! kemungkinan?

Jika tidak, bagaimana saya bisa menghasilkan urutan acak yang lebih baik yang dapat menghasilkan semua 52! kemungkinan?

Memilih permutasi acak membutuhkan lebih banyak dan lebih sedikit keacakan secara serentak daripada yang disiratkan oleh pertanyaan Anda. Biarkan saya jelaskan.

Berita buruknya: perlu lebih banyak keacakan.

Kelemahan mendasar dalam pendekatan Anda adalah bahwa ia mencoba untuk memilih antara ~ 2 ²²⁶ kemungkinan menggunakan 64 bit entropi (benih acak). Untuk secara adil memilih antara ~ 2 ²²⁶ kemungkinan Anda harus menemukan cara untuk menghasilkan 226 bit entropi alih-alih 64.

Ada beberapa cara untuk menghasilkan bit acak: perangkat keras khusus , instruksi CPU , antarmuka OS , layanan online . Sudah ada asumsi implisit dalam pertanyaan Anda bahwa Anda entah bagaimana dapat menghasilkan 64 bit, jadi lakukan saja apa yang akan Anda lakukan, hanya empat kali, dan sumbangkan kelebihan bit tersebut untuk amal. :)

Berita baiknya: perlu sedikit keacakan.

Setelah Anda memiliki 226 bit acak tersebut, sisanya dapat dilakukan secara deterministik dan sehingga sifat-sifatnya java.util.Randomdapat menjadi tidak relevan . Begini caranya.

Katakanlah kita menghasilkan semua 52! permutasi (tahan dengan saya) dan mengurutkannya secara leksikografis.

Untuk memilih salah satu permutasi yang kita butuhkan adalah bilangan bulat acak tunggal antara 0dan 52!-1. Bilangan bulat itu adalah 226 bit entropi kami. Kami akan menggunakannya sebagai indeks ke daftar permutasi yang kami sortir. Jika indeks acak terdistribusi secara seragam, Anda tidak hanya dijamin bahwa semua permutasi dapat dipilih, mereka akan dipilih secara dapat disetel (yang merupakan jaminan yang lebih kuat dari apa yang ditanyakan oleh pertanyaan).

Sekarang, Anda sebenarnya tidak perlu membuat semua permutasi itu. Anda dapat menghasilkan satu secara langsung, mengingat posisi yang dipilih secara acak di daftar hipotetis kami yang diurutkan. Hal ini dapat dilakukan di O (n ² ) waktu menggunakan Lehmer ^[1] kode (juga lihat penomoran permutasi dan sistem nomor factoriadic ). N di sini adalah ukuran dek Anda, yaitu 52.

Ada implementasi C dalam jawaban StackOverflow ini . Ada beberapa variabel integer di sana yang akan melimpah untuk n = 52, tetapi untungnya di Jawa Anda dapat menggunakan java.math.BigInteger. Sisa perhitungan dapat ditranskripsikan seperti apa adanya:

public static int[] shuffle(int n, BigInteger random_index) {
    int[] perm = new int[n];
    BigInteger[] fact = new BigInteger[n];
    fact[0] = BigInteger.ONE;
    for (int k = 1; k < n; ++k) {
        fact[k] = fact[k - 1].multiply(BigInteger.valueOf(k));
    }

    // compute factorial code
    for (int k = 0; k < n; ++k) {
        BigInteger[] divmod = random_index.divideAndRemainder(fact[n - 1 - k]);
        perm[k] = divmod[0].intValue();
        random_index = divmod[1];
    }

    // readjust values to obtain the permutation
    // start from the end and check if preceding values are lower
    for (int k = n - 1; k > 0; --k) {
        for (int j = k - 1; j >= 0; --j) {
            if (perm[j] <= perm[k]) {
                perm[k]++;
            }
        }
    }

    return perm;
}

public static void main (String[] args) {
    System.out.printf("%s\n", Arrays.toString(
        shuffle(52, new BigInteger(
            "7890123456789012345678901234567890123456789012345678901234567890"))));
}

^[1] Jangan bingung dengan Lehrer . :)

Analisis Anda benar: menaburkan generator nomor pseudo-acak dengan seed spesifik apa pun harus menghasilkan urutan yang sama setelah shuffle, membatasi jumlah permutasi yang bisa Anda peroleh hingga ⁶⁴ . Pernyataan ini mudah diverifikasi secara eksperimental dengan menelepon Collection.shuffledua kali, melewati aRandom objek yang diinisialisasi dengan seed yang sama, dan mengamati bahwa kedua acak acak identik.

Maka, solusi untuk ini adalah dengan menggunakan generator angka acak yang memungkinkan benih yang lebih besar. Java menyediakan SecureRandomkelas yang dapat diinisialisasi dengan byte[]berbagai ukuran yang hampir tidak terbatas. Anda kemudian bisa melewati contoh SecureRandomuntuk Collections.shuffleuntuk menyelesaikan tugas:

byte seed[] = new byte[...];
Random rnd = new SecureRandom(seed);
Collections.shuffle(deck, rnd);

Secara umum, generator nomor pseudorandom (PRNG) tidak dapat memilih di antara semua permutasi dari daftar 52-item jika panjang statusnya kurang dari 226 bit.

java.util.Randommengimplementasikan algoritma dengan modulus 2 ⁴⁸ ; jadi panjang statusnya hanya 48 bit, jauh lebih sedikit dari 226 bit yang saya maksud. Anda perlu menggunakan PRNG lain dengan panjang status yang lebih besar - khususnya, yang memiliki periode 52 faktorial atau lebih besar.

Lihat juga "Mengacak" di artikel saya tentang generator angka acak .

Pertimbangan ini tidak tergantung pada sifat PRNG; itu berlaku sama untuk PRNGs kriptografi dan nonkriptografi (tentu saja, PRNG nonkriptografi tidak tepat ketika keamanan informasi terlibat).

Meskipun java.security.SecureRandommemungkinkan benih dengan panjang tak terbatas dilewatkan, SecureRandomimplementasinya dapat menggunakan PRNG yang mendasarinya (misalnya, "SHA1PRNG" atau "DRBG"). Dan itu tergantung pada periode PRNG itu (dan pada tingkat lebih rendah, panjang menyatakan) apakah itu mampu memilih dari antara 52 permutasi faktorial. (Perhatikan bahwa saya mendefinisikan "panjang negara" sebagai "ukuran maksimum benih yang dapat diambil oleh PRNG untuk menginisialisasi keadaannya tanpa memperpendek atau mengompresi benih itu ").

Biarkan saya minta maaf sebelumnya, karena ini agak sulit untuk dipahami ...

Pertama-tama, Anda sudah tahu bahwa java.util.Randomitu tidak sepenuhnya acak sama sekali. Ini menghasilkan urutan dengan cara yang dapat diprediksi dengan sempurna dari seed. Anda sepenuhnya benar bahwa, karena benih hanya panjang 64 bit, hanya dapat menghasilkan 2 ^ 64 urutan yang berbeda. Jika Anda entah bagaimana menghasilkan 64 bit acak nyata dan menggunakannya untuk memilih sebuah seed, Anda tidak dapat menggunakan seed itu untuk secara acak memilih di antara semua 52! kemungkinan urutan dengan probabilitas yang sama.

Namun, fakta ini tidak ada konsekuensi selama Anda tidak benar-benar akan menghasilkan lebih dari 2 ^ 64 sekuens, selama tidak ada yang 'istimewa' atau 'terasa istimewa' tentang sekuens 2 ^ 64 yang dapat dihasilkan dihasilkannya .

Katakanlah Anda memiliki PRNG yang jauh lebih baik yang menggunakan biji 1000-bit. Bayangkan Anda memiliki dua cara untuk menginisialisasi - satu cara akan menginisialisasi menggunakan seluruh benih, dan satu cara akan memotong benih menjadi 64 bit sebelum menginisialisasi itu.

Jika Anda tidak tahu inisialisasi mana yang mana, bisakah Anda menulis segala jenis tes untuk membedakannya? Kecuali jika Anda (tidak) cukup beruntung untuk akhirnya menginisialisasi yang buruk dengan yang sama 64 bit yang dua kali, maka jawabannya adalah tidak. Anda tidak dapat membedakan antara kedua inisialisasi tanpa sedikit pengetahuan rinci tentang beberapa kelemahan dalam implementasi PRNG tertentu.

Atau, bayangkan bahwa Random kelas memiliki array 2 ^ 64 urutan yang dipilih sepenuhnya dan acak pada suatu waktu di masa lalu, dan bahwa benih itu hanya indeks ke dalam array ini.

Jadi fakta yang Randomhanya menggunakan 64 bit untuk bijinya sebenarnya tidak selalu menjadi masalah secara statistik, selama tidak ada peluang signifikan bahwa Anda akan menggunakan seed yang sama dua kali.

Tentu saja, untuk keperluan kriptografi , seed 64 bit tidak cukup, karena mendapatkan sistem untuk menggunakan seed yang sama dua kali layak secara komputasi.

EDIT:

Saya harus menambahkan bahwa, meskipun semua hal di atas benar, bahwa implementasi sebenarnya java.util.Randomtidak mengagumkan. Jika Anda menulis permainan kartu, mungkin menggunakan MessageDigestAPI untuk menghasilkan hash SHA-256 "MyGameName"+System.currentTimeMillis(), dan menggunakan bit-bit itu untuk mengocok deck. Dengan argumen di atas, selama pengguna Anda tidak benar-benar berjudi, Anda tidak perlu khawatir itu akan currentTimeMilliskembali lama. Jika pengguna Anda benar - benar berjudi, maka gunakan SecureRandomtanpa benih.

Saya akan mengambil sedikit taktik berbeda dalam hal ini. Anda benar dengan asumsi Anda - PRNG Anda tidak akan bisa mencapai semua 52! kemungkinan.

Pertanyaannya adalah: apa skala permainan kartu Anda?

Jika Anda membuat gim bergaya klondike sederhana? Maka Anda pasti tidak perlu semua 52! kemungkinan. Sebaliknya, lihat seperti ini: seorang pemain akan memiliki 18 trilyun gim yang berbeda. Bahkan terhitung untuk 'Masalah Ulang Tahun', mereka harus bermain miliaran tangan sebelum mereka mengalami permainan duplikat pertama.

Jika Anda membuat simulasi monte-carlo? Maka Anda mungkin baik-baik saja. Anda mungkin harus berurusan dengan artefak karena 'P' di PRNG, tetapi Anda mungkin tidak akan mengalami masalah hanya karena ruang benih rendah (sekali lagi, Anda sedang melihat trilyunan kemungkinan unik.) Di sisi sebaliknya, jika Anda bekerja dengan jumlah iterasi yang besar, maka, ya, ruang benih rendah Anda mungkin menjadi pemecah kesepakatan.

Jika Anda membuat permainan kartu multi pemain, terutama jika ada uang di telepon? Maka Anda perlu melakukan beberapa googling tentang bagaimana situs-situs poker online menangani masalah yang sama yang Anda tanyakan. Karena sementara ruang masalah rendah tidak terlihat oleh pemain rata-rata, itu dapat dieksploitasi jika sepadan dengan investasi waktu. (Situs poker semua melewati fase di mana PRNG mereka 'diretas', membiarkan seseorang melihat kartu hole semua pemain lain, hanya dengan menyimpulkan benih dari kartu yang terbuka.) Jika ini adalah situasi Anda, don 't hanya menemukan PRNG yang lebih baik - Anda harus memperlakukannya sebagai serius sebagai masalah Crypto.

Solusi singkat yang pada dasarnya sama dengan dasblinkenlight:

// Java 7
SecureRandom random = new SecureRandom();
// Java 8
SecureRandom random = SecureRandom.getInstanceStrong();

Collections.shuffle(deck, random);

Anda tidak perlu khawatir dengan kondisi internal. Penjelasan panjang mengapa:

Ketika Anda membuat SecureRandominstance dengan cara ini, itu mengakses generator nomor acak benar OS spesifik. Ini adalah salah satu kumpulan entropi di mana nilai diakses yang berisi bit acak (misalnya untuk timer nanosecond presisi nanosecond pada dasarnya acak) atau generator nomor perangkat keras internal.

Input ini (!) Yang mungkin masih mengandung jejak palsu dimasukkan ke hash yang kuat secara kriptografis yang menghapus jejak tersebut. Itulah alasan CSPRNG tersebut digunakan, bukan untuk membuat angka-angka itu sendiri! The SecureRandommemiliki counter yang menelusuri berapa banyak bit yang digunakan ( getBytes(), getLong()dll) dan isi ulang yang SecureRandomdengan bit entropi bila diperlukan .

Singkatnya: Lupakan saja keberatan dan gunakan SecureRandomsebagai penghasil bilangan acak sejati.

Jika Anda menganggap nomor sebagai hanya array bit (atau byte) maka mungkin Anda bisa menggunakan (Secure) Random.nextBytessolusi yang disarankan dalam pertanyaan Stack Overflow ini , dan kemudian memetakan array menjadi a new BigInteger(byte[]).

Algoritma yang sangat sederhana adalah dengan menerapkan SHA-256 ke urutan bilangan bulat yang bertambah dari 0 ke atas. (Garam dapat ditambahkan jika diinginkan untuk "mendapatkan urutan yang berbeda".) Jika kita berasumsi bahwa output dari SHA-256 adalah "sebaik" bilangan bulat terdistribusi antara 0 dan 2 ²⁵⁶ - 1 maka kita memiliki cukup entropi untuk tugas.

Untuk mendapatkan permutasi dari output SHA256 (ketika dinyatakan sebagai bilangan bulat) kita hanya perlu menguranginya modulo 52, 51, 50 ... seperti dalam pseudocode ini:

deck = [0..52]
shuffled = []
r = SHA256(i)

while deck.size > 0:
    pick = r % deck.size
    r = floor(r / deck.size)

    shuffled.append(deck[pick])
    delete deck[pick]