Jump to content

  • Log in with Facebook Log in with Twitter Log In with Google Log In with Steam Sign In
  • Create Account
Photo

Improved sorting algorithm for teams.

- - - - -

  • This topic is locked This topic is locked
20 replies to this topic

#1
OFFLINE   dempa

dempa

    Newbie

  • Members
  • Pip
  • 6 posts
1
A step in the right direction
For this to make sense, we have to assume what I have noticed about the current k/d system:
  • K/D does not reflect Kills per Death, but acts more as a ranking system for a player's effectiveness relating to kills.
The K/D of the player that (kills you/you killed) also affects your k/d's change:
  • The lower the K/D of the player you killed, the less your K/D increases and the less their K/D decreases.
  • The higher the K/D of the player you killed, the more your K/D increases and the more their K/D decreases.
  • The longer you've played (not necessarily xp, since that can reset), the harder for the k/d to change in either direction.
When you first join, your k/d is at 1.000. As you play, it slowly approaches a number, which is a fairly accurate measure of your "effectiveness as far as kills"


Now that we have that out of the way, we can assume that averaging the k/d's is a way to analyze overall skill, assuming each team has equal number of members. Since that can't happen with an odd number of players, we remove the dividing by number of players, and instead compare sums of each team's K/D.
=================================================================================================================================================
I will try to explain this without being too mathematical in my explanation so that the concept will be easy to understand.

