Bayesian scoring

• US 7,050,868 B1
• Filed: 01/24/2005
• Issued: 05/23/2006
• Est. Priority Date: 01/24/2005
• Status: Active Grant

• 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/041,752
• Time in Patent Office: 484 Days
• Field of Search: 463/42, 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 an outcome of a game between at least a first team opposing a second team, the first team including a plurality of players and the second team including at least one other player;

b) receiving a first score including an individual mean and an individual variance for each of the plurality of players of the first team, each individual mean and variance representing a distribution associated with a respective 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 individual mean and the individual variance for each of the plurality of players of the first team based on the outcome of the game, the outcomes of the game being selected from a set of possible game outcomes including the first team winning, the first team losing, and the first and second teams drawing;

e) providing an indication of the undated individual mean and the undated individual variance to at least one of the plurality of players of the first team.

2. The method of claim 1, further comprising updating each individual variance based on a dynamic score function of a period of time since the respective player last played the game.

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

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

5. The method of claim 1, wherein updating an individual mean and a variance of a player of the first team is independent of updates of other players in the first team.

6. 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.

7. The method of claim 1, wherein updating the first individual mean depends on a predetermined latent tie margin defining a difference in scores.

8. The method of claim 1, wherein updating includes modeling a posterior probability of the scores as a truncated rectified Gaussian distribution.

9. The method of claim 1, wherein updating includes estimating a posterior probability of the scores of the first and second teams using expectation propagation.

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

11. The method of claim 10, 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.

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 team, wherein determining the first score and first variance is determined from a plurality of player means and a plurality of player variances, each player mean and player variance being associated with one of a plurality of players of the first team;

b) receiving a second score including a second mean and a second variance representing a distribution associated with a second team;

c) determining an expectation of a gap between the first score and the second score;

d) matching the first team with the second team based on the expectation of a gap; and

e) providing an indication of the match to the first team and/or 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 team and a second score of a second team based on an 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, the first team including a plurality of players, the first score being based at least in part upon a plurality of player means and a plurality of player variances corresponding to the plurality of players;

b) means for updating the first score based on a dynamic score function of a period of time since the first team last played the game;

c) means for matching the first team with a third team based on the first score and a third score of the third team; and

d) means for providing an indication of the match to the first team, the third team, or the first team and third team.

16. The computer readable media of claim 15, wherein the means for matching includes means for determining a probability of an outcome of a game between the first team and the third team.

17. The computer readable media of claim 16, wherein the means for determining a probability of an outcome includes determining a probability of a difference between the first score and the third score.

18. The computer readable media of claim 16, wherein the outcome of the game between the first team and the third team is selected from a set of possible game outcomes including the first team winning, the first team losing, and the first and third teams drawing.