Catch up on stories from the past week (and beyond) at the Slashdot story archive

 


Forgot your password?
Close
typodupeerror
×
XBox (Games) Math

Details on XBox TrueSkill Ranking System 50

Posted by Zonk from the complicated-fun dept.
rupert0 writes "A research paper on the Microsoft website gives an insight into the way that gamers will be ranked on the new-style Xbox Live. The paper outlines some existing ranking systems, as well." From the article: "The TrueSkill(TM) ranking system is a skill-based ranking system designed to overcome the limitations of existing ranking systems, and to ensure that interesting matches can be reliably arranged within a league. It uses a technique called Bayesian inference for ranking players. Rather than assuming a single fixed skill for each player, the system characterises its belief using a bell-curve belief distribution (also referred to as Gaussian) which is uniquely described by its mean (speak [mju:]) ("peak point") and standard deviation (speak [sigma])("spread")."
This discussion has been archived. No new comments can be posted.

Details on XBox TrueSkill Ranking System More

Details on XBox TrueSkill Ranking System

Comments Filter:

  • The bell curve (Score:3, Insightful)

    by TimmyDee ( 713324 ) on Tuesday November 08, 2005 @07:54PM (#13983896) Homepage Journal
    Who would have thought this to be a novel way to rank people's skills?*

    *I do realize that's not the upshot of the paper. Still, I think all this emphasis on Gaussian distributions for dividing people according to "skill" (read IQ, test scores, etc.) is a bit over done. Convenient, but overdone.

  • The proof of the pudding is in the tasting (Score:3, Insightful)

    by LordNimon ( 85072 ) on Tuesday November 08, 2005 @08:03PM (#13983970)
    I'll believe this method works if I can join a Halo 3 game as a level 1 player and not have my ass kicked. As it is today, if a new Halo 2 player joins an online game, he will be destroyed by the other players regardless of what their ranks are.
    • I saw a presentation on this. I can only say that we [excluding griefers] are all going to be much happier when this ranking system is commonplace. In the paper, notice that Alice increased her level by 50% in one game... she won't be staying low level for long.

    • Re:The proof of the pudding is in the tasting (Score:5, Informative)

      by Joe Random ( 777564 ) on Tuesday November 08, 2005 @08:15PM (#13984072)
      I'll believe this method works if I can join a Halo 3 game as a level 1 player and not have my ass kicked.
      It's not possible to guarantee that. Even if the ranking system puts you in a game with other newbie players, it has no idea what any of the players' skill levels are prior to them playing their first match. However, after getting your ass kicked a couple of times, the ranking system should be able to more reliably group you with players of an approximately equal skill level.

      But it is necessary that your very first game is more likely to have some major asskicking, and you may be on the giving end or the receiving end depending on your prior, unrecorded experience.

    • Most importantly... (Score:5, Interesting)

      by game kid ( 805301 ) on Tuesday November 08, 2005 @08:15PM (#13984076) Homepage

      ...one must not be able to rank up [wikipedia.org] with simple tactics.

    • If you don't want your ass handed to you, there are a couple of options:

      #1- buy the game on the release date, and go on Live right away. You will be on an even playing field with the other players. I've done this quite a few times, and many of the best games I've played have been on day 1. Nobody knows the 'secrets' yet. Nobody knows where to hide, or what the shortcuts are (on a racing game) it's fair, and you can learn along with everyone else.

      #2- Play the single-player mode all the way through. DO T
      • #4 - have enough disposable income to verbally threaten the others by saying you'll fly out there to beat the shit out of them if they don't stop spawn camping. :-)

        Most of the time in online games people aren't playing to test other peoples skill and have a challenge. They simply want "more points". If they were in it for the sport they wouldn't stalk players [e.g. repeatedly kill the same guy, go after them when it's illogical [e.g. you're in danger] etc], spawn camp [e.g. hide at their spawn point with
      • So you're saying that the solution to being able to play online when you're not that good is to become good? That's a stupid answer! What if I don't have the time or energy to practice the game that much? What if I'm just not capable of becoming that good, no matter how much I practice?

        The whole point behind the TrueSkill system to is allow to accurately match up people by skill level, and that obviously includes people of low skill. You're so-called "solution" is really just ignoring the problem! No

        • You are expecting to go on-line with no 'skill' at all and still be competitive.

          Buying the game on day 1 does not mean that you have to be good.

          Playing in the morning does not mean that you have to be good.

          (those were two of my three suggestions)

          Playing the game through on single player means you have to have enough skill to get through the single player game, in order to learn the controls and have at least a few hours with the game.

          If you really think that I was saying that the only way to have a good gam

  • It has to be an improvement. (Score:5, Interesting)

    by numbski ( 515011 ) * <[numbski] [at] [hksilver.net]> on Tuesday November 08, 2005 @08:08PM (#13984008) Homepage Journal
    Given that the current system could be described as a "bubble sort".

    That is, the cheaters and glitchers bubble to the top, the people looking for a fair and fun game drop to the bottom and eventually give up and stop playing. :\
  • It uses a technique called Bayesian inference for ranking players.

    The submitter didn't really have to give Bayesian a magical aura...We geeks who remember the first Bayesian spam filters already know it's magical. :)
  • Great. A Microsoft announcment detailing their new development of a "bell curve" according to its "mean" and "standard deviation". Are MS claiming to have invented the Gaussian curve?

    What's next. Embrace, extend and extinguish calculus? I can just hear the boardroom conversation when the mathematicians try to claim precenent.

    Ballmer: "I'm going to f***ing bury that guy, I have done it before, and I will do it again. I'm going to f***ing kill Carl Friedrich Gauss!"

  • A Bayesian slight of hand? (Score:5, Interesting)

    by Anonymous Coward on Tuesday November 08, 2005 @08:59PM (#13984349)
    Let me start this by saying I have no problem with the Bayesian framework... this usually can be a source for a fight in statistics departments ... I've seen a situation where a professor snapped a potential professor hire for his usage of the Bayesian framework in his presentation.

    Typically the Elo system works on a iterative mechanism that updates after a match... that is to say that you have a prior rank, you play your game, and you have a post-match rank (not technical terms mind you) usually its R[player,after]=Rank[player,before]+("speed factor")(Result(0/1) - WinExpectancy(yourrank,theirrank). For Chess the logit function is used with some additional scaling factor (1/(1+exp(-(yours-theirs)/400)).

    This new system is taking advantage of the Bayesian framework, for those not P(A[i]|B)=P(B|A[i])*P(A[i])/sum(P(B|A[j])*P(A[j]), j=1..n)... or in more typical terms of likelihood the posterior density (density shaped by events) is proportional to the likelihood times a "prior" belief, or distribution.

    What's the problem in this... the Elo system can adapt to change in ability of the player over time. A Bayes based system can't. The Bayes estimates converge to what is the true values of the parameters in the model as the number of samples increase to infinity. So an estimate given under frequentist frameworks (MLE, UMVUE, Method of Moments) converge to the same estimate given under Bayes frameworks (mode of the posterior, mean of the posterior). Your estimate can only become more refined with data... if you play enough games, the framework cannot account for any substantial changes in skill. The variance of your stregth or ability rating will decrease. Of course the property of the updating scheme is a nice one to have... I've got to figure there is some usage of approximations... they are very scant in terms of either a prior or a modeled distribution for the event (logit, probit, cloglog, some arbitrary cumulative density function). I'm not going to complain about the normality assumptions in prior or posterior though... I wouldn't know about this situation in particular but the Central Limit Theorem pops up over and over again in statistics (there is a Bayesian CLT but I don't know what that entails). Especially in linear model variants such as this. I see this more as improvement by obfuscation... throw out cute words like "True Skill" and the idea that you have this better system that people will impart its own hopes on it. So, if you want to game the system, just win a lot really early before your variance decreases... looking at the formulae there doesn't seem to be any indication that they are utilizing a conjugate prior (which can help for giving forms for solutions that will not want to eat your pets)... otherwise they'd be staring at a gigantic matrix... and anybody who has dealt with multiple parameters in this situation knows that there will be a correlation structure... which seems to be ignored in the formulae.

    Most approaches I have seen thus far (as a second year grad student) in Bayes methods works away from a nice framework... many sound methods and realistic problems require Markov Chain Monte Carlo or similar techniques (which can be a nightmare in a computation sense)... either you have to have something of an incredibly nice form or you need to make use use of approximations to make a system like this work. I don't see how this will be all that appropriate in online gaming... sports I can see since you aren't taking somebody who mastered squash and putting them right into rugby. (Irrelevant to topic at hand-->) I've always had an interest in methods of ranking players/competitors but mainly from a sports angle. I've got a system drawn up in my head, its a matter of seeing if I can get it to work and then having a few hundred breaks work my way in terms of implementation (again, MCMC is probably the best tool in a lot of cases... but its a computational/time killer). The Bayesian framework is great if you have a good sense of piror belief as it can help guide you to a solution... but it is naturally biased (not necessarily from a point of malice) and at times it is used inappropriately.

    • Re:A Bayesian slight of hand? (Score:5, Informative)

      by Ralf Herbrich ( 929719 ) on Wednesday November 09, 2005 @05:49AM (#13987309)
      Thanks a lot for your comments; you certainly understood the math behind TrueSkill(TM) really well! But there are a few details (that we did not want to bore people with on our web pages) which address all your concerns:

      • The first problem you point out is that Bayesian estimates (in general) asymptotically converge to the maximum likelihood estimates and, hence, in the TrueSkill sytem the sigma's would eventually go to zero and not allow for adaptation in the change of the player's "true" skill. This is true for stationary models but not for models with dynamics (think of a Kalman filter, for example). In fact, in the TrueSkill system we have a dynamics factor in our model equation that says that the skill of every gamer can slightly go up or down (zero mean, small variance) between two consecutive games. If you want to see this at work, please go to http://www.research.microsoft.com/mlp/trueskill/Ra nkCalculator.aspx [microsoft.com] and put every gamer's Sigma at 0.5; then press Recalculate Skill Level Distribution and you will see that the Sigma's after the game are slighly bigger (they should be 0.504). We have worked out the asymptotic value of the uncertainity, sigma, theoretically and compared our solution to empirical findings on 3 million games; our asymptotic limit was close up to 3 digits of precision. This limit is reasonably large to allow constant adaptation for skill changes.
      • The second problem you point out is that of a conjugate prior. Unfortunately, there is no conjugate prior for the probit likelihood in any representation. The approximation method we are using is called "Expectation Propagation" (see http://research.microsoft.com/~minka/papers/ep/roa dmap.html [microsoft.com]) or belief propagation in factor graphs. This IS an "incredibly nice" algorithm, to say it in your words :)
      • The third problem you point out is that the whole correlation structure would be gigantic and you are absolutely right when considering that there are millions of people on Xbox Live so this matrix would be couple of million rows times couple of million columns. However, we only save the diagonal of the matrix, that is, the uncertainity in the skill of every gamer. Please note, though, that we do build up the whole correlation structure (temporarily) for all gamers within a game (to make the approximation of the update step as exact as possible).

      Best wishes,
      Ralf Herbrich & Thore Graepel, Microsoft Research Cambridge (UK)

  • I'll know it's working if it ranks me up near the top. Yeah, that'll be what decides it. If gives me any of that "below average" stuff I'll know it's utter crap.

    More seriously, FINALLY, an idea concerning X-Box 360 that I actually like.
  • I believe, unless my statistics course was in vain(highly probable) that the term for mean is mu, not mju.

    yes, I know its a spelling error, look at my name!

    • At one stage of Greek, possibly the stage where Latin borrowed heavily (and added K, X, Y, and Z to its alphabet), the letter upsilon was pronounced somewhere between "oo" [u] and "ee" [i], perhaps like a Japanese unrounded u [M] or a German rounded i spelt ü [y]. In the latter case, the name of the letter mu would be pronounced [my], and "myoo" [mju]/[mjUw] would be a decent English approximation given the homophony of "Führer" and "furor" in English dialects.

      But in modern Greek, words spelle

  • The beauty of the Chess rating system is that the higher the peak on the bell, the more complex your game is. If the peak never rises very high, your game doesn't have a large skill differential, and is probably on par with a 2nd rate Street Fighter 2 clone that is nothing but button mashing. But if your peak goes above and beyond Starcraft or Chess, then your game is epically complex.... Now we'll never be able to compare games together because they'll always use different systems, but if they adopted th

  • huh? (Score:4, Funny)

    by sho222 ( 834270 ) on Tuesday November 08, 2005 @10:41PM (#13984890)
    say what? (speak [english])

  • Bayesian Inferrence (Score:3, Informative)

    by NitsujTPU ( 19263 ) on Wednesday November 09, 2005 @12:40AM (#13985914)
    Bayesian Inferrence refers to a rather large class of algorithms. It would be nice if something were more specific.

    To give a heads up as to what this all is. Bayesian statistics are based on the idea that a probability can be updated based on additional information.

    So, perhaps you have a prior of 0.5. There is a 50/50 chance that whoever you're looking at is better than another player.

    Ok, so, 0.5 is the prior. Or, perhaps he's one 90% of the games played, so 0.9 is the prior. Now, 50% of games against the 2nd ranked person, he won, but only 20% against the third... and so on. That would be one form of bayesian inferrence.

    Other forms? Naive Bayes is a type of, fairly simple machine learning algorithm. There are also graphical models, which are rather advanced bayesian machine learning models.

  • I think the real question is (Score:3, Interesting)

    by Johnny Mnemonic ( 176043 ) <mdinsmore@NoSPaM.gmail.com> on Wednesday November 09, 2005 @12:58AM (#13986051) Homepage Journal

    Seriously, three Xbox 360 articles on the front page? There's astroturfing, and then there's Slashtroturfing. Give it a rest, guys. I mean, who gives a shit?

    Gaming is an interesting phenomenon, and I follow the market and read Penny-Arcade--but I don't need to see all this advertising for Microsoft's next attempt to win another market.

  • Bayesian inference is typically used when you have a guess about a certain distribution, in this case a player's skill, and you can take observations that give you some information about the true distribution to get a fairly good approximation that converges to the real distribution as the number of samples increases. There are a couple of problems with the framework here. First, it says that it takes 50-100 games to converge to the real value. This becomes problematic when you factor in the fact that ea
  • An idea I had for a ranking system would be to adapt a method used to determine the most influential person in a social network.

    You just put all of the records of how many times each player has killed every other player in a big matrix and compute the eigenvector with the largest positive real eigenvalue. The larger a player's entry is in this eigenvector, the more skilled they are. This method takes into consideration both how many people a player has killed and how many kills those people have and how man

  • WoW ranks (Score:2, Interesting)

    by smallguy78 ( 775828 )
    Possibly the worst ranking system I've seen is the World of Warcraft PVP ranking system. It basically rewards how often you play the game rather than the system which I'm use to in FPS - kills:death ratio.

    The system has 14 ranks, which get progressively harder as you get higher up. The amount of damage you deal to a person decides how much 'honor' you get. Your honor is added up and your rank improves each week.

    Now the problem with this is obviously the more you play, the more honor you get (much like XP).

    I
    • MMORPGs aren't set up to reward skill, they are designed to reward time spent, and little else. Not knocking WoW, I love it, but I can only shrug at the time requirements for the best equipment and higher PVP ranks. I just have to accept I won't ever be able to compete at that level.
    • An MMORPG with a monthly subscription that only rewards time spent? What a surprise!

  • Next Up: XBox Live BCS Edition (Score:3, Funny)

    by hal2814 ( 725639 ) on Wednesday November 09, 2005 @09:35AM (#13988183)
    This is all looking pretty complicated. It's interesting what all has to go on the try to keep players playing similarly skilled players. So I guess the next step is to have two human polls and a computer ranking system. Of course, they would only really be shooting to pit #1 against #2 and then just make as much money as possible of the rest of us. And don't even think about a playoff to determine the best players.
  • I don't know about the rest of you, but I get an uneasy feeling when companies start trademarking truth.

Slashdot Top Deals

Say "twenty-three-skiddoo" to logout.

Close