Determining Relative Skills of Players

• US 20090227313A1
• Filed: 01/16/2007
• Published: 09/10/2009
• Est. Priority Date: 02/10/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Graepel, Thore Kh, Herbrich, Ralf, Minka, Thomas
• Granted Patent: US 8,538,910 B2
• Time in Patent Office: Days
• US Class Current: 463/14
• CPC Class Codes: A63B 71/0616 Means for conducting or scheduling competition, league, tournaments or rankings
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling

Abstract

There is a desire to provide a way to determine relative skills of players of games such as computer games, chess, tennis and any other suitable type of game. Our earlier Bayesian Scoring system is implemented in Xbox Live (trade mark) and is currently commercially available under the trade name TrueSkill (trade mark). Here we build on our earlier work and use a new method of computation to enable processing times to be significantly reduced. Message passing techniques are adapted to enable computation of updated skill beliefs to be obtained quickly even in the case of multiple teams of multiple players.

Claims

1. A method of determining an indication of the relative skill of at least a first player and a second player of a game based on the outcome of one or more such games involving those players said method comprising the steps of:

(i) for each player, accessing statistics describing a probability distribution associated with belief about skill of that player;

(ii) receiving information about the outcome of one of the games;

(iii) forming a factor graph comprising nodes, said graph being formed using the received information about the outcome, and instantiating at least some of the nodes with the statistics; and

(iv) updating the statistics associated with each player by using message passing techniques over the factor graph.

2. A method as claimed in claim 1 wherein the statistics comprise at least a mean and a variance describing each probability distribution.

3. A method as claimed in claim 2 wherein the probability distributions are Gaussian.

4. A method as claimed in claim 3 wherein the factor graph is acyclic.

5. A method as claimed in claim 4 wherein the message passing techniques applied over the factor graph are arranged to perform Bayesian inference processes.

6. A method as claimed in claim 5 wherein said factor graph comprises a plurality of groups of nodes, each group being associated with a particular player and comprising nodes linked in series.

7. A method as claimed in claim 5 wherein said factor graph comprises a plurality of second groups of nodes, each second group being associated with a team of players.

8. A method as claimed in claim 6 wherein said groups of nodes are linked with edges such that the order of the linking reflects the outcome of the game.

9. A method as claimed in claim 8 wherein said groups of nodes are also ordered in the factor graph on the basis of teams that the players are in.

10. A method as claimed in claim 9 for determining an indication of the relative skill of players from games involving three or more players.

11. A method as claimed in claim 10 wherein information about the outcome of the game further comprises, for each player, an indication of a length of time that that player participated in the game and wherein the statistics are updated on the basis of that information.

12. A method as claimed in claim 10 wherein information about the outcome of the game comprises a partial ranking of players said partial ranking comprising order information for at least one player as compared to a plurality of other players and no order information among the plurality of said other players, and wherein said factor graph is formed such that a link is created between a node associated with said at least one player and a node associated with each of the said other players.

13. A computer-readable medium containing computer-executable instructions comprising:

for each player, accessing statistics describing a probability distribution associated with belief about skill of that player;

receiving information about the outcome of one of the games;

forming a factor graph comprising nodes, said graph being formed using the received information about the outcome, and instantiating at least some of the nodes with the statistics; and

updating the statistics associated with each player by using message passing techniques over the factor graph.

14. A computer-readable medium as claimed in claim 13 wherein the factor graph is acyclic.

15. An apparatus for determining an indication of the relative skill of at least a first player and a second player of a game based on the outcome of one or more such games involving those players said apparatus comprising:

(i) an input arranged to access, for each player, statistics describing a probability distribution associated with belief about skill of that player;

(ii) an input arranged to receive information about the outcome of one of the games;

(iii) means for forming a factor graph comprising nodes, said graph being formed using the received information about the outcome, said means also being for instantiating at least some of the nodes with the statistics; and

(iv) one or more processors arranged to update the statistics associated with each player by using message passing techniques over the factor graph.

16. An apparatus as claimed in claim 15 wherein the factor graph is acyclic.

17. An apparatus as claimed in claim 15 wherein the message passing techniques applied over the factor graph are arranged to perform Bayesian inference processes.

18. An apparatus as claimed in claim 15 wherein said factor graph comprises a plurality of groups of nodes, each group being associated with a particular player and comprising nodes linked in series.

19. An apparatus as claimed in claim 15 wherein said factor graph comprises a plurality of groups of nodes, each group being associated with a team of players.

20. An apparatus as claimed in claim 18 wherein said groups of nodes are linked with edges such that the resulting order reflects the outcome of the game.