Elo estimation using quasi-Monte Carlo integration

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Branko Radovanovic
Posts: 58
Joined: Sat Sep 13, 2014 2:12 pm

Elo estimation using quasi-Monte Carlo integration

Post by Branko Radovanovic » Tue Sep 30, 2014 7:18 pm

Hello everyone,

I've written an informal paper titled "Elo estimation using quasi-Monte Carlo integration". Here is the introduction section:
First, an introduction. In June 2014 there was a mild controversy about Stockish 5 entering the IPON rating list at #2, as scored by Bayeselo, behind Houdini 4. On the other hand, Ordo and Elostat put SF at #1. There was a Talkchess thread named “Empirically 1 win + 1 loss ~ 2 draws” that discussed the finer points of Elo estimation. Which program had it right?

I've always thought none of the above mentioned Elo estimation programs were entirely correct (to be fair, their authors themselves never claimed otherwise), and I've found their approach a bit "dirty" in some respects (granted, the problem seems to be notoriously hard to solve in a "clean" way). In particular, I was quite certain that 1 win + 1 loss is not equal to 2 draws, except perhaps as a rough approximation. So, the event inspired me to try and devise an algorithm which could yield more correct estimates. By August, I had the answer…

In chess, Elo estimation is the problem of determining the relative ratings of players given their respective performances in an n-player tournament. In a two-player match, given its final score, an exact Elo estimate can be obtained by integration over all possible prior probabilities of winning, drawing and losing. Of course, there are two degrees of freedom here - once e.g. pw and pl (prior probabilities of winning and losing) are fixed, pd must be equal to 1-pw-pl, so a double integral suffices. For tournaments with more than two players, the problem is much more difficult. One of the reasons is dimensionality, which is equal to N + M, where N is the number of players in a tournament, while M is the number of matches (pairings) between these players. Since these integrals do not have a closed form, even for comparably small tournaments numerical integration becomes impossible. Monte Carlo integration - or quasi-Monte Carlo integration (QMCI) - offers a way to work around the infamous "curse of dimensionality".

The basic properties of the QMCI algorithm are the following:
  • The algorithm relies on an assumption that prior probabilities of winning, losing and drawing a game between any two players are uniformly distributed.

    Hence, prior expected score (s = pw+pd/2) of any given player against the other has a triangular distribution.

    For all participants, QMCI calculates the expected Elo, the sampling error, as well as the 95% credible interval.

    The QMCI algorithm relies on a large number of (quasi-)randomly generated samples to calculate the expected Elo. Sampling error can be made smaller by increasing the number of iterations.

    The calculation takes roughly on the order of minutes, even for rather simple examples.

    While MC is necessarily a probabilistic technique, QMC uses quasi-random sequences, not actual random numbers, so Elo estimates are exactly reproducible over repeated runs, and depend only on the number of iterations.

    There are no pre-set "draw rates", "draw models", or any kind of special-case draw treatment. The prior probability of drawing is uniform, and is treated in exactly the same way as probability of winning or losing.

    The algorithm ignores color, i.e. the advantage of playing first. I believe enhancing it with "color-awareness" shouldn't be too difficult.

    The maximum problem size (dimensionality) is unfortunately still very limited, so the QMCI algorithm in its present form is far from replacing any of the above mentioned Elo estimation programs.
This document supplies the full working source code and explains the way it works. In the process, I’m going to say a few words about the underlying theory, which may or may not be new, but to my knowledge most of it hasn’t been discussed in online sources. A number of concrete examples are also provided. Interestingly, some results diverge from those of current Elo estimation programs. I'm hoping this document might stimulate some new thinking and better algorithms in the future.
The entire document can be found here: https://docs.google.com/document/d/11-J ... sp=sharing. I'd like to hear your comments or questions...

Adam Hair
Posts: 3201
Joined: Wed May 06, 2009 8:31 pm
Location: Fuquay-Varina, North Carolina

Re: Elo estimation using quasi-Monte Carlo integration

Post by Adam Hair » Wed Oct 01, 2014 4:31 pm

Hi Branko!

I just wanted to let you know that I am interested in your paper. But I need to read over it again before I can make any intelligent reponse to it, and I have not found the time to do that yet.

Adam

