Bagaimana cara membuat koleksi tertimbang dan kemudian mengambil elemen acak darinya?

34

Saya memiliki kotak jarahan yang ingin saya isi dengan item acak. Tapi saya ingin setiap item memiliki kesempatan berbeda untuk dipilih. Sebagai contoh:

  • 5% peluang 10 emas
  • 20% kemungkinan pedang
  • 45% kemungkinan perisai
  • 20% kemungkinan baju besi
  • 10% kemungkinan ramuan

Bagaimana saya bisa membuatnya sehingga saya dapat memilih salah satu item di atas, di mana persentase tersebut adalah peluang masing-masing untuk mendapatkan hasil rampasan?

Evorlor
sumber
1
FYI, secara teori, O (1) waktu per sampel dimungkinkan untuk setiap distribusi terbatas, bahkan distribusi yang entri-entrinya berubah secara dinamis. Lihat misalnya cstheory.stackexchange.com/questions/37648/… .
Neal Young

Jawaban:

37

Solusi Probabilitas Berkode Lunak

Solusi probabilitas hardcoded memiliki kelemahan yang Anda butuhkan untuk mengatur probabilitas dalam kode Anda. Anda tidak dapat menentukannya saat runtime. Ini juga sulit dipertahankan.

Berikut ini adalah versi dinamis dari algoritma yang sama.

  1. Buat array pasangan item aktual dan berat masing-masing item
  2. Saat Anda menambahkan item, berat item harus beratnya sendiri ditambah jumlah bobot semua item yang sudah ada dalam array. Jadi, Anda harus melacak jumlahnya secara terpisah. Terutama karena Anda akan membutuhkannya untuk langkah selanjutnya.
  3. Untuk mengambil objek, buat angka acak antara 0 dan jumlah bobot semua item
  4. iterate array dari awal sampai akhir sampai Anda menemukan entri dengan bobot lebih besar atau sama dengan angka acak

Berikut adalah contoh implementasi di Jawa dalam bentuk kelas templat yang dapat Anda instantiate untuk objek apa pun yang digunakan gim Anda. Anda kemudian dapat menambahkan objek dengan metode .addEntry(object, relativeWeight)dan memilih salah satu entri yang Anda tambahkan sebelumnya.get()

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class WeightedRandomBag<T extends Object> {

    private class Entry {
        double accumulatedWeight;
        T object;
    }

    private List<Entry> entries = new ArrayList<>();
    private double accumulatedWeight;
    private Random rand = new Random();

    public void addEntry(T object, double weight) {
        accumulatedWeight += weight;
        Entry e = new Entry();
        e.object = object;
        e.accumulatedWeight = accumulatedWeight;
        entries.add(e);
    }

    public T getRandom() {
        double r = rand.nextDouble() * accumulatedWeight;

        for (Entry entry: entries) {
            if (entry.accumulatedWeight >= r) {
                return entry.object;
            }
        }
        return null; //should only happen when there are no entries
    }
}

Pemakaian:

WeightedRandomBag<String> itemDrops = new WeightedRandomBag<>();

// Setup - a real game would read this information from a configuration file or database
itemDrops.addEntry("10 Gold",  5.0);
itemDrops.addEntry("Sword",   20.0);
itemDrops.addEntry("Shield",  45.0);
itemDrops.addEntry("Armor",   20.0);
itemDrops.addEntry("Potion",  10.0);

// drawing random entries from it
for (int i = 0; i < 20; i++) {
    System.out.println(itemDrops.getRandom());
}

Ini adalah kelas yang sama yang diimplementasikan dalam C # untuk proyek Unity, XNA atau MonoGame Anda:

using System;
using System.Collections.Generic;

class WeightedRandomBag<T>  {

    private struct Entry {
        public double accumulatedWeight;
        public T item;
    }

    private List<Entry> entries = new List<Entry>();
    private double accumulatedWeight;
    private Random rand = new Random();

    public void AddEntry(T item, double weight) {
        accumulatedWeight += weight;
        entries.Add(new Entry { item = item, accumulatedWeight = accumulatedWeight });
    }

