add a lobby algorithm that finds the fairest teams

[thecore]

I had an idea for the lobby, create a algorithm that finds the fairest teams and sorts the players. Give the following example

Players in lobby
player 1 - 700
player 2 - 783
player 3 - 843
player 4 - 953
player 5 - 1100
player 6 - 1253
player 7 - 1360
player 8 - 1593
player 9 - 1904
player 10 - 2599

Run algorithm (currently trying a bruit force method, maybe knapsack method would be better)

team 1
player 10 - 2599
player 7 - 1360
player 5 - 1100
player 2 - 783
player 1 - 700

team 2
player 9 - 1904
player 8 - 1593
player 6 - 1253
player 4 - 953
player 3 - 843

difference of 4

Though other thing to keep in mind is number of games played etc but this would take a lot of guess work out trying to create a fair team.
It could be at lease a starting point and players could readjust as needed

[Viba]

TheSetoner kinda has this function for TD's. Specify players and team size, it checks the ratings of the players and generates even teams based on that.

[Geosearchef]

The lobby already has an option to mix spawns on start and balance teams although I don't know how well this works. If you want to take a look or implement sth take a look at the github repo.

I also want to mention that your rating isn't a single number. You don't want to balance the ratings above which players will play with 99.7 % certainty (the displayed rating, 3 times the standard deviation percentile) but instead want to maximize draw probability (called game quality). Take a look here for info on trueskill: https://trueskill.org/

[thecore]

TheSetoner kinda has this function for TD's. Specify players and team size, it checks the ratings of the players and generates even teams based on that.

The lobby already has an option to mix spawns on start and balance teams although I don't know how well this works

The idea with this method is to quickly find the fairest teams based on rank/true skill but then allow the players to make adjustments when needed (it may be even teams but if the algorithm puts the lowest rank player in a key position against the highest rank player then that will affect the balance).

If you want to take a look or implement sth take a look at the github repo

Wanted to see what people think of the idea first.

[moonbearonmeth]

Wanted to see what people think of the idea first.

Sounds like effort.
But I'm not necessarily against it.

[thecore]

Ok been playing around with an algorithm here is what i have for creating 2 fairest teams.
reference here
https://www.codesdope.com/blog/article/ ... f-an-arra/

Note it is in as3 but should be easy to convert to c++

Code: Select all

var playerArray: Array = [700, 783, 843, 953, 1100, 1253];
var temp: int;
var a;
var b;

var stringArray: Array = [];
var lastScore: int = 99999;
var fairestTeam: String = "";

var i: int;
var j: int;
var size: uint;
var myString: String = "";
var team1: int;
var team2: int;
var diff: int;
f_mutate(playerArray, 0, playerArray.length - 1);

//returns a string with the team
trace(fairestTeam);

//f_mutate function
function f_mutate(arr: Array, start: int, end: int)
{
   if (start == end)
   {
      size = end + 1;
      i = 0;
      j = 0
      myString = "";
      team1 = 0;
      team2 = 0;
      diff = 0;
      for (i = 0; i < size; i++)
      {
         myString += String(arr[i] + ",");
         if (i < (size * 0.5))
         {
            team1 += arr[i];
         }
         else
         {
            team2 += arr[i];
         }
      }
      if (team1 >= team2)
      {
         diff = team1 - team2;
      }
      else
      {
         diff = team2 - team1;
      }
      myString += " diff " + diff;
      if (diff < lastScore)
      {
         fairestTeam = myString;
         lastScore = diff;
      }
      myString = "";
      return;
   }
   
   var k:int = 0;
   for (k = start; k <= end; k++)
   {
      //change position in array
      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;
   }
}


Out put
700,843,1253,953,1100,783, diff 40

resulting in
team 1
700
843
1253

Team 2
953
1100
783

So all that needs to be done is when a button is pressed have it store all the player's ratting/trueskill in playerArray, run the algorithm and from the output sort the players into teams.

Code is very messy but it is a start.

[Geosearchef]

Haven't read through the code yet, but looks promising. The target language in the end will be LUA.

Please take into account that the rating of a player IS NOT a single value but a normal distribution with a mean and standard deviation.

[Katharsas]

Why don't you simply choose the player team distribution with the highest game quality? I don't know but id guess that auto-teams does exactly that.

[Endranii]

That's true but it assigns random positions making people cry that they can't play this role/position instead of learning them all accordingly.

[Katharsas]

If i understand the above algorithm correctly, it simply calculates the summed difference of rating per team for every possible team combination.
IF that is true, it does nothing in terms of position balancing and is exactly the same as auto-teams except its worse than that because it uses shown rating instead of game quality (i might be wrong though because recursive code is somewhat confusing to me).

Btw., even though i am a programmer, i don't like expressing ideas in code (even worse if its low-level C-like stuff). It means that non-programmers can't discuss it and it doesn't work if the algorithm us non-trivial.

Proposed Algorithm for for best position balancing:
Treat every position in game as 1v1 game. So, you just ask Trueskill for all game qualities of all possible one-vs-one for all members of the team. Example:

If there are four players (A, B, C, D) you get game qualities of:
AvB, AvC, AvD, BvC, BvD, CvD

(If teams are fixed like AB vs CD but you want to randomize positions only, just get: AvC, AvD, BvC, BvD)

Then you calculate squared sum of game quality for all possible team compositons,where a team compositon is a combination of 1v1s so that every players appears once per composition:
Compositon 1 Quality = (AvB + CvD)
Compositon 2 Quality = (AvC + BvD)
Compositon 3 Quality = (AvD + BvC)
and choose the one with highest quality. If you don't want to punish high differences, use sum instead of squared sum, simple. Then you put players that are in a 1v1 into opposing spots on map. Of course this only works for two teams of same size.

Edit: Example code:
https://gist.github.com/Katharsas/c2697 ... 1d7a549087