three or more players ranks probability

sublee / trueskill

An implementation of the TrueSkill rating system for Python

https://trueskill.org/

Other

742 stars 112 forks source link

three or more players ranks probability #35

Open dotcom opened 5 years ago

dotcom commented 5 years ago

I think, if I want to calculate the win percentage for two players, I should calculate the difference distribution. X - Y ~ N(μ1 - μ2, σ12 + σ22) I think that it is sufficient to definitely integrate N in the interval of 0 or more.

But, if game is contained three or more players, how should I predict the ranking probability?

a = Rating(mu= m_a, sigma= s_a)
b = Rating(mu= m_b, sigma= s_b)
c = Rating(mu= m_c, sigma= s_c)

# I want to calculate the probability that rank c > b > a.

sublee commented 5 years ago

Simply isn't it P(c>b) * P(b>a)?

dotcom commented 5 years ago

In general, P(c>b>a) = P(b>a|c>b)P(c>b) ≠ P(c>b)P(b>a) Because "simply P(b>a)" differs from "P(b>a) with b that satisfies c>b" .

P(c>b>a) can be evaluated using the multivariate normal cumulative distribution function X = C - B Y = B - A We want P(X>0, Y>0). However, computing multivariate normal cumulative distribution function is so difficult.

4 variables example: P(d>b>c>a) = P(d>b|b>c,c>a)P(b>c|c>a)P(c>a)

ok, I will make an effort to consider whether it can be implemented and send a pull request, if you hope.

>>> a = Rating()
>>> b = Rating()
>>> c = Rating()
>>> ranks_probability([(a,)(b,),(c,)], ranks=[0,1,2])
0.1210593088888

Probrem

At this time, how to evaluate the team rate is a problem.
and, How should we evaluate the rating of an asymmetric team?
If the number of variables is too large, there is a possibility that the calculation amount will be too high.

sublee commented 5 years ago

Oh, awesome! Thank you for letting me know my mistake.

The function ranks_probability looks good but I don't want to adopt it as a part of this library. There are 2 reasons:

This library is just a transparent implementation of the TrueSkill paper. In my perspective, it should not provide any additional functionality.
As you mentioned, the function is hard to apply every valid conditions in TrueSkill such as 3v2v1 or 1v1v1v1v...v1.

Instead, would you paste the function as code at this issue?

dotcom commented 5 years ago

ok. I agree with the implementation philosophy that this library is a transparent implementation of Trueskill. I will only discuss (or paste function) the implementation here on this matter.

sublee commented 5 years ago

Thanks for your kindness!

lukebyrne commented 4 years ago

@dotcom did you ever get around to a ranks_probability method?