    public T GetRandom() {
        double r = rand.NextDouble() * accumulatedWeight;

        foreach (Entry entry in entries) {
            if (entry.accumulatedWeight >= r) {
                return entry.item;
            }
        }
        return default(T); //should only happen when there are no entries
    }
}

Dan di sini ada satu dalam JavaScript :

var WeightedRandomBag = function() {

    var entries = [];
    var accumulatedWeight = 0.0;

    this.addEntry = function(object, weight) {
        accumulatedWeight += weight;
        entries.push( { object: object, accumulatedWeight: accumulatedWeight });
    }

    this.getRandom = function() {
        var r = Math.random() * accumulatedWeight;
        return entries.find(function(entry) {
            return entry.accumulatedWeight >= r;
        }).object;
    }   
}

Pro:

  • Dapat menangani rasio berat apa pun. Anda dapat memiliki item dengan probabilitas astronomis kecil di set jika Anda mau. Bobotnya juga tidak perlu ditambah hingga 100.
  • Anda dapat membaca item dan bobot saat runtime
  • Penggunaan memori sebanding dengan jumlah item dalam array

Kontra:

  • Membutuhkan lebih banyak pemrograman untuk bisa benar
  • Dalam kasus terburuk, Anda mungkin harus mengulang seluruh array ( O(n)kompleksitas runtime). Jadi, ketika Anda memiliki satu set barang yang sangat besar dan menggambar sangat sering, itu mungkin menjadi lambat. Optimalisasi sederhana adalah menempatkan item yang paling memungkinkan terlebih dahulu sehingga algoritma berakhir lebih awal dalam kebanyakan kasus. Optimasi yang lebih kompleks yang dapat Anda lakukan adalah memanfaatkan fakta bahwa array diurutkan dan melakukan pencarian membagi dua. Ini hanya butuh O(log n)waktu.
  • Anda perlu membuat daftar dalam memori sebelum Anda dapat menggunakannya (walaupun Anda dapat dengan mudah menambahkan item saat runtime. Menghapus item juga dapat ditambahkan, tetapi itu perlu memperbarui bobot timbunan semua item yang datang setelah entri yang dihapus, yang lagi memiliki O(n)runtime kasus terburuk)
Philipp
sumber
2
Kode C # dapat ditulis menggunakan LINQ: return entries.FirstOrDefault (e => e.accumulatedWeight> = r). Lebih penting lagi, ada sedikit kemungkinan bahwa karena kehilangan presisi floating point, algoritma ini akan mengembalikan nol jika nilai acak mendapat sedikit lebih besar dari nilai akumulasi. Sebagai tindakan pencegahan, Anda mungkin menambahkan nilai kecil (katakanlah, 1.0) ke elemen terakhir, tetapi kemudian Anda harus secara eksplisit menyatakan dalam kode Anda bahwa daftar itu final.
IMil
1
Satu varian kecil dalam hal ini yang saya gunakan secara pribadi, jika Anda ingin nilai bobot dalam runtime tidak diubah ke nilai bobot-plus-semua-sebelumnya, Anda dapat mengurangi bobot setiap entri yang lulus dari nilai acak Anda, berhenti ketika nilai acak kurang dari berat item saat ini (atau ketika mengurangi berat membuat nilai <0)
Lunin
2
@ BlueRaja-DannyPflughoeft optimasi prematur ... pertanyaannya adalah tentang memilih objek dari kotak jarahan terbuka. Siapa yang akan membuka 1000 kotak per detik?
IMil
4
@IMil: Tidak, pertanyaannya adalah tangkapan umum semua untuk memilih item berbobot acak . Khusus untuk kotak loot, jawaban ini mungkin baik karena ada sejumlah kecil item dan kemungkinan tidak berubah (meskipun, karena biasanya dilakukan di server, 1000 / dtk tidak realistis untuk gim populer) .
BlueRaja - Danny Pflughoeft
4
@opa lalu beri tanda untuk menutup sebagai korban penipuan. Apakah benar salah memilih jawaban yang baik hanya karena pertanyaannya sudah diajukan sebelumnya?
Baldrickk
27

