Create random number filtering devices using the VectorChanceTree
If you are curious why we would need to filter random numbers that come out of a PRNG, then we should probably get you a full set of the Game Programming Gems series. The problem with a PRNG or even a full scale NSA class RNG is that random results aren't much fun. In fact the results are so random the human minds conceive they are not random at all, but rather directed. For instance, how many times do you have to pick a number from 1 to 20 before you pull 3 20's in a row? Well about 8000 times. Would really suck if the mob you were fighting happened to stick it to by pulling out 3 20's.
I'm willing to guess you'd take that death as a personal afront that some admin was sitting in the background controlling that creature. Had to be right? After all you've fought several 1000 bandertoad ice demons already and they've never hit you like that before. You see, your previous encounters have caused you to ignore random number generation altogether and make absolute assumptions about the performance of the creature you are going against. It isn't fun if the computer is lucky. Now you get some ideas of why we need a random number filter.
We'll implement the filter using a swapping mechanism. Since the probability tree is very efficient at removing items now, we can use that to temporarily deprive the tree of specific values that were previously pulled. I'm going to call this the SwapFilter, and make it capable of performing a couple of different filtering operations by controlling the size of a specialized filter buffer. This buffer will hold items that have been removed from the tree, and will be added back in once the filter is full.
public object SwapFilter(int swapLength) {
if ( filter == null ) {
filter = new Chance[swapLength];
filterOffset = 0;
}
Chances are retrieved normally, as we would for other methods. However, depending on the state of the filter, we'll either be removing the item or swapping it for an item in the filter. We'll remove items until the filter is completely full and then swap items after that point. The removal is expensive, but it only happens a couple of times. The swapping is very efficient and fast.
int prob = rand.Next(0, chances[0].GrowthWeight);
int index = FindNode(prob);
Chance item = chances[index];
// If the filter isn't full yet, we need to remove elements
if ( filter[filterOffset] == null ) {
// Remove the current element instead of swapping it
ModifyChances(index, -item.CurrentWeight);
} else {
Here is why the swap is so fast. We can set the growth weight of the item being swapped in to the exact same weight as the item being swapped out. This is not 100% accurate, since items may have different CurrentWeight's which would affect this method. I'm assuming for the swap filter that all items have identical weights since the filtering process and the way items are added to the collection is where the probability work comes into play. Once the filter item has been updated, we place it back in the collection.
// They keep the same children
filter[filterOffset].GrowthWeight = item.GrowthWeight;
// TODO TODO: Verify their CurrentWeight values are
// identical
// Replace the current item with the filtered item
chances[index] = filter[filterOffset];
}
The final step is to update the filter with our removed item and start walking around the queue. The queue length is very important to how the filtering works, as you'll see in the sample driver code that implements a doubles and triples filter.
// Update the Filter with the current item we are swapping
// out and then update the offset to point at the next
// element. We are using a basic queue.
filter[filterOffset] = item;
filterOffset = (filterOffset+1)%filter.Length;
return item.Item;
}
With the algorithm ready, we'll implement a doubles filter. This is the easiest filter and only requires that we add our dice values to the collection and then use the SwapFilter method with a length of 1. This will take the returned item and place it in the filtering queue, so that it can't be picked the next time. Because we prevent doubles we also prevent any string of numbers of any lenght of the same type. For instance, you can't have triples, quads, etc...
private static void NoDoubles(int sides, int rolls) {
Console.WriteLine("Running NoDoubles");
VectorChanceTree ct = new VectorChanceTree();
for(int i = 0; i < sides; i++) {
ct.AddChance(1, i+1);
}
bool doubles = false;
bool triples = false;
int[] lastValues = new int[3]; int offset = 0;
int[] sanity = new int[sides];
for(int i = 0; i < rolls; i++) {
lastValues[offset] = (int) ct.SwapFilter(1);
sanity[lastValues[offset]-1]++;
offset = (offset+1)%3;
if ( lastValues[(offset+1)%3] == lastValues[(offset+2)%3] ) {
doubles = true;
}
if ( lastValues[0] == lastValues[1] && lastValues[1] == lastValues[2] ) {
triples = true;
}
}
Console.WriteLine("Doubles: {0}", doubles);
Console.WriteLine("Triples: {0}", triples);
Console.WriteLine();
int average = rolls / sides;
for(int i = 0; i < sides; i++) {
Console.WriteLine("{0}: {1} with error {2}", i+1, sanity[i], sanity[i] - average);
}
Console.WriteLine();
}
If you were worried about statistical abnormalities because we are removing items, I placed some sanity checks at the bottom. We compute the error against the average to see how far off from ideal values we are. For 1 million roles, the largest error values were anywhere from -500 to +500. That is nearly identical to the error ratios you'd receive from not having the filtering applied and using just a PRNG. From the above, you'll get a print-out of false for both doubles and triples, but if doubles are too restrictive, you can implement a triples filter instead with just a few changes.
VectorChanceTree ct = new VectorChanceTree();
for(int i = 0; i < sides; i++) {
ct.AddChance(1, i+1);
ct.AddChance(1, i+1);
}
Instead of adding a single version of each item, we add two versions. After we remove one of them, we still want doubles to be possible, so we have a second in the tree. This is detrimental to doubles occuring at the same rate as they might normally. For instance, a double would normally be rolled 6 out of 36 or 1 out of 6 rolls of two dice. Because we are pulling a number out of a tree of 12 items where there is a 2 in 12 chance of getting a particular number, the second time there is only a 1 in 11 chance. If you count the items in the filter there is a 1 in 10 chance, but still, those aren't the same odds. The real odds after experimentation are 1 in 11, just like we thought originally.
lastValues[offset] = (int) ct.SwapFilter(2);
The last change is simple. Modify the swap filter to hold two values at a time. This prevents triples by holding a double roll in the filter ensuring a different third item is rolled. Swap filters don't have to stop at dice though. A great use of a swap filter is to apply a single element filter to the selection routines of some AI. This will ensure that an AI never selects the same thing twice in a row, which can be very efficient. Also, because we are swapping the item back in, you don't have to worry about managing the item yourself, and we are able to take advantage of the very performance swap functions instead of doing a remove, followed by an add.
Looking for comments at this point. If you have something you imagine might be solvable by a chance tree, let me know and maybe we can work it up as a sample. I'll continue adding more game like samples, and maybe some additional items that pertain to web development like the ad rotator.