add a lobby algorithm that finds the fairest teams

[ageekhere]

Hi all this is regarding my post here
https://forums.faforever.com/viewtopic.php?f=42&t=16989
Not sure if i should have made a draft pull request, new to this.

So my idea is to create an algorithm that finds the fairest teams while in the lobby. Once the script is done it moves the players to the fairest teams (in lobby) from there the players can decide what positions to play for that map or make adjustments.

I have never coded in lua and will need some help to get this to work
i wrote some as3 for testing, the output is

Team 1
1211
1000
985
699

Team 2
999
980
970
950

Difference of 4

//AS3--------------------
/*
Fairest Team finder
Loads all the players true skill in an array
Goes through every combination and compares the difference
The fairest team is the one which has the lowest difference of trueskill between the two teams
Note players may still need to pick what spots that want to play on their team, e.g air, navy etc
Only supports 2 teams
*/

var playerArray: Array = [1211, 1000, 950, 999, 980, 970, 699, 985]; //stores all players Trueskill
var lastScore: int = 99999;
var fairestTeam: String = ""; //for dubuging, stores the fairestTeam in a string
var compairTeam: String = ""; 
var updateCount: uint = 0; //result update 
var fairestTeamArray: Array = []; //holds the current fairest Team

f_mutate(playerArray, 0, playerArray.length - 1);
trace(fairestTeam);

//f_mutate function
function f_mutate(arr: Array, start: int, end: int)
{
	updateCount++;
	if (start == end)
	{
		var size:uint = end + 1;
		compairTeam = "";
		var team1:int = 0; //the total trueskill of team 1
		var team2:int = 0; //the total trueskill of team 2
		var diff:int = 0; //the difference in trueskill between the two teams
		for (var i: uint = 0; i < size; i++)
		{ //loop through the players
			compairTeam += String(arr[i] + ",");
			if (i < (size * 0.5))
			{ //add player trueskill to team 1
				team1 += arr[i]; 
			}
			else
			{ //add player trueskill to team 2 
				team2 += arr[i];
			}
		} //end for
		//see which team has more trueskill
		if (team1 >= team2)
		{ //store the difference between team 1
			diff = team1 - team2;
		}
		else
		{ //store the difference between team 2
			diff = team2 - team1;
		}
		compairTeam += " diff " + diff + "b";
		if (diff < lastScore)
		{ //checks if the difference is less than the current fairest Team
			fairestTeam = compairTeam; //stores the current fairest Team
			lastScore = diff; //store the new fairest team difference
			fairestTeamArray.length = 0; //reset array
			if (updateCount > 100)
			{ //out puts the current fairest team so the host can decide to stop the script 
			//Note, games with 8 or less players, the script is able to find the fairest Team quite quickly, however with games with 16 players it can take quite a while
			//To go through all the combinations, that is why a stop search button is needed so the host can stop the search when the host thinks the current fairest Team is good enough 		
				updateCount = 0;
				trace(fairestTeam);
			}
		}
		if (diff == lastScore)
		{
			fairestTeamArray.push(compairTeam);
		}
		compairTeam = "";
		return;
	}

	for (var k: int = start; k <= end; k++)
	{ //change position in array 
		if (diff == 0) return; //stop the script early if the difference between the two teams is 0
		var temp = arr[start];
		arr[start] = arr[k];
		arr[k] = temp;
		f_mutate(arr, start + 1, end);
		temp = arr[start];
		arr[start] = arr[k];
		arr[k] = temp;
	}

}

I used each players true skill to check for the fairest teams, however Trueskill.computeQuality(teams) seems to be a way to check for quality, not sure if that works for more than 2 teams
Here is my current lua code so far

//lua-------------------
local Trueskill = import('/lua/ui/lobby/trueskill.lua')
local playerArray = {}
local lastScore = 99999;
local fairestTeam = "";
local compairTeam = ""; 
local updateCount = 0;
local fairestTeamArray = [];
getPlayerTrueSkill()

function GetPlayerCount()
    local numPlayers = 0
    for k,player in gameInfo.PlayerOptions:pairs() do
        if player then
            numPlayers = numPlayers + 1
        end
    end
    return numPlayers
end

local function getPlayerTrueSkill()
	local numOfPlayers = GetPlayerCount()				
    for i = 1, numOfPlayers do
        playerArray[i] = playerName //not sure how to get name?
    end

    return mylist
end

There are a few things that need to be to considered

1. Running the script in a new thread so it does not lag the main thread
2. The host can stop the script when the teams are fair enough (for 8 players and less this is not an issue but for 16 players it can take quite a while to go through all combinations which would not be needed).

Well there is my idea so far, not a perfect solution but it may help players to get a ballpark balance and go from there

[rjy7wb]

get all the combinations of the two teams, compute the geometric mean of both teams, then take minimize the difference.

[shalkya]

hello thanks for posting on this repository. I advice you to make a PR for this change. I will then be able to test it, and get someone to review it. If it works well, i will then merge the PR.

[ageekhere]

As i am new to lua there are a few things that i am unsure on.
1 Can the script run in a new thread to prevent locking up the main thread, for under 9 players the search time is minimal however 12 or even 16 players the search can be very long. So the host should be able to stop the search once an ok balance has been found.

This idea was comparing the player true score values, however now i know that Trueskill.computeQuality(teams) can be used.

Will see what I can come up with.

Also this would be only for 2 teams

[ageekhere]

pull request #2887

[ageekhere]

https://forums.faforever.com/viewtopic.php?f=42&t=18354

[atomar94]

Should this be closed?

[MrRowey]

Should this be closed?

has this been implemented?

[MrRowey]

pull request #2887

closing Issue Based on PR for this issue has been closed in favor of a different PR