In-lobby Auto Balancing

@scout_more_often
Number of games played is very relevant to uncertainty, and uncertainty is taken into consideration with this autobalancing.

Some background info:
A player's displayed rating (what you see in-lobby) is actually the rounded result of:
Displayed Rating = Base Rating - Uncertainty
aka
Displayed Rating = Mean - (3 * Deviation)

A new player starts as
0 displayed rating = 1500 base rating - 1500 uncertainty

After playing a few games, the new player might be something like:
500 = 1600 - 1100

After playing enough games that the player is no longer 'gray', the rating might be something like:
1300 = 1600 - 300

So, as you can see, the uncertainty starts at 1500, and generally, as a player plays more rated games, the uncertainty decreases over time, and eventually stabilizes at around 150ish to 300ish points. Playing 1v1's lowers the initial uncertainty a lot faster than playing 8v8's, as smaller player counts enable more certainty on individual player skill in determining victory vs defeat.

So, while this autobalancing could be changed to more directly factor in the number of games played, I think balancing each team's uncertainty is a somewhat similar but better solution.

I will put this here as as refence https://github.com/FAForever/fa/pull/2903
The method I used to find the Fairest Teams is to get each player's Trueskill and then bruit force all combinations dividing players into 2 teams. For 8 players and under it can find that result instantly, however once you start going to 10, 12 players it starts to take some time, 16 players takes a very long time.
There are a few options though.
The script could be optimised to not repeat combinations that are mirrored
e.g
team 1 | team 2 team 1 | team 2
1000 | 1200 1200 | 1000
This can half the amount of combinations

Another idea is to find the max amount of players the script can support, say 8, and use the bruit force method for that. For player numbers > then the max use another method.

Another idea is to have the script stop once over 90% is found when over 8 players or X amount of time passes.

So it does not need to go through all combinations with lots of players, just when a good % is found or a calc time passes.

@thecore
I actually already made the process a lot more efficient by minimizing the number of iterations, while still checking every possible balance combination for the players on 2 teams of a given size. For perspective, in my testing, autobalancing 16 players took about 2-3 seconds on my computer. I was able to lower the iteration count so much by limiting the iterations to half of all possible combinations of players on team 1 (avoiding the needless testing of the remaining half of opposite/mirrored sets). Notably, I did iterations of combinations rather than permutations, which saves a lot of processing time without any loss of quality for what this balancing function does. For perspective, the number of permutations for 8 / 16 things is 518,918,400, while half the number of combinations for 8 / 16 things is 6,435 (reducing the complete iteration count for balancing 16 players by ~99.99876% compared to iterating through all those permutations, without reducing balance quality).

This is very cool, look forward to this feature finally being added.

Once added it can replace https://github.com/FAForever/fa/pull/3750

https://github.com/FAForever/fa/pull/3750 is the PR that added this functionality that I just described... it's on FAF Develop now
You can host a game on FAF Develop and click the AutoBalance button (with people in the lobby) and see the results.

@emperor_penguin just tested it, the AutoBalance works well, however I think there could be bug where some players were not placed correctly (their positions in the lobby did not match their game positions). I was the host on gap map and I was front on team 1, then I auto balanced and I was moved to air team 2. However when the game started I was placed front on team 1 (not sure on the other players) can you confirm this?

Very welcome addition, thank you.

The biggest improvement by far is the host gets to see the result and potentially alter it, as opposed to using opti balance and hoping for the best.

When there are open slots available, the balancer changes players' team assignment in place instead of moving them to the appropriate slots, messing up the auto teams setting in the process. For instance, in a 4v4, i ended up with 4 players top vs 2 players bottom, while one of the top players got assigned to team 2, alongside the bottom players. the remaining open slots were both on the bottom. The auto teams setting got switched from odd vs even to manual.

This might be tricky to fix because not all maps follow the same numbering conventions for slots. I know mapgen numbers slots in alternating team fashion, as i expect most maps do, but there are manmade maps that don't follow this convention, like Dunes of Arracis where the first 5 slots are supposed to be one team, and the last 5 are supposed to be the other. Maybe the autobalancer could query the active auto-teams setting and go off of that to figure out which slots should be what teams, or when manual team selection is active, maybe we should expect the host to set team assignments per slot and then the autobalancer should run with that, although the current process to do so is very tedious: you have to turn on the old autobalance then click each spawn point until it's assigned the right team number, then you'd have to turn off old autobalance again and click the new button... maybe there's a better way ?

@phong said in In-lobby Auto Balancing:

When there are open slots available, the balancer changes players' team assignment in place instead of moving them to the appropriate slots, messing up the auto teams setting in the process. For instance, in a 4v4, i ended up with 4 players top vs 2 players bottom, while one of the top players got assigned to team 2, alongside the bottom players. the remaining open slots were both on the bottom. The auto teams setting got switched from odd vs even to manual.

This might be tricky to fix because not all maps follow the same numbering conventions for slots. I know mapgen numbers slots in alternating team fashion, as i expect most maps do, but there are manmade maps that don't follow this convention, like Dunes of Arracis where the first 5 slots are supposed to be one team, and the last 5 are supposed to be the other. Maybe the autobalancer could query the active auto-teams setting and go off of that to figure out which slots should be what teams, or when manual team selection is active, maybe we should expect the host to set team assignments per slot and then the autobalancer should run with that, although the current process to do so is very tedious: you have to turn on the old autobalance then click each spawn point until it's assigned the right team number, then you'd have to turn off old autobalance again and click the new button... maybe there's a better way ?

