## The SPRT without draw model, elo model or whatever...

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Michel
Posts: 2080
Joined: Sun Sep 28, 2008 11:50 pm

### Re: The SPRT without draw model, elo model or whatever...

Sorry for bumbing this thread but it turned out that things are even much easier than I thought. See this thread http://talkchess.com/forum/viewtopic.php?t=61105 .

Here is very simple python code to implement the SPRT a la cutechess-cli or fishtest

Code: Select all

``````from __future__ import division

import math

bb=math.log&#40;10&#41;/400

def LL&#40;x&#41;&#58;
return 1/&#40;1+math.exp&#40;-bb*x&#41;)

def TrivialLLR&#40;W,D,L,elo0,elo1&#41;&#58;
"""
This function computes the log likelihood ratio of H0&#58;elo=elo1 versus
H1&#58;elo=elo1 under the trinomial &#40;w/d/l&#41; logistic model. W/D/L are
respectively the Win/Draw/Loss count.

For details see

http&#58;//hardy.uhasselt.be/Toga/GSPRT_approximation.pdf
"""
# to avoid division by zero
if W==0 or D==0 or  L==0&#58;
return 0.0
N=W+D+L
w,d,l=W/N,D/N,L/N
s=w+d/2
m2=w+d/4
var=m2-s**2
var_s=var/N
s0=LL&#40;elo0&#41;
s1=LL&#40;elo1&#41;
return &#40;s1-s0&#41;*&#40;2*s-s0-s1&#41;/var_s/2.0

def TrivialSPRT&#40;W,D,L,elo0,elo1,alpha,beta&#41;&#58;
"""
This function should be called after each game until it returns either
'H0' or 'H1' in which case the test stops.

alpha, beta are the type I,II error probabilities. The other parameters
are as in the description of the function TrivialLLR&#40;).
"""
LLR=TrivialLLR&#40;W,D,L,elo0,elo1&#41;
LA=math.log&#40;beta/&#40;1-alpha&#41;)
LB=math.log&#40;&#40;1-beta&#41;/alpha&#41;
if LLR>LB&#58;
return 'H1'
elif LLR<LA&#58;
return 'H0'
else&#58;
return ''``````
Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.

nionita
Posts: 161
Joined: Fri Oct 22, 2010 7:47 pm
Location: Austria

### Re: The SPRT without draw model, elo model or whatever...

Hi Michel,

I don't understand much from those statistic methods, but just looking at your last code there is something strange, maybe there is a typo or maybe you must really explain for some novice like me.

I'm looking at your function TrivialLLR below, and specifically at the comment and conditions that none of L,D,W can be zero:

Code: Select all

``````from __future__ import division

...
def TrivialLLR&#40;W,D,L,elo0,elo1&#41;&#58;
"""
This function computes the log likelihood ratio of H0&#58;elo=elo1 versus
H1&#58;elo=elo1 under the trinomial &#40;w/d/l&#41; logistic model. W/D/L are
respectively the Win/Draw/Loss count.

For details see

http&#58;//hardy.uhasselt.be/Toga/GSPRT_approximation.pdf
"""
# to avoid division by zero
if W==0 or D==0 or  L==0&#58;
return 0.0
N=W+D+L
w,d,l=W/N,D/N,L/N
s=w+d/2
m2=w+d/4
var=m2-s**2
var_s=var/N
s0=LL&#40;elo0&#41;
s1=LL&#40;elo1&#41;
return &#40;s1-s0&#41;*&#40;2*s-s0-s1&#41;/var_s/2.0

``````
You say: "to avoid division by zero", but the condition seems too strong to me, as this would not happen when for example W=1, D=1 and L=0, in which case we get var_s=-1.

On the other side, and this is more important to me, if we have W=0, D=1 and L=1 then we get var_s=0 and then a division by 0 (in the return of the function).

But for my intuition, the 2 cases are symmetric. For an ELO difference model I would not expect to see this different behaviour of the formula with respect to a division by 0.

