From: t68@nikhefh.nikhef.nl (Jos Vermaseren)
Newsgroups: rec.games.go
Subject: Re: ratings algorithm
Date: 30 Sep 92 14:51:20 GMT
Organization: Nikhef-H, Amsterdam (the Netherlands).

In article <1992Sep29.190411.9149@dvnspc1.Dev.Unisys.COM>, mdobbins@dvnspc1.Dev.Unisys.COM (Michael Dobbins) writes:
> In article <wekpniO00Woh54aEN_@andrew.cmu.edu> wjh+@andrew.cmu.edu (Fred Hansen) writes:
> >Paul Matthews describes below a statistically sound rating method that 
> >he claims a competent numerical programmer who knows elementary 
> >probability and statistics could implement in a weekend.  (I'm neither a 

Actually thie algorithm is rather old and is the one I was referring to
in an earlier posting. When properly set up it can even give error estimates.
A good probability function turns out to be

P(x) = (1/2)*(2/3)^(2*x)
in which x is the difference in numbers of dans or kyu's (positive)
and P(x) the chance that the weaker player wins.
For some ununderstood reason this distribution is amaizingly good, even
at large distances. Good is in the sense that when it was used to rate
a few hundred people in european tournaments the measured strength versus
the observed strength was statistically in good agreement. In principle there
could have been any other number instead of 2/3 and the relation would not
have been nearly as good.
The distribution has other good properties. It guarantees a single maximum
in the propability distribution. This is not necessarily the case for
any P(x)!

> 
> For usage in the IGS we should be able to pull out a table of values
> from Paul's system (say averages over the past year of rated games) and
> create a very simple non-iterative algorithm for modifying rankings
> based on the results of each game. The winner's rank would increase
> some fraction of a rank and the loser's rank would decrease some
> fraction. I believe the AGA ran this type of ratings system for years
> (previous to Paul's contribution).  Given the interactive nature of the
> IGS, it does not make sense to do any heavy number crunching to
> calculate ranks when a simpler, though less accurate mechanism would
> suffice.  The simpler algorithm would be adequate for sorting
> individuals into a reasonable skill hierarchy.  Nothing better is
> needed.
>
The trick is to run the full program itteratively till the changes are
less than 0.01 dan or something small. That fixes all differences, and
leavs as only free parameter the absolute normalization. This can be fixed
in several ways.  One way is to assume that the average of the strongest
players does not change very much. A more sophisticated scheme involves
promotions. If someone becomes stronger his old games should carry less weight
or be totally forgotten because they will mess up the system. The trick is to
move the old games to a non active entry. The strength of that person is
known at the time he gets promoted, so do as if this is the entry of
someone who died and a new n+1 dan is born. Obviously dead people don't
change strength any longer, so this strength is fixed and not a 
variable in the variational scheme any longer.
This leaves only one serious problem:
If there are people that only loose games one cannot measure their strength
and the variational scheme does not converge. This is also the case for
a subgroup of people who have only victories or only losses to people
outside the group. This can be artificially solved by giving everyone
some wins and/or some losses against 30Kyu and/or 10 dan. At least the
system converges. At this point one may need some manual interference.

Calculation probabilities allows also to compute the halfheight of the
peak, which gives an error estimate. To get this down to less than a 
dangrade requires already quite a number of games. A good promotion
scheme is to make sure that someones ranking is within the error bars.
If you are measured to be  2.6 +- 1.2 dan and officially you were 1 dan
you merit promotion to 2 dan. NOT to 3 dan, even though 3 dan is closer
to the center. The old entry is locked then to the 'dead' person with
a strength of 2.6 and a new entry is started. Eventually everything
will be very stable. Demotions should work the same way, but due to
the built in conservatism they will rarely be necessary.
 
> As far as the higher level question of should the IGS use the results
> of game to rank people, I would have no objection to it doing it all of
> the time as long as the individuals have the choice of selecting
> handicap values different from what the relative rankings would
> indicate.  
> 
This remains a good problem. Especially when one considers that people 
have a tendency to play with to low a handicap.

> The IGS is for fun and we should not get caught up in worrying about
> our rankings on it (that is what sanctioned tournaments are for.)  If
> you just play for fun and don't "try your hardest to win" then the IGS
> ranking will tend to move to that level and people will know that is
> the level you tend to play at on the IGS.  That should in no way be
> interpreted as how well you play in tournaments or what your real
> ranking is. I think it would be fun to see statistics on people.  
>
In that case the IGS would measure your 'fun' ranking. Which would be 
relevant if you are playing for fun.

> Along those lines, maybe we should allow people to adjust their ranking
> up if they think that they under-rated.  
>
Most (well many) people believe they are underrated. There are very many 
imaginary shodans.

Of course we don't need police enforced rankings. That would ridiculous.
But we like to have proper matchups. It is maybe fun for a 3 kyu to play 
at two stones against a 3 dan, because the 3 kyu thinks himself a 
shodan, but for the 3 dan this is no fun. Ronald Schlemper would always 
be very good at pointing this out the obnoxious way, by saying it would 
spoil his style. But there is a very large core of truth in it. It tends 
to make the stronger player sloppy, and eventually he may not want to 
play such games anymore. Hence proper handicap, based on past 
performance is not a bad thing, even though some people are so ambitious 
that they refuse to play when they think they have had a bad night and 
the ranking computer is running. Don't think of it. Just have fun and 
let the ranking computer 'run in the background'. It is just there to 
guarantee interesting games. And of course, if both players agree to a 
different handicap, who is going to stop them?

Cheers
Jos Vermaseren