About TrueSkill and game-quality optimization

[cyrili]

I'm a rather new and inexperienced player, but I asked myself: why isn't there a button to automatically balance teams (possibly even with constraints).

From the documentation it results that game quality is:

From [1] page 36 (look there for variable definitions) and "trueskill-0.4.4\trueskill\__init__.py" lines 515 to 568

Except for 1 exponential function and 1 square root it's a very straightforward calculation that isn't very demanding for a computer.
In the worst case scenario of 12 players (2 teams) the calculation would have to be done 12!/6!/6!/2 = 462 times, so why not optimize automatically?


A quick and dirty "2 team"-implementation:



Thus:





From this it is visible that the square-root does not depend on team composition, consequently only the exponential function has to be maximized in regards to A. It is apparent that the exponent is always negative, so for q to be maximal the exponent has to be close to zero. For this to be the case:



In other words: The sum of all mean-skills of each team have to be closest possible together for a game to have the best possible balance. (I suspect this is also valid for 3+ team games) In this case it would be really straight forward to implement.


Questions about beta..:

I am very confused about the meaning of beta. I get the 80/20 thing, but relative to what players?? Is it a global constant? a lobby specific constant? a function of the skill level?
From the faf source code it appears to me to be fixed at 250 globally. When i tried to predict the game quality it worked on noob games (up to +/- 0.2%), but in the one pro game i got in it was off by 10%.

data source: game.log
code used (C++):

Spoiler: show

Code: Select all

   float beta = 250.0f;

   float temp1 = beta*beta*n;   //b^2*A^T*A

   float temp2 = 0.0f; //A^T*S*A
   for (int i = 0; i < n; i++) { temp2 += players[i].dev * players[i].dev; }

   float temp3 = 0.0f; //u^T*A = A^T*u
   for (int i = 0; i < n; i++) { temp3 += (float)players[i].team * players[i].mean; }

   float quality = exp((-0.5f*temp3*temp3) / (temp1 + temp2)) * sqrt(temp1 / (temp1 + temp2));

Final words:

Hope someone finds the time to read this trough and check my calculations.
If they happen to be true I could propose to implement it myself, but I'm not very fluent in python.
Either ways, I would really enjoy having an "auto-balance" button in the lobby.




sources:

• http://www.moserware.com/assets/computing-your-skill/The%20Math%20Behind%20TrueSkill.pdf [1]
• http://www.moserware.com/2010/03/computing-your-skill.html [2]
• trueskill source code
• faf source code

[Hawkei]

This is interesting. I agree that a button implementing the algorithm you described would be a valuable addition to the lobby. It may even be possible to implement it as a lobby UI mod. Though, not being a modder myself I cannot be certain of this.

Balancing games is a fine art, and one that many players have developed. One thing which I should point out is that the balancing the sum of trueskill on a team does not ensure that a game is entirely balanced. As experience indicates that it is also necessary to balance the corresponding positions on each team. Particularly when these positions have a geographical or functional delineation. One common example of this being the Front, Beach, Rock, and Air positions on Seton's Clutch. Maps where this is less important might be the Canis River 3v3 and 4v4 maps.

This however can be organised in a rather elementary fashion by using the your balancing algorithm to designate players as being on team 1 or 2. Then order the players by rank in either ascending or descending order. Possibly with an options menu to fine tune these attributes.

The only final point I would make is that this algorithm is using a rather limited set of data to perform a complex calculation. As it is trying to characterise the skill of a certain player with a single number. Yet, I hope we can all appreciate that player performance cannot always be represented in such simple terms. As it is entirely possible for a players game experience to be limited to certain maps, and play styles. So it may be entirely possible for two players to have the same true skill rating, and yet perform very differently when asked to perform a particular task (such as providing T3 air top cover).

[Zock]

Isn't random spots doing exactly this? A not very obvious feature indeed.

[KeyBlue]

In the new beta patch, we have Optimal balance and Flexible balance. (an addition to only having Fixed teams and random)

I expect that Optimal balance will order the teams like you suggested.
No idea what flexible balance does exactly (maybe add some randomness that allows some extra imbalance compared to Optimal?)

Would be nice if someone could tell us where to read about these new settings.
Or just explain if/how they differ from cyrili's idea.

[everywhere116]

This is a very interesting idea and I appreciate the work you put in in figuring out the math, but I believe the random teams function already does something like this, correct?

[PhilipJFry]

yeah if only there would be a description of what every option does...

[JaggedAppliance]

Only difference is that with an auto balance button you could see what teams it's giving you rather than having it hidden before you enter the game.

[Viba]

Only difference is that with an auto balance button you could see what teams it's giving you rather than having it hidden before you enter the game.

So the host could just re-scramble the spawn options until he sees a good stack?

[JaggedAppliance]

Only difference is that with an auto balance button you could see what teams it's giving you rather than having it hidden before you enter the game.

So the host could just re-scramble the spawn options until he sees a good stack?

Yes precisely.

[Viba]

I like your thinking there