Secara akurat mensimulasikan banyak gulungan dadu tanpa loop?

OK jadi jika gim Anda melempar banyak dadu, Anda bisa memanggil generator angka acak dalam satu lingkaran. Tetapi untuk setiap set dadu yang digulung cukup sering Anda akan mendapatkan kurva distribusi / histogram. Jadi pertanyaan saya adakah perhitungan sederhana yang bagus yang dapat saya jalankan yang akan memberi saya angka yang sesuai dengan distribusi itu?

Misalnya 2D6 - Skor -% Probabilitas

2 - 2,77%

3 - 5,55%

4 - 8,33%

5 - 11,11%

6 - 13,88%

7 - 16,66%

8 - 13,88%

9 - 11.11%

10 - 8,33%

11 - 5,55%

12 - 2,77%

Jadi mengetahui di atas Anda bisa melempar D100 tunggal dan menghitung nilai 2D6 yang akurat. Tapi begitu kita mulai dengan 10D6, 50D6, 100D6, 1000D6 ini bisa menghemat banyak waktu pemrosesan. Jadi harus ada tutorial / metode / algoritma yang dapat melakukan ini dengan cepat? Mungkin berguna untuk pasar saham, kasino, permainan strategi, benteng kerdil dll. Bagaimana jika Anda bisa mensimulasikan hasil dari pertempuran strategis lengkap yang akan memakan waktu berjam-jam untuk bermain dengan beberapa panggilan ke fungsi ini dan beberapa matematika dasar?

Seperti yang saya sebutkan di komentar saya di atas, saya sarankan Anda profil ini sebelum terlalu rumit kode Anda. forDadu penjumlahan putaran cepat jauh lebih mudah untuk dipahami dan dimodifikasi daripada rumus matematika yang rumit dan pembuatan / pencarian tabel. Selalu profil dulu untuk memastikan Anda memecahkan masalah penting. ;)

Yang mengatakan, ada dua cara utama untuk sampel distribusi probabilitas canggih dalam satu gerakan:

1. Distribusi Probabilitas Kumulatif

Ada trik yang rapi untuk mengambil sampel dari distribusi probabilitas berkesinambungan dengan hanya menggunakan satu input acak seragam . Ini berkaitan dengan distribusi kumulatif , fungsi yang menjawab "Berapa probabilitas mendapatkan nilai yang tidak lebih besar dari x?"

Fungsi ini tidak menurun, mulai dari 0 dan naik ke 1 di atas domainnya. Contoh untuk jumlah dua dadu enam sisi ditunjukkan di bawah ini:

Jika fungsi distribusi kumulatif Anda memiliki invers yang mudah dihitung (atau Anda dapat memperkirakannya dengan fungsi piecewise seperti kurva Bézier), Anda dapat menggunakan ini untuk mengambil sampel dari fungsi probabilitas asli.

Fungsi invers menangani pembagian domain antara 0 dan 1 ke dalam interval yang dipetakan ke setiap output dari proses acak asli, dengan area tangkapan masing-masing sesuai dengan probabilitas aslinya. (Ini benar sangat kecil untuk distribusi kontinu. Untuk distribusi diskrit seperti gulungan dadu kita perlu menerapkan pembulatan yang cermat)

Berikut ini contoh penggunaan ini untuk meniru 2d6:

int SimRoll2d6()
{
    // Get a random input in the half-open interval [0, 1).
    float t = Random.Range(0f, 1f);
    float v;

    // Piecewise inverse calculated by hand. ;)
    if(t <= 0.5f)
    {
         v = (1f + sqrt(1f + 288f * t)) * 0.5f;
    }
    else
    {
         v = (25f - sqrt(289f - 288f * t)) * 0.5f;
    }

    return floor(v + 1);
}

Bandingkan ini dengan:

int NaiveRollNd6(int n)
{
    int sum = 0;
    for(int i = 0; i < n; i++)
       sum += Random.Range(1, 7); // I'm used to Range never returning its max
    return sum;
}

Lihat apa yang saya maksud tentang perbedaan dalam kejelasan dan fleksibilitas kode? Cara naif mungkin naif dengan loop-nya, tetapi pendek dan sederhana, segera jelas tentang apa yang dilakukannya, dan mudah untuk skala ke berbagai ukuran dan angka die. Membuat perubahan pada kode distribusi kumulatif membutuhkan beberapa matematika non-sepele, dan akan mudah untuk istirahat dan menyebabkan hasil yang tidak terduga tanpa kesalahan yang jelas. (Yang saya harap saya belum membuat di atas)

Jadi, sebelum Anda menghapus lingkaran yang jelas, pastikan benar-benar masalah kinerja yang layak untuk pengorbanan semacam ini.

2. Metode Alias

Metode distribusi kumulatif bekerja dengan baik ketika Anda dapat mengekspresikan kebalikan dari fungsi distribusi kumulatif sebagai ekspresi matematika sederhana, tetapi itu tidak selalu mudah atau bahkan mungkin. Alternatif yang andal untuk distribusi diskrit adalah sesuatu yang disebut Metode Alias .

