Fast LOS estimation

[lucasart]

I'm currently using Remi's excellent WhoIsBest (http://www.talkchess.com/forum/viewtopi ... 82&t=30624) for quick estimation of LOS. However, it's O(n^2), and when implemented in python, can be a bit slow for large numbers of games.

This is also for self-testing, so a relatively high draw rate. Any suggestions on a faster algorithm? I can't easily plug in bayeselo, or would definitely be using that .

I calculate that in an spreadsheet program (like MS Excel) in O(1) and always get the same results than you (as per posts on github).

If the problem is only with two opponents, it's absolutely trivial: just compute the mean and stdev, and the asymptotic gaussian distribution quantile.

did I miss something ?

[Laskos]

Correction (ans a pretty accurate one):

LOS=0.5*[1+ Erf{0.707*(wins-losses)/sqrt(wins+losses)}]

It works pretty well.

Great, thanks . Yes, I had noticed it was giving results between -1..1 so I had applied the 0.5 * 1 + erf() fix already.

Why 0.707 though? For sqrt(2)/2?

Yes, asymptotically for large number of games it goes as
LOS=0.5*[1+ Erf{(wins-losses)/sqrt(2*(wins+losses))}]

[gladius]

I calculate that in an spreadsheet program (like MS Excel) in O(1) and always get the same results than you (as per posts on github).

If the problem is only with two opponents, it's absolutely trivial: just compute the mean and stdev, and the asymptotic gaussian distribution quantile.

did I miss something ?

No, not missing anything . This is for automated generation of LOS for fairly high numbers of matches. I wanted it to be as fast as possible, as it's used in a web-page context.

[Ajedrecista]

Hello again:

I think you are referring to this calculator that you announced in this thread a while ago. In that web, line 17 is slow to execute when the numbers of wins and loses are large:

Code: Select all

pi[i + 1] = (pi[i + 1] + pi[i]) * 0.5;

In fact, Lucas' method and my own method are identical if I am not wrong (and they are also valid and fast for your request). I have to do strange things in my code because erf function is not implemeted in salflibc.dll, which uses my programme (or at least I do not know how use it).

Very interesting, thanks Jesus. I will definitely take a look at the LOS calculations including draws.

Draws have a very small impact on LOS when the numbers of wins and loses are fixed. For example:

Code: Select all

LOS(+120100      =0 -119900) ~ 65.85%  (0% of draws).
LOS(+120100  =60000 -119900) ~ 65.85% (20% of draws).
LOS(+120100 =160000 -119900) ~ 65.85% (40% of draws).
LOS(+120100 =360000 -119900) ~ 65.85% (60% of draws).
LOS(+120100 =960000 -119900) ~ 65.85% (80% of draws).

I say that draws are included because they appear in the formula I use, but they have very small impact (if any) in LOS with large numbers of wins and loses.

Summarizing, the formula written by Kai is perfect for your proposal:

Code: Select all

LOS = 0.5*(1 + erf{(wins - loses)/sqrt[2*(wins + loses)]})

Regards from Spain.

Ajedrecista.