Dynamic Weighting Randomization

Question

I'm trying to make a path by drawing from a pre-defined set of tiles, each of which are of a certain "type". However, I want to weight the randomization so that each "type" starts off with an equal chance, but certain conditions will cause the weighting of a particular "type" (such as having been chosen very often) to either increase or decrease.

I'm not very familiar with randomization algorithms. Are there any pre-existing algorithms that are a good match for my setup?

UPDATE

@CandiedOrange Here's how I'm imagining, as far as the general design of the code, what you were explaining.

Lets say we have a Enum named Letter with a few different elements simply named A, B, C, D, and E. Then lets say we have an array of integers that represent, in terms of your deck of cards analogy, the number of each type of Letter. The array will be initialized with a value of 1 in each entry. After choosing a Letter (thus removing it from the "deck"), I check if the corresponding entry has reached 0, in which case I increase all values by 1 as if I were shuffling in a new deck, then choose another Letter.

Does that sound like what you were trying to explain?

If so, I think I can modify this design to suit my needs. Every time a Letter is chosen and removed from the deck, I can check to see if choosing that particular Letter tripped any conditions. If so, I can then add or subtract particular values in the array to modify the probabilities.

Answer 1

Create an array of probability values (ranging 0.0 to 1.0) with a value for each of your types. 'roll' a random number and check if greater than value for type.

Your 'certain conditions' will increase or decrease the probability value for an type.

Answer 2

If having been chosen will affect the probability then you are doing a process without replacement. Choose a card out of a single deck and you can't choose it again. Put it back in and you might. That's a process with replacement.

Somewhere between these two extremes, never-choose-it-again and like-you-never-chose-it, is where it sounds like you want to be. There is a surprisingly easy way to get there. Use more than one deck of cards. Use an infinite number of decks and it's the same as putting the card you chose back.

What this means is if you take @MitchWheat's suggestion and give your tile types each a 1.0 weight at the start and subtract 0.5 each time one type is chosen it's exactly the same as if you took two complete sets of your tiles and shuffled them together. Why? 1 / 0.5 == 2.

Knowing that those are the same might let you find many more pre-existing algorithms that will do what you need. For example Fisher-Yates shuffle:

Shuffle a List

Shuffle a Map

http://www.java2s.com/Tutorials/Java/java.util/Collections/Java_Collections_shuffle_List_lt_gt_list_Random_rnd_.htm

If you need to be able to supply an infinite number of tiles simply restock and reshuffle the list once it's depleted.

In this approach the tiles are weighted simply by how many times each type is in the list.

UPDATE

I don't like the analogy of a deck of cards because it implies that tiles that have been chosen can't be used again until the next "deck" is shuffled in.

This is true if you only shuffle one deck at a time. Adding more decks or even simply more cards before shuffling would let you control starting 'weights' but still adjusts as selections are made and removed.

Once a type of tile has been chosen, each tile within that should have an equal chance of being chosen

I'm not sure how to take this. Each tile within the chosen type? This is meaningless unless two tiles of the same type are distinguishable in some way. With cards I'd say it doesn't matter which Ace of Clubs is chosen.

If you mean you want selection of types to always be equal then you don't need probability weights at all.

The analogy of shuffling a deck is meant to give some perspective on how weights can be adjusted based on selection. If you want to change weights based on other factors as well you can still do it simply by adding or removing tiles.

You can, of course, stick to 0.0 to 1.0 weights. I'm simply pointing out that the only thing that gets you is the ability to set weights to irrational numbers. Any set of weights that can be expressed as a fraction can be modeled as a shuffled stack of cards.

Answer 3

I had a similar need recently making a baseball game. There were all kinds of random choices to make, so I created two utility classes to help make my code simpler.

Consider the following enumeration for the possible trajectories of a baseball when hit.

enum Trajectory {
    FLY, GROUNDER, LINE_DRIVE, POPUP;
}

With my utility classes, determining a random trajectory is achieved by the following code snippet.

    List<Probability<Trajectory>> odds = Arrays.asList(
        Probability.of(Trajectory.FLY, 0.5),
        Probability.of(Trajectory.GROUNDER, 0.2),
        Probability.of(Trajectory.LINE_DRIVE, 0.3));

    Trajectory result = Luck.determine(odds);

If you like this design, here are simplified but totally functional versions of the two classes involved.

Probability.java

public class Probability<T>
{
    public static <T> Probability<T> of(T value, double chance) {
        return new Probability<T>(value, chance);
    }

    private final T value;
    private final double chance;

    public Probability(T value, double chance) {
        this.value = value;
        this.chance = chance;
    }

    T getValue() {
        return value;
    }

    double getChance() {
        return chance;
    }

    @Override
    public String toString() {
        return new StringBuilder(20)
            .append(value).append(": ").append(chance)
            .toString();
    }
}

Luck.java

import java.math.*;
import java.util.*;

public class Luck
{
    private static final MathContext CONTEXT = new MathContext(5);

    /**
     * Make a random determination from a list of probabilities based
     * on the fractional chance of each probability.
     * @throws IllegalArgumentException if the total chance of the
     *             probabilities is not within 1/10000th of 1.
     */
    public static <X, T extends Probability<X>> X determine(List<T> probabilities) {
        double chance = 0f;
        for (Probability<X> probability : probabilities) {
            chance += probability.getChance();
        }
        BigDecimal total = new BigDecimal(chance).round(CONTEXT);
        double determination = Math.random();
        // System.out.println(new StringBuilder(128).append(probabilities)
        //    .append(" :random: ").append(determination));
        if (BigDecimal.ONE.compareTo(total) != 0) {
            throw new IllegalArgumentException("probabilities' chances must total 1");
        }
        chance = 0f;
        for (Probability<X> probability : probabilities) {
            chance += probability.getChance();
            if (determination < chance) {
                return probability.getValue();
            }
        }
        return probabilities.get(0).getValue();
    }
}

Main.java

import java.util.*;

public class Main
{
    enum Trajectory {
        FLY, GROUNDER, LINE_DRIVE, POPUP;
    }

    public static void main(String[] args) {
        List<Probability<Trajectory>> odds = Arrays.asList(
            Probability.of(Trajectory.FLY, 0.5),
            Probability.of(Trajectory.GROUNDER, 0.2),
            Probability.of(Trajectory.LINE_DRIVE, 0.3));

        Trajectory result = Luck.determine(odds);

        // run the odds a hundred times to see how they work out
        Map<Trajectory, Integer> counts = new HashMap<Trajectory, Integer>();
        for (Trajectory trajectory: Trajectory.values()) {
            counts.put(trajectory, 0);
        }
        int i = 0;
        do {
            counts.put(result, counts.get(result) + 1);
            result = Luck.determine(odds);
            i++;
        } while (i < 100);
        System.out.println(counts);
    }
}

Output

{FLY=50, GROUNDER=19, LINE_DRIVE=31, POPUP=0}