User avatar
Ajedrecista
Posts: 1396
Joined: Wed Jul 13, 2011 7:04 pm
Location: Madrid, Spain.
Contact:

Re: Elo estimation using quasi-Monte Carlo integration.

Post by Ajedrecista » Thu Oct 02, 2014 12:27 pm

Hello Branko:

Very interesting. I only tried the example for two players, just to get sure I understood your notes. In your R script of page 5, where you write:

Code: Select all

prob <- pw^w*pl^l*pd^d
Did you intentionally remove (w + l + d)!/(w! · l! · d!) of the trinomial distribution because you later use divisions and this term will simplify because it is a constant (with fixed {w, l, d})? If that, I think it would be good that you explain it somewhere (for example saying that you get the same result but it speeds up the calculations). I say this because I did not find such an explanation, but I could be wrong, of course.

I wrote QMCI_2_players in Fortran 95, which is a more suited language than R for numerical computations (hence the big speed-up you claim with the use of C or C++). I used what you call method 1 because it looks very simple to me. The speed gain is huge, as you will see in this case of wins = 3, loses = 0 and draws = 7 (page 10 of your paper, version 1.0.0). Here are my results after 1e+8 iterations:

Code: Select all

Wins&#58;      3
Loses&#58;     0
Draws&#58;     7

1.00E+08 iterations&#58;

----------------------------------------------------

 eloprobsum/probsum               83.957406433183899
 score&#40;eloprobsum/probsum&#41;       0.61852627122243926

 elodiff&#40;sprobsum/probsum&#41;        81.644896085814932
 sprobsum/probsum                0.61538039581851035

 losprobsum/probsum              0.93749657785690944

----------------------------------------------------

Elapsed time&#58;   104.21 seconds.
Our results are very similar, as expected (I obtained ~ 0.08 Elo more than you, while our LOS estimates start to differ in the fouth decimal (curiously, this time your LOS is greater than mine).

My computer is an Intel Pentium D930 (two cores) of year 2006, with 2 GB of RAM and 3 GHz of clock speed... I mean, it is not a monster other than a dinosaur; I use Windows XP 32-bit and this compile (13 KB of size) is single threaded and 32-bit. Since I used your work and I do not know too much about GNU GPL v3 license, I think the easiest thing is paste my code:

Code: Select all

! Comments start with an exclamation mark.
! Original source&#58;
! https&#58;//docs.google.com/document/d/11-JVdKEsQdjWzMUUFQwnGYzg-Z2iaJxO4MwzfN93yIk/edit?pli=1
! © Branko Radovanovi&#263;, 2014.

program QMCI_2_players

implicit none

integer&#40;KIND=4&#41;, parameter &#58;&#58; iter = 1e8  ! 100 million of iterations.
integer&#40;KIND=4&#41; &#58;&#58; i
real&#40;KIND=3&#41; &#58;&#58; s, elo, w, l, d, pw, pl, pd, prob, probsum, eloprobsum, sprobsum, losprobsum, t0, t1

w = 3d0; l = 0d0 ; d = 7d0

! Values of wins, loses, draws and iterations are coded into the source.
! These values could be input by hand or read from a Notepad or other file.

write&#40;*,'&#40;A,I5&#41;') 'Wins&#58;  ', int&#40;w&#41;
write&#40;*,'&#40;A,I5&#41;') 'Loses&#58; ', int&#40;l&#41;
write&#40;*,'&#40;A,I5&#41;') 'Draws&#58; ', int&#40;d&#41;
write&#40;*,*)
write&#40;*,'&#40;ES8.2,A&#41;') 1d0*iter, ' iterations&#58;'
write&#40;*,*)
write&#40;*,'&#40;A&#41;') '----------------------------------------------------'
write&#40;*,*)

t0 = cpu_clock@()

probsum = 0d0; eloprobsum = 0d0 ; sprobsum = 0d0 ; losprobsum = 0d0  ! Initialization of the values.

do i=1,iter
  pw = random@(); pl = random@()
  if &#40;pw + pl >= 1d0&#41; then
    pw = 1d0 - pw; pl = 1d0 - pl
  end if
  pd = 1d0 - pw - pl
  s = pw + 5d-1*pd
  elo = 4d2*log10&#40;s/&#40;1d0 - s&#41;)
  prob = &#40;pw**w&#41;*&#40;pl**l&#41;*&#40;pd**d&#41;
  ! Doesn't it include the factorials of the trinomial distribution
  ! because it is a constant and it will simplify in the divisions?
  eloprobsum = eloprobsum + elo*prob
  sprobsum = sprobsum + s*prob
  probsum = probsum + prob
  if &#40;s > 5d-1&#41; then
    losprobsum = losprobsum + prob
  end if
end do

write&#40;*,*) 'eloprobsum/probsum          ',eloprobsum/probsum
write&#40;*,*) 'score&#40;eloprobsum/probsum&#41;   ',1d0/&#40;1d0 + 1d1**(-2.5d-3*eloprobsum/probsum&#41;)
write&#40;*,*)
write&#40;*,*) 'elodiff&#40;sprobsum/probsum&#41;   ',4d2*log10&#40;&#40;sprobsum/probsum&#41;/&#40;1d0 - sprobsum/probsum&#41;)
write&#40;*,*) 'sprobsum/probsum            ',sprobsum/probsum
write&#40;*,*)
write&#40;*,*) 'losprobsum/probsum          ',losprobsum/probsum
write&#40;*,*)
write&#40;*,'&#40;A&#41;') '----------------------------------------------------'

t1=cpu_clock@()

write&#40;*,*)
write&#40;*,'&#40;A,F8.2,A&#41;') 'Elapsed time&#58; ', &#40;t1 - t0&#41;/3d9,' seconds.'  ! My PC clock speed is 3 GHz.

end program QMCI_2_players
I encourage you to upgrade your script to C/C++. You will notice a great difference. ;)