A host using the auto-balancer could recognize what the teams are "supposed" to be. After auto-balancing, the host swap players to put them on the correct team.

Not a perfect solution but for maps with 8 or fewer players, that's probably not a huge amount of switching. And my impression is that the most popular maps for 10+ players mostly have versions with alternating slots for each team.

@thecore said in In-lobby Auto Balancing:

@emperor_penguin just tested it, the AutoBalance works well, however I think there could be bug where some players were not placed correctly (their positions in the lobby did not match their game positions). I was the host on gap map and I was front on team 1, then I auto balanced and I was moved to air team 2. However when the game started I was placed front on team 1 (not sure on the other players) can you confirm this?

I am not aware of a bug where the lobby positions don't match the in-game positions. If that happens when spawns are set to 'fixed', you can report it in the #game-bug-reporting channel on the FAF Discord. However, I imagine you might not have set spawns to 'fixed' (ie: you had opti enabled). I thought about it, and just made an additional PR to have clicking the AutoBalance button automatically set spawns to fixed.

@arma473 yes the host can fix it but I assumed the point of it all was to make the host's life easier. Ideally the balancer shouldn't mess with the auto teams setting at all and should be able to 'read the room' and make a proper 3v3 in a 4v4 lobby with 2 empty slots before this gets pushed out to everyone. People are gonna click that button early and for an inexperienced host the result could be quite confusing. First impressions matter.

I do love it though, don't get me wrong. I just think this is kind of an edge case the dev didn't immediately consider and the sort of thing testing is for. Just reporting my test results.

It is worth pointing out that even the existing optimal balance (mirrored) fails to do this right. A 4v4 launched with 6 players and 2 open slots does make a 3v3 but a different slot might be left open for each team, asymmetrically.

Would it be possible to hard-code positions information for some (10+) of the most popular maps that aren't organized this way?

In general, I'm guessing that all new maps tend to have alternating positions, so this would be a one-time effort without significant ongoing effort to maintain the list.

@arma473 said in In-lobby Auto Balancing:

Would it be possible to hard-code positions information for some (10+) of the most popular maps that aren't organized this way?

In general, I'm guessing that all new maps tend to have alternating positions, so this would be a one-time effort without significant ongoing effort to maintain the list.

You don't need to hardcore anything the balance should just respect the selected option of the teams like left vs right or top vs bottom or odd vs even. This way it is flexible enough to handle any map.

if it could go by whatever teams are assigned to the slots when you click the button that would be great. sort the spawn numbers per team and fill in order

@phong
FYI, the AutoBalance function was already set to use the slot-team combinations previously assigned if half of the occupied slots were set to team 1 and half to team 2. Otherwise, it was set to just remake the teams in alternating team order (1, 2, 1, 2, 1, 2, etc) for the occupied slots.

However, I understand your point about wanting to use odd vs even, top vs bottom, and left vs right AutoTeams; so, I just added functionality to support them to this PR. I had mixed thoughts on how to choose the order in which the slots will be filled with those AutoTeams. I tested out trying to have it sort by location, but between the different symmetry types and too many maps having inconsistent/imperfectly mirrored spawn locations, I wasn't satisfied with the results. So, I opted to set those AutoTeams configurations to just place people in numerical slot order, only skipping closed slots and slots necessary to skip to keep team size equal (if any). If there is an odd number of players with 1 of those configurations, it will make the last player an observer (or remove the player if it's an AI).

The previous functionality basically remains when AutoTeams are not set to odd vs even, top vs bottom, or left vs right. Additionally, if any of those configurations are set but yield an insufficient number of slots on one team, teams are set to a manual configuration to make an equal number of players on team 1 and team 2.

@arma473 While it is theoretically possible to hardcode things for individual maps, that is probably not the right approach for this. If there are some particularly important cases, you might want to talk to the map authors about fixing them (and or investigate getting FAF version of maps made if the authors are MIA/unknown).

thanks for the effort @Emperor_Penguin. I've been using it all day and I am very satisfied with it. It works great even as it is now if i close the open slots before clicking.

Reasons the new balance is better than old opti-balance:

Does better when grays are in the lobby

Does all the hard work but lets you tweak the result. On maps with rotational symmetry, I'd rather have strong players in the center lane and weaker players on the sides. Old opti sometimes made highest-vs-lowest rated machups on such maps. Your solution lets me fix this with 4 clicks

Not forced to re if the balance is only good on paper

Can accommodate premade teams easier. click button then swap some similarly rated players from one team to another

Would be cool to be able to lock some slots. "Me and my mate are on this team, now you balance the rest".

Slot based balancing would be cool too (matching similar slots against each other) but too tricky

The host has control over the lobby. The current solution gives the host full control.

@thecore said in In-lobby Auto Balancing:

@emperor_penguin just tested it, the AutoBalance works well, however I think there could be bug where some players were not placed correctly (their positions in the lobby did not match their game positions). I was the host on gap map and I was front on team 1, then I auto balanced and I was moved to air team 2. However when the game started I was placed front on team 1 (not sure on the other players) can you confirm this?

I've also experienced this bug just now. I used autobalance, then did 4 more swaps to fix lane balance. then someone said they had a premade, so i did one more swap, the last one. I was one of the players. This last swap didn't carry over to the game, instead, we spawned in the last position before this swap, which had also been set by a manual swap operations for each of us post autobalance.

I was using fixed spawns