Ini memungkinkan Anda mengambil sampel dari distribusi probabilitas diskrit arbitrer apa pun dengan menggunakan hanya dua input acak independen yang didistribusikan secara seragam.

Ini bekerja dengan mengambil distribusi seperti di bawah ini di sebelah kiri (jangan khawatir bahwa area / bobot tidak berjumlah 1, untuk Metode Alias ​​kita peduli dengan berat relatif ) dan mengubahnya menjadi tabel seperti yang ada di tempat yang tepat:

• Ada satu kolom untuk setiap hasil.
• Setiap kolom dibagi menjadi paling banyak dua bagian, masing-masing terkait dengan salah satu hasil asli.
• Area / berat relatif dari setiap hasil dipertahankan.

(Diagram berdasarkan gambar dari artikel hebat ini tentang metode pengambilan sampel )

Dalam kode, kami menyatakan ini dengan dua tabel (atau tabel objek dengan dua properti) yang mewakili probabilitas untuk memilih hasil alternatif dari setiap kolom, dan identitas (atau "alias") dari hasil alternatif tersebut. Maka kita dapat sampel dari distribusi seperti:

int SampleFromTables(float[] probabiltyTable, int[] aliasTable)
{
    int column = Random.Range(0, probabilityTable.Length);
    float p = Random.Range(0f, 1f);
    if(p < probabilityTable[column])
    {
        return column;
    }
    else
    {
        return aliasTable[column];
    }
}

Ini melibatkan sedikit pengaturan:

1. Hitung probabilitas relatif setiap hasil yang mungkin (jadi jika Anda memutar 1000d6, kita perlu menghitung jumlah cara untuk mendapatkan setiap jumlah dari 1000 hingga 6000)

2. Buat sepasang tabel dengan entri untuk setiap hasil. Metode lengkap melampaui lingkup jawaban ini, jadi saya sangat merekomendasikan merujuk pada penjelasan tentang algoritma Metode Alias ​​ini .

3. Simpan tabel-tabel itu dan lihat kembali setiap kali Anda membutuhkan die roll acak baru dari distribusi ini.

Ini adalah pertukaran ruang-waktu . Langkah precomputation agak melelahkan, dan kita perlu menyisihkan memori sebanding dengan jumlah hasil yang kita miliki (meskipun bahkan untuk 1000d6, kita berbicara kilobyte satu digit, sehingga tidak ada yang kurang tidur), tetapi sebagai gantinya pengambilan sampel kami adalah waktu yang konstan tidak peduli seberapa rumit distribusi kami.

Saya berharap satu atau yang lain dari metode-metode itu dapat berguna (atau bahwa saya telah meyakinkan Anda bahwa kesederhanaan metode naif sepadan dengan waktu yang diperlukan untuk mengulangi);)

Jawabannya sayangnya adalah bahwa metode ini tidak akan menghasilkan peningkatan kinerja.

Saya percaya bahwa mungkin ada beberapa kesalahpahaman dalam pertanyaan tentang bagaimana angka acak dihasilkan. Ambil contoh di bawah ini [Java]:

Random r = new Random();
int n = 20;
int min = 1; //arbitrary
int max = 6; //arbitrary
for(int i = 0; i < n; i++){
    int randomNumber = (r.nextInt(max - min + 1) + min)); //silly maths
    System.out.println("Here's a random number: " + randomNumber);
}

Kode ini akan berulang 20 kali mencetak angka acak antara 1 dan 6 (inklusif). Ketika kita berbicara tentang kinerja kode ini, ada beberapa waktu yang diperlukan untuk membuat objek acak (yang melibatkan pembuatan array bilangan bulat pseudo-acak berdasarkan jam internal komputer pada saat itu dibuat), dan kemudian 20 waktu konstan lihat setiap panggilan NextInt () berikutnya. Karena setiap 'roll' adalah operasi waktu yang konstan, ini membuat waktu bergulir sangat murah. Perhatikan juga bahwa kisaran min to max tidak masalah (dengan kata lain, komputer semudah untuk memutar d6 sebagaimana untuk menggulung d10000). Berbicara dalam hal kompleksitas waktu, kinerja solusi hanyalah O (n) di mana n adalah jumlah dadu.

Atau, kami dapat memperkirakan jumlah gulungan d6 dengan satu gulungan d100 (atau dalam hal ini d10000). Dengan menggunakan metode ini, pertama-tama kita perlu menghitung persentase [jumlah wajah ke dadu] * n [jumlah dadu] sebelum kita menggulung (persentase teknisnya adalah s * n - n + 1, dan kita harus dapat membaginya dengan kasar setengah karena simetris; perhatikan bahwa dalam contoh Anda untuk mensimulasikan gulungan 2d6, Anda menghitung 11 persen dan 6 unik). Setelah bergulir, kita dapat menggunakan pencarian biner untuk mencari tahu di mana rentang roll kita. Dalam hal kompleksitas waktu, solusi ini mengevaluasi ke solusi O (s * n), di mana s adalah jumlah sisi dan n adalah jumlah dadu. Seperti yang bisa kita lihat, ini lebih lambat daripada solusi O (n) yang diusulkan dalam paragraf sebelumnya.

