TrueSkill added to Tremstats

[nalf]

 Hi all,

I implemented the TrueSkill algorithm into TremStats. Since the original website seems to be abandoned, I made a fork on github. The working title is TremStats Too 2.

It can compute the skills of the players from the whole game history in the database, so upgrading it on an existing TremStats installation will compute player skills based on all stored games. Upgrading from a 1.9.3 installation is easy.

Suggestions welcome.

  Bye, nalf

[42]

Hmm; this is pretty interesting. I'd like to see an implementation of this, just to see how people would be rated.  How do you determine someone's score?  Points?  Kills? Deaths?

[/dev/humancontroller]

I'd like to see an implementation of this

fork

How do you determine someone's score?

TrueSkill

Suggestions welcome.

TrueSkill is patented, and the name is trademarked, so therefore it is limited to Microsoft projects and commercial projects that obtain a license to use the algorithm.

[nalf]

How do you determine someone's score?

The skill is based only on what games each player won or lost. No kills, no score, etc. The algorithm is quite complicated and to fully understand it, you need to know at least some basics of the probability theory. If you're really interested, see Microsoft's TrueSkill web page where there is a list of publications on the subject.

TrueSkill is patented, and the name is trademarked, so therefore it is limited to Microsoft projects and commercial projects that obtain a license to use the algorithm.

Yes, this can be a complication. I don't know the exact legal terms, but I think there is a difference between using someone's program and reimplementing a published idea from scratch. Also Microsoft's answers in TrueSkill FAQ in a similar tone:

Q: I am a software developer and am eager to develop a small application that mimics your TrueSkill Rank Calculator. Would it possible for you to provide me with an implementation of that application (since it was meant for research purposes, I do not see the harm) or at least pseudocode for its implementation?

A: We do not intend to make available the source code of the TrueSkill Rank Calculator in the near future. Of course, we would like to encourage you to pursue research in the subject area so here is a list of pointers that might be of help (this list will be regularly updated if new material can be released):

• Detailed description of TrueSkill
• Blog entry with F# sample code

I used such a reimplementation someone created on github. So I believe the only major problem is that I cannot use the name TrueSkill (which I will correct).

[Undeference]

It looks like the claimed patent for TrueSkill is US patent number 2007/0026934, though there are other Microsoft patents that explicitly refer to TrueSkill and may cover aspects of the currently described methods of determining TrueSkill on Microsoft's website. (Also, uspto.gov is worthless.)

Isn't it awfully nice of Microsoft to describe a scoring system and encourage people to use it, all the while failing to mention that they patented it? Here, have some candy. You'll pay for it later.

Edit: technically, purely mathematical formulae (like a scoring system) are not patentable. Tell that to the US courts.

[nalf]

Edit: technically, purely mathematical formulae (like a scoring system) are not patentable. Tell that to the US courts.

Yes, AFAIK ideas are not patentable, only their implementations. But as you say, it very much depends on the view of a court. I suppose the problem is that since judges lack any knowledge of programming, mathematics, etc., they can hardly distinguish what is an idea and what is an implementation.

Anyhow, I sent an email to Microsoft asking for a clarification of this issue, so let's see what (if) they respond...

Edit: Suppose I'd create a new, even more advanced scoring system, that would build on the results in Microsoft's papers on TrueSkill, and publish it as a new scientific result. Could Microsoft make any claims?

[Undeference]

Yes, AFAIK ideas are not patentable, only not their implementations.

FTFY. (You are confusing copyrights and patents, which are very different things.)

Edit: Suppose I'd create a new, even more advanced scoring system, that would build on the results in Microsoft's papers on TrueSkill, and publish it as a new scientific result.

You can describe a patented method (or a method based on a patented method, which would therefore be covered by the first patent) all you want, but as soon as you implement it without a license, that is infringement.

[nalf]

Yes, AFAIK ideas are not patentable, only not their implementations.

FTFY. (You are confusing copyrights and patents, which are very different things.)

Are you sure that ideas are patentable?

In modern usage, the term patent usually refers to the right granted to anyone who invents any new, useful, and non-obvious process, machine, article of manufacture, or composition of matter.

I thought that it must be a well described process, not just an idea.

Edit: Suppose I'd create a new, even more advanced scoring system, that would build on the results in Microsoft's papers on TrueSkill, and publish it as a new scientific result.