Catatan: Saya membuat perpustakaan C # untuk masalah ini

Solusi lain baik-baik saja jika Anda hanya memiliki sejumlah kecil item dan probabilitas Anda tidak pernah berubah. Namun, dengan banyak item atau perubahan probabilitas (mis. Menghapus item setelah memilihnya) , Anda akan menginginkan sesuatu yang lebih kuat.

Berikut adalah dua solusi paling umum (keduanya termasuk dalam perpustakaan di atas)

Metode Alias ​​Walker

Solusi cerdas yang sangat cepat ( O(1)!) Jika probabilitas Anda konstan. Intinya, algoritme ini membuat papan panah 2D ("tabel alias") dari probabilitas Anda dan melempar panah ke sana.

Papan panah

Ada banyak artikel daring tentang cara kerjanya jika Anda ingin mempelajari lebih lanjut.

Satu-satunya masalah adalah jika probabilitas Anda berubah, Anda perlu membuat ulang tabel alias, yang lambat. Jadi, jika Anda perlu menghapus item setelah diambil, ini bukan solusi untuk Anda.

Solusi berbasis pohon

Solusi umum lainnya adalah membuat array di mana setiap item menyimpan jumlah probabilitasnya dan semua item sebelumnya. Kemudian cukup buat angka acak dari [0,1) dan lakukan pencarian biner untuk mengetahui nomor mana yang masuk dalam daftar.

Solusi ini sangat mudah untuk dikodekan / dipahami, tetapi membuat pilihan lebih lambat daripada Metode Alias ​​Walker, dan masih tetap mengubah probabilitasnya O(n). Kita bisa memperbaikinya dengan mengubah array menjadi pohon pencarian biner, di mana setiap node melacak jumlah probabilitas di semua item dalam subtree-nya. Kemudian ketika kita menghasilkan angka dari [0,1), kita bisa berjalan turun pohon untuk menemukan item yang diwakilinya.

Ini memberi kami O(log n)untuk memilih item dan mengubah probabilitas! Ini membuat NextWithRemoval()sangat cepat!

Hasil

Berikut adalah beberapa tolok ukur cepat dari perpustakaan di atas, membandingkan dua pendekatan ini

         Tolok Ukur WeightedRandomizer | Pohon | Meja
-------------------------------------------------- ---------------------------------
Tambah () x10000 + NextWithReplacement () x10: | 4 ms | 2 ms
Tambah () x10000 + NextWithReplacement () x10000: | 7 ms | 4 ms
Tambah () x10000 + NextWithReplacement () x100000: | 35 ms | 28 md
(Tambah () + NextWithReplacement ()) x10000 (disisipkan) | 8 ms | 5403 ms
Tambah () x10000 + NextWithRemoval () x10000: | 10 ms | 5948 ms

Jadi seperti yang Anda lihat, untuk kasus khusus probabilitas statis (tidak berubah), metode Alias ​​Walker sekitar 50-100% lebih cepat. Tetapi dalam kasus yang lebih dinamis, pohon itu beberapa kali lipat lebih cepat !

BlueRaja - Danny Pflughoeft
sumber
Solusi berbasis pohon juga memberi kami run-time ( nlog(n)) yang layak saat menyortir item berdasarkan berat.
Nathan Merrill
2
Saya ragu dengan hasil Anda, tetapi ini adalah jawaban yang benar. Tidak yakin mengapa ini bukan jawaban atas, mengingat ini adalah benar-benar cara kanonik untuk menangani masalah ini.
whn
File mana yang berisi solusi berbasis pohon? Kedua, tabel tolok ukur Anda: apakah Walker Alias ​​adalah kolom "tabel"?
Yakk
1
@ Yakk: Kode untuk solusi berbasis pohon ada di sini . Itu dibangun di atas implementasi open-source dari pohon-AA . Dan 'ya' untuk pertanyaan kedua Anda.
BlueRaja - Danny Pflughoeft
1
Bagian Walker cukup hanya tautan saja.
Akumulasi
17

