Forged Alliance Forever

Re: About TrueSkill and game-quality optimization

2016-08-07T16:04:23+02:00

cyrili wrote:
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:
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

это никому не нужно.
лучше сделай что бы игра не лагала и фпс не падал на 2000 юнитов)

Statistics: Posted by gamedata — 07 Aug 2016, 16:04

Re: About TrueSkill and game-quality optimization

2016-08-07T15:26:00+02:00

cyrili wrote:
https://github.com/cyrili

how would i go about joining slack?

Assuming you want to join using the email you've registered on the forums with, you have an invite in your inbox. Otherwise let me know if I should send an invite elsewhere.

Statistics: Posted by Sheeo — 07 Aug 2016, 15:26

Re: About TrueSkill and game-quality optimization

2016-08-05T22:11:13+02:00

https://github.com/cyrili

how would i go about joining slack?

Statistics: Posted by cyrili — 05 Aug 2016, 22:11

Re: About TrueSkill and game-quality optimization

2016-08-05T20:05:52+02:00

cyrili wrote:
i understand.

what would one have to do to be able to contribute to the codebase itself? what are the requirements?

Mind, I'm not planning on doing anything without discussing it, but i feel like only suggesting stuff on this forum isn't cutting it. and I'd really like to see this game improve.

Join slack and have a github account

Statistics: Posted by Aulex — 05 Aug 2016, 20:05

Re: About TrueSkill and game-quality optimization

2016-08-05T19:49:40+02:00

i understand.

what would one have to do to be able to contribute to the codebase itself? what are the requirements?

Mind, I'm not planning on doing anything without discussing it, but i feel like only suggesting stuff on this forum isn't cutting it. and I'd really like to see this game improve.

Statistics: Posted by cyrili — 05 Aug 2016, 19:49

Re: About TrueSkill and game-quality optimization

2016-08-04T12:22:13+02:00

When it comes to lane definitions there is a normal convention which map makers are supposed to be using. Which is essentially that the player slots to configured for even vs odd team setting.

There are some notable exceptions to this. Such as Gap of Rohan (with players 1, 2, 3, and 4 vs. 8, 7, 6, and 5). Seton's Clutch does operate with even vs. odd, but because the map is rotationally symmetrical, and not mirrored, it has (players 1, 3, 5, and 7, vs. 2, 6, 4, and 8). Which is of course a slot balancing algorithm nightmare.

Statistics: Posted by Hawkei — 04 Aug 2016, 12:22

Re: About TrueSkill and game-quality optimization

2016-08-04T12:48:56+02:00

Happy to see that auto-balance will be implemented in the next patch.

Although i would have personally preferred seeing it implemented in the game lobby (before the game starts) as this would give the possibility to rearrange players within a team while maintaining high game-quality. possibly even giving the option for constraints (like keeping friends/clans together, keeping players in certain positions, and similar).

Looked at the source code. At this moment "Random" seems to actually be random and not optimal.

Spoiler: show

