Programming a Truly "Fair" Weighted Random Dice Roll

Question

I'm trying to devise a way to create a 'loot table' for an RPG, mostly to see if it can be done.

I'm partly inspired by old D&D style tables, which would list a range of values for each item on the table (i.e. 0-20 weather is clear, 21-50 weather is raining, 51-99 weather is cloudy) and you would roll a dice to see where you fall on the table.

I'd like to do this without a bunch of If/Elses, as I might want to construct tables from data stored in a file or database.

So I went with weighting the values on the 'table'. Higher weights would mean a higher chance of that value being selected. Sum all the weights, and then divide each individual weight by the sum to get a chance of passing. If the weights are 1, 1, 2, and 3, then the weight of 3 should have about a 3/7 chance of being selected.

SO here's what I came up with:

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;
        }
    };
}

And 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; }

}

The procedure is to go through each weight and 'roll' to see if we can roll under it's pass chance. The list is sorted so we start with the lowest weights and move up to the highest weights and we keep going through the list until we roll under one of the items pass chance.

Those who've done discrete maths or the like will probably see an issue, which I'm going to show now:

Given a table where every value has an equal weight, this is how many times each item is selected when rolling (out of 10,000 rolls):

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

If everything has an equal weight, then everything should have a fairly close number of hits, but clearly this is not the case with Item 6 being rolled less than half as often as Item 1 or Item 2!

Which makes sense. If we have 4 items with an equal chance, then using my above code we roll against a 25% chance for the first item. If that fails, we roll for 2, then if that fails 3, and so on. This means we have a 75% chance to try to roll for the second item. a ~56% chance to roll for the third item and a 42% chance to roll for the 4th item. (if I did the math right)

I'll post what I came up with to fix this, but I'm interested in if there's a better way to 'roll a dice' on a table.

Answer 1

Your problem is that you roll the dice multiple times to select an item. This is entirely unnecessary, and turns your simple loot table where each item has a range of dice values to a loot decision tree which introduces dependent probabilities. Instead, we roll the dice once to get a value in the range [0,sum), then iterate through all items until you have found the matching item.

Pseudocode:

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

The advantage of this solution is that it's simple, the weight corresponds linearly to selection probability, you don't need to sort the list, and most importantly: it is guaranteed to terminate in O(n).

Answer 2

Another way of doing randomness would be a deck of cards. If you fill the deck with 5 raining cards, and 10 cloudy cards, and 25 sunny cards, then you shuffle the deck. Each time you select a weather type draw the next card in the deck. You are guaranteed to have the correct ratios. After you have drawn all the cards in the deck reshuffle so that the order is different next time.

Answer 3

So, that doesn't really work. Maybe another way?

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;
    }

Here I randomly select an item from the list of WeightedValues and roll against it's pass chance. Lets see what the results are for a Group with 6 items with the same weight, doing 10,000 rolls:

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

This looks much better! Over 100,000 rolls it's even closer to an equal spread:

• 1 : 16618
• 2 : 16589
• 3 : 16876
• 4 : 16656
• 5 : 16679
• 6 : 16582