Solusi Roda Keberuntungan

Anda dapat menggunakan metode ini ketika probabilitas dalam kumpulan item Anda memiliki penyebut umum yang agak besar dan Anda harus sering menggunakannya.

Buat berbagai opsi. Tetapi masukkan setiap elemen ke dalamnya beberapa kali, dengan jumlah duplikat dari setiap elemen sebanding dengan peluangnya untuk muncul. Untuk contoh di atas, semua elemen memiliki probabilitas yang merupakan pengganda 5%, sehingga Anda dapat membuat array 20 elemen seperti ini:

10 gold
sword
sword
sword
sword
shield
shield
shield
shield
shield
shield
shield
armor
armor
armor
armor
potion
potion

Kemudian cukup pilih elemen acak dari daftar itu dengan menghasilkan satu bilangan bulat acak antara 0 dan panjang array - 1.

Kekurangan:

  • Anda perlu membuat array saat pertama kali ingin membuat item.
  • Ketika salah satu elemen Anda seharusnya memiliki probabilitas yang sangat rendah, Anda berakhir dengan array yang sangat besar, yang dapat membutuhkan banyak memori.

Keuntungan:

  • Ketika Anda sudah memiliki array dan ingin menggambar darinya beberapa kali, maka itu sangat cepat. Hanya satu bilangan bulat acak dan satu akses larik.
Philipp
sumber
3
Sebagai solusi hybrid untuk menghindari kerugian kedua, Anda dapat menunjuk slot terakhir sebagai "lain," dan menanganinya melalui cara lain, seperti pendekatan array Philipp. Dengan demikian Anda dapat mengisi slot terakhir dengan array yang menawarkan 99,9% peluang ramuan, dan hanya 0,1% peluang sebuah Epic Scepter of the Apocalypse. Pendekatan dua tingkat seperti itu memanfaatkan keunggulan kedua pendekatan tersebut.
Cort Ammon - Reinstate Monica
1
Saya menggunakan variasi ini dalam proyek saya sendiri. Apa yang saya lakukan adalah menghitung setiap item & berat, dan menyimpannya dalam sebuah array,, [('gold', 1),('sword',4),...]menjumlahkan semua bobot, dan kemudian menggulung angka acak dari 0 ke jumlah, kemudian iterate array dan menghitung di mana angka acak mendarat (yaitu a reduce). Berfungsi baik untuk array yang sering diperbarui, dan tidak ada memori utama.
1
@Thebluefish Solusi itu dijelaskan dalam jawaban saya yang lain "Solusi Probabilitas Berkode Lunak"
Philipp
7

Solusi Probabilitas Hard-kode

Cara paling sederhana untuk menemukan item acak dari koleksi tertimbang adalah dengan menelusuri rantai pernyataan if-else, di mana setiap if-else meningkat mungkin, karena yang sebelumnya tidak mencapai.

int rand = random(100); //Random number between 1 and 100 (inclusive)
if(rand <= 5) //5% chance
{
    print("You found 10 gold!");
}
else if(rand <= 25) //20% chance
{
    print("You found a sword!");
}
else if(rand <= 70) //45% chance
{
    print("You found a shield!");
}
else if(rand <= 90) //20% chance
{
    print("You found armor!");
}
else //10% chance
{
    print("You found a potion!");
}

Alasan kondisional sama dengan kesempatannya ditambah semua peluang kondisional sebelumnya adalah karena kondisional sebelumnya telah menghilangkan kemungkinan itu sebagai item tersebut. Jadi untuk kondisi perisai else if(rand <= 70), 70 sama dengan peluang 45% dari perisai, ditambah 5% peluang emas dan 20% peluang pedang.

Keuntungan:

  • Mudah diprogram, karena tidak memerlukan struktur data.