Also "Optimal Balance" seems to be choosing the best of 3 balancing functions of witch none picks the mathematically best option (all according to trueskill-quality).
(I'm not 100% sure on that one because coming from a low-level language LUA and generic for loops hurt my head. but since they all pick 1 player at a time i should be right in my assumption)

Spoiler: show

Code:: local setups = {} local functions = { rr=autobalance_rr, bestworst=autobalance_bestworst, avg=autobalance_avg, } local cmp = function(a, b) return a.quality > b.quality end local s, q for fname, f in functions do s = f(ratingTable, teams) if s then q = autobalance_quality(s) table.binsert(setups, {setup=s, quality=q}, cmp) end end -- skipped flex balance best = table.remove(setups, 1) rearrangePlayers(best)

Code:: local function autobalance_rr(players, teams) local players = table.deepcopy(players) local teams = table.deepcopy(teams) local result = {} local team_picks = { {}, {1,2, 2,1, 2,1, 1,2, 1,2, 2,1}, {1,2,3, 3,2,1, 2,1,3, 2,3,1}, {1,2,3,4, 4,3,2,1, 3,1,4,2}, } local picks = team_picks[table.getn(teams)] if not picks or table.getsize(picks) == 0 then return end i = 1 while table.getn(players) > 0 do local player = table.remove(players, 1) local team = table.remove(picks, 1) local slot = table.remove(teams[team], 1) if not player then break end table.insert(result, {player=player['pos'], rating=player['rating'], team=team, slot=slot}) end return result end

Code:: local function autobalance_bestworst(players, teams_arg) local players = table.deepcopy(players) local result = {} local best = true local teams = {} for t, slots in teams_arg do table.insert(teams, {team=t, slots=table.deepcopy(slots), sum=0}) end -- teams first picks best player and then worst player, repeat while table.getn(players) > 0 do for i, t in teams do local team = t['team'] local slots = t['slots'] local slot = table.remove(slots, 1) local player if best then player = table.remove(players, 1) else player = table.remove(players) end if not player then break end teams[i]['sum'] = teams[i]['sum'] + player['rating'] table.insert(result, {player=player['pos'], rating=player['rating'], team=team, slot=slot}) end best = not best if best then table.sort(teams, team_sort_by_sum) end end return result end

Code:: local function autobalance_avg(players, teams_arg) local players = table.deepcopy(players) local result = {} local teams = {} local max_sum = 0 for t, slots in teams_arg do table.insert(teams, {team=t, slots=table.deepcopy(slots), sum=0}) end while table.getn(players) > 0 do local first_team = true for i, t in teams do local team = t['team'] local slots = t['slots'] local slot = table.remove(slots, 1) local player local player_key for j, p in players do player_key = j if first_team or t['sum'] + p['rating'] <= max_sum then break end end player = table.remove(players, player_key) if not player then break end teams[i]['sum'] = teams[i]['sum'] + player['rating'] max_sum = math.max(max_sum, teams[i]['sum']) table.insert(result, {player=player['pos'], rating=player['rating'], team=team, slot=slot}) first_team = false end table.sort(teams, team_sort_by_sum) end return result end

And damn... the dev's aren't fans of commenting, are they?

Lane balance vs. game balance:
An extreme case would be something like these 2 team-division variants of the same lobby:

A:
1000 - 1500
1200 - 1600
2100 - 1600
2200 - 1800

B:
1000 - 1200
1600 - 1500
1600 - 1800
2200 - 2100

Trueskill would give A a better game quality, although Hawkei indicated that B may be more desirable (and that in both games it is important to minimize laning differences and to not match 2200 vs 1000 or similar)

From the tooltips in the beta client it appears that lanes are not regarded by the upcoming balancer algorithm ("random start locations"). Since I have time I'd like to propose a way to define lanes (at least rudimentary, since it's better than not doing it).

Lane definition algorithm:

Seton's Clutch

define teams as compositions with the smallest grey angles (convert to polar -> sort by phi -> try divisions of that list) (worked on all top ~80 2-team maps i tried). Or use user chosen team comp.
deduce the black combat-front line from the average starting position of each team.
mirror one team over that line.
define laning opponents as a list of pairs witch has the least average distance between pair-members (in mirrored coordinates).

This is merely a suggestion for a way to have at least some kind of idea about what players are laning against each other (not regarding player role and doesn't work well on asymmetrical maps). A much better solution would certainly be to consistently use a convention with the starting slots or to directly include the information in the map files.

The lane data could then be used to balance lanes as proposed by Hawkei and to have a better game quality reading by considering lane 1v1 quality.

Statistics: Posted by cyrili — 04 Aug 2016, 12:02

Re: About TrueSkill and game-quality optimization

2016-08-03T21:47:08+02:00

I like your thinking there

Statistics: Posted by Viba — 03 Aug 2016, 21:47

Re: About TrueSkill and game-quality optimization

2016-08-03T21:40:37+02:00

Viba wrote:
JaggedAppliance wrote: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.

Statistics: Posted by JaggedAppliance — 03 Aug 2016, 21:40

Re: About TrueSkill and game-quality optimization

2016-08-03T21:34:54+02:00

JaggedAppliance wrote:
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?

Statistics: Posted by Viba — 03 Aug 2016, 21:34

Re: About TrueSkill and game-quality optimization

2016-08-03T21:25:26+02:00

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.

Statistics: Posted by JaggedAppliance — 03 Aug 2016, 21:25

Re: About TrueSkill and game-quality optimization

2016-08-03T19:57:22+02:00

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

Statistics: Posted by PhilipJFry — 03 Aug 2016, 19:57

Re: About TrueSkill and game-quality optimization

2016-08-03T18:53:59+02:00

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?

Statistics: Posted by everywhere116 — 03 Aug 2016, 18:53

Re: About TrueSkill and game-quality optimization

2016-08-03T16:48:06+02:00

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.

Statistics: Posted by KeyBlue — 03 Aug 2016, 16:48

Re: About TrueSkill and game-quality optimization

2016-08-03T14:59:11+02:00

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

Statistics: Posted by Zock — 03 Aug 2016, 14:59