Bagaimana saya bisa membuat generator "acak" yang bias oleh peristiwa sebelumnya?

37

Saya mencari untuk menerapkan sistem berbasis kesempatan yang bias oleh peristiwa sebelumnya.

Latar belakang: Beberapa tahun yang lalu, saya ingat pembaruan untuk World of Warcraft mengumumkan bahwa mereka menerapkan kalkulator peluang baru yang akan menangkal rantai peristiwa runcing. (misalnya membuat serangan kritis atau menghindari beberapa kali berturut-turut). Idenya adalah bahwa jika Anda akan menghindari serangan, kemungkinan Anda akan menghindari serangan berikutnya akan berkurang, tetapi itu akan bekerja dua arah. Tidak menghindari serangan akan meningkatkan peluang menghindari serangan berikutnya. Trik utama di sini, adalah bahwa selama beberapa percobaan kesempatan menghindar masih akan sesuai dengan persentase yang diberikan kepada pemain dalam lembar statenya.

Sistem semacam ini sangat menggelitik saya pada waktu itu, dan sekarang saya dalam situasi membutuhkan solusi seperti itu.

Inilah masalah saya:

  • Saya menduga bahwa saya akan dapat menemukan sumber daya daring tentang penerapan sistem seperti itu, tetapi saya mungkin kurang memiliki kata kunci yang relevan untuk menemukannya.
  • Saya juga membutuhkan pendekatan ini agar sesuai dengan sistem yang tidak binomial (yaitu dua hasil), tetapi berisi 4 peristiwa yang saling eksklusif.

Pendekatan saya saat ini mirip dengan sistem tiket undian. Ketika suatu peristiwa terjadi, saya mengubah bobot untuk semua acara lainnya. Ini bisa bekerja jika keempat acara itu dimaksudkan untuk memiliki kemungkinan yang sama, tetapi dalam kasus saya, perlu lebih banyak. Tetapi karena peristiwa yang lazim terjadi lebih sering, itu menggeser bobot yang lain jauh lebih tinggi dari yang dimaksudkan dan saya tidak bisa menemukan angka untuk perubahan bobot yang diperlukan untuk menjaga jumlah tiket rata-rata di sekitar nilai awal bahwa acara tersebut diberikan.

Beberapa petunjuk arah atau contoh potongan yang jelas akan sangat dihargai.

Sonaten
sumber
4
Jika Anda menginginkan jawaban yang sangat bernuansa atau canggih, Anda mungkin lebih beruntung bertanya di Mathematics.SE. Para ahli matematika ada yang nyaman menjawab pertanyaan rumit tentang probabilitas. math.stackexchange.com
Kevin
1
PRNG
Jon
6
Alternatif untuk situs Matematika di mana Anda akan lebih mungkin untuk memahami jawabannya adalah Programmers.SE . Desain algoritma tidak terutama pada topik tentang Matematika dan Anda mungkin perlu membuat desain awal untuk mendapatkan input yang bermanfaat.
Lilienthal
1
Saya setuju dengan Kevin dan Lilienthal bahwa Anda mungkin mendapatkan jawaban yang lebih baik di sana, tetapi membaca jawaban mklingen, saya menyadari apa yang sedang dideskripsikan di sini dapat dimodelkan sebagai rantai Markov dan itu mungkin merupakan alat yang berguna untuk diketahui oleh pengembang game. Saya akan coba menuliskannya lebih terinci nanti.
nwellcome
1
Ketika saya sudah menjalankan angka pada beberapa jawaban di sini, saya menemukan ada sejumlah kendala yang berbeda, dan bahwa solusi yang memecahkan semuanya mungkin saya lebih kompleks daripada yang Anda butuhkan. Beberapa lebih spesifik pada kasus penggunaan Anda mungkin membantu mempersempit opsi terbaik. Misalnya, apakah probabilitas acara Anda cukup mirip (mis. 5 hasil berbeda dengan masing-masing 20%), atau sangat berbeda (mis. 10% kehilangan 80% mencapai 10% kritis)? Apakah Anda ingin meminimalkan run (mis. 3 misses berturut-turut) atau rumpun / tunggu (mis. 3 misses dari 8 percobaan, atau 20 percobaan sebelum saya mendapatkan kritikan)?
DMGregory

Jawaban:

19

Pada dasarnya, yang Anda minta adalah generator acara "semi-acak" yang menghasilkan acara dengan properti berikut:

  1. Tingkat rata-rata di mana setiap peristiwa terjadi ditentukan terlebih dahulu.

  2. Peristiwa yang sama lebih kecil kemungkinannya terjadi dua kali berturut-turut daripada secara acak.

  3. Peristiwa tidak sepenuhnya dapat diprediksi.

Salah satu cara untuk melakukannya adalah dengan mengimplementasikan generator peristiwa non-acak yang memenuhi tujuan 1 dan 2, dan kemudian menambahkan beberapa keacakan untuk memenuhi tujuan 3.


Untuk generator acara non-acak, kita dapat menggunakan algoritma dithering sederhana . Secara khusus, misalkan p 1 , p 2 , ..., p n menjadi kemungkinan relatif dari kejadian 1 ke n , dan mari s = p 1 + p 2 + ... + p n menjadi jumlah dari bobot. Kami kemudian dapat menghasilkan urutan kejadian yang secara acak disetarakan secara maksimal secara non-acak menggunakan algoritma berikut:

  1. Awalnya, biarkan e 1 = e 2 = ... = e n = 0.

  2. Untuk menghasilkan suatu peristiwa, tambah setiap e i dengan p i , dan output k acara yang e k terbesar (memutuskan ikatan apa pun yang Anda inginkan).

  3. Pengurangan e k oleh s , dan ulangi dari langkah 2.

