Auto Team "Power" Balancing

I’m looking for some guidance because I’m clueless on how to do this effectively. I need to take the “Power” of each player and use that to optimize the teams. Not how many players on each team but similar power…

--Ex.
Players = {
Player1 = 10,
Player2 = 21,
Player3 = 12
Player4 = 19,
Player5 = 15,
Player6 = 14}

--What the Expected Result Should be:
local Team1 = {
Player1 = 10,
Player2 = 21,
Player5 = 15}--Team "Power" is 46

local Team2 = {
Player3 = 12,
Player4 = 19,
Player6 = 14}--Team "Power" is 45
--Result is Most Fair Teams
1 Like

One easy way to do this is to give the highest powered player to one team, then to start adding up the next highest powers until they’ve exceeded the first team. Toggle back and forth until you’ve gone through everyone.

Eg.

{
100, 95, 70, 65, 50, 40}

Team1 = {100} -- Step 1 Give highest player to 1 team (Total 100)

Team2 = {95, 70} -- Team 2 is given players until they exceed team 1 (Total 165)

Team1 = {100, 65, 50} -- Team 1 is given players until exceeding team 2 (Total 215)

Team2 = {95, 70, 40} -- Team 2 is given players until exceeding team 1, or out of players (Total 205)
2 Likes

But is there any better way to do this, or how would you sort through all of the different combinations and find the best one?

2 Likes

After doing some intense research I found out that this problem is actually quite tough.

It’s known as a partition problem and it seems to match the scenario.

From the Wikipedia link:

S of positive integers can be partitioned into two subsets S 1 and S 2 such that the sum of the numbers in S 1 equals the sum of the numbers in S 2

Yeah, the problem is quite hard, might be best to use @polill00 method which seems very similar to the greedy algorithm mentioned in the Wikipedia article.

One approach to the problem, imitating the way children choose teams for a game, is the greedy algorithm , which iterates through the numbers in descending order, assigning each of them to whichever subset has the smaller sum. This approach has a running time of O ( n log n ). This heuristic works well in practice when the numbers in the set are of about the same size as its cardinality or less, but it is not guaranteed to produce the best possible partition

2 Likes

If you need to get the best possible scenario, you could just run through possible outcomes, and hold onto the one with the lowest difference between the two. It shouldn’t be too taxing on performance especially with only 6 players.

1 Like

I have spent >1 hour or so and I have choose to make a way with all the possible outcomes.
Its horrible inefficient but with only 6 or less players in the game its fine. Currently the system creates a table inside a table with randomized numbers 1-6, (No Duplicates)

ex.
local Numbers= {
{1,3,6,2,5,4},
{6,5,4,2,1,3},
--etc... for how many combinations
}

Now I hit my next roadblock of taking all of the different possible team configurations and finding out which has the smallest difference other than doing 20 if statements, does anyone know how to take a list of many numbers and see which one is the lowest?

Also for those curious:
Current Progress, Use Expressive output or change if statement at bottom.
Matchmaking testing.rbxl (19.5 KB)

--(109 Lines)
local Values = {
	Player1 = 10,
	Player2 = 21,
	Player3 = 12,
	Player4 = 19,
	Player5 = 15,
	Player6 = 14
}

local x = 0--#Values
for i,v in pairs(Values) do
	x +=1
end

--Factorial
local function factorial(n)
	if (n == 0) then
		return 1
	else
		return n * factorial(n - 1)
	end
end
--
local Comination1 = factorial(x)
local Combination2 = factorial((x / 2))
local Combination3 = factorial( (x)-(x/2) )
local formula = (Comination1) / (Combination2*Combination3)
print(formula.." Different Combinations")

local DifferentCombinations = {}

--Solution1
local function randomnum()
	return math.random(1,x)
end


local function getrandomorder()
		local x1 = randomnum()
		local x2 = randomnum()
		while x2 == x1 do
			x2 = randomnum()
			wait()
		end
	if x > 2 then
		local x3 = randomnum()
		while x3 == x2 or x3 == x1 do
			x3 = randomnum()
			wait()
		end
		local x4 = randomnum()
		while x4 == x3 or x4 == x2 or x4 == x1 do
			x4 = randomnum()
			wait()
		end
	if x > 4 then	
		local x5 = randomnum()
		while x5 == x4 or x5 == x3 or x5 == x2 or x5 == x1 do
			x5 = randomnum()
			wait()
		end
		local x6 = randomnum()
		while x6 == x5 or x6 == x4 or x6 == x3 or x6 == x2 or x6 == x1 do
			x6 = randomnum()
			wait()
		end
		return {x1,x2,x3,x4,x5,x6}
	else
		return {x1,x2,x3,x4}
	end
	else
		return {x1,x2}
end
end

while #DifferentCombinations < formula do
	local order = getrandomorder()
	
	--Check if order is already used
	--Get new values
	local x1 = order[1]
	local x2 = order[2]
	local x3
	local x4
	local x5
	local x6
	if x > 2 then
	 x3 = order[3]
	 x4 = order[4]
	if x > 4 then
	 x5 = order[5]
	 x6 = order[6]
	end
	end
	
	local can = true
	for q,z in pairs(DifferentCombinations) do
		 if z[1] == x1 and z[2] == x2 and z[3] == x3 and z[4] == x4 and z[5] == x5 and z[6] == x6 then--Change to be compatible with 2,4 in table
			can = false	
	 	end	
	end
	if can == true then
	table.insert(DifferentCombinations,1,order)	
	end
	wait()
end

print(DifferentCombinations)

Yeah that’s another popular computer science topic you can use a sorting algorithm to sort the tables in increasing order then pick the correct index which should indicate the correct team combination choice as well.

2 Likes

If anyone wanders or searches this topic, here is an updated module I made which does exactly what the topic is about. Most Balanced / Fairest Team Making System