Saturday, July 22, 2006

LF2, Ladders, and Logarithms

(Don't worry about LF2.5 - I'm still working on it ... and I'll release it in three days!!)

I've decided to help Mgccl, a fellow LF2 modder, build an online ladder system for LF2.

The ladder should have the following features:

  • Track and store the results of all ranked games. (No idea how we'll do this - for now we'll do it on an honor system, where players submit their game results.)
  • Keep track of each players' wins, ties, and draws.
  • Calculate each player's rating, using a variant of the ELO system.
  • Support clans and countries, and rank them as well as ranking individual users.
  • Support all possible team combinations, from 1-vs-1 to 2-vs-5 to 4-vs-4.
  • Track which character each player uses, and rank them on each player (i.e. best Davis players, best Julian players, etc.)
Today, the first thing we did was come up with a database. Here's what we have right now (courtesy of myself and Mgccl):

country:
country_id , country_name , country_flag , country_wins , country_total_elo, country_total_exp

clan:
clan_id , clan_name , clan_leader , clan_wins , clan_losses , clan_draws , clan_ranking, clan_total_elo, clan_total_exp, clan_members

user_stat:
stat_id, stat_elo, stat_exp, stat_rank, stat_win, stat_lose, stat_draw

user_prof:
user_id, clan_id, country_id

team_user_link:
team_id, user_id

vs_games:
game_id , team1_id , team1_winrounds, team2_winrounds

Mgccl also singlehandedly coded the ELO script (this guy's amazing at PHP!) Now we are missing one crucial feature - ranking for team games. Since I'm good at math, it falls to me to solve the following problems:
  1. I must find a way to average the team members' ratings to create a team rating. A simple arithmetic mean won't work - a team with one member rated 1500 and one member rated 1000 does not have a 1250 rating!

  2. Figuring out 1) will let us play 2-vs-2, 3-vs-3, and 4-vs-4 games, but what if we want to play a game with unequal teams? I must calculate how to adjust the temporary team ratings, to account for the fact that teams with more players have a much better chance of winning.

  3. Once I find 1) and 2), I am able to use Mgccl's ELO algorithm to find how to adjust each team's rating, but wait! Teams aren't rated - only players are! I must figure out how to apply the rating adjustment to the team members. As far as I see, the answer to this is to simply take the team adjustment and adjust each team member's rating by it, but I'll have to do some more research on this.

Some data to help me: The ELO system is designed so that if two players (or teams) have a rating difference of 200, then the stronger team should have a 75% chance of winning. I think that if I take a few logarithms, I should be able to figure out the answer to 1) and maybe 2) from that statement.

Whew. Long, very long, incredibly long, post.

12 comments:

Alex said...

I think I may have an answer for 1).

First I examined a case for a two-person team. If their ratings were, say, 1000 and 1200, then the 1200 player would have a 75% chance to win in a game between them, so it would make sense to put the average team rating around 1150.

For teams with more than 2 players, the same method can be applied, if you compare each player to the lowest-ranked player (using Mgccl's formula, the same way I demonstrated above), and then averaging. For example, for a team with 1000, 1200, and 1400 players, the average team rating would be about (1150 + 1363)/2 = 1257.

Mgccl, I hope you read this!

Anonymous said...

I don't believe the answer is 1150.
Team 1: 1000 and 1200.
Team 2: X and X.
To make the teams fair each player should have the same proportion of beating the other player. For example:
1000/x=x/1200. So x=1095.445

Alex said...

I am forced to admit defeat, Jagger.

Looks like you're right.

Just one question though - how would you apply this method for teams with more than 2 players?

Sinow said...

The skill of a two person team also depends on their experience together. A fighter who is a master at 1v1 fighting could be defeated by 2 fighters who might not be as good as him 1v1, but together they could defeat him. Perhaps it would be a good idea to include two separate rating for each player, a team rating and a solo rating. Of course, the team rating could become distorted itself. If an experience player on the same team as a low ranking player, the low ranking player might not contribute that much to the fight, but they could still win. In such a case, less points could be added to the weaker player for playing on the same team as the experienced player. This would encourage people to team up with others who share a common ranking. Of course this would probably require much more work...

And ultimately, i think that unless you guys are thinking about making this ranking compatible with Chiko's LF3 when it comes out, there's no real point in considering team cases. It just doesn't happen often enough. That's just my opinion.

Alex said...

I got it! It's just the geometric mean x=(p1*p2*p3*...*pn)^(1/n).

Following this, a 1000-1200-1400 team would have a rating of (1000*1200*1400)^(1/3) = 1188.78 .

=)

Problem 1) solved!

Alex said...

In response to Sinow's comment, yes, a team and solo ranking would be a good idea. I'll have to consult Mgccl on this...

Alex said...

For 2) i suppose I could use an ELO formula, but I'll need to know the odds for, say, a 2-on-3 game.

Alex said...

Here's something I came up for 2). There's no way to find out the actual formula, but I think I did pretty good:

If k players play n players of equal skill and n>k, the k players have only a (k/n)^4 chance of winning.

Exa,a[;es"

2-on-3 = 19.75% chance the 2 players will win
1-on-7 = 0.04% chance the 1 player will win

Alex said...

OK, I got a result for 1) and 2), and promptly submitted it to Mgccl. Here it is:


A team k (players k1,k2,...,kn) plays against a team m.

If team k has as many or less players than team m, then R_k = (k1 * k2 * ... * kn) ^ (1/n) .

If team k has more players than team m, then R_k = (k1 * k2 * ... * kn) ^ (1/n) + 400 log ((m^4-k^4)/k^4) .



Example

k {1000, 1500}
m {500, 700, 1200}

R_k = 1224.74
R_m = 748.887 + 243.517 = 992.405

Team k has a 79.2072% chance of winning.
Team m has a 20.7928% chance of winning.


Now we just have to covert my formulas to PHP and we're done!

Pepino said...

is there a chance to get the PHP-script for the ELO-ranking?

Alex said...

Sure, Pepino:

The web interface is located at http://www.nisnevich.com/alex/chessclub/calculator/calculator.php

If you want the PHP script itself, email me at alex.nisnevich@gmail.com

Alex said...

hmm that web link seems to be cut off. if you can't see it, it's:

http://www.nisnevich.com/alex/chessclub
/calculator/calculator.php