Post Reply 
 
Thread Rating:
  • 32 Votes - 3.22 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Shuffling algorithm
05-19-2011, 11:09
Post: #1
Shuffling algorithm
0
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 A-Xander --- 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 A-Xander (256)
Blue: NoyzZ Moonnique my8os PoCTaHK adelbonder PSICHiatr (259)

Last player goes into weaker team
Red: isrforce GrrrMan new_kids kamkam mavixx A-Xander shak007(257)
Blue: NoyzZ Moonnique my8os PoCTaHK adelbonder PSICHiatr (259)

Finally the new teams have
Red: 257 individual score, 4 former-red, 3 former-blue players
Blue: 259 individual score, 3 former-red, 3 former-blue 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 (score-wise) 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 acylum-children
4 Adsovonmelk
Total = 395, 5:5

Example 3
Balanced, one top-player
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 top-player
Total = 901, Players = 16, MinDiff = 5.631

Red team:
134 BaStArDBrAiN
73 fingold
66 NIKOLASHARK
57 Makeychik
48 Tikytak
43 Moonique
27 Baton-Shtender
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 top-player
Total = 238, Players = 8, MinDiff = 2.975

Red team:
78 radarfox
29 isrforce
16 -=Noda-ut5=-
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 A-Xander
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 top-player
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...
Find all posts by this user
Quote this message in a reply
05-19-2011, 12:13
Post: #2
RE: Shuffling algorithm
0
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.
Find all posts by this user
Quote this message in a reply
05-19-2011, 15:40
Post: #3
RE: Shuffling algorithm
0
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..Smile Tongue ...




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...
Find all posts by this user
Quote this message in a reply
05-19-2011, 16:40
Post: #4
RE: Shuffling algorithm
0
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.
Find all posts by this user
Quote this message in a reply
05-19-2011, 18:34
Post: #5
RE: Shuffling algorithm
0
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 single-player oriented tactics, like hammer-jump 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 Wink

I've experiments to run,
There is research to be done
On the people who are
still alive...
Find all posts by this user
Quote this message in a reply
05-19-2011, 19:08
Post: #6
RE: Shuffling algorithm
0
(05-19-2011 15:40)BetoneeR Wrote:  also look this..they are better team on points but we winn becouse PARA play for us..Smile Tongue ...

That apparently was long time ago. Wink

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. «
---------------------------------------------------------------------------------------------------------------
Visit this user's website Find all posts by this user
Quote this message in a reply
05-19-2011, 19:14
Post: #7
RE: Shuffling algorithm
0
Award for the longest post Smile

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 11-11-2010.
So many nice maps, but we play Shoebox etc. -.-.
Find all posts by this user
Quote this message in a reply
05-19-2011, 19:15
Post: #8
RE: Shuffling algorithm
0
(05-19-2011 19:14)_RattleSN4K3_ Wrote:  Award for the longest post Smile

Send me a PM to receive a free mp3 player Big Grin (jk)

---------------------------------------------------------------------------------------------------------------
» I don't suffer from insanity. I enjoy every minute of it. «
---------------------------------------------------------------------------------------------------------------
Visit this user's website Find all posts by this user
Quote this message in a reply
05-19-2011, 19:16
Post: #9
RE: Shuffling algorithm
0
It was Liliums one. ^^

_________________________________________________________________

DoS died on 11-11-2010.
So many nice maps, but we play Shoebox etc. -.-.
Find all posts by this user
Quote this message in a reply
05-19-2011, 19:18
Post: #10
RE: Shuffling algorithm
0
And I was referring to Lilium's post Wink

---------------------------------------------------------------------------------------------------------------
» I don't suffer from insanity. I enjoy every minute of it. «
---------------------------------------------------------------------------------------------------------------
Visit this user's website Find all posts by this user
Quote this message in a reply
Post Reply 




» Powered by: betamaster.us «» Partner sites : vsee.us | knet.us |