An exponential probability queue

Exponential Weighting

However, I don’t want linear relationships in my game. I stated an item with a 10 weight is twice as likely as one with a 9 weight. This is an exponential relationship. How does one create a random value that expresses that relationship?

The obvious answer is to convert it to linear weighting. Going back to our D100 example, the reason the weights need to add up to 100 is because there are limited options for fair random values using dice. You can’t, for example, produce a random value from 1 to 97 with dice. The tables are also integer based, since dice can also only produce an integer value.

A general algorithm lifts both restrictions. It’s no problem to produce a random number between the values of 1 and 97. Furthermore, we can produce a floating point number, such as 45.7. This is still a well-defined table location. Further loosening restrictions, table entries may begin and end fractionally.

So perhaps we want a range of 9.7 to 15.6 for that common copper goblet, and only 99.3 to 99.8 for the rare bag of holding. The linear weight of these items is 5.9 and 0.5 respectively.

Be aware of the pitfall with converting from the discrete integer tables to floating point. When using dice, the range 10-15 is inclusive: all of 15 is included. But that sounds silly. Since it’s a die, it can’t produce fractional values. But this is important since once we allow fractional random values, that inclusive means we have the range 10-15.99…, or 10-16 exclusive (meaning up to, but not including 16).

With this, I can express my exponential weights as linear weights. I convert exponential values to linear ones with the power function. In my class, I’m using a base of 2 for this. The first item with chance 10 gets a linear weight of \(2^{10} = 1024\) and the second item of chance 9 gets the linear weight \(2^9 = 512\).

As these are now linear weights, we can express the table of values, at least virtually. I added up all the weights to get the total weight, then produce a random floating point number from 0 to that weight. Then I walk through the items. I’m looking for the first item where the accumulated weight is higher than this number. In Recalc notice that I didn’t assign the per-item weight to the items, but only the total accumulated weight at that point.

The Class

Below is my ProbabilityQueue generic in C#. The caller adds items with Add, giving them their “chance” of occurring, which is their exponential chance. Getting items is done with GetRandom, which finds an item randomly based on the exponential weighting. In short, it does this by converting to linear weighting, taking a random value, and walking to find that item.

/*
Selects items from a set based on their exponential probability of occurring.

For example, using the default weightBase of 2:
- an item with chance 11 is twice as likely to appear as an item of chance 10
- an item with chance 9 is half as likely to appear as an item of chance 10
*/
public class ProbabilityQueue<T> where T : notnull {
	List<ProbabilityItem<T>> items = new List<ProbabilityItem<T>>();
	int curId = 0;
	bool dirty = false;

	const double defaultWeightBase = 2;
	const float defaultPullChanceReduce = 1;
	
	// the exponent basis for establishing item weight: weight = weightBase ^ chance
	double weightBase = defaultWeightBase;
	// how much to reduce the chance of each item selected in Pull
	float pullChanceReduce = defaultPullChanceReduce;
	
	public void Add( T source, float chance ) {
		items.Add( new ProbabilityItem<T>( ++curId, source, chance ) );
		dirty = true;
	}
	
	public ProbabilityQueue() {
	}
	
	public ProbabilityQueue( 
		double weightBase = defaultWeightBase, 
		float pullChanceReduce = defaultPullChanceReduce ) {
		this.weightBase = weightBase;
		this.pullChanceReduce = pullChanceReduce;
	}
	
	public void AddChance( T source, float chance ) {
		var cur = items.Find( x => x != null && x.source != null && x.source.Equals(source) );
		if( cur == null ) {
			// code biased to a fault-tolerant game, exception perhaps better in the general case
			D.Error("missing-item");
			return;
		}
		
		cur.chance += chance;
		dirty = true;
	}
	
	// Obtains a random item without adjusting its next chance to be pulled
	public T GetRandom() {
		var item = GetRandomItem();
		return item.source;
	}
	
	ProbabilityItem<T> GetRandomItem() {
		if( dirty ) {
			Recalc();
		}
		
		var atWeight = GameSetup.random.NextDouble(weightTotal);
		foreach( var item in items ) {
			if( item.weight > atWeight ) {
				return item;
			}
		}
		
		// deal with potential rounding, just return last item
		return items[items.Count-1];
	}
	
	/*
		Obtains a set of random items (non-duplicate) and reduce their future chance for selection.
		
		@param count Items will be randomly picked until this count is reached, 
			or a hard-limit of tries is reached.
	*/
	public T[] Pull(int count) {
		var selected = new HashSet<ProbabilityItem<T>>();
		
		// It's possible due to unluckiness, or heavily weighted items, that we can't find enough
		// non-duplicates. We don't update chance during the selection.
		int tries = 3 * count;
		while( tries > 0 && selected.Count < count ) {
			selected.Add( GetRandomItem() );
		}		
		
		foreach( var select in selected ) {
			select.chance -= pullChanceReduce;
			dirty = true;
		}
		
		return selected.Select( s => s.source ).ToArray();
	}
	