Sebagai contoh, mengingat tiga kejadian A, B dan C, dengan p A = 5, p B = 4 dan p C = 1, algoritma ini menghasilkan sesuatu seperti urutan output berikut:

A B A B C A B A B A A B A B C A B A B A A B A B C A B A B A

Perhatikan bagaimana urutan 30 peristiwa ini mengandung tepat 15 As, 12 Bs dan 3 Cs. Ini tidak cukup optimal mendistribusikan - ada beberapa kejadian dua As berturut-turut, yang bisa dihindari - tetapi semakin dekat.


Sekarang, untuk menambahkan keacakan ke urutan ini, Anda memiliki beberapa opsi (tidak harus saling eksklusif):

  • Anda dapat mengikuti saran Philipp , dan mempertahankan "setumpuk" acara N mendatang, untuk sejumlah N yang berukuran tepat . Setiap kali Anda perlu membuat acara, Anda memilih acara acak dari dek, dan kemudian menggantinya dengan output acara berikutnya dengan algoritma dithering di atas.

    Menerapkan ini pada contoh di atas, dengan N = 3, menghasilkan misalnya:

    A B A B C A B B A B A B C A A A A B B A B A C A B A B A B A

    sedangkan N = 10 menghasilkan yang lebih acak:

    A A B A C A A B B B A A A A A A C B A B A A B A C A C B B B

    Perhatikan bagaimana peristiwa umum A dan B berakhir dengan lebih banyak berjalan karena pengocokan, sedangkan peristiwa C langka masih cukup baik spasi.

  • Anda dapat menyuntikkan beberapa keacakan langsung ke dalam algoritma dithering. Misalnya, alih-alih menambah e i dengan p i pada langkah 2, Anda dapat menambahkannya dengan p i × acak (0, 2), di mana acak ( a , b ) adalah nomor acak yang terdistribusi secara seragam antara a dan b ; ini akan menghasilkan output seperti berikut:

    A B B C A B A A B A A B A B A A B A A A B C A B A B A C A B

    atau Anda dapat menambah e i dengan p i + acak (- c , c ), yang akan menghasilkan (untuk c = 0,1 x dtk ):

    B A A B C A B A B A B A B A C A B A B A B A A B C A B A B A

    atau, untuk c = 0,5 × s :

    B A B A B A C A B A B A A C B C A A B C B A B B A B A B C A

    Perhatikan bagaimana skema aditif memiliki efek pengacakan yang jauh lebih kuat untuk peristiwa langka C daripada untuk peristiwa umum A dan B, dibandingkan dengan yang multiplikatif; ini mungkin atau mungkin tidak diinginkan. Tentu saja, Anda juga bisa menggunakan beberapa kombinasi dari skema ini, atau penyesuaian lainnya terhadap kenaikan, asalkan itu mempertahankan properti yang kenaikan rata - rata e i sama dengan p i .

  • Atau, Anda bisa mengganggu output dari algoritma dithering dengan kadang-kadang mengganti event yang dipilih k dengan yang acak (dipilih sesuai dengan bobot mentah p i ). Selama Anda juga menggunakan k yang sama pada langkah 3 seperti yang Anda hasilkan pada langkah 2, proses dithering masih cenderung meratakan fluktuasi acak.

    Misalnya, inilah beberapa contoh hasil, dengan peluang 10% dari setiap acara dipilih secara acak:

    B A C A B A B A C B A A B B A B A B A B C B A B A B C A B A

    dan inilah contoh dengan peluang 50% dari setiap output secara acak:

    C B A B A C A B B B A A B A A A A A B B A C C A B B A B B C

    Anda juga dapat mempertimbangkan makan campuran kejadian murni acak dan ragu-ragu menjadi pencampuran kolam renang / deck, seperti dijelaskan di atas, atau mungkin mengacak algoritma dithering dengan memilih k secara acak, seperti ditimbang oleh e i s (memperlakukan bobot negatif nol).

Ps. Berikut adalah beberapa urutan peristiwa yang benar-benar acak, dengan tingkat rata-rata yang sama, untuk perbandingan:

A C A A C A B B A A A A B B C B A B B A B A B A A A A A A A
B C B A B C B A A B C A B A B C B A B A A A A B B B B B B B
C A A B A A B B C B B B A B A B A A B A A B A B A C A A B A

Tangent: Karena telah ada beberapa perdebatan dalam komentar tentang apakah perlu, untuk solusi berbasis dek, untuk memungkinkan geladak kosong sebelum diisi ulang, saya memutuskan untuk membuat perbandingan grafis dari beberapa strategi pengisian geladak:

Merencanakan
Plot beberapa strategi untuk menghasilkan membalik koin semi-acak (dengan rata-rata rasio head to tail 50:50). Sumbu horizontal adalah jumlah flips, sumbu vertikal adalah jarak kumulatif dari rasio yang diharapkan, diukur sebagai (ekor - kepala) / 2 = kepala - membalik / 2.

Garis merah dan hijau pada plot menunjukkan dua algoritma berbasis non-dek untuk perbandingan:

  • Garis merah, dithering deterministik : hasil yang bernomor genap selalu kepala, hasil angka ganjil selalu berekor.
  • Garis hijau, flip acak independen : setiap hasil dipilih secara independen secara acak, dengan kemungkinan kepala 50% dan peluang ekor 50%.

