Programmazione di un rotolo di dadi casuale ponderato "equo"

2

Sto provando a escogitare un modo per creare un "loot table" per un RPG, soprattutto per vedere se è possibile farlo.

Sono in parte ispirato alle vecchie tabelle di stile di D & D, che elencerebbero un intervallo di valori per ogni oggetto sul tavolo (ad esempio, 0-20 tempo è chiaro, 21-50 tempo sta piovendo, 51-99 è tempo nuvoloso) e arrotolerai un dado per vedere dove cadi sul tavolo.

Mi piacerebbe farlo senza un sacco di If / Elses, perché potrei voler costruire tabelle da dati memorizzati in un file o database.

Quindi sono andato ponderando i valori sul "tavolo". Pesi più alti significherebbe una maggiore possibilità di selezionare quel valore. Sommare tutti i pesi e quindi dividere ogni singolo peso in base alla somma per avere la possibilità di passare. Se i pesi sono 1, 1, 2 e 3, il peso di 3 dovrebbe avere circa 3/7 possibilità di essere selezionato.

QUINDI ecco cosa mi è venuto in mente:

public class WeightedRandomGroup<T> {

    private Random dice = new Random();
    private List<WeightedValue<T>> weightedList = new ArrayList<>();
    private float weightSum = 0;
    boolean isSorted = false;

    public void Insert(WeightedValue<T> wv){
        weightSum += wv.Weight();
        weightedList.add(wv);
        isSorted = false;
    }

    public T Roll(){
        if(weightSum <= 0.001){
            return null;
        }
        if(!isSorted){
            Sort();
        }

        T val = null;
        while(val == null)
        {
            for(WeightedValue<T> wv : weightedList)
            {
                //System.out.println("Weight: " + wv.Weight());
                if(dice.nextFloat() <= (wv.Weight() / weightSum)){
                    val = wv.Value();
                    break;
                }
            }
        }

        return val;
    }

    private void Sort(){
        Collections.sort(weightedList, comparator);
        isSorted = true;
    }

    private Comparator<WeightedValue<T>> comparator = new Comparator<WeightedValue<T>>(){
        public int compare(WeightedValue<T> w1, WeightedValue<T> w2){
            if(w1.Weight() > w2.Weight())
                return 1;
            else if (w1.Weight() == w2.Weight())
                return 0;
            else
                return -1;
        }
    };
}

E WeightedValue

public class WeightedValue<T> {

    private T value;
    private float weight;

    public WeightedValue(int weight, T value){
        this.weight = weight;
        this.value = value;
    }

    public float Weight() { return weight; }
    public T Value() { return value; }

}

La procedura consiste nel passare attraverso ogni peso e "rollare" per vedere se riusciamo a passare sotto la sua probabilità di passare. La lista è ordinata, quindi iniziamo con i pesi più bassi e saliamo ai massimi pesi e continuiamo a scorrere l'elenco fino a quando non passiamo sotto uno degli elementi.

Quelli che hanno fatto matematica discreta o simili probabilmente vedranno un problema, che mostrerò ora:

Dato un tavolo in cui ogni valore ha un peso uguale, questo è il numero di volte in cui ogni articolo viene selezionato quando rotola (su 10.000 rotoli):

  • Articolo 1: 2534
  • Articolo 2: 2078
  • Articolo 3: 1774
  • Articolo 4: 1436
  • Elemento 5: 1188
  • Articolo 6: 990

Se tutto ha lo stesso peso, allora tutto dovrebbe avere un numero abbastanza vicino di colpi, ma chiaramente non è questo il caso con l'Articolo 6 che viene arrotolato meno della metà delle volte che si tratta dell'Articolo 1 o dell'Articolo 2!

Il che ha un senso. Se abbiamo 4 oggetti con pari opportunità, quindi usando il mio codice sopra abbiamo una probabilità del 25% per il primo oggetto. Se fallisce, tiriamo per 2, poi se fallisce 3, e così via. Questo significa che abbiamo una probabilità del 75% di provare a tirare per il secondo oggetto. una probabilità del ~ 56% di rotolare per il terzo oggetto e una probabilità del 42% di rotolare per il 4 ° oggetto. (se ho fatto bene la matematica)

Pubblicherò ciò che mi è venuto in mente per risolvere il problema, ma mi interessa sapere se c'è un modo migliore per "tirare un dado" su un tavolo.

    
posta Magic Marbles 20.09.2016 - 23:59
fonte

3 risposte

7

Il tuo problema è che tiri i dadi più volte per selezionare un oggetto. Questo non è assolutamente necessario e trasforma il tuo semplice bottino in cui ogni oggetto ha una gamma di valori di dadi in un albero decisionale loot che introduce le probabilità dipendenti. Invece, lanciamo i dadi una volta per ottenere un valore nell'intervallo [0, somma), quindi iteriamo attraverso tutti gli elementi fino a quando non hai trovato l'oggetto corrispondente.

Pseudocodice:

assert list is not empty
roll = dice roll in [0, sum)
table-position = 0
for item in list:
  table-position += item.weight
  if roll < table-position:
    return item.value
assert unreachable

Il vantaggio di questa soluzione è che è semplice, il peso corrisponde linearmente alla probabilità di selezione, non è necessario ordinare l'elenco e, soprattutto, è garantito che termini in O (n).

    
risposta data 21.09.2016 - 08:33
fonte
0

Un altro modo di fare casualità sarebbe un mazzo di carte. Se riempi il mazzo con 5 carte piove e 10 carte nuvolose e 25 carte sole, allora mischia il mazzo. Ogni volta che selezioni un tipo di tempo, pesca la carta successiva nel mazzo. Hai la garanzia di avere i rapporti corretti. Dopo aver pescato tutte le carte nel rimpasto del mazzo in modo che l'ordine sia diverso la prossima volta.

    
risposta data 21.09.2016 - 04:31
fonte
-1

Quindi, questo non funziona davvero. Forse un altro modo?

public T Roll(){
        if(weightSum <= 0.001){
            return null;
        }
        if(!isSorted){
            Sort();
        }

        T val = null;
        while(val == null)
        {
            WeightedValue<T> wv = weightedList.get(dice.nextInt(weightedList.size()));
            //System.out.println("Weight: " + wv.Weight());
            if(dice.nextFloat() <= (wv.Weight() / weightSum)){
                val = wv.Value();
                break;
            }

        }

        return val;
    }

Qui seleziono casualmente un elemento dall'elenco di WeightedValues e lo tiro contro la sua pass chance. Vediamo quali sono i risultati per un gruppo con 6 articoli dello stesso peso, facendo 10.000 tiri:

  • Articolo 1: 1737
  • Articolo 2: 1615
  • Articolo 3: 1676
  • Articolo 4: 1638
  • Elemento 5: 1667
  • Articolo 6: 1667

Questo sembra molto meglio! Oltre 100.000 rotoli è ancora più vicino a uno spread uguale:

  • 1: 16618
  • 2: 16589
  • 3: 16876
  • 4: 16656
  • 5: 16679
  • 6: 16582
risposta data 21.09.2016 - 00:00
fonte

Leggi altre domande sui tag