You can describe a patented method (or a method based on a patented method, which would therefore be covered by the first patent) all you want, but as soon as you implement it without a license, that is infringement.

Let me give an example: Suppose a standard lightbulb is patented and its concepts known and published. Someone invents a halogen lightbulb, which is something very different, but still based on the original concept. In this case, is selling a halogen lightbulb an infringement?

[42]

What I was asking about the ranking is this: since I may be a very good player, but have a bunch of n00bs on my team, I score every single kill, and almost kill off the other team, when one of the n00bs decons the base.  Should I be punished for that loss?  That's why I was asking about wins/losses.  

And by implementation, I meant that I'd like to see it used on the trem servers. 

[Undeference]

This is getting quite off-topic, but I'll bite…

Are you sure that ideas are patentable?

In modern usage, the term patent usually refers to the right granted to anyone who invents any new, useful, and non-obvious process, machine, article of manufacture, or composition of matter.

I thought that it must be a well described process, not just an idea.

What is an idea? An idea can be as specific or generic as it happens to be (i.e., there is no specificity requirement for an idea, nor is the specificity of an idea even quantifiable). See http://en.wikipedia.org/wiki/Patentability for actual requirements of a patent. Anything sufficiently technical is likely non-obvious to patent examiners so will be granted, and it is expensive to invalidate a patent so there are a lot of patents that should not be valid that are.

Let me give an example: Suppose a standard lightbulb is patented and its concepts known and published. Someone invents a halogen lightbulb, which is something very different, but still based on the original concept. In this case, is selling a halogen lightbulb an infringement?

If the hypothetical patent covered a device capable of emitting radiation when an electrical current is applied (there are a lot of patents like that), then that patent would cover any type of electrical lamp or radio, among other things. If, however, the patent covered a device containing a thin carbon filament in a vacuum that, when an electrical current is applied, gets hot and emits radiation in the range of visible light, then a halogen lamp would clearly not be covered.

[nalf]

This is getting quite off-topic, but I'll bite…

True, thanks for valuable comments.

[nalf]

What I was asking about the ranking is this: since I may be a very good player, but have a bunch of n00bs on my team, I score every single kill, and almost kill off the other team, when one of the n00bs decons the base.  Should I be punished for that loss?  That's why I was asking about wins/losses.  

