Weighted Table Issues

Help and Feedback Scripting Support
1

This is a script I’m working on to pick random items from a table based on its weight but it doesn’t seem to pick based on weight all the time. Occasionally while testing online, one of the items is in the table is picked every time, usually the one with the lowest weight. I’ve tired running a simulation when the server starts but the numbers check out. Sometime when it’s not picking the same item over and over, it picks the rarest one much more frequently that it should.

Script:

local RarityTable= WeightedTable.new({ Rare = 50, Uncommon = 75, Common = 100})
print(RarityTable:ChooseRandom()) --Rare = 22%, Uncommon = 33%, Common = 44%

Simulation code

spawn(function() --won't let me indent for some reason
local probs = {}
for i=1,100 do
wait(.1)
local item = RarityTable:ChooseRandom()
probs[item] = (probs[item] ~= nil and probs[item] + 1) or 0
end
print("DONE SIMULATING",probs["Rare"],probs["Uncommon"],probs["Common"]) 
end)

ModuleScript:

local WeightedTable = {}


WeightedTable.__index = WeightedTable


function WeightedTable.new(tab)
	
	local this = {}
	setmetatable(this, WeightedTable)
	this.Ranges = {}
	this.Sum = 0
	this.Probability = {}
	
	
	local rangeIndex = 0
	for key,value in pairs(tab) do
		this.Ranges[key] = {rangeIndex,rangeIndex + value}
		rangeIndex = rangeIndex + value + 1
	end
	
	this.Sum  = rangeIndex - 1


	return this

end


local random = Random.new()

function WeightedTable:ChooseRandom()
	
	local randomNumber = random:NextInteger(0,self.Sum)
	
	--see what number range the random number falls under
	for key,range in pairs(self.Ranges) do
		if randomNumber >= range[1]  and randomNumber <= range[2] then
			return key
		end
	end
end


return WeightedTable
2 Likes
2

I can’t immediately see a problem and the results I’m getting look about right once I make the following tweaks to your simulation code:

  1. probs[item] = ... or 0 should be probs[item] = ... or 1

  2. Take more like 10000 samples to get reliable results

7 Likes
3

I see a bug in this code… though not an egregious one.

	local rangeIndex = 0
	for key,value in pairs(tab) do
		this.Ranges[key] = {rangeIndex,rangeIndex + value}
		rangeIndex = rangeIndex + value + 1
	end
	
	this.Sum  = rangeIndex - 1

Given the input {a=1, b=2, c=3} (and assuming pairs iterates alphabetically), we’d get output:

this.Ranges = {
    a = {0, 1};
    b = {2, 4};
    c = {5, 8};
}

Each entry gets one additional value that it doesn’t need. So, in reality, a has a weight of 2, b has a weight of 3, etc.

I’d probably make your upper bound “exclusive” to make things easier.

	local rangeIndex = 0
	for key,value in pairs(tab) do
		this.Ranges[key] = {rangeIndex,rangeIndex + value} --upper bound should be treated as
                                                           --exclusive, that is, if our range
                                                           --is [0, 1), "rolling" a value of
                                                           --1 should not give us this key.
		rangeIndex = rangeIndex + value --we no longer add 1 here.
	end
	
	this.Sum  = rangeIndex - 1
...
	local randomNumber = random:NextInteger(0,self.Sum)
	
	--see what number range the random number falls under
	for key,range in pairs(self.Ranges) do
		if randomNumber >= range[1]  and randomNumber < range[2] then --note: <= turned into <
			return key
		end
	end

Now, I mention this isn’t an egregious error, but if you’re choosing small values for the weight (your OP suggests values in the tens), this might have a meaningful impact. If you’re choosing large values, well… keep searching for a solution. :stuck_out_tongue:

One more thing that might be worth a shot.

local random = Random.new()

Often times when you seed a random number generator – even if you get a good seed – the first several generations are bad. I’ve seen advice to make them “run” for a little while, a la:

local random = Random.new();
for i = 1, 10000 do random:NextNumber(); end --improve entropy.
4 Likes
4

here’s a quick and dirty implementation:

local WeightedTables = {
	SomeUniqueIdentifier = {
		WeightedItem1 = 10,
		WeightedItem2 = 90
	},
        AnotherUniqueIdentifier = {
		WeightedItem1 = 20,
		WeightedItem2 = 80
	}
}

function GetRandomWeightedItem(identifier)
	local t = {}
	local rand = math.random(1, 1000)
	for item, probability in pairs(WeightedTables[identifier]) do
		for i = 1, probability * 10 do
			t[#t + 1] = item
		end
	end
	return t[rand]
end
3 Likes