Mengekstrapolasi dari sana, katakan Anda membuat kedua program ini untuk mensimulasikan roll 1000d20. Yang pertama hanya akan bergulir 1.000 kali. Program kedua pertama-tama perlu menentukan 19.001 persentase (untuk kisaran potensi 1.000 hingga 20.000) sebelum melakukan hal lain. Jadi, kecuali Anda menggunakan sistem aneh di mana pencarian memori jauh lebih mahal daripada operasi floating-point, menggunakan panggilan nextInt () untuk setiap roll sepertinya cara untuk pergi.

Jika Anda ingin menyimpan kombinasi dadu, kabar baiknya adalah ada solusi, yang buruk adalah komputer kita entah bagaimana terbatas dalam hal masalah seperti ini.

Berita bagus:

Ada pendekatan determistik dari masalah ini:

1 / Hitung semua kombinasi grup dadu Anda

2 / Tentukan probabilitas untuk setiap kombinasi

3 / Cari dalam daftar ini untuk hasil alih-alih melempar dadu

Berita buruknya:

Jumlah kombinasi dengan pengulangan diberikan oleh rumus berikut

$\Gamma_n^k={n+k-1 \choose k}=\frac{(n+k-1)!}{k!~(n-1)!}$

( dari wikipedia bahasa Prancis ):

Itu artinya, misalnya, dengan 150 dadu, Anda memiliki 698'526'906 kombinasi. Mari kita asumsikan Anda menyimpan probabilitas sebagai float 32 bit, Anda akan membutuhkan 2,6 GB memori, dan Anda masih harus menambahkan persyaratan memori untuk indeks ...

Dalam istilah komputasi, angka kombinasi dapat dihitung dengan konvolusi, yang berguna tetapi tidak menyelesaikan kendala memori.

Sebagai kesimpulan, untuk jumlah dadu yang tinggi, saya akan menyarankan untuk melempar dadu dan mengamati hasilnya daripada menghitung probabilitas yang terkait dengan setiap kombinasi.

Edit

Namun, karena Anda hanya tertarik pada jumlah dadu, Anda dapat menyimpan probabilitas dengan sumber daya yang jauh lebih sedikit.

Anda dapat menghitung probabilitas yang tepat untuk setiap jumlah dadu menggunakan konvolusi.

Rumus umum adalah $F_i(m) = \sum_n F_1(n) F_{i-1}(m - n)$

Kemudian mulai dari 1/6 dari setiap hasil dengan 1 dadu, Anda dapat menyusun semua probabilitas yang benar untuk sejumlah dadu.

Berikut ini adalah kode java kasar yang saya tulis untuk ilustrasi (tidak benar-benar dioptimalkan):

public class DiceProba {

private float[][] probas;
private int currentCalc;

public int getCurrentCalc() {
    return currentCalc;
}

public float[][] getProbas() {
    return probas;
}

public void calcProb(int faces, int diceNr) {

    if (diceNr < 0) {
        currentCalc = 0;
        return;
    }

    // Initialize
    float baseProba = 1.0f / ((float) faces);
    probas = new float[diceNr][];
    probas[0] = new float[faces + 1];
    probas[0][0] = 0.0f;
    for (int i = 1; i <= faces; ++i)
        probas[0][i] = baseProba;

    for (int i = 1; i < diceNr; ++i) {

        int maxValue = (i + 1) * faces + 1;
        probas[i] = new float[maxValue];

        for (int j = 0; j < maxValue; ++j) {

            probas[i][j] = 0;
            for (int k = 0; k <= j; ++k) {
                probas[i][j] += probability(faces, k, 0) * probability(faces, j - k, i - 1);
            }

        }

    }

    currentCalc = diceNr;

}

private float probability(int faces, int number, int diceNr) {

    if (number < 0 || number > ((diceNr + 1) * faces))
        return 0.0f;

    return probas[diceNr][number];

}

}

Panggil calcProb () dengan parameter yang Anda inginkan dan kemudian akses tabel proba untuk hasil (indeks pertama: 0 untuk 1 dadu, 1 untuk dua dadu ...).

Saya memeriksanya dengan 1'000D6 di laptop saya, butuh 10 detik untuk menghitung semua probabilitas dari 1 hingga 1.000 dadu dan semua kemungkinan jumlah dadu.

Dengan penyimpanan awal dan efisien, Anda bisa mendapatkan jawaban cepat untuk sejumlah besar dadu.

Semoga ini bisa membantu.