Michel
Posts: 2080
Joined: Sun Sep 28, 2008 11:50 pm

### Re: The SPRT without draw model, elo model or whatever...

You say: "to avoid division by zero", but the condition seems too strong to me, as this would not happen when for example W=1, D=1 and L=0, in which case we get var_s=-1.

You are right of course . The "correct" condition is that at least two among three of W,D,L are non-zero. However I did not immediately see a compact way to write this in Python so for simplicity I required all three of W,D,L are non-zero.

In practice this makes no difference whatsoever as after a few games the stronger condition will become true. (Recall that the SPRT is made for small elo differences).

One compact way to write the correct condition is W*D+W*L+D*L!=0. This is mathematically pleasing but perhaps not so good from a programmer's standpoint as it involves 3 multiplications.
Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.

Ajedrecista
Posts: 1405
Joined: Wed Jul 13, 2011 7:04 pm
Contact:

### Re: The SPRT without draw model, Elo model or whatever...

Hello Michel:
Michel wrote:One compact way to write the correct condition is W*D+W*L+D*L!=0. This is mathematically pleasing but perhaps not so good from a programmer's standpoint as it involves 3 multiplications.
Karnaugh map gives exactly the same function of W*D + W*L + D*L. I suggest other option without multiplications (at least obvious multiplications) but it can be computionally expensive: what about the condition sign(W) + sign(D) + sign(L) < 2?

In any case: w + d/4 - (w + d/2)² =/= 0.

Code: Select all

``This function computes the log likelihood ratio of H0&#58;elo=elo1 versus H1&#58;elo=elo1 under the trinomial &#40;w/d/l&#41; logistic model.``
Shouldn't H0 and H1 be different? I guess it is a minor typo that does not blur your good work.

Regards from Spain.

Ajedrecista.

Ajedrecista
Posts: 1405
Joined: Wed Jul 13, 2011 7:04 pm
Contact:

### Re: The SPRT without draw model, Elo model or whatever...

Hello again:

I want to add something. From Michel's code:

Code: Select all

``````# to avoid division by zero
if W==0 or D==0 or  L==0&#58;
return 0.0
N=W+D+L
w,d,l=W/N,D/N,L/N
s=w+d/2
m2=w+d/4
var=m2-s**2
var_s=var/N
s0=LL&#40;elo0&#41;
s1=LL&#40;elo1&#41;
return &#40;s1-s0&#41;*&#40;2*s-s0-s1&#41;/var_s/2.0``````

Code: Select all

``````Let's suppose that the initial 'if' statement is not satisfied&#58;
&#40;0 < w < 1&#41; AND &#40;0 < d < 1&#41; AND &#40;0 < l < 1&#41;

m2 = s - d/4
var = m2 - s² = s - d/4 - s² = var&#40;s&#41; = N*var_s

Singular points of var = var&#40;s&#41; = 0
s² - s + d/4 = 0
s = &#91;1 ± sqrt&#40;1 - d&#41;&#93;/2

|s - 1/2| = &#40;1/2&#41;*sqrt&#40;1 - d&#41;
|2s - 1|² = 1 - d``````
What about {w, d, l} combinations that fit in |s - 1/2| = (1/2)*sqrt(1 - d)? Is it possible? No!

Code: Select all

``````d&#40;var = 0&#41; = 1 - |2s - 1|²
&#40;Always&#41;&#58; d_max. = 2*min.&#40;s, 1 - s&#41; = d_max.&#40;s&#41;

Drawing both functions, they only share three &#40;s, d&#41; points&#58; &#40;0, 0&#41;; &#40;1/2, 1&#41;; &#40;1, 0&#41;
These three points imply, respectively&#58; W = D = 0; W = L = 0; D = L = 0
The initial 'if' statement is satisfied in those cases.
In the rest of cases of 0 < s < 1 &#40;except s = 1/2, as seen above&#41;&#58;
d&#40;var = 0&#41; > d_max., which is impossible.``````
Regards from Spain.

