Shuffling algorithm

05192011, 11:09
Post: #1




Shuffling algorithm
Motivation
This is mainly directed at Rattle, who wants to write a simple balancing mutator that wouldn't lag as TTF does, but I am writing it in public to get your opinion on this. Plus, maybe it will sparkle some new ideas... The main objective of shuffling teams at beginning of a match is:  Make game interesting, playing in different teams  Keep game balanced  Prevent team stacking and series of heavily imbalanced games  Make game challenging for everyone Problem statement A match has ended. We assume that all players are going to participate in the next match. Based on the current team composition, final score and individual player score, how do we shuffle teams? We want approximately half of a team to be swapped and we want to prevent total imbalance in next match. Suggested algorithm 1: Top 2 players from the winning team get separated. 2: Sort all other players by their individual score and put them into a list P 3: Take 2 players (a,b) from list P 4: One player from the pair will go to red team, the other  goes to blue. How? See 5: or 6: 5: If they were from the same team or their individual score difference is significant > put stronger player to a team which is currently weaker by the sum of individual score. The other player goes to the otehr team. 6: Otherwise  if players a & b are from different team and their score difference is insignificant > put the players to maximise the shuffling of red and blue players. 7: If criterium 6: is undecisive (e.g. teams already have 1:1 ratio of red and blue players) use 5: 8: While list P still contains at least 2 players, go to 3: 9: If there is last remaining player, put it to the weaker team By "significant difference" I define a difference that is greater than: sum_of_individual_scores / (10 * num_players) Example run of the algorithm Take the following match result: Although Moonnique has the highest score, she didn't win the match. sum_of_individual_scores = 516 num_players = 13 significant_difference = 3.97 Step 1: We put isrforce and NoyzZ into separate teams Red: isrforce (63) Blue: NoyzZ (49) In parenthesis I put the total individual score of players in the team Step 2: We sort all remaining players (and put into pairs already): P:= 106 Moonnique  71 GrrrMan 48 new_kids  45 my8os 41 kamkam  37 PoCTaHK 27 mavixx  19 adelbonder 6 AXander  3 PSICHiatr 1 shak007 Pair 1: score difference high  criterium 5 Red: isrforce GrrrMan (134) Blue: NoyzZ Moonnique (155) Pair 2: score difference low, but criterium 6 is undecisive: currently both teams have same number of red and blue players. Using criterium 5 Red: isrforce GrrrMan new_kids (182) Blue: NoyzZ Moonnique my8os (200) Pair 3: score difference high (above 3.97)  criterium 5 Red: isrforce GrrrMan new_kids kamkam (223) Blue: NoyzZ Moonnique my8os PoCTaHK (237) Pair 4: score difference high  criterium 5 Red: isrforce GrrrMan new_kids kamkam mavixx (250) Blue: NoyzZ Moonnique my8os PoCTaHK adelbonder (256) Pair 5: score difference low, first team has more blue players, while second has more red. That's why new red player enters the first team. Red: isrforce GrrrMan new_kids kamkam mavixx AXander (256) Blue: NoyzZ Moonnique my8os PoCTaHK adelbonder PSICHiatr (259) Last player goes into weaker team Red: isrforce GrrrMan new_kids kamkam mavixx AXander shak007(257) Blue: NoyzZ Moonnique my8os PoCTaHK adelbonder PSICHiatr (259) Finally the new teams have Red: 257 individual score, 4 formerred, 3 formerblue players Blue: 259 individual score, 3 formerred, 3 formerblue players Although Moonnique got very high score in that match, because of pairing she is now not assigned to a team consisting only of total noobs. Still, teams (scorewise) are even and a good mixture of red and blue players is achieved More examples I have downloaded few demos from DoS and tried to apply the algorithm: Example 1 Balanced, big match Total=413, Players=18, MinDiff=2.294 Red team: 58 antik0r 38 Sliveren 29 Razorjaw 26 lo2011 17 salazarfelix 16 Grand23 8 picikimi 8 okom 6 max3742877 Total = 206, Red = 6, Blue = 3 Blue team 49 Yip.M4n 46 isrforce 29 my8os 26 SODKIE 18 vitamin 15 LEGOT 14 JNH 8 carPOLISHer 2 HePizdi Total = 207, Red = 5, Blue = 4 Example 2 Balanced, big match Total = 807, Players = 20, MinDiff = 4.035 Red team: 72 RachmanyinoooV 79 izof 45 isrforce 44 carPOLISHer 39 my8os 30 antik0r 30 vitamin 28 okom 24 lo2011 21 NIKOLASHARK Total = 412, 5:5 Blue team: 72 picikimi 61 Razorjaw 58 Sliveren 45 salazarfelilx 42 LEGOT 36 Grand23 29 JNH 25 ruban 23 acylumchildren 4 Adsovonmelk Total = 395, 5:5 Example 3 Balanced, one topplayer Total = 207, Players = 15, MinDiff = 1.38 Red team: 40 radarfox 25 salazarfelix 19 DeineLtan 10 Ratona 8 NIKOLASHARK 3 max3742877 0 Poppy<3 Total = 105, 4:3 Blue team: 26 funak3i 33 Moonnique 20 LQtook 15 Heronimus_Prime 5 djdante06 2 0=4@59G18A>2 1 sSingleSs 0 Tikytak Total = 102, 3:5 Example 4: Imbalanced, one topplayer Total = 901, Players = 16, MinDiff = 5.631 Red team: 134 BaStArDBrAiN 73 fingold 66 NIKOLASHARK 57 Makeychik 48 Tikytak 43 Moonique 27 BatonShtender 19 SELTRUT Total = 467, 4:4 Blue team: 86 ANDREY(1977)321 75 iz145106 61 my8os 58 funak3i 49 Ratona 48 WindiS 34 Poppy<3 23 quad_gore Total = 434, 4:4 Example 5: One topplayer Total = 238, Players = 8, MinDiff = 2.975 Red team: 78 radarfox 29 isrforce 16 =Nodaut5= 3 Pokeda Total = 126, 3:1 Blue team: 34 salazarfelix 44 N4rck 25 Perem 9 Hamonadaka Total = 112, 2:2 Example 6: Top player in loosing team Total = 516, Players = 13, MinDiff = 3.97 Red team: 63 isrforce 71 GrrrMan 48 new_kids 41 kamkam 27 mavixx 6 AXander 1 shak007 Total = 257, 4:3 Blue team: 49 NoyzZ 106 Moonnique 45 my8os 37 PoCTaHK 19 adelbonder 3 PSICHiatr Total = 259, 3:3 Example 7 Imbalanced Total = 336, Players = 11, MinDiff = 3.05 Red team: 67 radarfox 30 Lilium_Atratum 28 LuxThor 21 Alexandros73 16 lunn 0 aleksandar83 Total = 162, 4:2 Blue team: 66 Petx77 63 darkredfoxxx 25 GrrrMan 18 sSingleSs 2 new_kids Total = 174, 1:4 Example 8 Slightly imbalanced, one topplayer Total = 421, Players = 8, MinDiff = 5.26 Red team: 120 radarfox 62 flab.slab 33 DonkeyKongXT 8 PblCb[Db105] Total = 221, 2:2 Blue team: 76 RattleSN4K3 66 Lilium_Atratum 34 LoodiBlud 22 BigUncle Total = 198, 2:2 Example 9 Low player count, imbalanced Total = 153, Players = 7, MinDiff = 2.19 Red team: 52 ROODROGS 21 Warstor 4 PSICHiatr 2 Ratona Total = 75, 2:2 Blue team: 32 Tikytak 26 new_kids 20 NIKOLASHARK Total = 78, 2:1 I've experiments to run, There is research to be done On the people who are still alive... 