I do not have time (and neither skills, surely) to give a try to your generalization of a N-player tournament. Anyway: good luck!

Regards from Spain.

Ajedrecista.

Branko Radovanovic
Posts: 58
Joined: Sat Sep 13, 2014 2:12 pm

Re: Elo estimation using quasi-Monte Carlo integration.

Post by Branko Radovanovic » Sun Oct 05, 2014 7:42 pm

Ajedrecista wrote:Hello Branko:

Very interesting. I only tried the example for two players, just to get sure I understood your notes. In your R script of page 5, where you write:

Code: Select all

prob <- pw^w*pl^l*pd^d
Did you intentionally remove (w + l + d)!/(w! · l! · d!) of the trinomial distribution because you later use divisions and this term will simplify because it is a constant (with fixed {w, l, d})? If that, I think it would be good that you explain it somewhere (for example saying that you get the same result but it speeds up the calculations). I say this because I did not find such an explanation, but I could be wrong, of course.
Hello Jesús,

Yes, (w + l + d)!/(w! · l! · d!) is essentially a constant, and it "cancels out" given the way expected Elo is calculated, so it's left out. But you're quite right, an explanation might have been helpful.
Ajedrecista wrote: I wrote QMCI_2_players in Fortran 95, which is a more suited language than R for numerical computations (hence the big speed-up you claim with the use of C or C++). I used what you call method 1 because it looks very simple to me. The speed gain is huge, as you will see in this case of wins = 3, loses = 0 and draws = 7 (page 10 of your paper, version 1.0.0). Here are my results after 1e+8 iterations:

Code: Select all

Wins&#58;      3
Loses&#58;     0
Draws&#58;     7

1.00E+08 iterations&#58;

----------------------------------------------------

 eloprobsum/probsum               83.957406433183899
 score&#40;eloprobsum/probsum&#41;       0.61852627122243926

 elodiff&#40;sprobsum/probsum&#41;        81.644896085814932
 sprobsum/probsum                0.61538039581851035

 losprobsum/probsum              0.93749657785690944

----------------------------------------------------

Elapsed time&#58;   104.21 seconds.
That's very interesting - if I'm calculating correctly, that's a 20x speedup! And with e.g. 4 cores running in parallel, that would have been 80x - indeed, close to my estimate of two orders of magnitude in the paper. The n-player version would see the same gain, so this is an important piece of information.

Also, since you're running 100M iterations - as opposed to 1M iterations in the paper - the above figures have to be even closer to the exact ones.

Regards,
Branko

Post Reply