Bayesian scoring

• US 7,376,474 B2
• Filed: 02/16/2006
• Issued: 05/20/2008
• Est. Priority Date: 01/24/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Herbrich, Ralf, Graepel, Thore K H
• Primary Examiner(s): Coburn; Corbett B.
• Application Number:
  US11/276,184
• Publication Number:
  US 20060178765A1
• Time in Patent Office: 824 Days
• Field of Search: 700 91- 93
• US Class Current: 700/93
• CPC Class Codes: A63B 71/06 Indicating or scoring devices for games or players , or for other sports activities
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G09B 7/02 of the type wherein the student is expected to construct an answer to the question which is presented or wherein the machine gives an answer to the question presented by a student

Abstract

Players in a gaming environment, particularly, electronic on-line gaming environments, may be scored relative to each other or to a predetermined scoring system. The scoring of each player may be based on the outcomes of games between players who compete against each other in one or more teams of one or more players. Each player'"'"'s score may be represented as a distribution over potential scores which may indicate a confidence level in the distribution representing the player'"'"'s score. The score distribution for each player may be modeled with a Gaussian distribution and may be determined through a Bayesian inference algorithm. The scoring may be used to track a player'"'"'s progress and/or standing within the gaming environment, used in a leaderboard indication of rank, and/or may be used to match players with each other in a future game.

Claims

1. A method comprising:

a) receiving a draw outcome of a game between at least a first team opposing a second team, the first team including at least one player and the second team including at least one other player;

b) receiving a first score including a first mean and a first variance representing a distribution associated with the at least one player of the first team;

c) receiving a second score including a second mean and a second variance representing a distribution associated with the at least one other player of the second team;

d) updating the first mean and the first variance based on the draw outcome of the game;

e) updating the first mean and the first variance of the first score due to changed abilities of the at least one player of the first team based on a dynamic score function of a period of time since the first team last played the game; and

f) providing an indication of the updated first mean and the updated first variance to the at least one player of the first team.

2. The method of claim 1, wherein the dynamic score function is a constant value for periods of time greater than zero.

3. The method of claim 2, wherein updating the first variance based on a dynamic score function includes summing the first variance with a square of the constant value.

4. The method of claim 1, wherein receiving an outcome includes receiving an outcome of the game between the first team, the second team, and a third team.

5. The method of claim 1, wherein updating the first mean based on the draw outcome of the game depends on a predetermined latent tie margin defining a difference in scores.

6. The method of claim 1, wherein updating based on the draw outcome of the game includes modeling a posterior probability of the scores as a truncated rectified Gaussian distribution.

7. The method of claim 1, wherein updating based on the draw outcome of the game includes estimating a posterior probability of the scores of the first and second teams using expectation propagation.

8. The method of claim 1, further comprising determining a score estimate of the at least one player of the first team based on a difference between the updated first mean based on the draw outcome of the game and a conservative level indicator multiplied by a square root of the updated first variance based on the draw outcome of the game.

9. The method of claim 8, further comprising comparing the score estimate of the at least one player of the first team with a score estimate of another player, and ranking the at least one player of the first team and the another player based on the respective score estimate.

10. The method of claim 1, wherein updating the first mean and the first variance based on the draw outcome of the game includes decreasing the first variance to indicate an increase in a confidence level of the first variance.

11. The method of claim 1, further comprising determining a first conservative score estimate based on a difference between the first mean and a level of conservatism parameter multiplied by the first variance, and ranking the first player in a leaderboard based on the conservative score estimate.

12. One or more computer readable media containing computer executable instructions that, when implemented, perform a method comprising:

a) determining a first score including a first mean and a first variance representing a distribution associated with a first player of a first team;

b) determining a second score including a second mean and a second variance representing a distribution associated with a second player of a second team, wherein the first score and the second score are updated based on a draw outcome of a game between the first team and the second team;

c) determining an expectation value of a gap between the first score and the second score based on the first mean, the first variance, the second mean, and the second variance;

d) matching the first team with the second team based on a comparison of the expectation value with a predetermined threshold, wherein the predetermined threshold is based on the number of players available for matching; and

e) providing an indication of the match to at least one of the first team and the second team.

13. The computer readable media of claim 12, wherein determining the expectation of a gap includes evaluating

$2$

σ

ij 2 ⁢

⁢

N ⁢

⁢

( μ

ij ;

0 , σ

ij 2 ) + μ

ij ⁡

( 2 ⁢

Φ

⁡

( μ

ij σ

ij ) - 1 ) ,

where μ

_ij is the difference in the means of the teams (i.e., μ

_ij=μ

_i−

μ

_j) and where σ

_ij² is the sum of the variances of the teams i and j (i.e., σ

_ij²=σ

_j²+σ

_j²).

14. The computer readable media of claim 12, wherein determining the expectation of a gap includes summing the first variance, the second variance, and a square of a difference between the first mean and the second mean.

15. One or more computer readable media containing computer executable components comprising:

a) means for updating a first score of a first player of a first team and a second score of a second player of a second team based on a draw outcome of a game between the first team and the second team, wherein each of the first score and the second score is modeled as a distribution; and

b) means for updating a first mean and a first variance of the first score due to changed abilities of the first player of the first team based on a dynamic score function of a period of time since the first player last played the game.

16. The computer readable media of claim 15, further comprising means for updating a third score of a third player of the first team, the third score being modeled as a distribution.

17. The computer readable media of claim 15, further comprising means for updating a fourth score of a fourth player of a third team a win outcome of the game, the fourth score being modeled as a distribution, the game being between the first team, the second team, and the third team, and the win outcome indicating the third team winning over both the first team and the second team.

18. The computer readable media of claim 15, further comprising means for ranking the first player and the second player based on the first score and the second score.