05192011, 12:13
Post: #2




RE: Shuffling algorithm
The algorithm looks fair.
If possible, I suggest instead of points use points/time. This will take into account for example good players with low score obtained in little time. 

05192011, 15:40
Post: #3




RE: Shuffling algorithm
good idea,,but you must take option a 'map'...look this:
so if that was the same teams on necro or sand we would have badly lost for sure...so have you some solution for that? also look this..they are better team on points but we winn becouse PARA play for us.. ... also you must take a option on players who play TDM in VCTF mode...only spam,snipe and camp... Life is a Game = someone is a Toy  someone is a Player... 

05192011, 16:40
Post: #4




RE: Shuffling algorithm
We're talking about a general and *fast* algorithm.
I don't know if you can take more factors into account like what you present, although it would be nice to have gametime information in the snapshots you present. 

05192011, 18:34
Post: #5




RE: Shuffling algorithm
Also, if some uneven match happens eventually, it is not really a problem. What problem is, is when several matches in a row are uneven.
You nicely dominated that RedroomUT3 match. But that's the problem of the map  small spamaps favors singleplayer oriented tactics, like hammerjump runs, especially when opponents are not prepared to defend against that. I always defend it on smapams against that and I think you already experienced that I've experiments to run, There is research to be done On the people who are still alive... 

05192011, 19:08
Post: #6




RE: Shuffling algorithm
(05192011 15:40)BetoneeR Wrote: also look this..they are better team on points but we winn becouse PARA play for us.. ... That apparently was long time ago. But as said, I might start playing again soon, yet I'm not sure though, as I currently don't know exactly what I'm going to do in future (I'd like to go to a university, but also got a nice job offer today)  » I don't suffer from insanity. I enjoy every minute of it. «  

05192011, 19:14
Post: #7




RE: Shuffling algorithm
Award for the longest post
Basically a shuffling algortithm is not need. But i would make matches more interesting. Since SeamLessTravel is deactivated, the option to stay on the server while loading a map, you will join on a quite random time and the teams get shuffled randomly. But in the scenario, the players with the fastest machine will join earlier and will always play against each other. The shuffling algorithm looks good. That's quite the same idea i was thinking about. But the most important part of having my "mutator" is to kick/switch idle players. These players unbalancing the game a lot. _________________________________________________________________ DoS died on 11112010. So many nice maps, but we play Shoebox etc. .. 

05192011, 19:15
Post: #8




RE: Shuffling algorithm
(05192011 19:14)_RattleSN4K3_ Wrote: Award for the longest post Send me a PM to receive a free mp3 player (jk)  » I don't suffer from insanity. I enjoy every minute of it. «  

05192011, 19:16
Post: #9




RE: Shuffling algorithm
It was Liliums one. ^^
_________________________________________________________________ DoS died on 11112010. So many nice maps, but we play Shoebox etc. .. 

05192011, 19:18
Post: #10




RE: Shuffling algorithm
And I was referring to Lilium's post
 » I don't suffer from insanity. I enjoy every minute of it. «  

« Next Oldest  Next Newest »
