Starcraft Ranking

Charles is testing a ranking system for Starcraft that he hopes will later get implemented in some large hall Battle.net server or somesuch.

Individuals

Each player is represented by a pair of numbers (a, t) corresponding to the player's individual playing strength and his teamwork capabilities respectively. If a player is alone on his side, then his team strength evaluates to his individual strength.

By Our Powers Combined

Suppose, then, that there are at least two people on a team. The strength of that team is then as follows:

Let each player P_i = (a_i, t_i). Let S = sum(a_i). Then the strength of the team is

S * product(t_i^(a_i/S))

Informally, the team strength is the additively combined individual strengths of the players, multiplied by a coefficient determined by their teamwork capabilities. The coefficient is a weighted geometric average, where the weighted assigned to each player is the fraction of the total team individual strength that he constitutes.

For example, suppose I have four people on a team, with profiles (3, 1), (3, 2), (1, 3), (2, 1) (The 1,2 player might represent someone who isn't that great a player, but is very supportive of his team. For example, a Terran player who just pumps out medics to accompany his ally's Zealots, and comsats on command.) Then their strength is

(3 + 3 + 1 + 2) * (1^(3/9)) * (2^(3/9)) * (3^(1/9)) * (1^(2/9)) = 12.812

Balancing Act

The Algorithm also accounts for team balance when one team has more players than the other. If one team has more players, then in that team we duplicate the individually strongest unduplicated player before calculating strengths. For example, in a match A+B+C vs. D+E+F+G+H, we perform the strongest-player-duplication twice, so the calculations done are actually for A+B+C vs. D+E+F+G+H+D+E.

Implementation

The Scheme implementation of the algorithm simply stores data about players, and the searches through all subsets of matches amongst a roster of players, and spits out the subset where subset vs. subset-complement results in the smallest strength difference.

The implementation uses the measure that a strength difference of 1 indicates that the stronger team will consistently win iterations of the same match.

Experience

The algorithm's data about players stays up to date by increasing the ratings of players on the winning side of a game, if that side were not already expected to win. To do this, it calculates a δ and an ε so that the teams (a_i + δ, t_i) and (a_i, t_i + ε) are both about 1 above the losing team. Then it gives each player (pδ, (1-p)ε), where p is the human-evaluated percentage of success that was a result of the player's own power, as opposed to synergy with his teammates.

One issue with this is that player ratings always go up, and never down, so while the strengths of players among themselves should remain consistent, the size of the numbers used in the ratings may eventually get meaninglessly big, and the definite-win radius of 1 may have to be reevaluated.

Download

You can try the Scheme implementation for yourself once I finish documenting the damn thing and upload it to the wiki.