(We will do a more realistic example later on, but for now, let's use a basic example to show the concept)

Let's assume we have 10 players. For simplicity sake, we'll say each players has the respective k/d of {1.0, 2.0, 3.0 ...}

As it works now, teams are arranged by alternating the skill onto each team:

Team 1: 10, 8, 6, 4, 2
Team 2: 9, 7, 5, 3, 1

We can represent this as "ABAB..." arrangement.

If we sum each team, we get:

Team 1: 10+8+6+4+2 = 30
Team 2: 9 + 7 + 5 + 3 + 1= 25

Diff: 5

That's a pretty substantial difference. Let's average them since each team has 5 players:

Team1: 30/5 = 6
Team 2: 25/5 = 5

Diff: 1

====-=-=-====
The method by which I believe will work more effectively is using an ABBAABBA... arrangement.

Team 1: 10, 7, 6, 3, 2
Team 2: 9, 8, 5, 4, 1

If we sum, we get:

Team 1: 10+7+6+3+2 = 28
Team 2: 9+8+5+4+1 = 27

Diff: 1

We can average these, since there are an equal number of players per team:

28/5 = 5.6
27/5 = 5.4

Diff: 0.2


ABAB ABBA

5 > 1
1 > 0.2
Looks much closer to me.




More realistic example:

For this, I recorded the k/d's of players on Hardcore at the time of me writing this.

14 players:

3.826
3.613
3.002
2.641
2.454
1.881
1.697
1.480
1.280
1.185
1.125
1.113
0.587
0.390

With how current shuffling works (ABAB), the sums are:

Team 1: 13.971 Ave: 2.00
Team 2: 12.303 Ave: 1.75

Diff: 1.668
Ave Diff: .25

With ABBA..., the sums are:

Team 1: 13.381 Ave: 1.91
Team 2: 12.893 Ave: 1.84

Diff: 0.488
Ave Diff: 0.07

ABAB ABBA
1.668 > 0.488
.25 > 0.07

Yet again, ABBA is more effective at balancing teams. If you have any examples in which you believe ABAB is more effective, by all means post it here.

#2
OFFLINE   gaoesa

gaoesa

    Advanced Member

  • Management
  • PipPipPipPip
  • 4391 posts
341
Will become famous
  • LocationFinland
Your observations look correct. With small correction, it does not become accurate measurement. For that it would need to have a shorter span. However, it often does give fairly good measurement what to expect.

One thing to notice on the subject is that the defending team should be stronger in order to prevent easy wins. Also, the KR is not an absolute measurement. Sum difference of 0.25 for 7 player teams sounds ok to me if it is in favour of the defence. By easy win, I mean advancing without making several reasonably team worked attacks.

#3
OFFLINE   Dragonji

Dragonji

    Advanced Member

  • Members
  • PipPipPipPip
  • 514 posts
142
On the road to fame
  • LocationPoland

For this to make sense, we have to assume what I have noticed about the current k/d system:

  • K/D does not reflect Kills per Death, but acts more as a ranking system for a player's effectiveness relating to kills.

And that's why it has been renamed to KR (Kill Rating?) I suppose :)

#4
OFFLINE   SunLight

SunLight

    Newbie

  • Members
  • Pip
  • 6 posts
0
Unknown
ABBA is better all the times when there is an even number of players, but if the number is odd ABAB is better in most cases (not all, it's like 97%)

an example with 15 players (I multiplied all ratings by 100):

set of 15 ratings:
[47, 70, 100, 108, 148, 182, 210, 221, 245, 251, 269, 298, 334, 383, 386]

ABAB
team1 [386, 334, 269, 245, 210, 148, 100, 47]
team2 [383, 298, 251, 221, 182, 108, 70]
total average: 216, axis: 217, allies: 216, diff:1

ABBA
team1 [386, 298, 269, 221, 210, 108, 100]
team2 [383, 334, 251, 245, 182, 148, 70, 47]
total average: 216, axis: 227, allies: 207, diff:19

You also assumed K/D is a measure of player skill, according to what I've seen it doesn't always work properly.

It was supposed to be a sort of ELO but if it hasn't been changed from when I saw it, I think it's a very dubious algorithm. It doesn't take many factors into account (weapons for example, I think old etpub took that into account, then you have backshooting, crossfire, etc.etc.) and once you have a low rating it's very hard to improve it even if you play better, while people who get high scores in lame ways don't go down...

#5
OFFLINE   SunLight

SunLight

    Newbie

  • Members
  • Pip
  • 6 posts
0
Unknown
hmm now that I think about it my previous post was utter bs :D
because even if a bad player lowers the average it's still a player more ... xd I don't know what I was thinking about wehen I wrote that. The fact that k/d can be improved stays, though

#6
OFFLINE   gaoesa

gaoesa

    Advanced Member

  • Management
  • PipPipPipPip
  • 4391 posts
341
Will become famous
  • LocationFinland
The distance from where the kill is made seems to be the most important factor. I have never seen ETPub implementation where it would take the weapon into account. I agree that the KR shoud be better. But it only is there to help the balance a little.

The problem is not simple for public servers. Even a bad player is a player more but sometimes the bad player might place bad artys or camp at the cp doing nothing. However, even if there is a method to make perfectly even teams, it might have a big negative impact on public servers. With perfectly even teams,the attacking side will have easier games and can easily lead into run through maps. Even more, on public servers it is usual that all the players are not ready from the start. This can even further increase the problem if the players on the defending team are the ones less ready.

PS. I woul like to add that the KR moves too slowly after a while. Slower then how players improve in their games on the server. Or decrease their effectiveness.

#7
OFFLINE   SunLight

SunLight

    Newbie

  • Members
  • Pip
  • 6 posts
0
Unknown

The distance from where the kill is made seems to be the most important factor. I have never seen ETPub implementation where it would take the weapon into account. I agree that the KR shoud be better. But it only is there to help the balance a little.

I don't remember which etpub version, but it's an old one, they removed it later. It had a factor for every weapon if I remember correctly.
And the distance of a kill is meaningless imho, if I kill a player in 1on1 then we are either both close or both far, so I don't see how it can be a skill factor...

If I had to do it myself, I would have a table with all clients, with the time when each client received damage from every other client. Then when a player receives damage, looking at that table I could see if he received damage from another player in the last x seconds, if not then it's 1on1, if yes then it's crossfire.
And maybe make a dot product of player vectors to see if it's backshoot or not.

Having 1on1 damage, I would then make an elo score based on that, but it would require a bit more resources since it must be updated every time a player gives damage and not every time he kills.

Of course having kr as a rough way to balance teams is one thing, thinking something on the lines of 'I have a higher kr so I must be a better player' is different.
It would require a more complex algorithm and maybe impossible to do, so I can understand that changing it is not a high priority, after all if a player is good everyone can see it, ratings or not.

For public servers it's better to have an admin moving some players to balance the total score (kills/deaths or damage given/received) of axis and allies.

#8
OFFLINE   gaoesa

gaoesa

    Advanced Member

  • Management
  • PipPipPipPip
  • 4391 posts
341
Will become famous
  • LocationFinland

If I had to do it myself, I would have a table with all clients, with the time when each client received damage from every other client. Then when a player receives damage, looking at that table I could see if he received damage from another player in the last x seconds, if not then it's 1on1, if yes then it's crossfire.
And maybe make a dot product of player vectors to see if it's backshoot or not.


I don't think 1on1 is in the scope what they attempted to implement. In team games the situations where player end in 1on1 are not that often. Crossfire is more common death for single players. Also, I'm not sure playing 1on1 fights is a skill on it's own. I think the closest it comes is to the aiming. Of course it has the strafing part too. The weapon would have some good use. For example fops can get several kills from one airstrike which all sum up. Of course he may be a skilled fops to make such an airstrike and should be rewarded, but on the other hand, it might be too much for getting the full increase from each killed. In here, the distance factors this a little, but not necessarily. The fops might just as well hide close or far. I.e. in my opinion the distance factor is not really good enough.

However, the battlesense like factor, getting damaged as well as damaging, might bring some more results. I would assume that when working on any important objective, healing, reviving, engineering etc., one would get some damage and it might imply the player is working on the areas where his effectiveness depends on skills.

#9
OFFLINE   SunLight

SunLight

    Newbie

  • Members
  • Pip
  • 6 posts
0
Unknown

I don't think 1on1 is in the scope what they attempted to implement.

Indeed, but if you are going to make an elo kind of score then only 2 players must be involved, if I crossfire together with a teammate I can get a kill even if he did most of the job.

And as far as objectives are concerned, even the smartest players will always fail if they can't aim, so it all boils down to aiming, especially in public servers. And in fact they (etpub) made 2 different ratings, 1 for objectives and 1 for fighting (not that it matters what they made, I think we are talking about what's better, not what has been made).

Btw, you say 1on1 is rare? Here are some stats gathered from an ettv demo, the player is mAus, map:goldrush, the match is from cdc4 lan, only defending part, he was axis.
(Damage from explosive weapons is not counted, only damage from bullets)
1on1 damage: given: 2168 rcvd:1711
crossfire: g:959 r:284
backshoot: g:807 r:558

I didn't take a public server game, becuse you could have said people don't play for obj in pubs. And there is no teamplay.

Anyway maybe I'm getting a bit ot... since the thread was about the sorting, it didn't question KR algorithm

#10
OFFLINE   gaoesa

gaoesa

    Advanced Member

  • Management
  • PipPipPipPip
  • 4391 posts
341
Will become famous
  • LocationFinland

And in fact they (etpub) made 2 different ratings, 1 for objectives and 1 for fighting (not that it matters what they made, I think we are talking about what's better, not what has been made).


ETPub made 2 ratings, one for winning the map (not for playing the objective or how good the players are in general) and one for killing. I agree that we shouldn't discuss on that. I think neither one works but the killing one is more effective on balancing the teams.

I'm only concerned about the public servers. And in my observations, on public servers crossfire kills are common. More common then pure 1on1. How people play on clan matches is a different issue and I hope we can also agree that mAus is an extreme example of a well aiming player who would not depend on teammates as much. I don't know if that demo was from 5vs5 game or 6vs6 game but I suspect that also increases the chances of playing 1on1. Depends on the team tactics as well.

I think we can go off topic since the sorting itself does not appear faulty but more the values it sorts. I'm starting to have some interest on ditching the PRW, haven't seen it would have worked, and the KR and replace with R, which would not only try to estimate kills and the plain K/D for the current map.

#11
OFFLINE   SunLight

SunLight

    Newbie

  • Members
  • Pip
  • 6 posts
0
Unknown
it was a 6on6 game, yes I agree that I should probably have chosen another player, not an 'aimer'. Actually I took an ettv game because in my opinion public servers have more 'rambos' or players that play solo without much teamplay. So I expected to have more crossfire in a clanwar. But as you say in 6vs6 there is less chance of getting crossfired.

I cannot calculate those stats from jaymod demos, because I took advantage of the fact that on etpro demos you can always know if a shoot is hs or not, regardless of the player.
That is not possible with other mods, so the stats would count hs as bodyshots.

But I can tell you that I've been taking such stats in etpro publics for years (splitting damage), to check if I was improving my aiming or if I just got crossfired/backshooted, and to check what my skill level was if compared to the average (and for other players as well).
And according to what I saw 1on1 damage given/received is a reliable factor when it comes to tell who is low/med/high if compared to others.

Actually even on jaymod I can tell how much damage is 1on1 or not, and I can confirm that almost half of the damage is 1on1 (at least for me, I don't necessarily have the playing style of others).

The only reason why I said 1on1 in the 1st place, is not only the fact that killing in 1on1 requires obviously more skill than backshooting, or just finishing the job of a teammate.
It is more because with a score like that one (killer's score goes up, victim's score goes down) it sounded reasonable to me to limit it only in those cases where nobody else was involved, that is no crossfire.

edit:
I mentioned jaymod because it's the mod I play the most, and so I have more demos, but public servers are all the same

Edited by SunLight, 04 April 2012 - 04:29 PM.


#12
OFFLINE   hellreturn

hellreturn

    Management

  • Management
  • PipPipPipPip
  • 2693 posts
158
On the road to fame
hrm how about implementing kills and wins based shuffle based on past 2 games?

First their would be shuffle based on kills.

i.e.
Player A (30 kills) vs Player B (28 kills)
Player C (26 Kills) vs Player D (27 kills)

Then it checks the win probability... aka if player A has won last 2 map and player B has won 1 map... then we move Player A to last loosing team and player B to winning team...

This way every 2 maps their can be auto shuffle.. and after each auto shuffle.. it makes sure that player doesn't end up in loosing team for more then 2 times in a row. Let's be realistic.. no one likes to be in loosing team forever. This way newbies don't get slaughtered all the maps and after every 2 maps they can be put with winning players.

We are not including here deaths.. cos for me.. K/D can be useless .. Ex: If a player Y kills 10 players and dies 2 time in 15 mins map..and if Player Z kills 30 players and dies 24 times...I would prefer player Z in my team rather then player Y ... cos player Z has more kills. Skills matter on 1 vs 1 game or scrims but on public servers.. I need someone who can kill more players in my team so engineers can do obj.. or let's say who is more active on field rather then camping..

And then auto lock of teams for next 1/4th time of map so players can fuck up shuffle which they normally do after auto shuffle ...and go back to winning team and make things more worse again.

#13
OFFLINE   gaoesa

gaoesa

    Advanced Member

  • Management
  • PipPipPipPip
  • 4391 posts
341
Will become famous
  • LocationFinland
I often see players defend certain objects by taking positions where they complement each other. Also, saving themselves from unexpected enemies when low on clip it is handy to have a teammate around that can give cover. Sure I have also seen lot of 1on1 and indeed they are a part of the game and have always been. Also, in recent years I have come across a lot on players who won't shoot the opponent because it was "1on1" or even complain on the frag steals when killing their opponents. I wouldn't have thought the 1on1 is a major part of the game though. Certainly it has a relation to how good players are, like I said, it is aiming and strafing. Aiming is important part of the game. 1on1 may even give better factor then pure accuracy taken that it includes the strafe. I admit I don't have statistics for my argument. It was just what I thought.

What I was thinking is making a new system that would include the kills, but also would give the value for the kills based on how involved the player is the different objectives in the map i.e. taking damage based on assumption that when doing something important the opponents will try to kill you. Certainly it couldn't be perfect either because some roles may reward players with less kills but can still have significant importance for the objectives. I would include the plain K/D in scores to satisfy the players who want to play only for kills.

Then it checks the win probability... aka if player A has won last 2 map and player B has won 1 map... then we move Player A to last loosing team and player B to winning team...


I like the idea on mixing the winners but this might turn into swap teams quite easily. What I understood was that players are first sorted based on kills. Then paired against the closest enemy. After that, the one of the 2 that has won most maps in a row is placed on the previous maps losing team. And the player with less wins is placed on the previous winning team.

#14
OFFLINE   SunLight

SunLight

    Newbie

  • Members
  • Pip
  • 6 posts
0
Unknown
I agree with you that skills are not just fighting skills, the problem is that teamplay is harder if not impossible to calculate, and when people complain about unbalanced teams they generally mean being outaimed by their opponents.

The only way to take teamplay into account would be to check who wins the map. But when it comes to 'winning a map', what does that mean? In my opinion you win when you had 50% chance to lose, all else being equal. Otherwise it shouldn't even be called a win. And that happens only when a map is played twice. All the public severs where I played for objectives had stopwatch mode on.
Without stopwatch you could win a map only because it's easy, how can you *not* win, for example, maps like Adlernest or Frostbite, even if teams are even?

For shuffles, the scores of last map (or maybe 2) would be easier than KR since, as it has been pointed out already, that rating is too 'slow' to change, while data from the previous map are more up to date. (I would take damage, kills are more or less the same, but damage has more 'samples' and it is not influenced by crossfire, since you can't 'steal' damage)
The only problem is if a client connects or disconnects.

(of course having a working 'rating' can give a goal to players, and make them join the server again to see if they can improve their score)

#15
OFFLINE   gaoesa

gaoesa

    Advanced Member

  • Management
  • PipPipPipPip
  • 4391 posts
341
Will become famous
  • LocationFinland

The only way to take teamplay into account would be to check who wins the map. But when it comes to 'winning a map', what does that mean? In my opinion you win when you had 50% chance to lose, all else being equal. Otherwise it shouldn't even be called a win. And that happens only when a map is played twice. All the public severs where I played for objectives had stopwatch mode on.
Without stopwatch you could win a map only because it's easy, how can you *not* win, for example, maps like Adlernest or Frostbite, even if teams are even?


Yes. That is why it is better to have the defending team being stronger. It gives more chances for uncomfortable games. When it has the correct proportions regarding the map, the mentality and the current level the players achieve. I.e., I don't think it is possible to achieve near perfect teams without the players themselves being active in it.

The only problem is if a client connects or disconnects.


This can be sorted out.

(of course having a working 'rating' can give a goal to players, and make them join the server again to see if they can improve their score)


One of my back thoughts. I don't think when players keep looking and impoving the current KR they are necessarily good for the game as it is. The kills are inherent and most important part of the game, but I think if they are rewarded with rating when they are actually important is closer to the real kill effectiveness. Then again, what is an unimportant kill. Damage sounds good measurement how effectively the player is inflicting injuries to the enemy. Added with receiving damage, not only 1on1 but overall, may indicate harder circumstances. Think about a player killing the group medic so the others would not get revived anymore and the group is easier to stop. It may well include getting damage from everyone else but not from the medic itself. Still the kill may have a big importance and it is harder to achieve then backshooting.

#16
OFFLINE   dempa

dempa

    Newbie

  • Members
  • Pip
  • 6 posts
1
A step in the right direction

hrm how about implementing kills and wins based shuffle based on past 2 games?

First their would be shuffle based on kills.

i.e.
Player A (30 kills) vs Player B (28 kills)
Player C (26 Kills) vs Player D (27 kills)

Then it checks the win probability... aka if player A has won last 2 map and player B has won 1 map... then we move Player A to last loosing team and player B to winning team...

This way every 2 maps their can be auto shuffle.. and after each auto shuffle.. it makes sure that player doesn't end up in loosing team for more then 2 times in a row. Let's be realistic.. no one likes to be in loosing team forever. This way newbies don't get slaughtered all the maps and after every 2 maps they can be put with winning players.

We are not including here deaths.. cos for me.. K/D can be useless .. Ex: If a player Y kills 10 players and dies 2 time in 15 mins map..and if Player Z kills 30 players and dies 24 times...I would prefer player Z in my team rather then player Y ... cos player Z has more kills. Skills matter on 1 vs 1 game or scrims but on public servers.. I need someone who can kill more players in my team so engineers can do obj.. or let's say who is more active on field rather then camping..

And then auto lock of teams for next 1/4th time of map so players can fuck up shuffle which they normally do after auto shuffle ...and go back to winning team and make things more worse again.


It's a good idea, but too much variability. The method I suggests takes into account the fact that some players do slay omnibots at night. Your method would rank those players far greater than someone with more skill but less kills, as his last two maps may have been against actual players.

#17
OFFLINE   dempa

dempa

    Newbie

  • Members
  • Pip
  • 6 posts
1
A step in the right direction

ABBA is better all the times when there is an even number of players, but if the number is odd ABAB is better in most cases (not all, it's like 97%)

an example with 15 players (I multiplied all ratings by 100):

set of 15 ratings:
[47, 70, 100, 108, 148, 182, 210, 221, 245, 251, 269, 298, 334, 383, 386]

ABAB
team1 [386, 334, 269, 245, 210, 148, 100, 47]
team2 [383, 298, 251, 221, 182, 108, 70]
total average: 216, axis: 217, allies: 216, diff:1

ABBA
team1 [386, 298, 269, 221, 210, 108, 100]
team2 [383, 334, 251, 245, 182, 148, 70, 47]
total average: 216, axis: 227, allies: 207, diff:19

You also assumed K/D is a measure of player skill, according to what I've seen it doesn't always work properly.

It was supposed to be a sort of ELO but if it hasn't been changed from when I saw it, I think it's a very dubious algorithm. It doesn't take many factors into account (weapons for example, I think old etpub took that into account, then you have backshooting, crossfire, etc.etc.) and once you have a low rating it's very hard to improve it even if you play better, while people who get high scores in lame ways don't go down...


You can only compare averages if each team has the same number of players. If they don't, you compare sums:

ABAB
1: 1739
2: 1513
diff: 226

ABBA
1: 1592
2: 1660
diff: 68

Substantially more fair.

With ABAB, the team with 'A' will always have a greater sum than B. With ABBA, it is completely variable. I'm not sure if it would be difficult to implement, but you could always compare sums, and set the higher summed team to be axis.

#18
OFFLINE   dempa

dempa

    Newbie

  • Members
  • Pip
  • 6 posts
1
A step in the right direction
I found out something interesting regarding the algorithm. However if you are as intelligent as you say you are hell, you should be able to notice it as well.

Edited by dempa, 06 April 2012 - 10:30 PM.


#19
OFFLINE   gaoesa

gaoesa

    Advanced Member

  • Management
  • PipPipPipPip
  • 4391 posts
341
Will become famous
  • LocationFinland
So helpfull from you dempa! Please keep the trolling out from this forum. Yes I have seen your trolls at the FA forum. If you could have taken a little moment to think, we could have instructed you to do your own changes against ETPub. We could have then reviewed them and seen if they are any worth. Even give the possibility to join our team if you had shown us that you can do good additions without messing up the code. However, even if you would have the skills, which I doubt based on the crap you talk so much, you have no such chance anymore because of your personality.

#20
OFFLINE   dempa

dempa

    Newbie

  • Members
  • Pip
  • 6 posts
1
A step in the right direction

So helpfull from you dempa! Please keep the trolling out from this forum. Yes I have seen your trolls at the FA forum. If you could have taken a little moment to think, we could have instructed you to do your own changes against ETPub. We could have then reviewed them and seen if they are any worth. Even give the possibility to join our team if you had shown us that you can do good additions without messing up the code. However, even if you would have the skills, which I doubt based on the crap you talk so much, you have no such chance anymore because of your personality.


How am I trolling this forum? I haven't said a single thing in this thread that I would classify as a troll post, I've only written valuable information.

I only trolled the F|A forums after they decided to openly make fun of me rather than listen to my suggestion. If they cannot take me seriously, I cannot possibly take them seriously.

Edited by dempa, 07 November 2012 - 10:52 PM.





0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users