Kekurangan:

  • Sulit dipertahankan, karena Anda perlu mempertahankan drop-rate Anda dalam kode Anda. Anda tidak dapat menentukannya saat runtime. Jadi, jika Anda menginginkan bukti lebih banyak di masa depan, Anda harus memeriksa jawaban lainnya.
Evorlor
sumber
3
Ini akan sangat menjengkelkan untuk dipertahankan. Misalnya, jika Anda ingin menghilangkan emas, dan membuat ramuan mengambil tempat, Anda perlu menyesuaikan probabilitas semua item di antara mereka.
Alexander - Pasang kembali Monica
1
Untuk menghindari masalah yang disebutkan oleh @Alexander, Anda dapat mengurangi kurs saat ini di setiap langkah, alih-alih menambahkannya ke setiap kondisi.
AlexanderJ93
2

Di C # Anda bisa menggunakan pemindaian Linq untuk menjalankan akumulator Anda untuk memeriksa terhadap nomor acak dalam kisaran 0 hingga 100.0f dan .First () untuk mendapatkan. Jadi seperti satu baris kode.

Jadi sesuatu seperti:

var item = a.Select(x =>
{
    sum += x.prob;
    if (rand < sum)
        return x.item;
    else
        return null;
 }).FirstOrDefault());

sumadalah nol integer yang diinisialisasi dan amerupakan daftar prob / item struct / tuple / instance. randadalah nomor acak yang dihasilkan sebelumnya dalam kisaran.

Ini hanya mengakumulasi jumlah di atas daftar rentang hingga melebihi angka acak yang dipilih sebelumnya, dan mengembalikan item atau null, di mana nol akan dikembalikan jika rentang nomor acak (mis. 100) kurang dari rentang bobot total karena kesalahan , dan nomor acak yang dipilih berada di luar rentang bobot total.

Namun, Anda akan melihat bahwa bobot dalam OP sangat cocok dengan distribusi normal (Bell Curve). Saya pikir secara umum Anda tidak akan menginginkan rentang tertentu, Anda akan cenderung menginginkan distribusi yang berangsur-angsur berkurang baik di sekitar kurva lonceng atau hanya pada kurva eksponensial yang menurun (misalnya). Dalam hal ini Anda bisa menggunakan rumus matematika untuk menghasilkan indeks ke dalam array item, diurutkan dalam urutan probabilitas pilihan. Contoh yang baik adalah CDF dalam distribusi normal

Juga contoh di sini .

Contoh lain adalah bahwa Anda dapat mengambil nilai acak dari 90 derajat hingga 180 derajat untuk mendapatkan kuadran kanan bawah dari sebuah lingkaran, mengambil komponen x menggunakan cos (r) dan menggunakannya untuk mengindeks ke daftar prioritas.

Dengan formula yang berbeda, Anda dapat memiliki pendekatan umum di mana Anda hanya memasukkan daftar prioritas panjang apa pun (misalnya N) dan memetakan hasil rumus (misalnya: cos (x) adalah 0 hingga 1) dengan perkalian (misalnya: Ncos (x) ) = 0 hingga N) untuk mendapatkan indeks.

Penjaga
sumber
3
Bisakah Anda memberi kami baris kode ini jika hanya satu baris? Saya tidak terbiasa dengan C # jadi saya tidak tahu apa yang Anda maksud.
HEGX64
@ HEGX64 ditambahkan tetapi menggunakan ponsel dan editor tidak berfungsi. Bisakah Anda mengedit?
Sentinel
4
Bisakah Anda mengubah jawaban ini untuk menjelaskan konsep di baliknya, alih-alih penerapan tertentu dalam bahasa tertentu?
Raimund Krämer
@ RaimundKrämer Erm, selesai?
Sentinel
Downvote tanpa penjelasan = tidak berguna dan antisosial.
WGroleau
1

Kemungkinan tidak perlu dikodekan dengan keras. Item dan ambang batas bisa bersama-sama dalam sebuah array.

for X in itemsrange loop
  If items (X).threshold < random() then
     Announce (items(X).name)
     Exit loop
  End if