That can happen, and there is not much that could be done to prevent that. The only solution I can think of is a good player etiquette, so that if a team gets deconed, the both teams agree on a draw. (As far as I've seen it usually works the opposite - the other team rushes instantly to take an advantage the deconed team.)

Each game alters the computed skills only a little bit. So if this happens to you once in several dozens of games, the effect on your score will be probably negligible. The score change depends on several factors, including:

• The overall skill of the teams. If your teams is significantly worse than the other, loosing is an expected result and your score will be decreased only very slightly. But if you loose against a team that is expected to be worse than yours, your score will be decreased more.
• The number of players in the teams. The more players, the more games it takes to determine their skills. So if you loose in a game 1vs1, your score is decreased much more than if you loose in a game 10vs10.

There is another way how a scoring system can help. One could run several "league" servers - each accepting only players with a certain minimal skill. A player that has invested many hours to improving his/her skill would not risk deconing and getting banned. Also, such a setup would lead to more interesting games (since in each "league" players would have roughly similar skills). But I suppose now there are to few Tremulous players for that.

And by implementation, I meant that I'd like to see it used on the trem servers. 

Me too. That is a question for server administrators, if they're willing to install/upgrade TremStats.

[42]

What I was asking about the ranking is this: since I may be a very good player, but have a bunch of n00bs on my team, I score every single kill, and almost kill off the other team, when one of the n00bs decons the base.  Should I be punished for that loss?  That's why I was asking about wins/losses. 

That can happen, and there is not much that could be done to prevent that. The only solution I can think of is a good player etiquette, so that if a team gets deconed, the both teams agree on a draw. (As far as I've seen it usually works the opposite - the other team rushes instantly to take an advantage the deconed team.)

Each game alters the computed skills only a little bit. So if this happens to you once in several dozens of games, the effect on your score will be probably negligible. The score change depends on several factors, including:

• The overall skill of the teams. If your teams is significantly worse than the other, loosing is an expected result and your score will be decreased only very slightly. But if you loose against a team that is expected to be worse than yours, your score will be decreased more.
• The number of players in the teams. The more players, the more games it takes to determine their skills. So if you loose in a game 1vs1, your score is decreased much more than if you loose in a game 10vs10.

There is another way how a scoring system can help. One could run several "league" servers - each accepting only players with a certain minimal skill. A player that has invested many hours to improving his/her skill would not risk deconing and getting banned. Also, such a setup would lead to more interesting games (since in each "league" players would have roughly similar skills). But I suppose now there are to few Tremulous players for that.

And by implementation, I meant that I'd like to see it used on the trem servers. 

Me too. That is a question for server administrators, if they're willing to install/upgrade TremStats.

What if you modified the algorithm so that the outputted score was based on their score in the game, as well as their time (which is already in the algorithm).  In tremulous, score is a much more meaningful indicator than whether you won or lost.  For example, i that game, the n00bs would probably have a score of around 30, and maybe I'd have 400 or so.  It's fairly easy to see that I was much better than them, and that if, say, the opposing team had 4 players each with 90 or so points, our team had an even greater combined score. 

[nalf]

...
In tremulous, score is a much more meaningful indicator than whether you won or lost.  For example, i that game, the n00bs would probably have a score of around 30, and maybe I'd have 400 or so.  It's fairly easy to see that I was much better than them, and that if, say, the opposing team had 4 players each with 90 or so points, our team had an even greater combined score. 

That is just what skill computations try to avoid. Any scoring method such as the one built in Tremulous is arbitrary. Why are score rewards for killing players, buildings, or for building, set just as they are? There is no precise way how to decide.

Let's say two players work in team. The one specializes on killing players from the opposing team, the other specializes on killing buildings. With the current scoring method, the second would be given much higher score. Does that mean that the second is better than the first?

So the skill computation method I used avoids this. Instead, it only reflects on whether you participated in a winning or loosing game. IMHO that is much better, because it correctly reflects your real contribution to the team, not some arbitrary score. The only disadvantage compared to scoring is that it takes several (or up to several dozens) games to approximate the skills.

[42]

...
In tremulous, score is a much more meaningful indicator than whether you won or lost.  For example, i that game, the n00bs would probably have a score of around 30, and maybe I'd have 400 or so.  It's fairly easy to see that I was much better than them, and that if, say, the opposing team had 4 players each with 90 or so points, our team had an even greater combined score. 

That is just what skill computations try to avoid. Any scoring method such as the one built in Tremulous is arbitrary. Why are score rewards for killing players, buildings, or for building, set just as they are? There is no precise way how to decide.

Let's say two players work in team. The one specializes on killing players from the opposing team, the other specializes on killing buildings. With the current scoring method, the second would be given much higher score. Does that mean that the second is better than the first?

So the skill computation method I used avoids this. Instead, it only reflects on whether you participated in a winning or loosing game. IMHO that is much better, because it correctly reflects your real contribution to the team, not some arbitrary score. The only disadvantage compared to scoring is that it takes several (or up to several dozens) games to approximate the skills.

I camp in the base the entire game.  I get the full advantages that those who did the actual killing did.  Fair?  No.

What if you adjusted it so that points are awarded based on range of points.  If you score higher than the mean score/time ratio (of all playing), then you have a win recorded.  If you score lower, a loss.  This would be much more fair, especially in a game where the losers may perform at the same or better level as the other team.  You should also keep separate scores for humans and aliens.  I know that I am better at humans than at aliens; a low score for aliens should nor effect my score for humans. 

[nalf]

I camp in the base the entire game.  I get the full advantages that those who did the actual killing did.  Fair?  No.

You're viewing the problem from the point of view of a single game. This is not correct. Skill systems are based on statistical calculations covering many games. If you are a bad player and you don't help your team, you can win sometimes, when you're playing with a good team, but you'll also loose when your other teammates aren't so good. Statistically, you'll do much worse than somebody who is always a key player of his/her team.

Also, as I said, if you're playing with a team that has good skills then your team is expected to win. And so if you win, the skill algorithm raises your skill value only very little.

What if you adjusted it so that points are awarded based on range of points.  If you score higher than the mean score/time ratio (of all playing), then you have a win recorded.  If you score lower, a loss.  This would be much more fair, especially in a game where the losers may perform at the same or better level as the other team.  You should also keep separate scores for humans and aliens.  I know that I am better at humans than at aliens; a low score for aliens should nor effect my score for humans. 

For the reasons I've said before, I'm not inclined to use any such scoring system. I don't deny that it has some value and I don't mind if somebody else uses it, but I want to do something different. Something that _is_ based just on the wins/defeats. IMHO in long term, that is the most (and only) fair method.

You're not addressing the problem how much score is awarded for each action. For example, is destroying a telenode worth 10 frags? Or 100 frags? And why? What is the single correct reward and how to determine it? Before solving this, it has no meaning to talk about mean score/time ratio. A different rewards settings would result in somebody else being the winner or looser, no matter what you do with the score then.

Let me give another example why I think that a skill computation should be based only on wins/defeats: Imagine a player who is not especially good at killing or destroying buildings. But who is really good at organizing his team. He has a charisma, can motivate people to cooperate, can spot weaknesses of the enemy, is good at explaining to newbies how to help their team. A natural leader. Such a person wouldn't get a high score with any scoring system you're advocating. It is something that can hardly be measured in the game. But such a person would be the single most important factor of the team's success!

[42]

I have absolutely no idea how scoring works, but I know that it's balanced, because of the time that it's been in use.  It works, however, and is a good mark of skill.  For example, I have played 72:39-4:28=68:11 minutes, and have a score of 11,872.  That means that, on average, I score 11872/4359=2.72 points per minute.  *<{Merry Christmas, a much better player than me, has played for 838:59-267:34=571:25 minutes, and has a score of 692,681.  This gives him an average score of 692681/34285=20.20 points per minute.  It is very easy to tell that he is much better than me.  (More interesting would be to see what someone's points/minute score for aliens and humans would be). 

[Asvarox]

Actually most of the "better" players will tell you that score system needs vast refining at the least. I consider myself as a decent player, but there are many with skill-level around mine and yet their score is much lower. I see regular players with score much beyond their skill because they whored points on unpowered buildings. And these aren't single-games situations, but actually quite common.

Score is certainly better than just "frags", but it doesn't mean it's good.

[ULTRA Random ViruS]

I have absolutely no idea how scoring works, but I know that it's balanced, because of the time that it's been in use.  It works, however, and is a good mark of skill.  For example, I have played 72:39-4:28=68:11 minutes, and have a score of 11,872.  That means that, on average, I score 11872/4359=2.72 points per minute.  *<{Merry Christmas, a much better player than me, has played for 838:59-267:34=571:25 minutes, and has a score of 692,681.  This gives him an average score of 692681/34285=20.20 points per minute.  It is very easy to tell that he is much better than me.  (More interesting would be to see what someone's points/minute score for aliens and humans would be). 

I wouldn't say so that he's that 'skilled'. He could be just the type who pouncewhores to get his evos when hes low and simply destroys the enemy structure before others could.
The gpp scoring system i find quite dodgy, i mean, lets say i am the only one that has less than one kill every minute. And also lets say i fed the usual, but worse. Lets say 2 feeds/minute. 1kill/10 minutes. But then i decide to kill 5 tubes without aliens paying attention. I go to the top of the ladder after gaining 80 odd points points.
I think points gained per structure kill should be halved at least.
Yes, i say that killing a few structures is worth than doing nothing at all, but killing a few simple structures like tubes from one grenade equalling to about 20 odd kills is unbalanced.
Right now i think conversion rate is about 2x build points used to build it, and for killing, weakest class 4 points and strongest class 16 points. (probably related to evos earned*4?)

Score is certainly better than just "frags", but it doesn't mean it's good.

[RAKninja-Decepticon]

I have absolutely no idea how scoring works, but I know that it's balanced, because of the time that it's been in use.  It works, however, and is a good mark of skill.  For example, I have played 72:39-4:28=68:11 minutes, and have a score of 11,872.  That means that, on average, I score 11872/4359=2.72 points per minute.  *<{Merry Christmas, a much better player than me, has played for 838:59-267:34=571:25 minutes, and has a score of 692,681.  This gives him an average score of 692681/34285=20.20 points per minute.  It is very easy to tell that he is much better than me.  (More interesting would be to see what someone's points/minute score for aliens and humans would be). 

I wouldn't say so that he's that 'skilled'. He could be just the type who pouncewhores to get his evos when hes low and simply destroys the enemy structure before others could.

in other words, s/he is a better player and more skilled.

[42]

This reminds me:

If you look at the win/loss graphs, you'll notice that aliens win more often, on most of the maps.  So if I play more human than alien, I may get a worse ranking than a player with similar skill who plays alien.