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.
Jawaban:
Pada dasarnya, yang Anda minta adalah generator acara "semi-acak" yang menghasilkan acara dengan properti berikut:
Tingkat rata-rata di mana setiap peristiwa terjadi ditentukan terlebih dahulu.
Peristiwa yang sama lebih kecil kemungkinannya terjadi dua kali berturut-turut daripada secara acak.
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:
Awalnya, biarkan e 1 = e 2 = ... = e n = 0.
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).
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:
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:
sedangkan N = 10 menghasilkan yang lebih acak:
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:
atau Anda dapat menambah e i dengan p i + acak (- c , c ), yang akan menghasilkan (untuk c = 0,1 x dtk ):
atau, untuk c = 0,5 × s :
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:
dan inilah contoh dengan peluang 50% dari setiap output secara acak:
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:
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:
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:
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":
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).
sumber
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
n
kali jumlah hasil yang mungkin dan memasukkan setiap hasil yang mungkin ke dalamnyan
kali sebelum mengocok. Atau Anda dapat mengubah susunan daftar sebelum iterasi sepenuhnya.sumber
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:
Anda dapat mengatur model transisi sedemikian rupa sehingga hit kritis tidak terjadi lagi hanya dengan mendistribusikan kembali massa probabilitasnya ke peristiwa lain secara seragam:
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!
sumber
Berikut ini adalah implementasi yang saya buat di C # yang akan:
Saya telah menambahkan beberapa komentar sehingga Anda dapat melihat apa yang saya lakukan.
Semoga ini bisa membantu, tolong sarankan perbaikan kode ini di komentar, terima kasih!
sumber
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
n
kemungkinan kejadian dengan probabilitasp_1, p_2, ..., p_n
. Ketika suatu peristiwai
terjadi, kemungkinannya akan berskala kembali dengan faktor0≤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 biasanyaa_i<1
. Misalnyaa_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 beberapaa_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_i
sehingga jumlah semua probabilitas sama dengan satu, yaituSejauh 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
menunjukkan probabilitas peristiwa yang
j
terjadi setelah peristiwai
dan perhatikan bahwap_ij≠p_ji
kecualib_i=b_j (2)
(yang secara tidak(1)
langsung menyatakana_j = 1 - a_i*p_i + (1-a_i)*p_i/p_j
). Ini juga yang dibutuhkan teorema Bayes dan ini juga menyiratkanseperti yang diinginkan. Hanya perhatikan bagaimana ini berarti satu
a_i
memperbaiki 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
Perhatikan bahwa ini biasanya melanggar Bayes, karena misalnya
p_jik≠p_ikj
dalam kebanyakan kasus.b) Gunakan gunakan probabilitas
p_ij
(untuk tetapi
) sebagai probabilitas barupi_j
dari mana Anda mendapatkan probabilitas barupi_jk
untuk acarak
akan terjadi selanjutnya. Apakah Anda memodifikasiai_j
atau tidak itu terserah Anda, tetapi perlu diingat bahwa yang barubi_j
pasti berbeda karena yang dimodifikasipi_j
. Kemudian lagi, pilihanai_j
mungkin dibatasi dengan mengharuskan semua permutasiijk
terjadi dengan probabilitas yang sama. Ayo lihat...dan permutasi sikliknya, yang harus sama untuk masing-masing kasus.
Saya khawatir kelanjutan saya pada ini harus menunggu beberapa saat ...
sumber
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-1
dan 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.
sumber
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.
sumber
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:
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):
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 kamix=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 menjadix+x*p=2*p
, ataup=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.
sumber
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.
EDIT Dalam kasus di mana Anda ingin menyesuaikan bobot secara otomatis, misalnya meningkatkan peluang A ketika hasilnya adalah B. Anda bisa,
nextOutcome()
metode, sehingga memodifikasi bobot sesuai dengan hasilnyasetWeight()
untuk memodifikasi bobot sesuai dengan hasilnya.sumber