Ajedrecista.

Michel
Posts: 2080
Joined: Sun Sep 28, 2008 11:50 pm

### Re: The SPRT without draw model, Elo model or whatever...

sign(W) + sign(D) + sign(L) < 2?
Yes that's nice! I do not really understand your other comment. Are you confirming my (easy) claim that if W<>0 and D<>0 and L<>0 then (empiric) var <> 0 ?

Note that the results about the GSPRT are asymptotic so it does not really matter how the computation is regularized for small N.
This function computes the log likelihood ratio of H0:elo=elo1 versus H1:elo=elo1 under the trinomial (w/d/l) logistic model.
Ah yes sorry for the typo in this comment. I hope it was clear what I meant.
Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.

Ajedrecista
Posts: 1405
Joined: Wed Jul 13, 2011 7:04 pm
Contact:

### Re: The SPRT without draw model, Elo model or whatever...

Hello Michel:
Michel wrote:Are you confirming my (easy) claim that if W<>0 and D<>0 and L<>0 then (empiric) var <> 0 ?
That's it. In fact, I was trying to provide numeric examples of the opposite, negating your claim, but an unexpected problem arose: when I randomly chose a value for score = s and a (draw ratio) = d, then calculating the (win ratio) = w was easy, but I faced the unpleasant situation (lose ratio) = l = 1 - w - d < 0; after two or three trials, I realised that the problem could be an incompatible condition of (s, d), as it was.

The maximum draw ratio [d_max. = 2min.(s, 1 - s)] is a triangular function with three (s, d) vertex in the domain 0 < s < 1: (0, 0); (1/2, 1); (1, 0). OTOH, the condition d(var = 0) = 1 - |2s - 1|² is a parabolic function with its maximum at (s, d) = (1/2, 1) and therefore d(var = 0) > d_max., which is impossible.

Regards from Spain.

Ajedrecista.

Michel
Posts: 2080
Joined: Sun Sep 28, 2008 11:50 pm

### Re: The SPRT without draw model, Elo model or whatever...

Jesus wrote:That's it. In fact, I was trying to provide numeric examples of the opposite, negating your claim,
Ok I see.

Since Var(X)=E((X-EX)^2) it follows that if Var(X)=0 then X=EX with probability one. In other words X must take constant values (as events with probability zero do not occur).

So for a multionimal distribution to have variance zero all probabilities except one must be zero.
Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.

Michel
Posts: 2080
Joined: Sun Sep 28, 2008 11:50 pm

### Re: The SPRT without draw model, Elo model or whatever...

Bumping this old thread once again... I am just recording the following.

I have now verified that the following simple formula (discussed elsewhere)

Code: Select all

``&#40;1/2&#41;*N*log&#40;sum_i&#40;xi-mu0&#41;**2/sum_i&#40;xi-mu1&#41;**2&#41;        (*)``
gives a very accurate approximation of the LLR for mu=mu0 versus mu=mu1 where mu is the expectation value of a distribution. The sample is xi, i=1,.... The approximation seems to be much more generally valid than the one discussed in this thread (which requires fairly small elo differences).

The implementation is here

http://hardy.uhasselt.be/Toga/computeLLR.py

The theoretical basis for (*) is to replace the distribution by a normal one with parameters (mu,sigma). Then (*) computes the generalized LLR for mu0 versus mu1 for a normal distribution with sigma as a nuissance parameter. So rather than using Taylor series expansions, (*) is based on the central limit theorem which explains why it is more generally valid.

I have verified the properties of (*) by comparing it with the exact generalized LLR, which can only be computed numerically for the pentanomial model.
Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.

Michel
Posts: 2080
Joined: Sun Sep 28, 2008 11:50 pm

### Re: The SPRT without draw model, Elo model or whatever...

Here is a little document with the derivation of the approximation

http://hardy.uhasselt.be/Toga/computeLLR.pdf

The document also shows how to do the exact computation. It leads to an equation in one variable which can be trivially solved numerically.
Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.