add a lobby algorithm that finds the fairest teams

add a lobby algorithm that finds the fairest teams

Postby thecore » 13 Dec 2018, 07:50

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
thecore
Crusader
 
Posts: 11
Joined: 11 Dec 2018, 04:46
Has liked: 0 time
Been liked: 0 time
FAF User Name: thecore

Re: add a lobby algorithm that finds the fairest teams

Postby Viba » 13 Dec 2018, 17:02

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.
Viba
Moderator
 
Posts: 690
Joined: 22 Jan 2015, 21:42
Has liked: 136 times
Been liked: 216 times
FAF User Name: !smurfcheck Viba

Re: add a lobby algorithm that finds the fairest teams

Postby Geosearchef » 13 Dec 2018, 18:02

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/
Developer, Server Admin, ICE, currently working on Team Matchmaking, FAF Client
User avatar
Geosearchef
Priest
 
Posts: 320
Joined: 18 Oct 2013, 14:08
Location: Germany
Has liked: 4 times
Been liked: 98 times
FAF User Name: Geosearchef

Re: add a lobby algorithm that finds the fairest teams

Postby thecore » 14 Dec 2018, 01:03

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.
thecore
Crusader
 
Posts: 11
Joined: 11 Dec 2018, 04:46
Has liked: 0 time
Been liked: 0 time
FAF User Name: thecore

Re: add a lobby algorithm that finds the fairest teams

Postby moonbearonmeth » 14 Dec 2018, 06:16

thecore wrote:Wanted to see what people think of the idea first.


Sounds like effort.
But I'm not necessarily against it.
Ask me about my amazing content production to watch while you wait in a lobby.
User avatar
moonbearonmeth
Contributor
 
Posts: 397
Joined: 15 Jul 2016, 21:15
Has liked: 166 times
Been liked: 225 times
FAF User Name: Suomi KP-31 desu

Re: add a lobby algorithm that finds the fairest teams

Postby thecore » 14 Dec 2018, 14:35

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.
thecore
Crusader
 
Posts: 11
Joined: 11 Dec 2018, 04:46
Has liked: 0 time
Been liked: 0 time
FAF User Name: thecore

Re: add a lobby algorithm that finds the fairest teams

Postby Geosearchef » 14 Dec 2018, 14:56

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.
Developer, Server Admin, ICE, currently working on Team Matchmaking, FAF Client
User avatar
Geosearchef
Priest
 
Posts: 320
Joined: 18 Oct 2013, 14:08
Location: Germany
Has liked: 4 times
Been liked: 98 times
FAF User Name: Geosearchef

Re: add a lobby algorithm that finds the fairest teams

Postby Katharsas » 17 Dec 2018, 23:34

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.
Katharsas
Avatar-of-War
 
Posts: 115
Joined: 29 May 2015, 21:44
Has liked: 17 times
Been liked: 18 times
FAF User Name: Katharsas

Re: add a lobby algorithm that finds the fairest teams

Postby Endranii » 18 Dec 2018, 00:48

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.
Endranii
Avatar-of-War
 
Posts: 224
Joined: 16 Feb 2017, 18:07
Has liked: 65 times
Been liked: 44 times
FAF User Name: Empty_Spot

Re: add a lobby algorithm that finds the fairest teams

Postby Katharsas » 19 Dec 2018, 19:41

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
Katharsas
Avatar-of-War
 
Posts: 115
Joined: 29 May 2015, 21:44
Has liked: 17 times
Been liked: 18 times
FAF User Name: Katharsas

Next

Return to FAF Suggestions

Who is online

Users browsing this forum: No registered users and 1 guest