Tiga baris lainnya (biru, ungu dan cyan) menunjukkan hasil dari tiga strategi berbasis dek, masing-masing diimplementasikan menggunakan setumpuk 40 kartu, yang awalnya diisi dengan 20 kartu "kepala" dan 20 kartu "ekor":

  • Garis biru, isi ketika kosong : Kartu diambil secara acak hingga geladak kosong, lalu geladak diisi ulang dengan 20 kartu "kepala" dan 20 kartu "ekor".
  • Garis ungu, isi ketika setengah kosong : Kartu digambar secara acak hingga dek memiliki 20 kartu tersisa; kemudian dek diisi dengan 10 kartu "kepala" dan 10 kartu "ekor".
  • Baris cyan, isi terus menerus : Kartu diambil secara acak; undian bernomor genap segera diganti dengan kartu "kepala", dan undian bernomor ganjil dengan kartu "ekor".

Tentu saja, plot di atas hanyalah satu realisasi dari proses acak, tetapi cukup representatif. Secara khusus, Anda dapat melihat bahwa semua proses berbasis dek memiliki bias terbatas, dan tetap cukup dekat dengan garis merah (deterministik), sedangkan garis hijau murni acak akhirnya berkeliaran.

(Faktanya, penyimpangan garis biru, ungu dan cyan dari nol sangat dibatasi oleh ukuran dek: garis biru tidak pernah bisa melayang lebih dari 10 langkah dari nol, garis ungu hanya bisa mendapatkan 15 langkah dari nol , dan garis cyan dapat melayang paling jauh 20 langkah dari nol. Tentu saja, dalam praktiknya, salah satu garis yang benar-benar mencapai batasnya sangat tidak mungkin, karena ada kecenderungan kuat bagi mereka untuk kembali mendekati nol jika mereka berjalan terlalu jauh mati.)

Sekilas, tidak ada perbedaan yang jelas antara strategi berbasis dek yang berbeda (meskipun, rata-rata, garis biru tetap agak lebih dekat dengan garis merah, dan garis cyan berada agak jauh lebih jauh), tetapi pemeriksaan lebih dekat dari garis biru tidak mengungkapkan pola deterministik yang berbeda: setiap 40 undian (ditandai oleh garis vertikal abu-abu putus-putus), garis biru persis memenuhi garis merah di nol. Garis ungu dan cyan tidak dibatasi dengan ketat, dan dapat menjauhi nol pada titik mana pun.

Untuk semua strategi berbasis dek, fitur penting yang membuat variasi mereka tetap terikat adalah kenyataan bahwa, sementara kartu diambil dari dek secara acak, dek diisi ulang secara deterministik. Jika kartu yang digunakan untuk mengisi ulang dek itu sendiri dipilih secara acak, semua strategi berbasis dek akan menjadi tidak dapat dibedakan dari pilihan acak murni (garis hijau).

Ilmari Karonen
sumber
Jawaban yang sangat rumit. Menambahkan faktor acak ke algoritma dithering tampak lurus ke depan. :)
Sonaten
Memutuskan untuk pergi dengan jawaban Anda. :) Tapi saya akan merekomendasikan agar Anda menambahkan tambahan dari tinjauan metode di bagian atas. Apa yang akan saya lakukan, berdasarkan jawaban Anda adalah mencoba solusi "Merah" dan "Ungu".
Sonaten
53

Jangan melempar dadu, kartu kesepakatan.

Ambil semua kemungkinan hasil RNG Anda, masukkan dalam daftar, kocok secara acak, dan kembalikan hasilnya dalam urutan acak. Ketika Anda berada di akhir daftar, ulangi.

Hasilnya masih akan didistribusikan secara seragam, tetapi hasil individual tidak akan diulangi kecuali yang terakhir dari daftar juga merupakan yang pertama dari yang berikutnya.

Ketika ini agak terlalu mudah ditebak untuk selera Anda, Anda bisa menggunakan daftar yang merupakan nkali jumlah hasil yang mungkin dan memasukkan setiap hasil yang mungkin ke dalamnya nkali sebelum mengocok. Atau Anda dapat mengubah susunan daftar sebelum iterasi sepenuhnya.