End loop

Anda masih harus mengakumulasi ambang, tetapi Anda dapat melakukannya saat membuat file parameter alih-alih mengkodekannya.

WGroleau
sumber
3
Bisakah Anda menguraikan cara menghitung ambang yang benar? Misalnya, jika Anda memiliki tiga item dengan peluang 33% masing-masing, bagaimana Anda membuat tabel ini? Karena acak baru () dihasilkan setiap kali, yang pertama akan membutuhkan 0,3333, yang kedua akan membutuhkan 0,5 dan yang terakhir akan membutuhkan 1,0. Atau apakah saya salah membaca algoritme?
pipa
Anda menghitungnya seperti yang dilakukan orang lain dalam jawaban mereka. Untuk probabilitas yang sama dari item X, ambang pertama adalah 1 / X, yang kedua, 2 / X, dll.
WGroleau
Melakukan hal itu untuk 3 item dalam algoritma ini akan membuat ambang 1/3, 2/3 dan 3/3 tetapi probabilitas hasil 1/3, 4/9 dan 2/9 untuk item pertama, kedua dan ketiga. Apakah Anda benar-benar bermaksud memiliki panggilan random()dalam loop?
pipa
Tidak, itu pasti bug. Setiap cek membutuhkan nomor acak yang sama.
WGroleau
0

Saya melakukan fungsi ini: https://github.com/thewheelmaker/GDscript_Weighted_Random Now! dalam kasus Anda, Anda dapat menggunakannya seperti ini:

on_normal_case([5,20,45,20,10],0)

Ini hanya memberikan angka antara 0 hingga 4 tetapi Anda dapat meletakkannya di array di mana Anda mendapatkan item.

item_array[on_normal_case([5,20,45,20,10],0)]

Atau dalam fungsi:

item_function(on_normal_case([5,20,45,20,10],0))

Ini kodenya. Saya membuatnya di GDscript, Anda bisa, tetapi bisa mengubah bahasa lain, juga memeriksa kesalahan logika:

func on_normal_case(arrayy,transformm):
    var random_num=0
    var sum=0
    var summatut=0
    #func sumarrays_inarray(array):
    for i in range(arrayy.size()):
        sum=sum+arrayy[i]
#func no_fixu_random_num(here_range,start_from):
    random_num=randi()%sum+1
#Randomies be pressed down
#first start from zero
    if 0<=random_num and random_num<=arrayy[0]:
        #print(random_num)
        #print(array[0])
        return 0+ transformm
    summatut=summatut+arrayy[0]
    for i in range(arrayy.size()-1):
        #they must pluss together
        #if array[i]<=random_num and random_num<array[i+1]:
        if summatut<random_num and random_num<=summatut+arrayy[i+1]:
            #return i+1+transform
            #print(random_num)
            #print(summatut)
            return i+1+ transformm

        summatut=summatut+arrayy[i+1]
    pass

Kerjanya seperti ini: on_normal_case ([50,50], 0) Ini memberi 0 atau 1, keduanya memiliki probabilitas yang sama.

on_normal_case ([50,50], 1) Ini memberi 1 atau 2, keduanya memiliki probabilitas yang sama.

on_normal_case ([20,80], 1) Ini memberi 1 atau 2, ia memiliki perubahan yang lebih besar untuk mendapatkan dua.

on_normal_case ([20,80,20,20,30], 1) Ini memberikan angka acak berkisar 1-5 dan angka yang lebih besar lebih mungkin daripada angka yang lebih kecil.

on_normal_case ([20,80,0,0,20,20,30,0,0,0,0,33], 45) Lemparan dadu ini antara angka 45,46,49,50,51,56 yang Anda lihat ketika ada adalah nol tidak pernah terjadi.

Jadi fungsinya mengembalikan hanya satu bilangan acak yang bergantung pada larik array dan jumlah transformm itu, dan int dalam array adalah bobot probabilitas yang mungkin terjadi, di mana bilangan itu terletak pada array, pluss transformm number.

Narutofan
sumber