	double weightTotal = 0;
	void Recalc() {
		double total = 0;
		foreach( var item in items ) {
			var local = Math.Pow(weightBase, item.chance);
			total += local;
			item.weight = total; 
		}
		dirty = false;
		weightTotal = total;
	}
	
	public int Count { get { return items.Count; } }
}

class ProbabilityItem<T> {
	public int id;
	// represents a log-based probability, so 11 is twice as likely as 10, and 9 is half as likely (see weightBase)
	public float chance;
	public T source;
	public double weight;
	
	public ProbabilityItem( int id, T source, float chance ) {
		this.id = id;
		this.chance = chance;
		this.source = source;
		this.weight = 0;
	}
	
	public override int GetHashCode() {
		return id.GetHashCode();
	}
	
	public override bool Equals(object obj) {
		return this.Equals(obj as ProbabilityItem<T>);
	}
	
	public bool Equals(ProbabilityItem<T>? o) {
		return o?.id == id;
	}
}

Optimization and Adjusted Values

The code for GetRandom linearly walks through the list to find the item, which is algorithmically quite slow. If producing random results was the primary purpose of the code, then I’d optimize this to use a binary tree to get O(log N) speed instead.

However, in my game, an example use of this code is buying vacuum tubes in the shop. The game will pull out two-to-four random items for the player. Then, for each item I’ll decrement the chance of that item occurring again (calling `AddChance` with `-1`). I wanted a slight variation on other games, where items occur only once. In Rabanaz, each time the item occurs, it effectively drops a rarity class. It can still appear again, but less likely. This actually solves one of my problems of having a long play-through somehow run out of items.

This pattern is common enough that it’s encapsulated in the function called Pull in the code. The pullChanceReduce member variable says how much to reduce the chance of items it selects.

Anyway, for optimization, what this means is I call GetRandom only two-to-four times before I call AddChance and thus trigger the dirty flag again. If I used a binary tree, I would have to rebuild it each time this happens. It’s likely that building this binary tree is costlier than several linear iterations. Obviously, at some count of iterations, like in my test loop, a binary tree would be better. But that’s more code surface and I don’t need it here.

If you need a challenge, write the binary tree that would make the GetRandom code faster. The key here is to produce a balanced tree. What is the balancing criteria? The test cases would obviously need a lot more items to test the difference. My game will include slightly more than 100 items.

Precision

If the deltas between the item chances grow too high, then floating point precision will start to affect the results. The critical problem point is the summations; values with a small enough chance may simply disappear as their linear weight is too small. Double precision is 53 bits, and since my queue is exponential, each one value difference in chance will require one of those bits, plus some wiggle room to account of multiple items of that class.

I think I’m fine though, since the starting rarity classes have a range of 5. The player can increase the values, but probably not more than by 5, so still a range of 10. Values decrease only slightly during gameplay.

But here’s the fun part: this class is effectively self correcting. If an item’s likelihood is too large, it’ll be the only item selected by GetRandom, but as my game then knocks the chance down, eventually it’ll get low enough to not become dominant again. Vice versa as well, if we have a rare enough item that just disappears due to precision, as the other items reduce their chance, it’ll eventually come back into the fold. Certain game modes may play on this behaviour.

An extra lever

This approach also gives me an extra lever to pull in my game. What if play-testing shows that the rarity classes are too significant, or not significant enough? I could adjust the base weight, instead of using 2 I could use 1.5 instead. This would have the effect of reducing the rarity differences, or 2.5 which would increase the rarity differences.

Or I might decide that decrementing rarity by 1 is not enough, so I do 2, or use floats and do 1.5.

Moreso, these give me some good ideas for implementing items that actually change these values, or game modes that change them. I’m looking forward to seeing what happens.

Test Code

static public class ProbabilityTest {
	static void PQTest() {
		GameSetup.StaticBootstrap();
		
		var q = new ProbabilityQueue<Rarity>();
		foreach( Rarity rarity in Enum.GetValues(typeof(Rarity)) ) {
			q.Add( rarity, (int)rarity );
		}

		RunSamples(q);
		D.Log("-- -- -- --");
		
		q.AddChance( Rarity.Uncommon, 2 );
		RunSamples(q);
	}

	static void RunSamples<T>(ProbabilityQueue<T> q) where T : notnull {
		var count = new Dictionary<T,int>();
		const int iter = 10;
		for( int i=0; i < iter; ++i ) {
			var r = q.GetRandom();
			count[r] = count.GetOrDefault(r,0) + 1;
		}
		foreach( var entry in count ) {
			D.Log( entry.Key, $"{entry.Value * 100f/ iter:F2}%" );
		}
	}
}