New Algorithm for "Force Even Teams" for the next build.
moultano
Creator of ns_shiva. Join Date: 2002-12-14 Member: 10806Members, NS1 Playtester, Contributor, Constellation, NS2 Playtester, Squad Five Blue, Reinforced - Shadow, WC 2013 - Gold, NS2 Community Developer, Pistachionauts
Creator of ns_shiva. Join Date: 2002-12-14 Member: 10806Members, NS1 Playtester, Contributor, Constellation, NS2 Playtester, Squad Five Blue, Reinforced - Shadow, WC 2013 - Gold, NS2 Community Developer, Pistachionauts
@remi.D and I have implemented a brand new algorithm for "Force Even Teams" for the next build!
We determined two problems with the previous implementation.
1. It used last round's kills as much as the skill values, which breaks for players that were commanding or joined late.
2. It reassigned all the players whether it was necessary to do so or not. This lead to people switching their team right back after being reassigned because they really wanted to play marines, or aliens, or they really wanted to play with their friends.
We fixed #1 by switching over to using the values from Hive entirely. These certainly aren't perfect yet, but they have the nice property that if they are wrong, they won't be wrong for long. The fastest way to make them better is to play games that hive thinks are balanced, and hive will learn from each game what each player's actual skill is.
To fix #2, Initially we thought about restricting team switching for 2 minutes after a force even teams vote, but we came up with a better idea.
The new algorithm takes the teams as they are, and tries to swap players until they are even. However, it does a few clever things to swap as few players as possible.
1. It starts by trying to even the teams using only the players in the readyroom which we interpret to be players who have no preference for team.
2. When looking for players to swap, it finds the pair that makes the skill difference as close to 0 as possible, and repeats this process until there are no available swaps that reduce the skill difference.
The nice thing about #2 is that it tries to make big swaps (best player for worst player if necessary) so it doesn't have to make too many of them.
Finding the optimal team balance is NP-Complete in general, but we think we've found a nice balance that finds a local optimum without disturbing people too much.
We determined two problems with the previous implementation.
1. It used last round's kills as much as the skill values, which breaks for players that were commanding or joined late.
2. It reassigned all the players whether it was necessary to do so or not. This lead to people switching their team right back after being reassigned because they really wanted to play marines, or aliens, or they really wanted to play with their friends.
We fixed #1 by switching over to using the values from Hive entirely. These certainly aren't perfect yet, but they have the nice property that if they are wrong, they won't be wrong for long. The fastest way to make them better is to play games that hive thinks are balanced, and hive will learn from each game what each player's actual skill is.
To fix #2, Initially we thought about restricting team switching for 2 minutes after a force even teams vote, but we came up with a better idea.
The new algorithm takes the teams as they are, and tries to swap players until they are even. However, it does a few clever things to swap as few players as possible.
1. It starts by trying to even the teams using only the players in the readyroom which we interpret to be players who have no preference for team.
2. When looking for players to swap, it finds the pair that makes the skill difference as close to 0 as possible, and repeats this process until there are no available swaps that reduce the skill difference.
The nice thing about #2 is that it tries to make big swaps (best player for worst player if necessary) so it doesn't have to make too many of them.
Finding the optimal team balance is NP-Complete in general, but we think we've found a nice balance that finds a local optimum without disturbing people too much.
Comments
A server mod where every round is randomized using this system would be very nice though. Have it account for players preferred side and even allow an option to set pre-select a team. If a slot is open on the preferred or pre-selected side and is deemed balanced by the algorithm, you will be placed there.
And have you guys fixed the "force" part of this vote? You aren't forcing anyone to do anything if they can switch out of the team they were placed on and stack to the team they want by simply pressing f4.
The common complaint is "I am always being switched" and "I want to play X but it has made me Y for the last 5 rounds" (as well as "It makes it worse", but that is almost never true, although it sure could be better). Random ready room solves this problem for that player but unfortunately will make the most unbalanced teams since it will keep the stack intact and then just randomly assign the other half. But this just shifts the complains towards the end of the game ("How was that a gg!?"). This can make force even effective against this, on the other hand there may be a few players whose "always me" complaint would be valid! If needed perhaps the hive could also keep internal stats on how often the player has recently been swapped and the algorithm prefer to switch someone that has been switched less often. Probably isn't needed.
I would suggest keeping assigning late connecting players for the first 5 or so minutes of the game (optionally wait sign of life or team join attempt since they may be AFK from not looking at the loading screen). It's very common that the presumably highest ranking player if there is one above most others, will leave before the start, leaving the teams unbalanced. A high ranking player could also join late and offset the balance. It's also common that a vote is simply initiating too early, while a good chunk of players are still loading the map.
Never assume players are not deliberately stacking. A few minutes of no team switching (sans F4?) could still be beneficial, but maybe for the next patch. F4 could still be useful since it's better to have no player than a useless player that doesn't want to play taking up a slot. Having a free slot means you might get a player that want to play on the next join, or if the teams become significantly unbalanced player count wise, auto balance will kick in and fix it.
There is also a problem with how votes are being handled in general. A single player has too much power over what to vote for. It's enough for a single player to initiate a random rr vote to block out the possibility of a force even vote. I don't know how to solve this. A simple fix would be to not allow random rr votes until the game has started or players has been waiting for a com for a while, but this problem extends beyond team balance and random rr votes, which map to change to also comes to mind.
Also, this sounds great Moultano! My 2c of input:
* Force Even Teams does have a bad rap at the moment, so I hope 269 includes some education and promotion of this change (In Super Effective's video changelog, for eg?). Make it known that using it should = better balanced teams = better games.
* I agree that it perhaps it should even be a default, toggle-able by a server admin. Something like 2-3 mins to allow people to join their preferred team, then at game start the algorithm kicks in. This way, presumably, most people still get to play on their preferred team, but the teams are balanced and RR players are allocated.
* Agree with lwf's suggestions to a) only assign RR where there's signs of life for a player and b) keep assigning players who join for 5 odd minutes after game starts. Especially true for votes that pass while players are still joining.
* I know there is a divisive opinion, so I leave it here as just that, an opinion: but I see merits in forcing players to stay on their allocated teams, at least again for 5 minutes or so, where upon if they stay they may now be invested. Is forcing a player to stay on a team a good thing? Probably not, but then assigning 'balanced' teams and having people F4 or switch defeats the whole purpose of voting for Force Even in the first place, and then the game ends and people complain about imbalanced teams *facepalm*. The predicted skill balance allocation of teams from Hive only works if people stick to it. Hence having it as a modus operandi is probably a good thing, especially if people can still choose their 'preferred' side by joining a side before the algorithm kicks in.
I propose the tentative name "Skill Balance"
Or, if you will, "Moultano for president"
IMO :
Make it kick in when game starts for all active players in RR (not AFK).
___Maybe some ppl will ask for a "AFK status" to avoid joining and idle. Depends on what is decided for Spectate mode. Disable F4 at the moment for 1 minute or until both teams have a commander.
Make it be used when a player go in "random" during the game.
___So everybody have the same process.
Disable other forms of vote about random/even teams.
___That would be the tricky part. I can't help thinking about the 'RTV' vote and official change map vote that sometimes are thrown at the same time.
Edit: it also currently says '(this will reassign all players)' which of course it won't now.
1. People have switched teams after the vote in the past, people will keep switching teams if you do not enforce it
2. Taking people from the Ready Room is assuming that they will be playing the next round, which is very often not the case
3. The vote is often made too early (before leaving players have left and connecting players are done loading)
4. The vote is highly unpopular AFAIK, so it may take a while to get used, if at all (some sort of re-naming might help a lot - "Make teams using Skill-Ranks" or something like that)
I would like something like that much more. Some kind of system where the team skill-scores are monitored (maybe also displayed somewhere so people can keep track of them as teams are forming) and something happens when a round is starting with a high skill gap.
For example there could be an automatic vote to "Force even teams" when the skill-gap exceeds a certain threshold. (Note that the players could still vote "No").
This should happen when the round is starting (both teams have a comm), because this is the best possible moment to balance without disrupting a running game.
The vote should leave the players in the Ready Room untouched. The problem of players being afk there for long times can be fixed with the AFK-kick functions.
What could be done though is that players who want to join a running round (which had a passed skill-vote), do not have the freedom of race-choice anymore, but get automatically sorted into a team in order to minimize the skill gap. This would only be possible if both teams have the same amount of players at that time I suppose.
If something like that would be implemented and found to be working as intended, I would be in favor of getting rid of the "Force even team"/"Randomize RR" votes completely.
Lets hope this will work.
I would definitely random everytime if it meant I get 3-5 extra pres
The proper solution would be that players can signal that they are ready to play, but don't care in which team.
In the current 3D ready room metaphor, players could (for example) start in a new first room called "Lobby". From there, they step through doors labeled "Marines", "Aliens", or "Ready Room". This new "Ready Room" would be where team balance draws players from. After a match ends, all players are returned to the Lobby instead of the Ready Room, so only players that want to play will enter the Ready Room. Players detected to be AFK are automatically moved to the Lobby.
However, reworking the ready rooms on all maps would probably be too much work (assuming the door naming like "Random" etc. is built into the map, and not generated). So maybe some kind of "ready to play" flag could solve this without map changes? Maybe automatically set by player movement - assuming that most players that want to leave don't run around in the ready room?
Simply create a mod where people can press F1 or F2 to flag themselves.
Because we all know how we like to chill out, go to secret rooms, jump around and get comfy.
Better yet if this was built into a pleasing UI:
Force Even Teams? (12 seconds to vote) Yes - F1 / No - F2
then if the vote passes, it presents people with X seconds to "Choose preferred side for balancing" Marine - F1, Alien - F2
Then perhaps after the second countdown, it assigns with weighted consideration on people's preferences.
If you never played Evolve, you do NOT have a choice what side to play on, instead you have a dropdown box in your options. (support, assault, medic, tracker, goliath, kraken, ???) but it can help more often than not to get the side you are itching for. It may also help the "force even team" A.I. create balanced teams that also appeases preference.
Function fails to fit description again.
When we tried it the other night it seemed to work toward making a more pleasant experience. I am excited about this, thanks.
This is awesome work. Thank you!
Sorry to spoil the praise but I would like to suggest something: Take into account those who entered through the door, "Random". People who entered through random clearly do not mind what team they are on and should be ranked higher than those who are in the lobby, as they could possibly be afk. Sorry for the suggestion, but I hope it helps. (Also in my personal and humble opinion I think the Random "door" should be the main/biggest/and centered door rather than the team doors; from there you can walk to the specific door you want if you really don't want to go random)