Philipp
sumber
1
lookup "shuffle bag" (bahkan di situs ini)
jhocking
3
Ini adalah berapa banyak permainan Tetris yang menghindari meninggalkan pemain kelaparan karena kepingan kunci terlalu lama. Penting untuk mengosongkan tas / dek seperti yang disarankan Philipp sebelum memasukkan kartu baru jika Anda ingin mengontrol kejadian pada interval yang ditentukan. Dengan memasukkan kembali kartu saat Anda berjalan (atau mengatur ulang bobot), Anda dapat mengubah distribusi probabilitas dengan cara yang sulit untuk dihitung, dan mudah salah.
DMGregory
2
@DMGregory: Sebenarnya, tidak apa-apa untuk menggabungkan kartu baru sebelum deck dikosongkan (dan, pada kenyataannya, saya akan merekomendasikan melakukan ini untuk membuat hasil lebih alami dan lebih sulit untuk diprediksi). Yang penting adalah untuk memastikan bahwa (rata-rata) sebagian kecil dari kartu baru dikocok ke dalam dek sama dengan fraksi yang diinginkan yang Anda ingin menarik keluar dari itu.
Ilmari Karonen
4
Illmari Karonen: ketika Anda mengganti item, Anda dapat kehilangan manfaat dari shuffle bag dalam hal membatasi proses dengan hasil yang identik atau kesenjangan yang panjang antara hasil tertentu. Jika tingkat penggantian Anda sama dengan distribusi probabilitas target, Anda sekarang terbukti dalam posisi yang sama dengan menghasilkan setiap hasil secara independen secara acak. Jika tidak sama dengan distribusi probabilitas target, maka Anda dapat membelokkan probabilitas efektif dengan cara yang sulit diprediksi dan diseimbangkan - penanya menjelaskan tentang berjuang dengan masalah ini secara tepat.
DMGregory
2
Setuju dengan @DMGregory. Dengan menyeret kartu-kartu baru, Anda membatalkan sistem itu sendiri. Sistem transaksi kartu secara khusus dan sangat cocok untuk hasil yang diinginkan. Misalnya, ketika Anda menghapus Ratu (menggunakan kartu tradisional misalnya) dari dek, probabilitas menggambar Ratu berkurang, dan kemungkinan gambar kartu lain selain Ratu meningkat. Ini adalah sistem penyesuaian diri, jika Anda mau.
Volte
17

Anda dapat mencoba Grafik Acak Markov . Pertimbangkan setiap peristiwa yang dapat terjadi sebagai simpul dalam grafik. Dari setiap acara, buat tautan ke acara lainnya yang mungkin bisa terjadi setelahnya. Masing-masing tautan ini diberi bobot oleh sesuatu yang disebut probabilitas transisi . Kemudian, Anda melakukan jalan acak grafik sesuai dengan model transisi.

Misalnya, Anda dapat memiliki grafik yang mewakili hasil serangan (serangan kritis, menghindar, dll.). Inisialisasi simpul awal menjadi satu pick secara acak mengingat statistik pemain (cukup "lempar dadu"). Kemudian, pada serangan berikutnya, tentukan apa yang terjadi selanjutnya dengan diberikan model transisi.

Kehati-hatian harus diambil untuk memutuskan bagaimana menentukan transisi. Untuk satu hal, semua transisi yang keluar dari sebuah simpul perlu dijumlahkan hingga probabilitas 1. Satu hal sederhana yang dapat Anda lakukan adalah melakukan transisi dari setiap simpul ke setiap simpul lainnya, dengan bobot yang setara dengan probabilitas bahwa peristiwa-peristiwa itu terjadi a priori , mengingat bahwa kejadian saat ini tidak dapat terjadi lagi.

Misalnya, jika Anda memiliki tiga acara:

  Critical, P = 0.1
  Hit,      P = 0.3
  Miss,     P = 0.6

Anda dapat mengatur model transisi sedemikian rupa sehingga hit kritis tidak terjadi lagi hanya dengan mendistribusikan kembali massa probabilitasnya ke peristiwa lain secara seragam:

  Critical -> Critical,   P = 0.0
  Critical -> Hit,        P = 0.35
  Critical -> Miss,       P = 0.65

EDIT: Seperti komentar di bawah ini, model ini tidak cukup rumit untuk mendapatkan perilaku yang diinginkan. Sebagai gantinya, Anda mungkin harus menambahkan beberapa status tambahan!

