Accounts e-mail HP

Rank the Folk

It's 5am again and you are still sitting in front of your computer and chatting with some tv's while watching a bloody duel? Welcome friend :)

Rank the Folk

Postby Davide » Thu Aug 16, 2012 12:55 am

:arrow: About introducing a players rank list that will be displayed on the forum and automatically updated after each match.

What data is available at the end of each game to update the rank position of the players:
  • List of all players participating to the game; total number of humans and AIs
  • Player score of the ended game
  • Player state of victorious or loser
  • Player's previous position in rank, and any eventually associated data (score)

A chess-like or Elo ranking system can't be applied as these consider the outcome of a player's game to be in one of only three possible states: victory, loss, draw.

Ideas on ranking algorithm and its presentation page layout are well welcomed.
User avatar
Davide
 
Posts: 864
Joined: Sat Mar 24, 2012 12:34 am

Re: Rank the Folk

Postby Julien » Thu Aug 16, 2012 6:57 pm

So, as I told you in the chat I think we can easily adapt the ELO system.
You can found here the mathematical explanation of this system : http://fr.wikipedia.org/wiki/Classement_Elo (this time I found the french page to be clearer on the mathematical principles). In a nutshell the ELO system is :
  • A kind of first-order differential equation, which should converge to some point if we always play against the same opponent (we cannot claim that it converges when we play with different opponent, except if we restrict the set of opponents to a very special class)
  • A model in which some function of the probabilities can be factorized as a ratio of functions that only depends on the skill of one of two opponents (this is not something that can be proven, it is actually an arbitrary model very far from reality, since in reality we cannot associate the players with a complete order relation satistfying basic properties)
So we see there is not a lot of theoretical stuff, that's mainly arbitrary stuff we can change.
So the master equation is Image and we just have to choose a scoring system for W and a p(D) model. And if we want to complicate, the K could be caracteristic of the importance of the game, for instance bigger for games with lots of players.

So what to choose as W and p(D) ?
The simplest would actually be to simply keep the system of chess, only keeping the victorious/loser status and dropping the rank and score information.
On the contrary here's a way to keep the score (then I drop the victorious/loser info, but we can keep it with a linear combination or for instance mapping the winners to [0.5,1] and the losers to [0,0.5]) : mapping the scores to the [0,1] intervall through an affine transformation (or something more complicated if it is needed for more numerical stability). For instance if one player has 1000 points, another 700, and the last 500, the first has W=1 (he totally wins), the last has W=0 (he totally loose), and the second has W=(700-500)/(1000-500)=0.4 (a kind of slightly-losing draw). And we can keep p(D) to the same function since all of its shape is arbitrary except some basic properties such as p(0)=0.5 and p(inf)=1

Actually maybe an important feature of the ELO system is that the sum of the ELO points of the two opponents is conserved in a match : Its variation is K*(W-p(D))+K*(W'-p(-D)) = K*(1-p(D)-p(-D)) = 0
This ensures that the system doesn't converge to a trivial point (except if we have on open system, with a steady input of new noobs). So if we want to keep this interesting property we have to ensure that the W of all players sum to 1.
Therefore I have to drop my suggestion of mapping the scores to [0,1], we should instead map on [0,a] where a is chosen so that all the W sum to 1. For instance in my former exemple 1000/700/500 we now have a/0.4a/0 where 1.4a=1, so the W are finally 0.71/0.29/0
Julien
 

Re: Rank the Folk

Postby Davide » Thu Aug 16, 2012 9:16 pm

I'm taking the time to understand in-deepth the Elo and evaluate how it could be adapted to Freeciv and if it would be applicable and eventually with what corrections. I should reply within two days.
User avatar
Davide
 
Posts: 864
Joined: Sat Mar 24, 2012 12:34 am

Musings

Postby Davide » Sat Aug 18, 2012 5:23 pm

I've considered the Elo but still I think it's not suitable as-is for Freeciv, exclusively because we don't play 1 vs 1 and a ranker can't keep track of fortunate multi-user interaction during game.
However the rank I have outlined in mind is similar. Basically it increases and reduces scores linearly upon how a player performs during game, and not by the match outcome; it's a relative ranking, probably tuned on the mean points of all the ranked players rather than on the scarcest player, to preserve scores stability. The range is linear and starts from 1 up to 1,000.

A draft of how the rank page could appear:

1 :ugeek: Me
2 :geek: You
3   :x   She

4   8-)   Antonio
5   8-)   Alejandro
6   :cry:   Lolly
User avatar
Davide
 
Posts: 864
Joined: Sat Mar 24, 2012 12:34 am

Re: Rank the Folk

Postby Keysersoze » Sat Aug 18, 2012 8:36 pm

Davide
I think that ELO can be adapted to freeciv.
All you have to do is to take the game final standings and analyze it by taking two players each time.
This way, a game with 4 players (A,B,C,D) would require 6 matchings: A vs. B; A vs. C; A vs. D; B vs. C; B vs. D; and C vs. D.
The fact that a draw isn't a possible outcome in freeciv doesn't invalidate the system for the other possible outcomes.
BTW, in fact, a draw is possible in freeciv.
I don't think that the final points of the score of the game should have any role in the formula to calculate the ranking.
So, it would be indifferent if A wins B by 1 point or by 100 points in the game; what counts is relative position: 1st, 2nd, 3rd...
Taken two-by-two, the performance of the players can be compared by their relative position in final standings.
KS.
Keysersoze
 

Re: Rank the Folk

Postby Davide » Sun Aug 26, 2012 1:19 am

I matured some really interesting ideas about the ranking algorithm and their web presentation.
But I realized there are other serious to moderate problems to be solved before implementing the ranking. I need to step back on these to maintain an image of efficiency in front of all the work i'm doing. For example, you can look at this. I hope you understand.
User avatar
Davide
 
Posts: 864
Joined: Sat Mar 24, 2012 12:34 am

Re: Rank the Folk

Postby Kryon » Sun Jan 06, 2013 1:18 pm

Davide,

I think it is not only easier but also better to assign rank points according to win/lose instead of in-game scores. The reason is an alliance of players work together to beat other alliances. A nation can have very low in-game score but could have contributed a lot to his alliance (for example by being the small researcher nation). Or a nation could be at the front lines and bear the most of the enemy alliance attacks protecting his allies but weaken or even die during the process. In the ranking system we use in LT games, the winners of a game all earn equal points and losers lose equal points. However, the points earnt/lost increases when a) there are less winners and more losers b) the losers are stronger. It is an elegant system. You can find the explanation of the exact algorithm used here: http://longturn.org/ranking/ (Note: Marduk designed the system and I wrote the MATLAB code to implement it automatically).
Kryon
 


Return to Community

Who is online

Users browsing this forum: No registered users and 1 guest

cron