mklingen
sumber
1
Skema reweighting yang Anda usulkan tidak mempertahankan probabilitas yang diinginkan masing-masing negara. Melakukan tes empiris dengan angka-angka ini, rindu terjadi sekitar 41% dari waktu dan Kritis sekitar 25%, jauh dari nilai input. Transisi ke negara-negara yang tersisa sebanding dengan probabilitas mereka (mis. Miss memiliki peluang 25% untuk pergi ke Crit dan 75% kemungkinan pergi ke Hit) melakukan sedikit lebih baik, dengan tingkat kehilangan 44% dan 17% krit, tetapi masih tidak mencerminkan probabilitas yang diinginkan dalam input.
DMGregory
Saya lupa aturan bayes :( Akan dihitung ulang lagi nanti. Mungkin tidak mungkin untuk mempertahankan distribusi probabilitas sebelumnya karena model transisi seperti berdiri meninggalkan kemungkinan urutan seperti CCHM atau CHHM atau MMHM yang sangat mungkin, dll.
mklingen
Batasan "no repeats" mungkin mengikat tangan Anda di sini, terkait dengan bobot sangat tinggi & rendah. Jika Anda ingin 1 dari 10 upaya menjadi Kritis, satu-satunya cara metode ini dapat memenuhi itu adalah dengan mengganti 5 Misses & 5 hit, yang mendistorsi probabilitas hit & miss menuju rata-rata mereka. Tidak ada urutan tanpa kesalahan berturut-turut yang dapat memenuhi persyaratan input di sini.
DMGregory
4
@mklingen, saya setuju dengan DMGregory, "sama sekali tidak ada pengulangan" tidak diinginkan di sini. Sebaliknya, mereka ingin probabilitas rantai panjang dari hasil yang sama lebih kecil kemungkinannya dibandingkan dengan probabilitas acak yang seragam. Anda bisa melakukan ini dengan Rantai Markov (yang diarahkan) yang terlihat seperti ini . Ini menggunakan banyak negara untuk mewakili peristiwa berulang di mana probabilitas transisi dari "Hit 1" ke "Hit 2" dan "Hit 2" ke "Hit 3+" turun dan probabilitas transisi kembali ke "Hit 1" dan "Crit 1 "naik.
nwellcome
@nwellcome, itu ide yang bagus.
mklingen
3

Berikut ini adalah implementasi yang saya buat di C # yang akan:

  • Aktifkan acara berdasarkan probabilitas
  • Sesuaikan probabilitas tersebut untuk mengurangi kemungkinan kejadian berulang
  • Tidak menyimpang terlalu jauh dari probabilitas asli

Saya telah menambahkan beberapa komentar sehingga Anda dapat melihat apa yang saya lakukan.

    int percentageEvent1 = 15; //These are the starter values. So given a scenario, the
    int percentageEvent2 = 40; //player would have around a 15 percent chance of event
    int percentageEvent3 = 10; //one occuring, a 40 percent chance of event two occuring
    int percentageEvent4 = 35; //10 percent for event three, and 35 percent for event four.

    private void ResetValues()
    {
        percentageEvent1 = 15;
        percentageEvent2 = 40;
        percentageEvent3 = 10;
        percentageEvent4 = 35;
    }

    int resetCount = 0; //Reset the probabilities every so often so that they don't stray too far.

    int variability = 1; //This influences how much the chance of an event will increase or decrease
                           //based off of past events.

    Random RandomNumberGenerator = new Random();

    private void Activate() //When this is called, an "Event" will be activated based off of current probability.
    {
        int[] percent = new int[100];
        for (int i = 0; i < 100; i++) //Generate an array of 100 items, and select a random event from it.
        {
            if (i < percentageEvent1)
            {
                percent[i] = 1; //Event 1
            }
            else if (i < percentageEvent1 + percentageEvent2)
            {
                percent[i] = 2; //Event 2
            }
            else if (i < percentageEvent1 + percentageEvent2 + percentageEvent3)
            {
                percent[i] = 3; //Event 3
            }
            else
            {
                percent[i] = 4; //Event 4
            }
        }
        int SelectEvent = percent[RandomNumberGenerator.Next(0, 100)]; //Select a random event based on current probability.

        if (SelectEvent == 1)
        {
            if (!(percentageEvent1 - (3 * variability) < 1)) //Make sure that no matter what, probability for a certain event
            {                                                //does not go below one percent.
                percentageEvent1 -= 3 * variability;
                percentageEvent2 += variability;
                percentageEvent3 += variability;
                percentageEvent4 += variability;
            }
        }
        else if (SelectEvent == 2)
        {
            if (!(percentageEvent2 - (3 * variability) < 1))
            {
                percentageEvent2 -= 3 * variability;
                percentageEvent1 += variability;
                percentageEvent3 += variability;
                percentageEvent4 += variability;
            }
        }
        else if (SelectEvent == 3)
        {
            if (!(percentageEvent3 - (3 * variability) < 1))
            {
                percentageEvent3 -= 3 * variability;
                percentageEvent1 += variability;
                percentageEvent2 += variability;
                percentageEvent4 += variability;
            }
        }
        else
        {
            if (!(percentageEvent4 - (3 * variability) < 1))
            {
                percentageEvent4 -= 3 * variability;
                percentageEvent1 += variability;
                percentageEvent2 += variability;
                percentageEvent3 += variability;
            }
        }

        resetCount++;
        if (resetCount == 10)
        {
            resetCount = 0;
            ResetValues();
        }

        RunEvent(SelectEvent); //Run the event that was selected.
    }

Semoga ini bisa membantu, tolong sarankan perbaikan kode ini di komentar, terima kasih!

Superdoggy
sumber
1
Skema reweighting ini cenderung membuat acara menjadi bisa disetarakan. Menyetel ulang bobot secara berkala sebenarnya hanyalah bantuan band yang membatasi seberapa buruknya, sambil memastikan bahwa 1 dari 10 gulungan tidak mendapat manfaat sama sekali dari reweighting. Juga, satu catatan algoritme: Anda menyia-nyiakan banyak pekerjaan dengan mengisi tabel 100 entri untuk melakukan pemilihan acak Anda. Alih-alih, Anda bisa menghasilkan gulungan acak dan kemudian mengulangi 4 hasil Anda, menjumlahkan probabilitas mereka saat Anda melangkah. Begitu gulungan kurang dari jumlah, Anda memiliki hasil. Tidak perlu mengisi meja.
DMGregory
3

Biarkan saya menggeneralisasi jawaban mklingen sedikit. Pada dasarnya, Anda ingin menerapkan Kekeliruan Gambler , meskipun saya akan memberikan metode yang lebih umum di sini:

Katakanlah ada nkemungkinan kejadian dengan probabilitas p_1, p_2, ..., p_n. Ketika suatu peristiwa iterjadi, kemungkinannya akan berskala kembali dengan faktor 0≤a_i≤1/p_i(yang terakhir adalah penting, jika tidak, Anda berakhir dengan probabilitas lebih besar dari satu dan peristiwa lainnya harus memiliki probabilitas negatif , yang pada dasarnya berarti " anti " -kejadian. Atau sesuatu), meskipun biasanya a_i<1. Misalnya a_i=p_i, Anda dapat memilih , yang berarti probabilitas suatu peristiwa terjadi untuk kedua kalinya adalah probabilitas asli kejadian yang terjadi tepat dua kali berturut-turut, misalnya lemparan koin kedua akan memiliki probabilitas 1/4 bukannya 1/2. Di sisi lain, Anda juga dapat memiliki beberapa a_i>1, yang berarti memicu "pukulan keberuntungan".

Semua peristiwa lain harus tetap sama kemungkinannya relatif satu sama lain, yaitu mereka semua harus diubah dengan faktor yang sama b_isehingga jumlah semua probabilitas sama dengan satu, yaitu

1 = a_i*p_i + b_i*(1-p_i)  # Σ_{j≠i) p_j  = 1 - p_i
 b_i = (1 - a_i*p_i) / (1 - p_i).   (1)

Sejauh ini, sangat sederhana. Tetapi sekarang mari kita tambahkan persyaratan lain: Mempertimbangkan semua urutan yang mungkin dari dua peristiwa, probabilitas peristiwa tunggal yang diekstraksi darinya akan menjadi probabilitas asli.

Membiarkan

        / p_i * b_i * p_j  (ji)
p_ij = <
        \ a_i * (p_i     (j=i)

menunjukkan probabilitas peristiwa yang jterjadi setelah peristiwa idan perhatikan bahwa p_ij≠p_jikecuali b_i=b_j (2)(yang secara tidak (1)langsung menyatakan a_j = 1 - a_i*p_i + (1-a_i)*p_i/p_j). Ini juga yang dibutuhkan teorema Bayes dan ini juga menyiratkan

Σ_j p_ij = p_i * b_i * (1 - p_i) + a_i * (p_i
         = b_i * p_i + (a_i - b_i) * (p_i
         = p_i  # using (1)

seperti yang diinginkan. Hanya perhatikan bagaimana ini berarti satu a_imemperbaiki semua yang lainnya.


Sekarang mari kita lihat apa yang terjadi ketika kita menerapkan prosedur ini beberapa kali, yaitu untuk urutan tiga dan lebih banyak peristiwa. Pada dasarnya ada dua opsi untuk pilihan probabilitas kecurangan acara ketiga:

a) Lupakan acara pertama dan rig seolah-olah hanya yang kedua terjadi, yaitu

         / p_ij * a_j * p_j  (j=k)
p_ijk = <
         \ p_ij * b_j * p_l  (jk)

Perhatikan bahwa ini biasanya melanggar Bayes, karena misalnya p_jik≠p_ikjdalam kebanyakan kasus.

b) Gunakan gunakan probabilitas p_ij(untuk tetap i) sebagai probabilitas baru pi_jdari mana Anda mendapatkan probabilitas baru pi_jkuntuk acarak akan terjadi selanjutnya. Apakah Anda memodifikasi ai_jatau tidak itu terserah Anda, tetapi perlu diingat bahwa yang baru bi_jpasti berbeda karena yang dimodifikasi pi_j. Kemudian lagi, pilihan ai_jmungkin dibatasi dengan mengharuskan semua permutasi ijkterjadi dengan probabilitas yang sama. Ayo lihat...

         / p_ij * bi_j * pi_k  (jk)
p_ijk = <
         \ (p_ij * ai_j      (j=k)

         / b_i * bi_j * p_i * p_j * pi_k  (ijki)
         | b_i * ai_j * p_i * (p_j      (ij=k)
      = <  a_i * (p_i * bi_i * pi_k     (i=jk)
         | b_i * p_i * bi_j * p_k * pi_i  (i=kj)
         \ a_i * ai_i * (p_i * pi_i     (i=k=j)

dan permutasi sikliknya, yang harus sama untuk masing-masing kasus.

Saya khawatir kelanjutan saya pada ini harus menunggu beberapa saat ...

Tobias Kienzler
sumber
Menguji ini secara empiris, ini masih menghasilkan distorsi jauh dari probabilitas input selama banyak berjalan. Jika a_i / p_i = 0,5 misalnya, (dan menggunakan angka dari jawaban mklingen), tingkat kesalahan input 60% menjadi tingkat yang diamati sebesar 50,1%, dan tingkat input kritis 10% diamati sebesar 13,8%. Anda dapat memverifikasi ini dengan mengambil matriks transisi yang dihasilkan ke daya tinggi. Memilih rasio a_i: p_i lebih dekat ke 1 menghasilkan distorsi lebih sedikit, tetapi juga kurang efektif dalam mengurangi berjalan.
DMGregory
@DMGregory good point: Anda tidak bisa begitu saja mengambil kekuatan dari matriks transisi. Saya akan memperluas jawaban saya nanti
Tobias Kienzler
@DMGregory Saya mulai menggambarkan proses lengkap (varian b)), tetapi menjadi cukup membosankan dan saya saat ini kekurangan waktu: /
Tobias Kienzler
1

Saya pikir pilihan terbaik adalah menggunakan pemilihan item tertimbang secara acak. Ada implementasi untuk C # di sini , tetapi mereka dapat dengan mudah ditemukan atau dibuat untuk bahasa lain juga.

Idenya adalah untuk mengurangi bobot opsi setiap kali itu diambil, dan menambahnya setiap kali itu tidak diambil.

Misalnya, jika Anda mengurangi bobot opsi yang dipilih NumOptions-1dan menambah bobot setiap opsi lainnya sebesar 1 (berhati-hati untuk menghapus item dengan berat <0 dan membacanya saat mereka naik di atas 0) , setiap opsi akan diambil kira-kira jumlah yang sama dalam jangka waktu yang lama, tetapi opsi yang baru-baru ini dipilih akan lebih kecil kemungkinannya untuk dipilih.


Masalah dengan menggunakan pemesanan acak, seperti yang disarankan oleh banyak jawaban lain, adalah bahwa setelah setiap opsi tetapi satu telah dipilih, Anda dapat memprediksi dengan kepastian 100% opsi apa yang akan diambil berikutnya. Itu tidak terlalu acak.

BlueRaja - Danny Pflughoeft
sumber
1

Jawaban saya salah, tes saya cacat.

Saya meninggalkan jawaban ini di sini untuk diskusi dan komentar yang menunjukkan kekurangan dalam desain ini, tetapi tes yang sebenarnya salah.

Yang Anda cari adalah bobot tertimbang: bobot untuk empat kemungkinan hasil Anda perlu disesuaikan lebih lanjut (tertimbang) dengan hasil sebelumnya, sambil tetap mempertahankan bobot yang tepat secara keseluruhan.

Cara termudah untuk mencapai ini adalah dengan mengubah semua bobot untuk setiap gulungan dengan mengurangi bobot untuk nilai spesifik yang digulung dan menambah bobot lainnya .

Sebagai contoh, katakanlah Anda memiliki 4 bobot: Fumble, Miss, Hit, dan Crit. Katakan juga bobot keseluruhan yang Anda inginkan untuk mereka adalah Fumble = 10%, Miss = 50%, Hit = 30%, dan Crit = 10%.

Jika Anda menggunakan generator angka acak (RNG) untuk menghasilkan nilai antara 1 dan 100, dan kemudian membandingkan nilai itu dengan di mana ia berada dalam kisaran ini (1-10 Fumble, 11-60 miss, 61-90 hit, 91-100 crit ), Anda menghasilkan gulungan individual.

Jika, ketika Anda membuat gulungan itu, Anda kemudian segera menyesuaikan rentang tersebut berdasarkan nilai yang digulung, Anda akan menimbang gulungan berikutnya, tetapi Anda juga perlu mengurangi bobot gulungan tersebut dengan jumlah total yang sama dengan yang Anda menambah bobot lainnya. Jadi, dalam contoh kami di atas, Anda akan mengurangi berat gulungan sebesar 3 dan menambah bobot lainnya masing-masing sebesar 1.

Jika Anda melakukan ini untuk setiap gulungan, Anda masih akan memiliki peluang goresan, tetapi mereka akan sangat berkurang, karena untuk setiap gulungan Anda meningkatkan peluang bahwa gulungan di masa depan akan menjadi apa pun selain apa gulungan saat ini. Anda dapat meningkatkan efek ini, dan dengan demikian semakin mengurangi kemungkinan goresan, dengan menambah / mengurangi bobot dengan faktor yang lebih besar (mis. Kurangi arus sebesar 6 dan tambah yang lain sebesar 2).

Saya menjalankan aplikasi cepat untuk memvalidasi pendekatan ini, dan setelah 32000 iterasi dengan bobot tersebut, itu menghasilkan grafik berikut. Grafik atas menunjukkan 4 bobot nilai langsung pada setiap gulungan, dan grafik yang lebih rendah menunjukkan jumlah penjumlahan dari setiap jenis hasil yang digulung hingga ke titik itu.

Seperti yang Anda lihat, bobot berfluktuasi sedikit di sekitar nilai yang diinginkan, tetapi bobot keseluruhan tetap dalam kisaran yang diinginkan, dan setelah variasi awal dari angka awal menetap, hasilnya cocok dengan persentase yang diinginkan hampir sempurna.

Perhatikan bahwa contoh ini dibuat menggunakan kelas .NET System.Random, yang sebenarnya bukan salah satu RNG yang lebih baik di luar sana, jadi Anda mungkin bisa mendapatkan hasil yang lebih akurat dengan menggunakan RNG yang lebih baik. Perhatikan juga bahwa 32000 adalah hasil maksimum yang dapat saya grafik dengan alat ini, tetapi alat pengujian saya mampu menghasilkan lebih dari 500 juta hasil dengan pola keseluruhan yang sama.

David C Ellis
sumber
Perhatikan bahwa ini hanya berfungsi jika +1 Anda / -3 diterapkan relatif terhadap bobot asli, daripada bobot yang terakhir digunakan. (Terus-menerus memodifikasi bobot secara seragam seperti ini membuat mereka melayang ke arah yang dapat disetel). Meskipun hal ini menjaga probabilitas on-target dalam jangka panjang, itu sangat sedikit untuk mengurangi jalan. Mengingat bahwa saya telah melewatkan satu kali, peluang bahwa saya akan kehilangan dua kali berturut-turut adalah 22% dengan skema ini, vs 25% dengan hasil imbang independen. Meningkatkan pergeseran berat untuk efek yang lebih besar (katakanlah ke + 3 / -9) menghasilkan bias kemungkinan jangka panjang.
DMGregory
Sebenarnya data yang disajikan di atas menerapkan +1 / -3 untuk bobot terbaru setiap kali gulungan diproses. Jadi, jika Anda kehilangan satu kali pada berat 50% awal, berat kehilangan berikutnya adalah 47%, dan jika Anda kehilangan lagi, berat berikut adalah 44%, dan seterusnya. Itu mengurangi jalan (metrik terpisah melacak jalan, ditemukan sebanyak pengurangan jalan 24%), tetapi mereka masih tak terhindarkan karena skema ini masih memiliki peluang kuat untuk meninggalkan masing-masing dari 4 bobot dengan probabilitas bukan nol ( mis. Empat crit berturut-turut akan meninggalkan bobot crit dengan kesempatan nol terjadi).
David C Ellis
Jika itu maksud Anda, maka implementasi Anda memiliki bug. Lihat grafik - Bobot gagal hanya memantul antara 7 dan 11, tanpa nilai di luar itu. Saya menjalankan simulasi menggunakan modifikasi berkelanjutan yang Anda gambarkan, dan grafiknya sangat berbeda, dengan probabilitas setiap negara konvergen menuju 25% masing-masing dalam seratus percobaan pertama.
DMGregory
Dangit, memang itu disadap seperti yang Anda tunjukkan. Baiklah, serang jawaban ini.
David C Ellis
@ Davidvidll Apakah Anda mengatakan implementasi Anda cacat, atau idenya sendiri? Intuisi back-of-a-serbet saya datang ke kira-kira model yang Anda gambarkan (sesuaikan probabilitas ke bawah saat ditarik, secara bertahap kembalikan semua probabilitas ke nilai aslinya dari waktu ke waktu) dan itu masih masuk akal bagi saya.
dimo414
0

Anda dapat melakukan apa yang pada dasarnya adalah filter. Melacak masa lalu dan acara. Probabilitasnya adalah sebagian dari beberapa filter yang diterapkan pada peristiwa tersebut. Filter ke-0 adalah probabilitas dasar, jika 0 maka Anda menghindar, jika 1 Anda gagal. Katakanlah basis adalah 25%, dan filter berkurang setengah setiap iterasi. Filter Anda akan menjadi:

[.25 .125 .0625 .03125] 

Silakan lanjutkan jika Anda mau. Probabilitas keseluruhan skema ini sedikit lebih tinggi dari probabilitas dasar 0,25. Faktanya, probabilitas, dengan skema yang sama, adalah (Saya memanggil x probabilitas nyata, p adalah input probabilitas):

x=p+(1-x)*(p/2+p/4+p/8)

Memecahkan untuk x, orang menemukan jawabannya adalah p(1+1/2+1/4+1/8)/(1+p(1/2+1/4+1/8), atau untuk kasus kami x=0.38461538461,. Tetapi yang Anda inginkan adalah menemukan p, mengingat x. Itu ternyata menjadi masalah yang lebih sulit. Jika Anda mengasumsikan filter tak terbatas, masalahnya menjadi x+x*p=2*p, atau p=x/(2-x). Jadi dengan meningkatkan filter Anda, Anda kemudian bisa menyelesaikannya dengan angka p yang rata-rata akan memberi Anda hasil yang sama, tetapi pada tingkat yang tergantung pada seberapa banyak kesuksesan yang baru-baru ini terjadi.

Pada dasarnya, Anda menggunakan nilai-nilai sebelumnya untuk menentukan apa ambang penerimaan putaran ini, dan mengambil nilai acak. Kemudian menghasilkan nilai acak berikutnya yang diberi filter.

PearsonArtPhoto
sumber
-1

Sama seperti yang Anda usulkan sendiri, salah satu pendekatan untuk ini adalah menerapkan acak tertimbang. Idenya adalah untuk membuat generator nomor acak (atau hasil) di mana bobot dan hasil dapat dimodifikasi.

Berikut ini adalah implementasi dari ini di Jawa.

import java.util.Map;
import java.util.Random;

/**
 * A psuedorandom weighted outcome generator
 * @param <E> object type to return
 */
public class WeightedRandom<E> {

    private Random random;
    private Map<E, Double> weights;

    public WeightedRandom(Map<E, Double> weights) {
        this.random = new Random();
        this.weights = weights;
    }

    /**
     * Returns a random outcome based on the weight of the outcomes
     * @return
     */
    public E nextOutcome() {
        double totalweight = 0;

        // determine the total weigth
        for (double w : weights.values()) totalweight += w;

        // determine a value between 0.0 and the total weight
        double remaining = random.nextDouble() * totalweight;

        for (E entry : weights.keySet()) {
            // subtract the weight of this entry
            remaining -= weights.get(entry);

            // if the remaining is smaller than 0, return this entry
            if (remaining <= 0) return entry;
        }

        return null;
    }

    /**
     * Returns the weight of an outcome
     * @param outcome the outcome to query
     * @return the weight of the outcome, if it exists
     */
    public double getWeight(E outcome) {
        return weights.get(outcome);
    }

    /**
     * Sets the weight of an outcome
     * @param outcome the outcome to change
     * @param weight the new weigth
     */
    public void setWeight(E outcome, double weight) {
        weights.put(outcome, weight);
    }
}

EDIT Dalam kasus di mana Anda ingin menyesuaikan bobot secara otomatis, misalnya meningkatkan peluang A ketika hasilnya adalah B. Anda bisa,

  1. Ubah perilaku nextOutcome() metode, sehingga memodifikasi bobot sesuai dengan hasilnya
  2. Gunakan setWeight()untuk memodifikasi bobot sesuai dengan hasilnya.
erikgaal
sumber
Saya pikir Anda mungkin salah membaca pertanyaan: OP tidak menanyakan bagaimana cara menghasilkan hasil acak tertimbang, tetapi bagaimana menyesuaikan bobot untuk mengurangi kemungkinan hasil yang sama terjadi beberapa kali berturut-turut.
Ilmari Karonen
Saya mengerti, saya telah mengubah beberapa jawaban saya untuk menjelaskan bagaimana itu mungkin menggunakan sistem ini.
erikgaal